Algorithm 50 · Phase 9 · Planning & Search

Monte Carlo Tree Search

Search without a scoring function — just a simulator and a budget
Style: notebook-3d Anytime algorithm Behind AlphaGo
Monte Carlo Tree Search notebook infographic: four-phase loop, UCT formula, asymmetric tree growth
Hero generated with gpt-image-2 · notebook-3d preset

Core Concept

Classic game search (minimax) needs a hand-written evaluation function to score positions it cannot search to the end. MCTS deletes that requirement. Instead of judging a position, it plays the game out at random from there — many times — and uses the win rate as a rough score. Then it does the clever part: it spends the next rollout on the branch that currently looks best while still leaving room for doubt. The tree therefore grows asymmetrically, deep and narrow along strong lines, barely at all along obviously bad ones. Stop it whenever you like and it returns its best move so far.

Key Components

01The Statistics Tree

Every node stores just two numbers: n (times visited) and w (total reward backed up through it). No board evaluation, no learned weights — two counters.

02The Rollout (Simulation)

From a new leaf, play to a terminal state with a cheap policy — often uniform random. One noisy sample of "how does this position tend to end?"

03UCT / UCB1 Selection

The tree policy that decides where to spend the next rollout. Balances the observed win rate against how under-explored a child is.

04Backpropagation

The rollout result is added to every node on the path back to the root, flipping sign each ply in a two-player game. This is what makes the estimates sharpen over time.

How It Works — The Four-Phase Loop

  1. Selection. Start at the root. While the current node is fully expanded, pick the child with the highest UCT score and descend. You are walking down the currently-most- interesting line of play.
  2. Expansion. When you reach a node with untried moves, add one new child for an untried move. The tree grows by exactly one node per iteration.
  3. Simulation. From that new child, play out to a terminal state with the cheap rollout policy. Record the outcome (win / loss / draw, or a score).
  4. Backpropagation. Walk back up the path you came down, incrementing n on every node and adding the outcome to w — negated at each opponent ply.
  5. Repeat until the budget (time or rollout count) runs out, then play the root child with the highest visit count — not the highest win rate, which is noisier on rarely-visited children.
UCT = w / n  +  c · √( ln N  /  n )
w/n → exploit: observed win rate √(lnN/n) → explore: uncertainty bonus N = parent visits c ≈ √2 tunes the trade-off
Why the explore term has that shape: an unvisited child has n = 0, so its bonus is infinite — every move gets tried at least once. As n grows the bonus decays like 1/√n while ln N grows only logarithmically, so attention drifts toward proven lines without ever fully abandoning the others. That is a bandit guarantee applied recursively at every node of the tree.

Real-World Applications

AlphaGo / AlphaZero
MCTS is the planner; the neural net replaces the random rollout with a value estimate and biases selection with a policy prior. The search is still this loop.
General game playing
Hex, Amazons, Settlers, card games — anywhere writing a good evaluation function is hard but simulating the rules is easy.
Planning & scheduling
Logistics routing, chemical synthesis route search, procedural content generation — large discrete action spaces with a cheap simulator.
LLM reasoning search
Tree-of-thought style methods run MCTS over partial reasoning traces, scoring branches with a verifier instead of a rollout.

Where It Breaks

Random rollouts are a terrible proxy in games with sharp tactics — chess traps MCTS because one forced refutation is invisible to random play, which is why chess engines stayed alpha-beta until a learned value function replaced the rollout. MCTS also needs a fast, resettable simulator; if one rollout is expensive, your budget buys almost no information.

Checkpoint — answer before you move on

  1. Why does MCTS not need an evaluation function, and what does it pay for that freedom? Think about what replaces the score, and how noisy that substitute is.
  2. In UCT, what happens to a child's score as its visit count n grows while the parent's N grows too? Which term dominates early, and which late? Look at the decay rate of 1/√n against the growth of ln N.
  3. After the budget expires, why pick the root child with the most visits rather than the best win rate? Consider a child visited twice that won both times.