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.
| Phase | What happens | Data touched |
|---|---|---|
| Selection | Descend from the root by applying a tree policy at each node | Reads visit counts and values |
| Expansion | Add one or more child nodes for untried actions | Creates new nodes |
| Simulation | Play out from the new node with a default policy, or call a value estimate | Produces a return |
| Backpropagation | Send the return back up the visited path | Updates counts and values |
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 policy | Selection rule | Typical use |
|---|---|---|
| UCT (UCB1) | Mean value plus logarithmic exploration bonus | General games and planning |
| PUCT | Bonus weighted by a learned prior policy | Neural-network guided search |
| Thompson-style selection | Sample from a posterior over node values | Stochastic or noisy domains |
| Progressive widening | Limit children by visit count | Continuous or huge action spaces |
MCTS compared with related planning and learning methods
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.
| Approach | Needs a model | Main strength | Main weakness |
|---|---|---|---|
| Monte Carlo tree search | Yes | Focuses compute on promising lines | Costly at decision time |
| Minimax with alpha-beta | Yes | Exact within its depth | Requires a good static evaluation |
| Value iteration | Yes | Solves the whole state space | Infeasible for large spaces |
| Q-learning | No | Learns from raw experience | Sample hungry, no lookahead |
| Plain Monte Carlo methods | No | Simple unbiased returns | No tree, no focused search |
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.
| Situation | Recommended choice | Reason |
|---|---|---|
| Random rollouts give misleading values | Use a learned value estimate or heuristic rollouts | Reduces variance and bias from aimless play |
| Search wastes time on bad moves | Add a prior policy with PUCT | Prunes implausible actions softly |
| Agent ignores good but rare moves | Raise the exploration constant | Restores visits to under-sampled children |
| Tight time limit per decision | Reuse the subtree from the previous move | Keeps statistics already gathered |
| Very large action space | Apply progressive widening | Keeps the branching manageable |
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.