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

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.