Monte Carlo tree search

Also known as: MCTS

On this page 7

Monte Carlo tree search (MCTS) is a heuristic planning algorithm that chooses actions by building a search tree incrementally and estimating the value of each node from the results of simulated play. In reinforcement learning and artificial intelligence more broadly, it is the standard way to plan inside a known or learned model of an environment when the state space is far too large for exhaustive search.

Instead of evaluating every possible continuation, MCTS spends its computation where it matters: it repeatedly samples promising lines, records the outcomes, and gradually concentrates effort on the moves that look best while still testing alternatives. The algorithm is anytime, meaning it can be stopped after any number of iterations and still return the best action found so far.

The four phases of each MCTS iteration

Every iteration of Monte Carlo tree search runs four phases in a fixed order, starting at the root node that represents the current state. The tree stores, for each node, a visit count and an accumulated value, and these two statistics drive all later decisions.

PhaseWhat happensData touched
SelectionDescend from the root by applying a tree policy at each nodeReads visit counts and values
ExpansionAdd one or more child nodes for untried actionsCreates new nodes
SimulationPlay out from the new node with a default policy, or call a value estimateProduces a return
BackpropagationSend the return back up the visited pathUpdates counts and values
What each phase does and what it updates

The simulation phase, often called a rollout, gives MCTS its Monte Carlo character: the value of a position is the average return of sampled trajectories rather than a hand-coded score. Modern systems frequently replace random rollouts with a learned value function, which lowers variance at the cost of possible bias in the estimate.

After a fixed budget of iterations or time, the agent acts. The usual choice is the most-visited child of the root, which is more robust than the child with the highest mean value because a rarely visited node can have an inflated average from a few lucky samples.

How UCT balances exploration and exploitation

The most widely used tree policy is Upper Confidence bounds applied to Trees (UCT), which treats each node as a multi-armed bandit and applies the upper confidence bound rule. UCT selects the child that maximizes the mean value plus an exploration bonus proportional to the square root of the logarithm of the parent visit count divided by the child visit count.

This bonus shrinks as a child is visited more often, so under-sampled actions keep getting chances while strong actions receive most of the budget. Under standard assumptions UCT converges to the minimax or optimal action as the number of iterations grows, which gives the method a solid theoretical footing within the exploration-exploitation tradeoff.

The constant that scales the exploration term is the most important tuning parameter. Typical starting values lie between 0.5 and 2 when returns are normalized to the range from 0 to 1, and the best setting depends on the branching factor and on how noisy the rollouts are.

Tree policySelection ruleTypical use
UCT (UCB1)Mean value plus logarithmic exploration bonusGeneral games and planning
PUCTBonus weighted by a learned prior policyNeural-network guided search
Thompson-style selectionSample from a posterior over node valuesStochastic or noisy domains
Progressive wideningLimit children by visit countContinuous or huge action spaces
Common tree policies and their trade-offs

MCTS is a model-based planning method: it needs a simulator or model that predicts the next state and reward for an action. It differs from model-free reinforcement learning, which learns a policy or Q-function directly from experience, and from exhaustive search, which ignores sampling and expands every branch to a fixed depth.

ApproachNeeds a modelMain strengthMain weakness
Monte Carlo tree searchYesFocuses compute on promising linesCostly at decision time
Minimax with alpha-betaYesExact within its depthRequires a good static evaluation
Value iterationYesSolves the whole state spaceInfeasible for large spaces
Q-learningNoLearns from raw experienceSample hungry, no lookahead
Plain Monte Carlo methodsNoSimple unbiased returnsNo tree, no focused search
How MCTS relates to neighboring approaches

The most influential combination couples MCTS with deep networks and self-play. In this scheme a policy network supplies prior probabilities for selection, a value network replaces rollouts, and the visit distribution produced by the search becomes an improved training target for the policy. Search improves the network, and the network improves the next search, a loop that resembles policy iteration carried out with sampling.

Variants for harder domains

The basic algorithm assumes deterministic transitions and full observability, yet many problems violate both. Several well-studied variants extend MCTS to these settings without changing the four-phase structure.

  • Open-loop MCTS stores action sequences instead of states, which suits stochastic environments where the same action leads to different outcomes.
  • Information set MCTS searches over sets of indistinguishable states, which handles hidden information such as concealed cards in a partially observable Markov decision process.
  • Learned-model MCTS plans inside a model learned from data rather than given rules, a central idea in model-based reinforcement learning.
  • Parallel MCTS distributes iterations across threads using virtual loss, a temporary penalty that stops several workers from exploring the same path.

Practical configuration and common mistakes

Most failures of MCTS in practice come from poor rollout quality, a badly tuned exploration constant or too small a budget. The following decision table summarizes typical situations and the adjustments that experienced practitioners make first.

SituationRecommended choiceReason
Random rollouts give misleading valuesUse a learned value estimate or heuristic rolloutsReduces variance and bias from aimless play
Search wastes time on bad movesAdd a prior policy with PUCTPrunes implausible actions softly
Agent ignores good but rare movesRaise the exploration constantRestores visits to under-sampled children
Tight time limit per decisionReuse the subtree from the previous moveKeeps statistics already gathered
Very large action spaceApply progressive wideningKeeps the branching manageable
Configuration choices by situation

A frequent mistake is reporting values from the wrong player perspective in two-player games, which silently makes the search choose the opponent’s best move. Another is treating MCTS as a learning algorithm by itself: without a network or stored statistics across episodes, it plans from scratch at every decision and accumulates no lasting knowledge. Finally, the method can be trapped by narrow tactical lines, where only one precise sequence avoids a loss and sampling rarely finds it.

In everyday language

Imagine deciding your next chess move by quickly playing out many imaginary games in your head. Moves that keep leading to good endings get more of your attention, and moves that keep going badly get less, although you still check them now and then in case you missed something.

That is what Monte Carlo tree search does. It tries possible futures many times, keeps a running score for each choice, and picks the move it explored most. The more time it has, the better its choice usually becomes.

Seen in the real world

A logistics team builds a planner for automated warehouse robots that must decide, every few seconds, which shelf to fetch next while avoiding congestion in narrow aisles. The team already has a fast simulator of the warehouse floor, so it uses MCTS to look ahead about ten decisions per robot, running roughly 2,000 iterations within a 200 millisecond budget.

Random rollouts initially produce poor plans because robots in simulation wander aimlessly and block each other. The engineers replace them with a simple heuristic policy that always heads for the nearest free aisle, and they reuse the search tree between consecutive decisions. The result is a planner that reduces aisle blocking noticeably compared with the previous greedy rule, while staying within the real-time limit.