🎯 Monte Carlo Tree Search
Game AI: UCB1 selection, rollout, backpropagation
Nim: take 1, 2, or 3 stones from a pile of 15 — last to take wins
Controls
Stats
Total simulations
0
Root visits
0
Best move
—
Pile size
15
Info & Theory

Monte Carlo Tree Search (MCTS) builds a search tree incrementally by repeating four phases, using randomised simulations instead of a hand-crafted evaluation function.

The four phases

  • Selection — starting at the root, walk down the tree choosing the child that maximises UCB1, until reaching a node with untried moves or no children.
  • Expansion — add one new child node for an untried move.
  • Rollout (simulation) — play uniformly random legal moves from the new node until the game ends.
  • Backpropagation — walk back to the root, updating visit and win counts on every node along the path.

UCB1: balancing exploration and exploitation

Upper Confidence Bound applied to trees selects the child maximising winRate + C·√(ln(parentVisits) / childVisits). The first term favours moves that have won often (exploitation); the second term grows for rarely-visited children (exploration), so the search keeps sampling promising but under-explored branches instead of fixating on early results. C = √2 ≈ 1.41 is the theoretically motivated constant for rewards in [0,1].

No heuristic evaluation needed

Unlike minimax, which needs a hand-crafted evaluation function to score non-terminal positions, MCTS estimates a position's value purely from the outcomes of random rollouts. This makes it applicable to games where good heuristics are hard to design.

Convergence & real-world use

As the number of simulations grows, visit counts concentrate on the strongest moves and win-rate estimates converge toward true game values. MCTS scales gracefully with large branching factors, which is why it powered AlphaGo and AlphaZero, where it was combined with deep neural networks that replaced random rollouts with learned value and policy estimates.

About Monte Carlo Tree Search

Written by MySimulator Team · Reviewed by MySimulator Editorial Review

Last updated: 11 July 2026

Monte Carlo Tree Search (MCTS) is an algorithm for finding strong moves in sequential decision problems, such as board games, by incrementally building a search tree through repeated random sampling. Each iteration performs four phases: selection, which walks down the tree from the root using the UCB1 formula — winRate + C·√(ln(parentVisits)/childVisits) — to balance exploiting known-good moves against exploring under-visited ones; expansion, which adds one new node for an untried move; rollout, which plays uniformly random moves to a terminal state; and backpropagation, which updates visit and win statistics along the path back to the root. Because MCTS estimates position values from simulation outcomes rather than a hand-crafted heuristic, it scales well to games with enormous branching factors, such as Go, where exhaustive minimax search is computationally infeasible. This property made MCTS the backbone of DeepMind's AlphaGo and, combined with deep neural networks replacing random rollouts, AlphaZero — systems that surpassed human expertise in Go, chess, and shogi.

Frequently Asked Questions

What are the four phases of Monte Carlo Tree Search?

MCTS repeats four phases each iteration: selection, which descends the tree using UCB1 to pick promising children; expansion, which adds a new child node for an untried move; rollout (simulation), which plays random moves to a terminal outcome; and backpropagation, which updates visit and win counts for every node on the path back to the root. Repeating this thousands of times grows an asymmetric tree focused on strong lines of play.

What is UCB1 and how does it balance exploration and exploitation?

UCB1 (Upper Confidence Bound 1) scores each child node as winRate + C·√(ln(parentVisits)/childVisits). The win-rate term favours moves that have performed well (exploitation), while the square-root term grows larger for children with few visits (exploration), pulling the search back to under-sampled branches. The constant C = √2 balances the two terms for rewards scaled between 0 and 1.

Why is a random rollout sufficient without a hand-crafted evaluation function?

A single random rollout is noisy, but averaged over many simulations, rollout outcomes give an unbiased statistical estimate of a position's true win probability. This lets MCTS evaluate positions in games where designing an accurate heuristic evaluation function — as minimax requires — would be difficult or impossible, such as Go's vast and pattern-dependent board states.

Where is MCTS used in real-world game AI?

MCTS is the core search algorithm behind DeepMind's AlphaGo, which defeated top human Go players in 2016, and its successor AlphaZero, which mastered Go, chess, and shogi from self-play. In these systems, MCTS's random rollouts were replaced with a trained neural network's value and policy estimates, but the selection-expansion-backpropagation structure of the tree search remained.