Monte Carlo Tree Search (MCTS)

Why Does This Exist?

Some games are too big to search the normal way. Go has around $10^{170}$ legal positions, so breadth first search drowns in branches. Minimax needs a hand written score for every middle position, and nobody could write a good one for Go for decades. Pure random playouts need no scoring but blunder, because they never look one move ahead on purpose.

Monte Carlo Tree Search, from Kocsis and Szepesvari (2006), takes the middle path. It grows a search tree that is deliberately lopsided: deep along lines that keep winning, shallow where losses pile up. Each round it walks down the tree with a bandit formula called UCT, adds one new node, plays one fast random game from there, and backs the result up the path. No hand written evaluation, no uniform expansion. That recipe became the planning core of AlphaGo, so the details here pay off directly in MuZero and AlphaZero.

The one idea you need first

This page leans on the multi-armed bandit: one state, several levers, unknown payouts, and the tension between pulling the current best and testing the rest. UCT is the bandit rule UCB1 applied at every tree node. If bandits are new, read that page first, then come back.

Think of It Like This

How It Actually Works

Nodes are states $s$, edges are actions $a$. Every edge stores two numbers: $N(s, a)$, how many times it was tried, and $Q(s, a)$, the average result after trying it. One iteration runs four phases.

Select, expand, roll out, back up

Select. From the root, repeatedly pick the action with the highest UCT score:

$Q(s, a)$ exploits what won before. The square root term explores: $\ln N(s)$ grows with total parent visits $N(s)$ while $N(s, a)$ in the denominator shrinks the bonus each time the action is tried. The constant $c$ sets the trade. With rewards in $[0, 1]$, theory says $c = \sqrt{2} \approx 1.4142$. An untried action gets infinite score, so everything is tried once first.

Expand. At the first node with an untried action, or a terminal node, stop. If it is not terminal, add one child for an untried action with $N = 0$ and $Q = 0$.

Roll out. From the new node, play to the end with a fast default policy, often uniform random. No tree, no learning here, just one terminal reward $R$, such as $+1$ for a win.

Back up. Walk the recorded path upward. For each edge, add one visit and fold $R$ into the running average:

When the budget of iterations or milliseconds runs out, play the action with the most visits, $\arg\max_a N(\text{root}, a)$, not the highest $Q$. Visits already blend value with confidence, which is why they survive noisy playouts.

Worked example

Root state with two actions, $c = \sqrt{2} \approx 1.4142$, parent visits $N = 10$. Action $a_1$ has $N = 7$ and $Q = 0.60$. Action $a_2$ has $N = 3$ and $Q = 0.40$. Since $\ln 10 \approx 2.3026$:

Selection picks $a_2$: worse record, far less tested, bigger uncertainty bonus. Expansion adds a child under $a_2$. The rollout wins, $R = 1.0$. Backup updates the $a_2$ edge from totals $1.2$ over $3$ visits to $2.2$ over $4$:

Next round starts with $a_2$ at $0.55$ instead of $0.40$, so search leans into the line that just paid off. The diagram above draws exactly these numbers.

Code

This snippet replays the worked example: score both actions with UCT, then back up the win. It uses only the standard library.

1import math2
3
4def uct(q: float, n_child: int, n_parent: int, c: float = math.sqrt(2)) -> float:5    """UCT score for one edge. Untried edges score infinite."""6    if n_child == 0:7        return float("inf")8    return q + c * math.sqrt(math.log(n_parent) / n_child)9
10
11def back_up(q: float, n: int, reward: float) -> tuple[float, int]:12    """Fold one terminal reward into the running average."""13    n_new = n + 114    return q + (reward - q) / n_new, n_new15
16
17s_a1 = uct(0.60, 7, 10)18s_a2 = uct(0.40, 3, 10)19print(f"UCT(a1)={s_a1:.4f} UCT(a2)={s_a2:.4f}")  # -> UCT(a1)=1.4111 UCT(a2)=1.639020q_new, n_new = back_up(0.40, 3, 1.0)21print(f"Q(a2)={q_new:.4f} N={n_new}")  # -> Q(a2)=0.5500 N=4

The printed scores match the hand computation: $1.4111$ against $1.6390$, and the win moves $Q(a_2)$ to $0.55$.

Watch Out For

The Quick Version

• MCTS plans by repeating four steps: select with UCT, expand one node, roll out randomly, back up the result.
• UCT adds an exploration bonus $c \sqrt{\ln N(s) / N(s, a)}$ to each win rate, so untried and stale lines get revisited on schedule.
• The tree grows lopsided: deep where wins pile up, shallow where losses do, which is how it survives huge branching factors.
• Leaf positions need no hand written score; fast random playouts supply the signal instead.
• The played move is the most visited one, because visit counts already combine value with confidence.

What to Read Next

• Upper Confidence Bound (UCB)
• Model-Based Reinforcement Learning
• MuZero and AlphaZero