Monte Carlo Tree Search (MCTS), in depth: one generic loop, chance nodes, open-loop search, parallel search, learned models and search over LLM reasoning

The idea from first principles

Start from the simplest idea. To judge a move, play many random games after it and average the results. This flat Monte Carlo approach wastes effort on bad moves and judges each move against a random opponent. MCTS fixes both by growing a tree: statistics are kept for the positions after the root moves too, and in-tree moves are chosen by a rule that balances promising moves against uncertain ones. As counts grow, in-tree play gets stronger and the averages approach the values of best play.

In the selection phase the usual rule is UCT: pick the child maximising W/N + c * sqrt(ln N_parent / N), where W is total reward, N visits and c an exploration constant. Expansion adds one new child. Evaluation estimates the new node's value, classically by a random playout to the end. Backup adds the result to every node on the path. After the budget is spent, play the root child with the most visits, which is more robust than the highest average because a high average on few visits is often luck.

A generic implementation

The implementation below separates the game from the search. The state object supplies legal_moves, play, is_terminal, rewards and player_just_moved; every reward is from a named player's point of view, which handles two-player and multi-player games without sign tricks.

import math, random

class Node:
    __slots__ = ("parent", "move", "player", "children", "untried", "N", "W")
    def __init__(self, state, parent=None, move=None):
        self.parent, self.move = parent, move
        self.player = state.player_just_moved()      # who made `move`
        self.children = []
        self.untried = list(state.legal_moves())
        self.N, self.W = 0, 0.0

def uct_child(node, c):
    log_n = math.log(node.N)
    return max(node.children,
               key=lambda ch: ch.W / ch.N + c * math.sqrt(log_n / ch.N))

def random_rollout(state):
    while not state.is_terminal():
        state.play(random.choice(state.legal_moves()))
    return state.rewards()                           # {player: reward in [0, 1]}

def mcts(root_state, iterations, c=1.4, evaluate=random_rollout):
    root = Node(root_state)
    for _ in range(iterations):
        node, state = root, root_state.clone()
        while not node.untried and node.children:    # 1. select
            node = uct_child(node, c)
            state.play(node.move)
        if node.untried:                             # 2. expand
            move = node.untried.pop(random.randrange(len(node.untried)))
            state.play(move)
            node.children.append(Node(state, node, move))
            node = node.children[-1]
        result = evaluate(state)                     # 3. evaluate
        while node is not None:                      # 4. backup
            node.N += 1
            node.W += result[node.player]            # credit the player who moved here
            node = node.parent
    return max(root.children, key=lambda ch: ch.N).move

The one convention to get right is in the backup: each node stores reward from the point of view of the player who made the move into it, because that is the player choosing among siblings when the parent is selected. Getting this backwards produces a search that confidently plays the worst move, and it is the most common MCTS bug.

Worked example: two iterations by hand

Suppose the root has been visited 16 times and has three children: m1 with N = 10 and W = 6, m2 with N = 5 and W = 2, and m3 with N = 1 and W = 1. With c = 1.4 and ln 16 = 2.773 the UCT scores are m1: 0.60 + 1.4 x sqrt(0.277) = 1.34, m2: 0.40 + 1.4 x sqrt(0.555) = 1.44, and m3: 1.00 + 1.4 x sqrt(2.773) = 3.33. Move m3 is selected; it won its one playout and has the largest exploration bonus.

Say the playout below m3 is a loss for the player who chose m3. Backup makes m3 N = 2, W = 1, and the root N = 17. Now m3 scores 0.50 + 1.4 x sqrt(2.833 / 2) = 2.17, still the highest, so the next iteration explores m3 again. This is the asymmetric growth MCTS is known for: a rarely visited move keeps being tried until its average is pinned down, and only then does the search settle on the strongest sibling.

Randomness: chance nodes and open-loop search

Many problems have randomness between decisions: dice, card draws, an opponent's hidden hand, or noise in a simulated robot. Plain MCTS treats the state after a move as fixed, which is wrong when the same move leads to different states. The fix is a chance node after each such move. In selection, instead of choosing a child by UCT, the search samples an outcome from the true distribution and descends into the child for that outcome, creating it if needed.

class ChanceNode:
    """Placed after a move whose result is random."""
    def __init__(self):
        self.outcomes = {}        # outcome -> decision Node
        self.N, self.W = 0, 0.0

def descend_chance(chance, state, move):
    outcome = state.sample_outcome(move)      # e.g. a dice roll
    state.apply(move, outcome)
    if outcome not in chance.outcomes:
        chance.outcomes[outcome] = Node(state, parent=chance)
    return chance.outcomes[outcome]

Because outcomes are visited in proportion to their probability, the plain average in the backup converges to the expected value, which is what expectimax computes exhaustively. When outcomes are continuous or very numerous, each sample creates a new child and the tree never revisits anything; cap the number of outcome children with progressive widening, described below, or switch to open-loop search.

Open-loop MCTS stores statistics on sequences of actions rather than on states. A node means "the plan that starts with these moves", and every iteration re-simulates from the real root, so the state under a node can differ between visits. It suits single-player planning in noisy simulators, trading some precision for needing no chance nodes.

Huge action spaces: progressive widening

When there are thousands of moves, or a continuous action such as a steering angle, the expand-every-child rule never gets past depth one. Progressive widening allows a node to have at most about k * N ** alpha children, adding a new one only when the visit count crosses the next threshold. With k = 1 and alpha = 0.5, a node visited 100 times has at most 10 children, and one visited 10,000 times has 100. New children should be drawn from a sensible proposal, such as a policy network or a heuristic sampler, not uniformly, or the few children the node ever gets will be poor.

