Monte Carlo tree search (MCTS) is a heuristic tree search algorithm used for decision processes, particularly in software that plays board games. It solves the game tree by focusing on the most promising moves, expanding the search tree based on random sampling of the search space. MCTS was combined with neural networks in 2016 and has since been applied to games like Chess, Shogi, Checkers, Backgammon, Contract Bridge, Go, Scrabble, and Clobber, as well as turn-based strategy video games and other domains.
The algorithm operates through repeated playouts, or roll-outs, where games are simulated to completion with random moves. The results of these playouts are used to weight nodes in the game tree, guiding future selections toward more promising moves. Each round of MCTS consists of four steps: selection, expansion, simulation, and backpropagation.
History
The Monte Carlo method, which uses random sampling for deterministic problems, dates back to the 1940s. In 1987, Bruce Abramson combined minimax search with an expected-outcome model based on random game playouts, demonstrating its effectiveness on tic-tac-toe and other games. In 1989, W. Ertel, J. Schumann, and C. Suttner applied similar methods to automated theorem proving, improving search times. In 1992, B. Brügmann used the approach in a Go-playing program. In 2002, Chang et al. proposed Adaptive Multi-stage Sampling (AMS), which introduced UCB-based exploration and exploitation in Monte Carlo trees, laying groundwork for UCT.
In 2006, Rémi Coulom coined the term Monte Carlo tree search, while L. Kocsis and Cs. Szepesvári developed the UCT (Upper Confidence bounds applied to Trees) algorithm. S. Gelly et al. implemented UCT in the program MoGo, which achieved dan level in 9x9 Go by 2008. In 2012, the Zen program won a match against an amateur 2 dan player on a 19x19 board. Google DeepMind's AlphaGo, using MCTS with neural networks, became the first program to beat a professional human Go player in 2015 and defeated Lee Sedol in 2016.
Principle of Operation
The focus of MCTS is on analyzing the most promising moves by expanding the search tree based on random sampling. Each playout simulates a game to the end, and the results weight nodes so that better moves are chosen more frequently. The basic Pure Monte Carlo Game Search applies equal playouts to each legal move and selects the move with the most wins.
Each round of MCTS involves four steps:
- Selection: Starting from the root, select successive child nodes until a leaf node is reached.
- Expansion: Create one or more child nodes from the leaf, unless the game is decided.
- Simulation: Complete a random playout from the new node.
- Backpropagation: Update node statistics along the path from the new node to the root.
UCT Algorithm
The UCT algorithm balances exploration and exploitation using the Upper Confidence Bound formula. It selects child nodes based on their average win rate and a bonus for less-visited nodes, allowing the tree to expand toward promising moves while still exploring alternatives. This approach is central to MCTS efficiency.
Applications
MCTS has been used in programs for board games like Hex, Havannah, Game of the Amazons, and Arimaa, as well as real-time video games such as Ms. Pac-Man and Fable Legends. It also applies to nondeterministic games like skat, poker, Magic: The Gathering, and Settlers of Catan. Beyond games, MCTS has been explored in planning and optimization problems.
Significance
The combination of MCTS with deep neural networks, as in AlphaGo, marked a milestone in Artificial intelligence and Machine learning. It demonstrated how heuristic search can be integrated with Deep learning methods to achieve superhuman performance in complex domains, influencing subsequent research in Generative AI and other areas.