Monte Carlo
Tree Search

Chapter 1: A move's value is the average of its playouts

In the MDP lesson you computed action-values Q(s,a) — the expected return of taking action a in state s — by solving Bellman equations. That needed the full transition model and a sweep over every state. Here is the radical shortcut: you built that machinery already, so we will not re-derive it; the new idea is to throw the equations away.

To estimate Q(s,a), take action a, play the rest of the game out at random, record the return, and average over many such playouts. No model of transition probabilities, no global sweep — just a simulator you can roll forward and a running mean.

This is the heart of Monte Carlo control from the Monte Carlo lesson, now aimed at a single decision sitting in an astronomically large tree. The estimate is anytime: every extra playout refines it, and you can read it off whenever you stop.

The contrast with value iteration is sharp and worth stating precisely. Value iteration backs up values through the Bellman equation, propagating information through all states using the model. MCTS rollouts estimate one state's action-values by direct sampling, needing only a simulator. It trades exactness for the ability to plan in spaces too big to sweep even once.

Mechanically, each node stores two numbers: a visit count N and a running sum of returns W. The value estimate is just Q = W / N. When a new return arrives, you do an incremental update: bump N by one, add the return to W. No need to store the individual returns — the running sum is sufficient.

Because returns can be 0/1 win-loss or continuous shaped rewards (a score, a distance to goal), the same running-mean machinery covers both. The only thing that changes is what number each playout reports back.

Worked example: eight fixed rollouts, then a ninth

Action a gets 8 playouts with fixed returns [1, 1, 0, 1, 0, 1, 1, 1], where 1 = reached the goal and 0 = failed.

Q(s,a) is the incremental average. The sum of returns is 1+1+0+1+0+1+1+1 = 6, and N = 8, so

Notice we never wrote a Bellman equation — the average of sampled rollouts is the estimate. Now suppose a 9th playout arrives and it succeeds (return 1). The incremental update is trivially

The estimate refined itself with one cheap addition — that is the anytime, self-improving nature of Monte Carlo value estimation. Stop after 8 and you have 0.75; let one more land and you have 0.778; the rule never changed.

python
class Node:
    def __init__(self):
        self.N = 0            # visit count
        self.W = 0.0          # running sum of returns
    def update(self, ret):
        self.N += 1           # one more playout
        self.W += ret          # add its return
    @property
    def Q(self):
        return self.W / self.N if self.N else 0.0  # mean return

Every MCTS library stores exactly these two fields under different names. The "one-liner" is just the same divide:

python
# inside any MCTS lib: node holds visit_count and value_sum
Q = node.value_sum / node.visit_count

Chapter 2: The exploration bonus — optimism under uncertainty

There is a slot-machine problem hiding inside every tree node. Several actions, each with a noisy estimated value, and a limited number of pulls to spend. This is the classic multi-armed bandit: you must decide which arm (action) to pull next.

Two naive strategies both fail. Pull only the current best ("greedy") and you might be permanently stuck on a move that got lucky in its first couple of playouts. Pull everything equally and you waste budget re-confirming the obvious losers. We need something in between.

The elegant bandit answer is UCB1 (Upper Confidence Bound). Rank each action not by its mean alone, but by its mean PLUS a bonus that is large when you've sampled the action little and shrinks as you sample it more. Be optimistic about the things you are unsure about.

Here Q̂(a) is the current mean value of arm a (the exploitation term), N is the total number of pulls at this node, n_a is how many of those went to arm a, and c is an exploration constant you choose (often √2). The bonus is the exploration term.

Look at the denominator: na sits under the square root. A rarely-pulled arm (small n_a) gets a LARGE bonus, so it temporarily looks attractive and gets re-checked. As n_a grows, the bonus collapses toward zero and selection becomes greedy on the mean. Optimism decays with knowledge.

And the ln N in the numerator means: as the whole node accumulates pulls, every arm's bonus floor creeps up logarithmically, ensuring no arm is starved forever. The log growth is slow enough that it never overwhelms a clearly-better arm in the long run — that balance is what gives UCB1 its provable regret bound.

Worked example: one arm's UCB score

An arm has mean Q = 0.6, has been pulled n = 10 times, the node's total pulls is N = 100, and the exploration constant is c = √2 ≈ 1.414.