Parallel MCTS

MCTS iterations are sequential by nature, since each one uses statistics the previous ones produced. There are three ways to use more cores:

Tree parallelism has a herding problem: workers starting at the same time all select the same promising path. Virtual loss fixes it by counting a pending visit as a loss until the real result arrives. In the worked example above, a worker descending into m3 with a virtual loss of 3 temporarily makes m3 N = 4, W = 1, and the root N = 19. A second worker then sees m3 at 0.25 + 1.4 x sqrt(2.944 / 4) = 1.45, m2 at 0.40 + 1.4 x sqrt(2.944 / 5) = 1.47 and m1 at 1.36, and goes to m2 instead. When the real result comes back, the virtual loss is removed and the true reward added.

With a neural network evaluator, the same mechanism enables batching: workers queue their leaves, a GPU evaluates a batch of 16 to 256 positions at once, and virtual loss keeps the queued leaves distinct. Larger batches trade search quality, lost to stale statistics, for throughput.

Learned priors, values and models

AlphaZero replaces both random playouts and uniform expansion with one network that outputs a move prior P and a value v. The value replaces the playout in the evaluate phase. The prior enters selection through the PUCT rule, which picks the child maximising Q + c_puct * P * sqrt(N_parent) / (1 + N), so moves the network likes are tried first and unlikely ones are almost never expanded. During self-play training, Dirichlet noise is mixed into the root prior, and root visit counts become the policy's training target, so search improves the network and the network improves the search.

MuZero, published by Schrittwieser and colleagues in Nature in 2020, removes the need for a simulator. It learns a representation function from observations to a hidden state, a dynamics function that predicts the next hidden state and reward from a hidden state and an action, and a prediction function for policy and value. MCTS then runs entirely inside the learned model, which let the same algorithm play Atari as well as Go and chess.

Gumbel MuZero, from Danihelka and colleagues at ICLR 2022, changes the root. Instead of PUCT it samples a few candidate actions with the Gumbel-top-k trick and allocates simulations among them by sequential halving, which guarantees policy improvement and helps most when only a handful of simulations are affordable.

Search over LLM reasoning

The newest use of MCTS is search over the reasoning of a language model. A node is a partial solution, such as the steps of a proof or a program so far; an action is the next step sampled from the model; and evaluation comes from a verifier, a learned value or process-reward model, or a quick rollout to a final answer that can be checked. Selection uses the model's own probability of the step as a prior, PUCT-style.

Three engineering facts dominate. Each expansion is an LLM call, so an iteration costs milliseconds to seconds, not microseconds, and budgets are tens or hundreds of nodes, which is where root-focused methods like Gumbel's matter. The value signal is the weak link: a reward model that can be fooled will steer the search to answers that fool it, and more search makes this worse, not better. And the baseline to beat is cheap: sampling N complete answers and picking the best by the same verifier often matches tree search at equal compute when the verifier only judges final answers. Tree search pays off when steps can be checked or scored partway through. How the returns from this kind of test-time search scale is analysed in search scaling in reasoning.

Engineering a production search

• Memory. One node per iteration grows the tree without bound. Allocate nodes from a preallocated pool, store children compactly, and free or prune subtrees when the pool fills.
• Tree reuse. After a move is played, keep the subtree under it as the new root; it already holds many of the next search's visits.
• Time control. Stop early when the most-visited root child cannot be overtaken in the remaining iterations, and spend more time in critical positions where the top two children are close.
• Transpositions. When different move orders reach the same state, sharing statistics through a hash table saves work but turns the tree into a graph, and naive backups then double-count; update only along the path actually taken.

Failure modes

• Backup from the wrong perspective. The search plays the opponent's best move. Test on a position with a one-move win.
• Narrow traps. In tactical games a single forced refutation can hide under many plausible moves; MCTS samples around it and misses it where alpha-beta search would not.
• Bad playout policy. Random playouts in long games can be so noisy that averages mean little; a light heuristic policy or a value function usually helps more than extra iterations.
• Untuned exploration constant. c that is too small locks onto the first lucky move; too large spreads visits almost evenly. Tune it against a fixed opponent.
• Chance treated as deterministic. Without chance nodes, the search plans as if the dice will always repeat the first roll it saw.
• Reward hacking in LLM search. The search finds answers the verifier scores highly but are wrong; audit top-ranked outputs by hand.

Trade-offs

MCTS is the default when the branching factor is large, a good hand-written evaluation is hard to come by, and a simulator exists. It is anytime, so it returns a sensible move at any budget, and it focuses effort where it matters. It is weaker than alpha-beta in sharp tactical positions with a strong evaluator, it needs a fast simulator or a learned model, and its statistics take many iterations to stabilise. For simultaneous-move or imperfect information games, where the right answer is a mixed strategy, see game theory, in depth before reaching for MCTS, since naive MCTS converges to a pure strategy that can be exploited.

What to do next

1. Implement the generic search above for tic-tac-toe or Connect Four and check it never loses to random play.
2. Write the one-move-win test for the backup perspective and keep it in your suite.
3. Add chance nodes and test on a dice game where the expected value is known.
4. Add progressive widening and run it on a problem with a continuous action.
5. Parallelise with a shared tree and virtual loss, and measure strength per second, not iterations per second.
6. If you search over LLM reasoning, compare against best-of-N with the same verifier at equal compute before adopting the tree.