About | |

What is MCTS? Monte Carlo Tree Search (MCTS) is a method for making optimal decisions in artificial intelligence (AI) problems, typically move planning in combinatorial games. MCTS combines the generality of random simulation with the precision of tree search. John von Neumann's 1928 minimax theorem paved the way for adversarial tree search methods that have formed the basis of decision making in computer science and AI almost since their inception. Monte Carlo methods were later formalised in the 1940s as a way to approach less well-defined problems unsuitable for tree search through the use of random sampling. RĂ©mi Coulomb combined these two ideas in 2006 to provide a new approach for move planning in Go now known as MCTS. Research interest in MCTS has risen sharply due to its spectacular success with computer Go and potential application to a number of other difficult problems. Its application extends beyond games, and MCTS can theoretically be applied to any domain that can be described in terms of { Basic Algorithm The basic MCTS algorithm is simplicity itself: a search tree is built, node by node, according to the outcomes of simulated playouts. The process can be broken down into the following steps: 1. Selection 2. Expansion 3. Simulation 4. Backpropagation Each node must contain two important pieces of information: an estimated value based on simulation results and the number of times it has been visited. In its simplest and most memory efficient implementation, MCTS will add one child node per iteration. Note, however, that it may be beneficial to add more than one child node per iteration depending on the application. Node Selection Bandits and UCB
where vi is the estimated value of the node, ni is the number of the times the node has been visited and N is the total number of times that its parent has been visited. C is a tunable bias parameter. Exploitation vs Exploration MCTS and UCT UCT may be described as a special case of MCTS, that is: UCT = MCTS + UCB Benefits MCTS offers a number of advantages over traditional tree search methods. Contextual Freedom Asymmetric Tree Growth This makes MCTS suitable for games with large branching factors such as 19x19 Go. Such large combinatorial spaces typically cause problems for standard depth- or breadth-based search methods, but the adaptive nature of MCTS means that it will (eventually) find those moves that appear optimal and focus its search effort there. Graceful Exit Simplicity Drawbacks MCTS has few drawbacks, but they can be major. Playing Strength Luckily, the performance of the algorithm can be sigificantly improved using a number of techniques. Improvements There are two types of improvements that may benefit an MCTS implementation: those specific to the current domain and those common to all domains. Domain Specific Domain specific improvements typically involve the completion of local move patterns known to work for the current game, such as capturing moves in Go or bridge intrusions in Hex. They can yield significant performance improvements for the current game at the expense of generality. Domain Independent See the Enhancements page for a more detailed list of MCTS improvements. Open Research Topics As MCTS is a new field of study, there are many open research topics. Algorithmic Enhancements Automated Parameter Tuning Node Expansion Node Reliability Tree Shape Analysis |