Monte-Carlo tree search enhancements for one-player and two-player domains
Hendrik Baier · 2015
This thesis is concerned with enhancing the technique of Monte-Carlo Tree Search (MCTS), applied to making move decisions in games.MCTS has become the dominating paradigm in the challenging field of computer Go, and has been successfully applied to many other games and non-game domains as well.It is now an active and promising research topic with room for improvements in various directions.This thesis focuses on enhancing MCTS in one-player and two-player domains.Chapter 1 provides a brief introduction to the field of games and AI, and presents the following problem statement guiding the research. Problem Statement: How can the performance of Monte-Carlo Tree Search in a givenone-or two-player domain be improved?Four research questions have been formulated to approach this problem statement.Two questions are concerned with one-player domains, while two questions are dealing with adversarial two-player domains.The four research questions address (1) the rollout phase of MCTS in one-player domains, (2) the selection phase of MCTS in one-player domains, (3) time management for MCTS in two-player tournament play, and (4) combining the strengths of minimax and MCTS in two-player domains.