Single Player Monte Carlo Tree Search implementation.
This is a game-independent Python implementation of the single player Monte Carlo tree search as described in the paper: Schadd, Maarten PD, et al. "Single-player monte-carlo tree search." International Conference on Computers and Games. Springer Berlin Heidelberg, 2008. https://dke.maastrichtuniversity.nl/m.winands/documents/CGSameGame.pdf
"So far, MCTS has been applied rarely in one-player games. The only example we know of is the Sailing Domain [17]. There, it is applied on a game with uncertainty. So, to the best of our knowledge, MCTS has not been used in a one-player game with perfect information (a puzzle). The traditional approaches to puzzles [16] are applying A* [14] or IDA* [19]. These methods have been quite successful for solving puzzles. The disadvantage of the methods is that they need an admissible heuristic evaluation function. The construction of such a function can be difficult. Since MCTS does not need an admissible heuristic, it may be an interesting alternative. In this paper we will investigate the application of MCTS to a puzzle. We introduce a new MCTS variant called SP-MCTS."