Monte Carlo tree search

Overview

Monte Carlo tree search (MCTS) chooses an action by building a search tree from simulated futures. Each node keeps a visit count and a value estimate. Each iteration walks down the tree, adds a node, estimates its value, and updates the path back to the root 2610.17391 §5.2.

The part that all variants share is the choice rule. A child is scored by its mean value plus a bonus that grows when the child has been visited rarely (UCT). Its exploration term is scaled by a constant the user tunes 2610.17391 §5.2.4 2507.07426 eq. 1. The search can stop after any number of iterations or when time runs out, so the budget is the main knob for trading quality against cost 2610.17391 §5.2.

Variants

Vanilla UCT with random playouts

The textbook form. Leaves are evaluated by playing random moves to the end of the game. The result is +1 for a win by the first player, 0 for a draw and -1 for a loss, and it is added to the nodes on the path 2610.17391 §5.2.1. The book suggests 1,000 to 10,000 iterations as a typical range, not a tuned value 2610.17391 §5.2. The book leaves draw handling and the player whose perspective is stored unspecified, so an implementation has to choose both 2610.17391 §5.2.1.

Prior-guided search with a value network and fast rollouts (AlphaGo)

AlphaGo adds a policy prior to the selection step, using a P-UCT variant. It uses a slow policy network, trained by supervised learning and then refined by self-play, and a fast rollout policy. Leaves are scored by a mix of a value network and a fast rollout, with weight 0.5 on the rollout. The exploration constant is 5 2610.17391 app. B. The book does not write out the mixing formula 2610.17391 app. B.

Network-guided search with self-play (AlphaGo Zero, AlphaZero)

One residual network with a policy head and a value head replaces the three AlphaGo networks, and there are no rollouts. Self-play games are generated by search with 1,600 simulations per move. Each stored position keeps the search probabilities and the game outcome, and the next network is trained on samples from recent games 2610.17391 app. B. AlphaZero applies the same architecture to Go, Chess and Shogi, with a 20-block residual network 2610.17391 §7.3.1. The book reports that the AlphaGo supervised stage took about three weeks of training 2610.17391 app. B.

Particle-belief search for partially observable problems (POMCP)

When the state is hidden, the tree is built over action-observation histories, and beliefs are represented by particles. The review describes POMCP as UCT over histories with a generative model and particle beliefs 2107.07599 §3.1. The review names it alongside ABT and DESPOT, which are alternatives in the same online family 2107.07599 §3.1. It gives no constants for POMCP, and it notes that the printed action rule differs from the UCB1 rule it cites 2107.07599 §3.1. See Contradictions.

Search over LLM agent actions (DrugMCTS)

Here the tree nodes are steps of a pipeline. Each step is a retrieval, an analysis, a filter or a decision, performed by a general language model that is not fine-tuned 2507.07426 §2.3. The reward of a finished path averages two shares: how often repeated answers agree (self-consistency, four samples) and how often a yes/no check says yes 2507.07426 eq. 4 2507.07426 eq. 5 2507.07426 eq. 6. The paper runs 12 rollouts at temperature 0.8 2507.07426 §3.2. The UCT constant is not stated in the paper 2507.07426 eq. 1. Card: DrugMCTS.

Search over imagined robot futures with a VLA prior (STORM)

Here the tree nodes are robot states and the edges are candidate actions. At each expansion, a diffusion-based vision-language-action policy proposes K = 8 candidate actions with priors 2512.18477 §3.1 2512.18477 §4.1. Each simulation imagines the outcome of one unvisited candidate with a video world model, and the predicted reward is that simulation's value. Selection uses the PUCT score, which includes the prior 2512.18477 §3.3 2512.18477 eq. 5. The paper runs 8 simulations per decision with c_puct = 1.0 2512.18477 §4.1. The author-reported mean success on four SimplerEnv WidowX tasks is 51.0%, against 47.9% for the base policy 2512.18477 tab. 1. The paper does not state how the priors are computed or how γ = 0.9 enters the value, so an implementation has to choose both 2512.18477 §3.1 2512.18477 §4.1. Card: STORM.

When to use which

Simulation budgets differ by about three orders of magnitude across these papers: the textbook range is 1,000 to 10,000 2610.17391 §5.2, AlphaGo Zero used 1,600 per move 2610.17391 app. B, DrugMCTS used 12 rollouts 2507.07426 §3.2, and STORM used 8 simulations per decision 2512.18477 §4.1. Budgets are not transferable between domains without a check.