First the exploration bonus. Inside the root: ln 100 = 4.605, divided by n = 10 gives 0.4605, whose square root is 0.6786. Multiply by c:

Now the full UCB1 score is the mean plus that bonus:

Stare at those numbers: the bonus (0.96) currently dwarfs the mean (0.6). Early on, uncertainty dominates and the algorithm explores. As n climbs into the hundreds the bonus shrinks toward zero and the score collapses onto the true mean — late selection is nearly greedy. The same arm that scored 1.56 at n=10 would score barely above 0.6 once it has thousands of visits.

python
import numpy as np
def ucb1(child, N_parent, c=np.sqrt(2)):
    if child.N == 0:
        return float('inf')        # force-try any unvisited arm first
    exploit = child.W / child.N      # mean value
    explore = c * np.sqrt(np.log(N_parent) / child.N)
    return exploit + explore

Most libraries expose c as the single exploration knob and compute this internally:

python
# open_spiel and most libs: pass uct_c, they handle the sqrt(ln N / n) inside
bot = mcts.MCTSBot(game, uct_c=np.sqrt(2), max_simulations=10000)

Chapter 3: UCT — run UCB1 at every node of the tree

One bandit is easy. A tree is many bandits stacked. Every node faces its own explore-vs-exploit choice over its children, and — here is the twist — the "reward" of a child is itself estimated by searching the subtree below it.

Kocsis and Szepesvári's 2006 insight was wonderfully simple: just run UCB1 at every node and chain the decisions. Starting at the root, repeatedly pick the highest-UCB child and step into it, descending until you reach a leaf (a node with unexpanded children). That recursive rule is UCT — UCB applied to Trees.

UCT is the tree policy: the rule that decides which path through the existing tree to walk on each iteration. It is what turns a disorganized bag of rollouts into a focused, self-deepening search. The path it walks is where the next playout's budget gets spent.

Crucially, UCT treats each node's children as a fresh bandit with its own N(s) and per-child N(s,a). The exploration bonus uses the parent's visit count as N and the child's visit count as n. An unvisited child has n = 0, which makes its bonus infinite — so every child is tried at least once before any is revisited.

This recursion is the engine of asymmetric growth (Chapter 6): nodes on good lines get descended into again and again, so their children's bonuses shrink and the search digs deeper there, while bad lines are visited just enough to confirm they're bad.

One more warning that catches everyone: the rule that picks children during the search (high UCB) is NOT the rule that picks the final move after the search (usually most-visited). Confusing the two is a classic bug — we'll return to it in Chapter 6.

Worked example: which child does UCT descend into?

A node has total visits N = 200 and two visited children. Child A: Q = 0.7, n = 80. Child B: Q = 0.55, n = 20. A third child is unvisited. Use c = √2.

First, the unvisited child has infinite UCB, so in a real descent it would be selected before A or B. Setting it aside, compare A and B directly.

Child A: ln 200 = 5.298, over n = 80 gives 0.0662, square root 0.2574, times c = 1.414 gives bonus 0.364.

Child B: ln 200 = 5.298, over n = 20 gives 0.2649, square root 0.5147, times c = 1.414 gives bonus 0.728.

Despite A having the higher mean (0.7 vs 0.55), B wins the UCB comparison (1.278 > 1.064). Why? B's 4×-smaller visit count gives it a 2×-larger exploration bonus (0.728 vs 0.364). UCT descends into B — exploration in action, re-checking the under-sampled but plausibly-good line before committing.

python
def select(node, c):
    while node.children and node.fully_expanded():
        # descend by UCB until a leaf / unexpanded node
        node = max(node.children, key=lambda ch: ucb1(ch, node.N, c))
    return node

UCT is the default tree policy in essentially every MCTS library — you only set c and the budget:

python
# mctspy / open_spiel default to UCT; you supply only c and max_simulations
bot = mcts.MCTSBot(game, uct_c=1.414, max_simulations=10000)

Chapter 4: Select, Expand, Simulate, Backpropagate

You now hold the two pieces: value-by-rollout (Chapter 1) and UCT selection (Chapter 3). The full MCTS algorithm is just these glued into a four-step loop, repeated until time or budget runs out. Each pass through the loop is called an iteration (or simulation).

