Esplorazione dell'albero di gioco della Dama Cinese

Il gioco della Dama Cinese offre un contesto ideale per studiare il comportamento di algoritmi decisionali basati su alberi di gioco, in particolare il Minimax, tipico dei giochi a somma zero. In questo elaborato sono stati implementati e analizzati diversi algoritmi per la scelta ottimale delle mosse con l’obiettivo di ridurre il numero di nodi esplorati e migliorare le prestazioni del processo decisionale. A partire dall’implementazione del Minimax base, sono stati introdotti successivamente: • il taglio alfa-beta (alpha–beta pruning), • l’uso di tabelle hash per la memorizzazione degli stati visitati, • il move ordering, insieme ad altri accorgimenti specifici per la Dama Cinese, non ancora documentati in letteratura. Il lavoro prosegue con l’estensione dell’algoritmo a scenari con più di due giocatori, implementando e confrontando le versioni Paranoid e MaxN (estensione del Minimax al caso multi-giocatore). Sono presentati i risultati sperimentali relativi al numero di nodi esplorati, alle tabelle memorizzate e ai cut-off individuati durante l’esplorazione dell’albero di gioco, su partite simulate con parametri modulari e tabelloni di dimensione crescente.