# Monte Carlo Tree Search

Monte Carlo tree search (MCTS) is a heuristic tree search algorithm for decision processes, notably board-game AI, that uses random playouts to guide search. It gained prominence after being combined with neural networks in 2016, as in AlphaGo.

Monte Carlo tree search (MCTS) is a heuristic tree search algorithm used in 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 non-game applications.

The algorithm operates through repeated playouts, also called roll-outs, where the game is played to the end with random moves. The results of these playouts are used to weight nodes in the game tree, making better nodes more likely to be chosen in future playouts. This approach differs from traditional minimax search by avoiding a static evaluation function, instead relying on simulated outcomes.

## 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 precision and domain independence in tic-tac-toe, Othello, and chess. In 1989, W. Ertel, J. Schumann, and C. Suttner applied similar methods to automated theorem proving, improving on uninformed search algorithms. In 1992, B. Brügmann first 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 name 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 9×9 Go by 2008. The Fuego program also began defeating strong amateurs in 9×9 Go around that time. In January 2012, the Zen program won 3:1 against an amateur 2 dan player on a 19×19 board.

Google DeepMind developed AlphaGo, which in October 2015 became the first program to beat a professional human Go player without handicaps on a full-sized board. In March 2016, AlphaGo defeated Lee Sedol 4:1, earning an honorary 9-dan level. AlphaGo combined MCTS with artificial neural networks, a deep learning method, for policy and value evaluation, marking a significant milestone in machine learning.

## Principle of Operation

MCTS focuses on analyzing the most promising moves by expanding the search tree based on random sampling. Each round consists of four steps:

- **Selection**: Starting from the root node (current game state), select successive child nodes until a leaf node is reached. The selection is biased to favor promising moves, often using UCT.
- **Expansion**: Unless the leaf node ends the game, create one or more child nodes representing legal moves.
- **Simulation**: Complete a random playout from a chosen child node, playing until the game is decided.
- **Backpropagation**: Update the nodes on the path from the child to the root with the playout result, incrementing simulation counts and win counts appropriately.

In games with draws, a draw increments the numerator by 0.5 and denominator by 1 for both players. This ensures that each player's choices expand towards moves that maximize their own value.

## UCT Algorithm

The UCT algorithm, introduced in 2006, applies Upper Confidence Bounds to tree search. It balances exploration and exploitation by selecting child nodes based on their average reward and a bonus for less-visited nodes. This allows the search tree to expand towards the most promising moves while still exploring alternatives. UCT became the standard for MCTS implementations, including in MoGo and later programs.

## Applications

MCTS has been used in programs for board games such as Hex, Havannah, Game of the Amazons, and Arimaa, as well as real-time video games like Ms. Pac-Man and Fable Legends. It also handles nondeterministic games like Skat, Poker, Magic: The Gathering, and Settlers of Catan. In turn-based strategy games, Total War: Rome II uses MCTS in its high-level campaign AI. Beyond games, MCTS has applications in planning and optimization problems.

The combination of MCTS with neural networks, as in AlphaGo, has proven particularly effective. This hybrid approach uses neural networks to guide selection and evaluate positions, reducing the need for extensive random playouts. Subsequent programs like AlphaZero have extended this to Chess and Shogi, achieving superhuman performance.

## See Also

- [artificial-intelligence](https://www.wikiprompt.org/wiki/artificial-intelligence)
- [machine-learning](https://www.wikiprompt.org/wiki/machine-learning)
- [deep-learning](https://www.wikiprompt.org/wiki/deep-learning)
- [neural-network](https://www.wikiprompt.org/wiki/neural-network)
- [google-deepmind](https://www.wikiprompt.org/wiki/google-deepmind)
- [chess-computer](https://www.wikiprompt.org/wiki/chess-computer)

---
Source: https://www.wikiprompt.org/wiki/monte-carlo-tree-search
License: CC BY-SA 4.0 (https://creativecommons.org/licenses/by-sa/4.0/)
Last updated: 2026-09-07T02:33:38.181409+00:00