Evaluation of Simulation Strategy on Single-Player Monte-Carlo Tree Search and its Discussion for a Practical Scheduling Problem
Shimpei Matsumoto, Noriaki Hirosue, Kyohei Itonaga, Kazuma Yokoo, Hisatomo Futahashi · 2010
Monte-Carlo Tree Search (MCTS) is a best-first search where the pseudorandom simulations guide the solution of problem. Recent improvements on MCTS have produced strong computer Go pro- gram, which has a large search space, and the suc- cess is a hot topic for selecting the best move. So far, most of reports about MCTS have been on two- player game, and MCTS has been applied rarely in one-player games. MCTS does not need an admis- sible heuristic, so the application of MCTS for one- player games might be an interesting alternative. Ad- ditionally, one-player games changed its situation by player's decision like puzzles are describable as net- work diagrams like PERT with the representation of interdependences between each operation. Therefore if MCTS for one-player games is developed as a meta- heuristic algorithm, we would use this for not only many practical problems, but also combinatorial op- timization problems. This paper investigated the ap- plication of Single Player MCTS (SP-MCTS) intro- duced by Schadd et al. to a puzzle game called Bubble Breaker. Next this paper showed the effectiveness of new simulation strategies on SP-MCTS by numerical experiments, and found the differences between the search methods and their parameters. Based on the results, this paper discussed the application potential- ity of SP-MCTS for a practical scheduling problem.