--- kind: concept slug: monte-carlo-tree-search title: Monte Carlo tree search summary: >- Monte Carlo tree search builds a look-ahead tree from simulated futures and picks moves with the UCT rule, which balances mean value against rarely tried options. Variants swap random playouts for learned evaluators (AlphaGo, AlphaZero), search over particle beliefs, search over LLM agent actions, or search imagined robot futures (STORM). Trade-off: many simulations or model calls per decision. tags: [planning, search, reinforcement-learning, games, partial-observability, llm-agents, robotics] papers: ["2107.07599", "2507.07426", "2512.18477", "2610.17391"] related: [self-play, self-consistency, multi-agent-systems, retrieval-augmented-generation, world-model, vision-language-action-model] status: draft updated_at: 2026-10-25 --- ## 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 [arxiv: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 [arxiv:2610.17391 §5.2.4] [arxiv: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 [arxiv: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 [arxiv:2610.17391 §5.2.1]. The book suggests 1,000 to 10,000 iterations as a typical range, not a tuned value [arxiv:2610.17391 §5.2]. The book leaves draw handling and the player whose perspective is stored unspecified, so an implementation has to choose both [arxiv: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 [arxiv:2610.17391 app. B]. The book does not write out the mixing formula [arxiv: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 [arxiv:2610.17391 app. B]. AlphaZero applies the same architecture to Go, Chess and Shogi, with a 20-block residual network [arxiv:2610.17391 §7.3.1]. The book reports that the AlphaGo supervised stage took about three weeks of training [arxiv: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 [arxiv:2107.07599 §3.1]. The review names it alongside ABT and DESPOT, which are alternatives in the same online family [arxiv: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 [arxiv: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 [arxiv: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 [arxiv:2507.07426 eq. 4] [arxiv:2507.07426 eq. 5] [arxiv:2507.07426 eq. 6]. The paper runs 12 rollouts at temperature 0.8 [arxiv:2507.07426 §3.2]. The UCT constant is not stated in the paper [arxiv:2507.07426 eq. 1]. Card: [DrugMCTS](/papers/2507.07426). ### 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 [arxiv:2512.18477 §3.1] [arxiv: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 [arxiv:2512.18477 §3.3] [arxiv:2512.18477 eq. 5]. The paper runs 8 simulations per decision with c_puct = 1.0 [arxiv:2512.18477 §4.1]. The author-reported mean success on four SimplerEnv WidowX tasks is 51.0%, against 47.9% for the base policy [arxiv: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 [arxiv:2512.18477 §3.1] [arxiv:2512.18477 §4.1]. Card: [STORM](/papers/2512.18477). ## When to use which | Situation | Use | Why | |---|---|---| | A fast, exact simulator exists and no training data is available | Vanilla UCT with random playouts | It needs only the forward model and the loop in [arxiv:2610.17391 §5.2] | | Expert data and large training compute are available, and the goal is strong play in a board game | Network-guided search with self-play | Reported results cover Go, Chess and Shogi [arxiv:2610.17391 §7.3.1], but the training cost is high [arxiv:2610.17391 app. B] | | The state is hidden, and a generative model exists but a closed-form belief update does not | Particle-belief search over histories | It is the online sampling family in [arxiv:2107.07599 §3.1]; these solvers give approximate, not optimal, policies [arxiv:2107.07599 §1] | | The actions are calls to a general LLM, no training budget exists, and the decision is not latency-critical | Search over agent actions with a self-consistency and judgement reward | The paper reports gains over single-shot LLM baselines on its benchmark [arxiv:2507.07426 tab. 1], but the paper gives no per-query cost, and each reward needs several extra model calls [arxiv:2507.07426 §2.4] | | A policy can propose several candidate actions, a world model can be conditioned on actions, and each control step can afford many model calls | Search over imagined futures with a VLA prior (STORM) | The paper argues that checking imagined outcomes lets a robot avoid repeating a failed action [arxiv:2512.18477 §1]. The reported gain is small: 3.1 points over the base policy on four tasks [arxiv:2512.18477 tab. 1], and the video model's cost limits depth and breadth [arxiv:2512.18477 §5] | Simulation budgets differ by about three orders of magnitude across these papers: the textbook range is 1,000 to 10,000 [arxiv:2610.17391 §5.2], AlphaGo Zero used 1,600 per move [arxiv:2610.17391 app. B], DrugMCTS used 12 rollouts [arxiv:2507.07426 §3.2], and STORM used 8 simulations per decision [arxiv: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 [arxiv:2507.07426 tab. 1] [arxiv:2507.07426 §3.4]. Compare at a fixed top-k as well before claiming a gain over a baseline [arxiv: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. ```pseudocode # 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 [arxiv: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 [arxiv:2610.17391 app. B]. - **Exploration constant scale.** AlphaGo's constant of 5 is given without a reward scale [arxiv:2610.17391 app. B]. The DrugMCTS rewards lie in [0, 1], and the paper does not state its constant [arxiv:2507.07426 eq. 1]. STORM uses c_puct = 1.0 [arxiv: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](/papers/2507.07426)). 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 [arxiv:2107.07599 §3.1]. The UCT form in the book and in DrugMCTS includes the logarithm [arxiv:2610.17391 §5.2.4] [arxiv:2507.07426 eq. 1]. STORM's PUCT score [arxiv: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 [arxiv:2507.07426 §3.4] [arxiv:2507.07426 tab. 1]. ## Papers - [Partially Observable Markov Decision Processes (POMDPs) and Robotics](/papers/2107.07599): 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](/papers/2507.07426): 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](/papers/2512.18477): 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](/papers/2610.17391): a textbook covering MCTS with UCT, the AlphaGo family and self-play.