Learn · Intermediate

Monte Carlo tree search: deciding which possibility to explore next

Monte Carlo tree search, usually called MCTS, is a planning method that decides which possible future to investigate by balancing what has worked so far against what has not been tried enough. It matters because an agent rarely has time to simulate every action sequence; MCTS turns a finite budget of trials into a progressively better map of the choices that matter. From game-playing systems to tool-using agents, it is one of the clearest ways to make search deliberate rather than merely prolific.

Imagine choosing a restaurant in a city with thousands of streets. You could walk every street before deciding, but dinner would be over. You could return to the first promising cafe forever, but might miss a better neighborhood one block away. MCTS behaves like a disciplined explorer: revisit places that have produced good meals, while occasionally spending a trip on a street with too little evidence. Each visit improves the map and changes where the next visit goes.

The structure is a tree. A node represents a state: a board position, a partial proof, a program candidate, or the current state of an agent task. An edge represents an action: a move, a proof step, a code edit or a tool call. A path from the root is one possible sequence of decisions. The word Monte Carlo means the method estimates the value of a path by sampling outcomes rather than calculating every consequence exactly. The word tree means it remembers and reuses what those samples taught it.

A basic MCTS loop has four steps. Selection walks from the root through already-expanded choices, choosing an action that balances a high average reward with an exploration bonus. Expansion adds a new child once the walk reaches a choice that has not been developed. Simulation, also called rollout, estimates what happens from that new state; it might play a quick game, execute code, call a verifier or ask a policy model for a continuation. Backup sends the observed reward back up the path, updating each node's visit count and value estimate. Then the loop starts again.

The classic decision rule is Upper Confidence bounds applied to Trees, or UCT, developed by Levente Kocsis and Csaba Szepesvári in Bandit Based Monte-Carlo Planning. It combines a child's average reward with a bonus that is larger when that child has been visited less often and when its parent has been visited more often. You do not need the formula to understand the behavior. A restaurant with many excellent reviews keeps getting visits; a restaurant with one mediocre review gets another chance because one review is weak evidence; a restaurant tried 10,000 times with poor results stops consuming attention.

This is a form of the exploration-versus-exploitation tradeoff. Exploitation uses the best current estimate. Exploration buys information that might overturn the estimate. The tradeoff appears everywhere in AI: a recommender deciding whether to show a familiar item, an optimizer deciding which configuration to benchmark, or a coding agent deciding whether to repair the likely bug or inspect an odd log line. MCTS makes the tradeoff explicit at every node in a sequence, not just once at the beginning.

MCTS became famous through Go. The branching factor of Go is far too large for exhaustive lookahead, and hand-written evaluation functions struggled to judge positions. In AlphaGo, David Silver and colleagues combined neural networks with tree search. A policy network proposed moves worth exploring; a value network estimated the quality of a position; MCTS used both to allocate simulations. The result was not that search disappeared. Learning made search more selective, and search generated improved training data. This division of labor is central: the neural model supplies informed intuition, while the tree supplies lookahead and a mechanism for checking alternatives.

Modern language-model agents use related ideas whenever they generate multiple candidate plans, verify them, branch on tool results or run rollouts before selecting an answer. The details differ because language tasks have costly tools, nonstationary web environments and rewards that are often delayed or ambiguous. A verifier can make MCTS especially powerful: if a compiler, test suite, proof checker or security sandbox returns a trustworthy signal, the agent does not need to rely only on its own confidence. That connects directly to reinforcement learning with verifiable rewards and to tool use and function calling.

MCTS is not a magic guarantee. It can overfit to a flawed reward, repeatedly explore branches that are easy to simulate rather than important, or inherit bias from the policy that proposes moves. Rollouts can be expensive, and a sparse or deceptive evaluator can make a well-balanced tree confidently pursue the wrong objective. In open-ended agent work, the tree can also grow too large to manage. Techniques such as pruning, value models, transposition tables and limited depth exist because the ideal full tree is usually unaffordable.

The enduring lesson is modest and powerful: when a task has many possible next steps, do not spend all computation on the first plausible one or distribute it blindly. Record what each attempt taught you, return to promising branches, and reserve enough budget to discover that your favorite branch was a mirage. That is the planning instinct MCTS formalizes.

Ground Truth. (2026, September 17). Monte Carlo tree search: deciding which possibility to explore next. Ground Truth. https://groundtruth.day/learn/monte-carlo-tree-search.html

@misc{groundtruth:monte-carlo-tree-search,
  title  = {Monte Carlo tree search: deciding which possibility to explore next},
  author = {{Ground Truth}},
  year   = {2026},
  month  = {sep},
  url    = {https://groundtruth.day/learn/monte-carlo-tree-search.html}
}

Topics: planning · reinforcement-learning · agents · search · reasoning