Evaluating Simulation Heuristics in Monte-Carlo Tree Search and its Application to a Production Scheduling
Shimpei Matsumoto, Kosuke Kato, Noriaki Hirosue, Hiroaki Ishii, Sio-Iong Ao, Hideki Katagir, Xu Li, Alan H. S. Chan · AIP conference proceedings · 2010
This paper reports simulation heuristics of Monte‐Carlo Tree Search (MCTS) and shows an application example. MCTS introduced by Coulom is a best‐first search where pseudorandom simulations guide the solution of problem. Recent improvements on MCTS have produced strong computer Go program, which has a large search space, and the success is a hot topic for selecting the best move. So far, most of reports about MCTS have been on two‐player games, and MCTS has been used rarely for one‐player perfect‐information games. MCTS does not need admissible heuristic, so the application of MCTS for one‐player games might be an interesting alternative. Additionally, one‐player games like puzzles are determinately operated only by one player’s decision, so the sequences of changes in state are describable as a network diagram with interdependence between operations. If MCTS for one‐player games is available as a meta‐heuristic algorithm, we can use this algorithm for not only combinatorial optimization problems, but also many practical problems. Especially, as MCTS does not fully depend on evaluation function, so the solutions based on MCTS remain effective if objective function is modified. This paper firstly investigates on the application of Single Player MCTS (SP‐MCTS) introduced by Schadd et al. to a puzzle game called Bubble Breaker. Next this paper shows the effectiveness of new simulation strategies of SP‐MCTS, and considers the differences between each parameter. Based on the results, this paper discusses the application potentiality of SP‐MCTS for a scheduling problem.