Single-Player Monte-Carlo Tree Search for SameGame

Classic methods such as A * and IDA * are a popular and successful choice for one-player games. However, without an accurate admissible evaluation func-tion, they fail. In this article we investigate whether Monte-Carlo Tree Search (MCTS) is an interesting alternative for one-player games where A * and IDA* methods do not perform well. Therefore, we propose a new MCTS variant, called Single-Player Monte-Carlo Tree Search (SP-MCTS). The selection and back-propagation strategy in SP-MCTS are different from standard MCTS. Moreover, SP-MCTS makes use of randomized restarts. We tested IDA * and SP-MCTS on the puzzle SameGame and used the Cross-Entropy Method to tune the SP-MCTS parameters. It turned out that our SP-MCTS program is able to score a substantial number of points on the standardized test set