DrugMCTS's headline recall depends on a protocol choice. Its two rows in the main table are labelled by the ground-truth count, which is not known at prediction time, and by that count plus three 2507.07426 tab. 1 2507.07426 §3.4. Compare at a fixed top-k as well before claiming a gain over a baseline 2507.07426 §3.4.

Implementation sketch

The loop is shared. The select, evaluate and backup steps are where the variants differ. The sketch is in Python-like pseudocode, with the citation on each step.

# Generic MCTS loop; variants differ in select, evaluate and backup.
# Each node keeps: visits n, total value w, and an optional prior p.

def mcts(root_state, budget, c):
    # Root holds the current state; the budget is iterations or seconds
    # [arxiv:2610.17391 §5.2]
    root = Node(root_state)
    for _ in range(budget):
        node = root
        # 1. Select: descend by UCT while all children are expanded
        #    [arxiv:2610.17391 §5.2.4] [arxiv:2507.07426 eq. 1]
        #    PUCT variants add a prior term [arxiv:2512.18477 eq. 5]
        while node.fully_expanded() and not node.terminal():
            node = max(node.children, key=lambda ch: uct(ch, node.n, c))
        # 2. Expand: add a child; LLM variants may add several
        #    [arxiv:2610.17391 §5.2.1] [arxiv:2507.07426 §2.2]
        if not node.terminal():
            node = node.add_child()
        # 3. Evaluate: random playout, value network, LLM reward, or a
        #    world-model reward [arxiv:2610.17391 §5.2.1] [arxiv:2610.17391 app. B]
        #    [arxiv:2512.18477 §3.3]
        value = evaluate(node.state)
        # 4. Backup: add the value to every node on the path
        #    [arxiv:2610.17391 §5.2.1]
        backup(node, value)
    # Return the root action with the most visits, or the best mean value
    # [arxiv:2610.17391 §5.2.2] [arxiv:2507.07426 §2.2]
    return best_root_action(root)

Two-player games need one perspective for stored values. The book leaves that choice open, so the implementation must make it and keep it consistent 2610.17391 §5.2.1.

Contradictions

• Value conventions inside one source. The book describes AlphaGo's value output as a probability of winning, while AlphaGo Zero trains its value against an outcome in {-1, +1}. The book does not reconcile the two 2610.17391 app. B.
• Exploration constant scale. AlphaGo's constant of 5 is given without a reward scale 2610.17391 app. B. The DrugMCTS rewards lie in [0, 1], and the paper does not state its constant 2507.07426 eq. 1. STORM uses c_puct = 1.0 2512.18477 §4.1 but does not state the range of its predicted reward, so its constant cannot be placed on the same scale. The companion repository defaults to 3.0, which is not in the paper (DrugMCTS card). Constants from different reward scales are not directly comparable.
• Selection rule notation. The review prints a POMCP action rule with a square root of a count ratio and no logarithm, and says it differs from the UCB1 rule it cites 2107.07599 §3.1. The UCT form in the book and in DrugMCTS includes the logarithm 2610.17391 §5.2.4 2507.07426 eq. 1. STORM's PUCT score 2512.18477 eq. 5 uses the square root of the parent's total visits and a prior term, with no logarithm. Check the original POMCP paper before implementing it.
• DrugMCTS text versus table. The text gives the deep-learning KIBA recall as 26.45%, while Table 1 gives 0.3216 2507.07426 §3.4 2507.07426 tab. 1.

Papers

• Partially Observable Markov Decision Processes (POMDPs) and Robotics: a review of sampling-based POMDP solvers, including POMCP, which is UCT over histories with particle beliefs.
• DrugMCTS: a drug repurposing framework combining multi-agent, RAG and Monte Carlo Tree Search: MCTS over LLM agent actions, with a reward from self-consistency and a yes/no judgement. Results are author-reported.
• STORM: Search-Guided Generative World Models for Robotic Manipulation: PUCT search over candidate actions from a diffusion VLA policy, with a video world model supplying each simulated value. Results are author-reported.
• Learning to Play: Reinforcement Learning and Games: a textbook covering MCTS with UCT, the AlphaGo family and self-play.