Monte Carlo Tree Search

Definition

Monte Carlo Tree Search (MCTS) is a heuristic search algorithm that builds a search tree by running randomized simulations, used to select strong actions in large decision spaces such as board games, without needing to exhaustively search all possibilities.

Overview

MCTS builds a partial search tree incrementally through repeated simulation rather than exhaustively expanding every possible move, making it effective in domains with enormous branching factors like Go, where traditional minimax search with alpha-beta pruning is computationally infeasible. Each simulation cycle consists of four phases: selection, where the algorithm traverses the existing tree choosing promising nodes using a formula that balances exploitation of known-good moves against exploration of under-visited ones (commonly UCT, Upper Confidence bounds applied to Trees); expansion, where a new node is added to the tree; simulation (or rollout), where a fast, often random, playout estimates the outcome from the new node to the end of the game; and backpropagation, where the simulation's result updates the value estimates of all nodes visited along the path. Repeating this cycle thousands or millions of times concentrates search effort on the most promising branches of the tree, producing increasingly accurate estimates of each move's value as computation continues — MCTS is an anytime algorithm, meaning it can be stopped at any point and still return its current best move. Unlike minimax, it requires no hand-crafted evaluation function, since outcomes are estimated empirically through simulated playouts. MCTS became famous as a core component of DeepMind's AlphaGo, which combined tree search with deep neural networks — a policy network to guide which moves to explore and a value network to evaluate positions without needing full random rollouts — to defeat top human Go players in 2016. Its successors AlphaZero and MuZero generalized this recipe to chess, shogi, and (in MuZero's case) domains without a known set of game rules at all. Beyond games, MCTS-style search is used in planning problems, resource scheduling, and increasingly in combination with large language models for structured reasoning and tool-use planning.

Key Concepts

• Builds a search tree incrementally through repeated randomized simulations
• Four-phase cycle: selection, expansion, simulation, backpropagation
• UCT formula balances exploration of new moves against exploitation of known-good ones
• Anytime algorithm — usable results available at any computation budget
• No hand-crafted evaluation function required; estimates values empirically
• Scales to enormous branching factors, such as the game of Go
• Combines naturally with learned policy and value networks (as in AlphaGo/AlphaZero)

Use Cases

Frequently Asked Questions

Related in AI Fundamentals