We apply the extension of Monte Carlo Tree Search for single player games (SP-MCTS) to Sokoban and compare its performance to a solver integrating Iterative Deepening A* (IDA*) with several problem-specific heuristics. We introduce two extensions of MCTS to deal with some of the challenges that Sokoban poses to MCTS methods, namely, the reduced search space that deadlock situations can cause and the large number of cycles. We also evaluate three domain-independent enhancements that have been shown to improve MCTS performance, namely, UCB1-Tuned, Rapid Action Value Estimation (RAVE), and Node Recycling. We perform a series of experiments to determine the best SP-MCTS configuration and then compare its performance to IDA*. We show that SP-MCTS can solve around 85% of the levels with 1000000 iterations, that is the same performance reached by IDA* with only 10000 nodes. Overall, our results suggest that IDA* is still the best solver for Sokoban, also because it can easily integrate much domain knowledge. At the same time, our results also highlight some interesting directions to design better MCTS solvers for this domain.

An analysis of Single-Player Monte Carlo Tree Search performance in Sokoban

Pierluca Lanzi;
2022-01-01

Abstract

We apply the extension of Monte Carlo Tree Search for single player games (SP-MCTS) to Sokoban and compare its performance to a solver integrating Iterative Deepening A* (IDA*) with several problem-specific heuristics. We introduce two extensions of MCTS to deal with some of the challenges that Sokoban poses to MCTS methods, namely, the reduced search space that deadlock situations can cause and the large number of cycles. We also evaluate three domain-independent enhancements that have been shown to improve MCTS performance, namely, UCB1-Tuned, Rapid Action Value Estimation (RAVE), and Node Recycling. We perform a series of experiments to determine the best SP-MCTS configuration and then compare its performance to IDA*. We show that SP-MCTS can solve around 85% of the levels with 1000000 iterations, that is the same performance reached by IDA* with only 10000 nodes. Overall, our results suggest that IDA* is still the best solver for Sokoban, also because it can easily integrate much domain knowledge. At the same time, our results also highlight some interesting directions to design better MCTS solvers for this domain.
2022
Artificial intelligence
Monte Carlo Tree Search
Puzzle games
Sokoban
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0957417421015372-main.pdf

Accesso riservato

Descrizione: Articolo Principale
: Publisher’s version
Dimensione 975.86 kB
Formato Adobe PDF
975.86 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1207992
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 5
social impact