Picture one iteration as a single drop of water. It falls down the existing tree along the UCB path (Select). It grows the tree by one node at the bottom (Expand). It splashes out a quick random game to see who'd win (Simulate). Then the result trickles back up, updating every node it passed (Backpropagate).

1. Select. Starting at the root, apply the tree policy (UCT) to descend child-by-child until you reach a node that is not fully expanded — a node with at least one untried action. This is the leaf of the current tree.

2. Expand. Add ONE new child to that leaf, corresponding to one previously-untried action. (Some variants add all immediate children at once; none ever adds the deep subtree.) This is the single new node the tree grows this iteration.

3. Simulate. From the new node's state, run one fast random playout to a terminal result — the Monte Carlo value estimate from Chapter 0. One playout, one return.

4. Backpropagate. Walk back up the path from the new node to the root, incrementing each node's visit count N and adding the return into W. (In two-player games the value flips at each ply — the topic of Chapter 5.) The estimates everywhere on the path just got one sample better.

Repeat thousands of times and a smart tree self-assembles. Because UCT pours iterations down the best-looking lines, the tree grows deep-and-narrow under good moves and barely sprouts under bad ones — the asymmetric growth we'll watch in Chapter 6.

Worked example: which child does SELECT descend into?

At a node with N = 50, three children: A (Q=0.8, n=30), B (Q=0.5, n=15), C (Q=0.3, n=5), with c = √2. The Select phase compares UCB scores. ln 50 = 3.912.

The pointer descends into C — 1.5509 is the highest. Although C has the worst mean (0.3), it has been visited only 5 times, so its exploration bonus (1.251) is by far the largest. After Expand adds a new child under C and Simulate returns, say, a win, Backpropagate increments N and W on C and on the root along the path. C's mean will tick up and its bonus will shrink — the search is doing its job, re-checking the under-sampled line.

python
def mcts_iter(root, c, rng):
    leaf  = select(root, c)                 # 1. tree policy descends by UCB
    child = leaf.expand(rng)                # 2. add one new node
    ret   = rollout_value(child.state, 1, rng)  # 3. simulate
    while child:                          # 4. backpropagate up the path
        child.update(ret)
        ret = 1 - ret                    # flip for the opponent (Ch 5)
        child = child.parent

The library version is the same loop with the four phases factored out behind one step call:

python
bot = mcts.MCTSBot(game, 2.0, n_sims, rollout_evaluator)
action = bot.step(state)   # runs n_sims four-phase iterations, returns best move

Chapter 5: Backpropagation and flipping value for the opponent

A rollout from deep in the tree produces one number — say, a win for Black. That number is news for every node along the path that led there. But it is not the same news at every node: a position that is good for Black is exactly bad for White.

So as the result flows back up the path, you must flip it at each level. This is the negamax convention: every node scores the outcome from the perspective of the player who is to move at that node. A win for the player to move is a 1; the parent, where the opponent moves, sees that same outcome as a 0.

Get this backup right and the tree's win-rates are self-consistent — each node's Q honestly reflects "how good is this for the player choosing here." Get it wrong and the search confidently walks into losing lines, because it scored the opponent's wins as its own.

Concretely, backpropagation updates every node on the selection path from leaf to root, not just the leaf. That is how deep evidence improves shallow estimates: a strong line discovered eight plies down nudges the root's child values, which is what makes the root pick the right move.

