Monte-Carlo Tree Search
Guillaume M. J. -B. Chaslot · 2010
This thesis studies the use of Monte-Carlo simulations for tree-search problems.The Monte-Carlo technique we investigate is Monte-Carlo Tree Search (MCTS).It is a best-first search method that does not require a positional evaluation function in contrast to αβ search.MCTS is based on a randomized exploration of the search space.Using the results of previous explorations, MCTS gradually builds a game tree in memory, and successively becomes better at accurately estimating the values of the most promising moves.MCTS is a general algorithm and can be applied to many problems.The most promising results so far have been obtained in the game of Go, in which it outperformed all classic techniques.Therefore Go is used as the main test domain.Chapter 1 provides a description of the search problems that we aim to address and the classic search techniques which are used so far to solve them.The following problem statement guides our research.