Single Player Monte Carlo Tree Search implementation
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
Examples
MCTS.py
Node.py Implemented bin packing problem, tree updates. Jul 2, 2017
README.md Update README.md Nov 20, 2017

README.md

SP-MCTS

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."