Monte Carlo tree search for Sokoban

Monte Carlo Tree Search (MCTS) is one of the most used algo- rithm in the field of Artificial Intelligence applied to board and card games. The aim of this thesis is to evaluate the performance of MCTS algorithm applied to the puzzle game Sokoban, comparing it to another well known algorithm, Iterative Deepening A*, which has been proven to be quite successful in this puzzle game. In this thesis we apply MCTS and IDA* to Sokoban and Samegame, another puzzle game. We also develop a series of known optimiza- tions to MCTS and IDA* and present some new ones. Finally, we evaluate the effects of the optimizations on both domains. Our re- sults show that in Samegame the UCB1-Tuned formula performs better than SP-MCTS, a single player version of MCTS that ob- tained good results in that domain in the past. In Sokoban, the best MCTS configuration uses the standard UCT with the addi- tion of the proposed optimizations called Node Elimination and Cycles Avoidance, which lead to a drastic increase in the number of levels solved. Despite this, even with a set of enhancements that can be found in the literature, which have been widely used and have achieved successful results, the MCTS algorithm could not match IDA* performance in terms of number of solved levels. For this reason IDA* still remains the best algorithm for Sokoban.

Monte Carlo Tree Search (MCTS) `e uno degli algoritmi piu` uti- lizzati nel campo dell’intelligenza artificiale applicata ai giochi da tavolo e ai giochi di carte. Lo scopo di questa tesi `e di valutare le prestazioni dell’algoritmo MCTS applicato al puzzle game Sokoban, confrontandolo con un altro algoritmo ben noto, Iterative Deepen- ing A*, che ha dimostrato di avere un discreto successo in questo puzzle game. In questa tesi applichiamo MCTS e IDA* a Sokoban e Samegame, un altro puzzle game. Sviluppiamo anche una serie di ottimizzazioni conosciute per MCTS e IDA* e ne presentiamo alcune nuove. Infine, valutiamo gli effetti delle ottimizzazioni su entrambi i domini. I nostri risultati mostrano che in Samegame la formula UCB1-Tuned ottiene prestazioni migliori rispetto a SP- MCTS, una versione single player di MCTS che ha ottenuto buoni risultati in quel dominio in passato. In Sokoban, la migliore configu- razione del MCTS usa l’UCT standard con l’aggiunta delle ottimiz- zazioni proposte denominate Node Elimination e Cycles Avoidance, che portano ad un drastico aumento del numero di livelli risolti dall’algoritmo MCTS in Sokoban. Nonostante ci` o, anche con una serie di miglioramenti che possono essere trovati in letteratura, che sono stati ampiamente utilizzati e hanno raggiunto risultati di suc- cesso, l’algoritmo MCTS non ha potuto eguagliare le prestazioni di IDA* in termini di numero di livelli risolti. Per questo motivo IDA* rimane ancora il miglior algoritmo per Sokoban.