The flip is one line: after adding the value to a node, replace value with 1 - value before moving to the parent. For 0/1 win-loss returns this turns a win into a loss and vice versa. (For symmetric ±1 returns you'd negate instead — same idea, hence "negamax.")

This is also where a deliberately-broken "no-flip" mode is instructive: if you average the raw result into every node without flipping, the opponent's nodes start preferring moves that are good for you, which is exactly backwards. The recommended root move then drifts to a losing one. Seeing the wrong answer appear is the best way to remember why the flip exists.

Worked example: one win, up two plies

A node currently has W = 6 wins over N = 10 visits, so Q = 0.6. A new playout from below returns a WIN (value 1) for this node's player.

Update this node: W becomes 6 + 1 = 7, N becomes 10 + 1 = 11, so

The win nudged its estimate up from 0.60 to 0.636. Now move to the parent, which is the opponent's decision node. The value flips: this node's win (1) is the opponent's loss.

The parent averages in a 0, nudging ITS estimate down. That alternating add-1-then-add-0 up the path is the negamax backup, and it is what keeps each player's win-rate honest. Had we forgotten the flip, the parent would have averaged in a 1 — teaching the opponent to like a move that is good for us.

python
def backprop(node, value):
    while node is not None:
        node.N += 1
        node.W += value          # average in from THIS node's view
        value = 1 - value        # negamax flip for the parent's player
        node = node.parent

Libraries handle the flip by storing player-relative returns instead of a single scalar — they look up the value for whichever player is to move:

python
# returns is a vector indexed by player; each node reads its own entry
node.W += returns[node.player_to_move]

Chapter 6: Asymmetric growth and the anytime property

Watch an MCTS tree for a while and it looks nothing like the balanced, breadth-first trees of classic game search like minimax. It is lopsided: a few promising lines are explored dozens of moves deep while bad moves are barely touched.

This asymmetry is a feature, not a bug. Budget follows value. Because UCT keeps descending into high-UCB children (Chapter 3), iterations pile up under the good lines, deepening them, while a line that looks bad gets just enough visits to confirm it's bad and is then left alone.

The second gift is the anytime property. Every iteration only refines the estimates — it never makes them categorically worse. So you can interrupt the search at literally any moment and return the best move found so far. More thinking time simply means a better answer, never a wrong one.

This is why MCTS fits real-time games and time-limited agents: a Go program given 5 seconds and one given 30 both return a legal, reasonable move — the longer one is just stronger. Robotics planners that must act on a deadline rely on exactly this.

But which move do you actually return after searching? The natural guess — "the move with the highest average value Q" — is a trap. A move can have a high mean from a few lucky rollouts. In practice MCTS returns the most-visited move (the "robust child").

Why most-visited? Visit count reflects sustained UCT preference: a move only accumulates many visits if it kept looking good across many iterations. That is far more robust to noise than a raw mean that a handful of fluke wins can inflate. The selection rule (high UCB, during search) and the final-move rule (most-visited, after search) are deliberately different — the bug Chapter 3 warned about.

Worked example: reading off the recommended move

After 1600 total simulations at the root, the move visit counts are: move-1 = 1000, move-2 = 400, move-3 = 150, move-4 = 50.

MCTS recommends the MOST-VISITED root move — move-1. Its visit share is

So move-1 carries 62.5% of all root visits — a clear, robust recommendation. Now look at the asymmetry. The best move got

twenty times the visits of the worst move. That lopsided allocation IS the asymmetric growth: once move-4 looked bad, the search barely bothered with it again, pouring its budget into move-1 instead. And the anytime guarantee: stop at 800 sims and the proportions would look similar — the answer is stable across stopping points.

python
def best_move(root):
    # robust child: most-visited, NOT max mean
    return max(root.children, key=lambda ch: ch.N).move

Most libraries default to the robust child, with max-Q or a hybrid available as an option:

python
# open_spiel: solve=False -> robust child (max visits); some libs expose child_selection_fn
action = max(root.children, key=lambda c: c.explore_count).action

Chapter 7: AlphaGo — priors and a value net steer the search

Plain UCT with random rollouts is strong but blind. Early on, every move's Q is near-zero noise, so UCT explores all moves roughly equally before any signal emerges. In Go that wastes enormous budget on obviously bad moves.

AlphaGo (2016 — the program that beat Lee Sedol 4–1) fixed this by learning two things from human games and self-play. A policy network P(a) that predicts which moves are worth considering, and a value network that scores a position without a full rollout.

The policy enters selection as a prior in a modified bandit rule, PUCT (Predictor + UCB applied to Trees). Instead of a uniform exploration bonus, the bonus is weighted by how much the policy likes each move:

Here P(a) is the learned prior probability of move a, N the parent visits, n_a the child visits. The prior multiplies the exploration term, so the tree immediately fans out toward sensible moves instead of wasting budget on junk. Knowledge guides the search.

Read the structure carefully: the prior does NOT replace the visit-count denominator. The (1 + na) still shrinks the term as a move is visited, so even a high-prior move gets de-emphasized once it's been explored a lot — Q takes over. The prior shapes early exploration; the data shapes the rest.

AlphaGo also used the value network at leaves, but — importantly — it mixed the value-net estimate with a fast-rollout estimate rather than replacing rollouts entirely. Dropping rollouts completely came one year later, with AlphaZero (Chapter 8).

Worked example: three moves under PUCT

At a node with N = 100, c_puct = 1.5. Move A: Q=0.2, P=0.6, n=10. Move B: Q=0.3, P=0.05, n=40. Move C: unvisited, P=0.6, n=0. Note √100 = 10.

Move A: prior term = 1.5 · 0.6 · 10 / (1+10) = 9.0/11 = 0.818.

Move B: prior term = 1.5 · 0.05 · 10 / (1+40) = 0.75/41 = 0.018.

Move C (unvisited, high prior): Q is 0, prior term = 1.5 · 0.6 · 10 / (1+0) = 9.0/1.

So C's huge prior term (9.0) forces it to be tried first — a high-prior move with zero visits dominates. Among the visited moves, A (high prior 0.6, few visits) crushes B (tiny prior 0.05) despite B's higher mean (0.3 vs 0.2). The prior, not raw uncertainty, now drives early exploration. Compare this to plain UCT, where B's lower visit count alone would have given it a big bonus — PUCT overrides that with learned knowledge.

python
def puct(ch, N, c=1.5):
    prior = c * ch.P * np.sqrt(N) / (1 + ch.N)   # policy-weighted exploration
    return ch.Q + prior                          # Q = 0 until visited

AlphaZero-style libraries implement PUCT with a neural-net evaluator that returns both the prior and the value:

python
# alpha-zero-general / open_spiel AlphaZero: NN returns (P, v); PUCT uses P as prior, v at leaf
P, v = net(state); child.P = P[action]

Chapter 8: AlphaZero — drop the rollout, trust the value net

Random rollouts are noisy and slow, and in a tactical game like Chess a random playout is laughable — both sides flail until a fluke decides it. The rollout's variance is a real cost: you need many of them to get a usable estimate.

AlphaZero (2017) made a clean break. When search reaches a new leaf, it does NOT play a game out. It asks the value network "how good is this position?" exactly once, gets a scalar v, and backs that number up. There is no rollout policy at all — the entire SIMULATE phase of classic MCTS is gone.

This is the single biggest structural change in the lesson. The four-phase loop becomes Select → Expand → Evaluate (one net call) → Backpropagate. Each leaf contributes ONE deterministic number instead of one noisy playout return, which is why AlphaZero needs far fewer simulations per move than rollout MCTS.

The networks learn purely from self-play, with a beautiful bootstrap. MCTS runs a strong search using the current net. The search's improved visit-count distribution becomes the training target for the policy. The eventual game outcome trains the value. Search improves the net; the net improves search; around and around.

The key subtlety: the policy net is NOT trained to imitate its own raw output. It is trained toward the MCTS visit-count distribution — which is strictly stronger than the raw policy, because search refined it. That gap between "what the net suggested" and "what search concluded" is exactly the signal that drives improvement.

One algorithm, no game-specific knowledge beyond the rules, mastered Go, Chess, and Shogi from scratch — each to superhuman level — using this single search-plus-self-play recipe.

Worked example: Q without rollouts, and the policy target

A node is built WITHOUT rollouts. Its three backed-up leaf evaluations from the value network are v = [0.4, 0.6, 0.5] — each a single net call, no playout.

With rollouts removed, the node's Q is just the mean of the value-network estimates that flowed up:

There is no playout variance: each leaf contributes ONE deterministic net evaluation. That low variance is precisely why AlphaZero needs orders of magnitude fewer simulations per move than rollout MCTS.

Now the training side. Suppose the three child moves ended the search with visit counts 30, 15, 5 (total 50). The policy training target is the normalized visits:

The search's own preferences — it visited the first move 60% of the time — become the net's next lesson. The net is nudged to output [0.6, 0.3, 0.1] next time it sees this position, so its raw policy creeps toward what search discovered.

python
def evaluate_leaf(leaf, net):
    P, v = net(leaf.state)        # policy prior + value, ONE forward pass
    leaf.expand_with_priors(P)    # children get priors P (for PUCT)
    return v                     # back this up; no rollout at all

# policy target for training the net:
pi = visits / visits.sum()      # normalized visit counts -> stronger than raw P

Reference implementations expose a neural evaluator returning (pi, v) that the search consumes:

python
# alpha-zero-general / open_spiel AlphaZero: NeuralNet -> (pi, v); MCTS uses pi as prior, v at leaf
pi, v = nnet.predict(board)

Chapter 9: MuZero — search inside a learned model of the world

AlphaZero needs a perfect simulator: to expand the tree it must know the exact rules to compute the next position. That's fine for board games. But for Atari, robotics, or any messy environment, you don't have a clean rule-based simulator to roll forward.

MuZero (2019) drops that requirement. It learns its own model, as three networks. A representation net encodes the raw observation into an abstract hidden state. A dynamics net predicts the next hidden state and the reward, given an action. A prediction net outputs a policy and a value from a hidden state.

MCTS then unrolls inside this learned model. Expansion applies the dynamics net (action → next hidden state, predicted reward) instead of the real rules; the prediction net tags each hidden node with a policy and value. The search plans over imagined latent transitions — no real-environment steps occur during planning.

The result: MuZero matched AlphaZero on Go, Chess, and Shogi and mastered the full Atari suite, all without ever being told the rules of any of them. It learns what it needs to plan, and nothing more.

Here is the part that surprises everyone: the hidden state does NOT reconstruct the real game state. It is an abstract vector trained ONLY to make good policy, value, and reward predictions — not to reproduce observations. There is no pixel-level world model. The latent state can be unintelligible to humans yet perfectly useful for planning.

That freedom is exactly what lets MuZero plan without the true rules: it only has to predict the quantities that matter for choosing actions (rewards, values, policies), not the full physics of the world. After planning, only the first action is taken in the real environment; then it re-plans from the new observation.

Worked example: an n-step value target in imagination

MuZero forms a value target by bootstrapping along an imagined trajectory. Discount γ = 0.997, predicted rewards over 3 steps r = [0, 0, 1], and a bootstrap value v = 0.8 at the node 3 steps ahead.

The n-step value target is the sum of discounted rewards plus the discounted bootstrap value:

Plug in the numbers. The reward terms: 0 + 0.997·0 + 0.997²·1. Now 0.997² = 0.994, so the reward contribution is 0.994. The bootstrap term: 0.997³·0.8. Since 0.997³ = 0.99102, that gives 0.99102·0.8 = 0.7928. Adding:

The crucial point: EVERY quantity here — the rewards, the bootstrap value, the dynamics that produced this trajectory — came from learned networks, not from the real game. MCTS plans over these imagined numbers, then only the first action is actually executed. The world model is entirely internal.

python
h = representation(obs)        # encode observation -> hidden state h0
def expand(h, a):
    h2, r = dynamics(h, a)       # learned transition + predicted reward
    P, v  = prediction(h2)       # policy prior + value at hidden node
    return h2, r, P, v          # MCTS unrolls this in latent space

Reference implementations bundle the three nets; the search calls them instead of a real simulator:

python
# muzero-general / EfficientZero: nets = representation + dynamics + prediction
hidden, reward, policy, value = model.recurrent_inference(hidden, action)

Chapter 10: Showcase — build the whole search and watch it think

Time to put it all on one screen. You'll run a real MCTS over a small game, flip between plain UCT (random rollouts) and PUCT (priors + value net, AlphaZero-style), crank the exploration constant and the simulation budget, and watch the tree grow asymmetric, the recommended move stabilize, and the principal variation deepen.

This is the payoff chapter. Every earlier idea — the four phases (Ch 4), the UCB/PUCT tree policies (Ch 3, 7), rollout-vs-value-net leaf evaluation (Ch 8), negamax backup (Ch 5), the anytime most-visited recommendation (Ch 6) — is live and tunable here so you can feel how "think longer" turns into "search wider and deeper."

The principal variation (PV) is the most-visited path from the root downward — the line the search currently believes both sides will play. Watch it highlighted and deepening as budget grows.

Try the experiments. Set c = 0 (pure greedy) and notice the tree barely branches — it entrenches its first guess and more budget can't fix a bad one. Crank c high and the tree fans wide but shallow, wasting budget re-checking losers. The sweet spot in between is where MCTS shines.

Flip to PUCT and the priors immediately collapse the early search onto a few sensible moves — the same pruning AlphaGo bought with its policy net. Flip leaf-eval to value-net and watch the per-iteration variance vanish (no more noisy rollout bars), so the recommendation settles faster.

Everything here is deterministic given the visit counts, so the sim is not a black box: you can pause and verify its arithmetic against the same numbers you computed by hand in earlier chapters. That is the whole point — you built every piece, and now you can see them cooperate.

Reproducing the checkpoints in code

The lab's tree policy is exactly the search loop you've been building, parameterized by the two toggles:

python
def search(root, budget, c, tree_policy, leaf_eval):
    for _ in range(budget):
        leaf  = select(root, c, tree_policy)   # UCT or PUCT
        child = leaf.expand()
        value = leaf_eval(child.state)         # rollout OR value-net
        backprop(child, value)                 # negamax up the path
    return max(root.children, key=lambda ch: ch.N).move  # robust child

python
# open_spiel MCTSBot wraps exactly this: policy=UCT/PUCT, evaluator=rollout or NN, budget=max_simulations
bot = mcts.MCTSBot(game, uct_c=1.41, max_simulations=800, evaluator=evaluator)

Chapter 11: Reasoning as search — MCTS for LLMs, and what's next

MCTS escaped the game board. A chain of reasoning is a sequence of decisions, so a tree of reasoning steps is a search problem — and 2023–2025 saw this idea explode across large language models.

Tree of Thoughts (2023) branches a tree of partial solutions and explores it with search instead of committing to one greedy chain. At each node the LLM proposes several candidate next thoughts; the tree is searched to find a strong complete solution.

rStar-Math (2025) runs self-play MCTS over math reasoning steps, using a process reward model (PRM) to score each intermediate step, and made small models rival far larger ones on competition math. AlphaProof and AlphaGeometry (2024) brought tree search to formal theorem proving, reaching IMO-medal performance.

The thread is constant. A node is a partial solution. Expansion proposes next steps (sampled from the LLM). A learned reward model "rollouts" the value of a step. Visit counts pick the path. It is the same select-expand-simulate-backprop loop — only the "state" is a partial solution and the "reward" is a process/outcome reward model instead of a game result.

This is why "test-time compute" is, in large part, search. Spending more inference budget = running more iterations of the tree = exploring the solution space wider and deeper. See the test-time compute Gleam for the broader framing of how thinking-longer scales.

The transfer is direct: PUCT, visit-count selection, and the explore-exploit tradeoff all carry straight over from AlphaZero to rStar-Math. Recent work like AB-MCTS (2025) even makes the branching factor itself adaptive — deciding on the fly whether to widen (try a new step) or deepen (refine an existing one).

Worked example: UCT over reasoning steps, plus self-consistency

At a reasoning node with N = 20, c = 1, two candidate next steps are scored by a process reward model. Step A: PRM value Q = 0.9, n = 3. Step B: Q = 0.7, n = 1. (ln 20 = 2.996.)

The search expands step B next (2.43 > 1.90). Its single visit gives a large exploration bonus (1.731), so even a slightly-lower-scored reasoning step gets re-examined — exactly like an under-visited game move. Knowledge from the PRM guides; uncertainty still forces re-checking.

For the final answer, a complementary trick is self-consistency: sample several complete solutions and take the majority vote. Suppose 5 sampled final answers are [7, 7, 7, 3, 7]. The value 7 appears 4 of 5 times:

So the answer is 7 with confidence 0.8. Search (to find good reasoning paths) plus voting (to aggregate over them) beats a single greedy chain — the essence of modern test-time-compute reasoning.

python
def reason_search(prompt, llm, prm, budget, c=1.0):
    root = Node(prompt)
    for _ in range(budget):
        node  = select(root, c)               # UCT over reasoning steps
        steps = llm.propose_next(node.text)   # expand candidate steps
        for s in steps:
            node.add_child(s, prior=prm.score(s))
        leaf = node.children[0]
        backprop(leaf, prm.value(leaf.text))  # reward model plays the 'rollout' role
    return best_path(root)

python
# Conceptual; see Tree-of-Thoughts repos and rStar-Math (self-play MCTS + process reward model)
answer = reason_search(problem, llm, prm, budget=64)

Where MCTS sits among its cousins

Connections to explore next: MDPs (the planning substrate), Q-learning and RL algorithms (value-based alternatives), model-based RL (MuZero's family), and Monte Carlo (where the rollouts came from).