Did you know? Imagine a game in which you have ten possible moves and each move creates ten more possible replies. Looking just four turns ahead could involve thousands of branches. A computer cannot always examine every possible future in the time available. What if it could sample possible futures and spend more effort investigating promising moves?
That is the intuition behind Monte Carlo Tree Search (MCTS). It combines a partial search tree with simulations, gradually estimating which actions lead to stronger outcomes according to a defined reward. It is especially associated with game-playing AI, but the framework can also be adapted to planning problems where outcomes can be simulated.
Quick answer: start from the current state → select a promising path → expand an unexplored action → simulate an outcome → backpropagate the result → repeat within a budget → choose a move from accumulated evidence. These are the four familiar phases: selection, expansion, simulation and backpropagation.
A search simulation is not proof that a move will work in reality. Good simulation models, legal actions, correct reward accounting and appropriate safeguards still matter.
Monte Carlo Tree Search in 30 seconds
- Root: the state where a decision must be made now.
- Node: a game or planning state reached after taking a sequence of actions.
- Edge: a legal action leading from one state to another.
- Visit count: how often the algorithm explored a node or edge during search.
- Value estimate: an average or other summary of simulated outcomes.
- Selection: choosing a path through already explored parts of the tree.
- Expansion: adding a previously unexplored state.
- Simulation or rollout: following a policy from an expanded state to estimate an outcome.
- Backpropagation: updating statistics along the selected path using the result.
- Budget: a limit on simulations, computation or time.
A miniature game with only two choices
Imagine a fictional, harmless classroom puzzle. From the starting square you may choose Move A or Move B. After either action, the rest of the puzzle has several random-looking possibilities. We give a result score of 1 for success and 0 for failure.
Suppose the search has already simulated A eight times and seen six successes, so its observed mean value is 6 ÷ 8 = 0.75.
It has simulated B only twice, with one success, giving observed mean value 1 ÷ 2 = 0.50.
If we chose only the higher observed average immediately, we would keep selecting A. But B has barely been tested. A search rule may choose B next to reduce uncertainty about it.
Step 1: Define the state and legal actions
A state must describe everything required to simulate what can happen next. In a board game, that may include board positions, whose turn it is, remaining special moves and whether the game is over.
An action must be legal under those rules. A search algorithm cannot repair an incorrect rule engine. If the simulator silently allows impossible moves, excellent search statistics can point to an unusable plan.
For practical planning, the state may include resources, deadlines and constraints. The quality of any outcome estimate depends on whether those details are represented accurately.
Step 2: Define a reward before searching
Our toy puzzle gives 1 for success and 0 for failure. A different game might assign win = 1, draw = 0 and loss = −1, or use another clearly stated convention.
Whatever scale you choose, apply it consistently. In a two-player adversarial game, a gain for the root player may be a loss for the opponent. Backpropagation and node selection must respect which player’s perspective each value represents.
Do not use a loosely worded target such as ‘choose the best outcome for everyone’ without defining how outcomes are measured and what hard constraints cannot be traded away.
Step 3: Begin the tree at the present decision
The root is the present state. Its children represent available first moves. Each child’s children represent later replies or outcomes.
MCTS normally builds only the parts of the tree it chooses to explore. It does not need to materialise all possible states in advance.
As the number of available actions and the planning horizon grow, this selective approach can make a search possible within limited resources.
Step 4: Selection balances promise and exploration
Selection follows a tree policy, often using a score that rewards high estimated value while giving less-visited options an exploration bonus.
A common pedagogical form is UCB score = average reward + c × √(ln N / n), where N is the parent’s total visit count, n is the candidate’s visit count and c controls exploration strength.
Several real implementations use the related UCT idea or policy-guided variants. The exact formula, reward scaling and treatment of unexplored children vary. A formula should be presented alongside its convention, not as the only possible MCTS rule.
Step 5: Calculate a selection score by hand
In our example, A was visited 8 times with mean reward 0.75; B was visited 2 times with mean reward 0.50. The parent total is 10 visits. Set c = 1 for this illustrative calculation.
For A, the exploration bonus is √(ln 10 / 8) ≈ 0.536, so its total score is 0.75 + 0.536 = 1.286.
For B, the exploration bonus is √(ln 10 / 2) ≈ 1.073, so its total score is 0.50 + 1.073 = 1.573.
B is selected next even though its average reward is lower. The extra bonus reflects how little B has been explored. This is a search choice, not a claim that B is currently the best final move.
Step 6: Why the logarithm appears in a UCB-style rule
The exploration bonus grows with the parent’s visit count N but shrinks as a particular child is visited more often. The logarithm makes the pressure to revisit under-explored choices increase slowly.
This is related to the exploration–exploitation problem: how much effort should we spend on the option that has looked good so far, and how much should we spend checking other options that might be better?
Different settings and nonstationary environments require caution. These terms are not magic guarantees, particularly when rollouts are biased or reward values are highly variable.
Step 7: Expand an unexplored action
After selection, the algorithm reaches a state that has some legal action not yet represented in the tree. Expansion usually adds one or more child nodes.
Creating every possible child on every visit can consume substantial memory. Many simple implementations add a single new child per iteration.
A terminal state—one where the task has definitively ended—does not require expansion. Its outcome can be backed up directly.
Step 8: Run a simulated continuation
A rollout follows the game or environment rules from the expanded node to an outcome. The simplest rollout may choose legal actions at random.
Random rollouts are convenient but may be poor approximations of competent future play. A stronger rollout policy, a learned value function or a model-based estimate can improve guidance when carefully validated.
The phrase Monte Carlo refers to repeated sampling. It does not mean the algorithm is merely choosing random moves at the root.
Step 9: Backpropagate the outcome
Suppose the selected simulation ends in success and receives reward 1 for the root player’s perspective. MCTS updates the visit count and accumulated reward for the edges or nodes along the path that was explored.
Returning to B in our toy example, its visits rise from 2 to 3 and successful outcomes from 1 to 2. Its new observed mean becomes 2 ÷ 3 ≈ 0.667.
If the simulation had failed, B would instead have mean 1 ÷ 3 ≈ 0.333. Both updates are useful evidence, but a single rollout should not be overinterpreted.
In adversarial games, values may be stored from the player-to-move perspective and signs flipped as turns alternate. Other implementations maintain a consistent root-player perspective. Mixing these conventions produces serious search bugs.
Step 10: Repeat without exhausting the whole tree
A single iteration learns little. MCTS repeats selection, expansion, simulation and backpropagation, gradually concentrating samples in useful portions of the tree.
With a tight budget, the tree can remain shallow and uncertain. With a larger budget, estimates can become more informative—but extra simulations do not compensate for wrong rules, incorrect rewards or pathological sampling.
Performance should be measured under fixed computation limits so that comparisons are fair.
Step 11: Choose the final move using an explicit rule
During search, an exploration bonus encourages checking uncertain choices. At the final decision point, implementations commonly choose a move using a different rule, such as most visits or highest estimated value.
These are not always identical. Most visits can be more stable when value estimates are noisy, but the right convention depends on the algorithm and task.
Do not choose the move with the highest UCB exploration score as though that score were a calibrated expected real-world payoff.
Step 12: Search is not the same as reinforcement learning
Reinforcement learning is a broader family of methods for learning actions from reward and experience. MCTS is a planning method that can operate without updating a long-term policy at all.
A search system may use a learned policy to guide selection or a learned value function to evaluate leaves. Such hybrids can be powerful, but they combine distinct components.
Careful explanation should separate the policy that proposes moves, the search that evaluates possibilities and any training that changes model parameters.
Step 13: What AlphaGo demonstrated—and what it did not
Well-known Go-playing AI systems combined search with learned guidance. This helped focus computation on promising positions in an enormous move space.
The takeaway is not that MCTS alone automatically solves Go or every strategic decision. The strength depends on accurate rules, useful policies or evaluation functions, extensive engineering and appropriate computational resources.
A classroom MCTS implementation using random rollouts may behave very differently from a specialised high-performance system.
Step 14: The branching factor changes the problem
If there are 10 legal moves at each step, a naive four-ply search may face roughly 10 × 10 × 10 × 10 = 10,000 action sequences before considering repeated states or other complications.
MCTS samples only part of that tree. This is particularly useful when full enumeration is infeasible and plausible continuations can be simulated.
However, a very large number of actions can still make each candidate under-explored. Progressive widening and other variants address particular large-action settings.
Step 15: What if the simulator is wrong?
Suppose a robot’s simulator assumes a dry floor, but the actual floor is wet. The search may prefer a fast turn that works beautifully in simulation and fails physically.
The tree’s mathematics can be correct relative to the simulation while the decision is wrong in the world. This is model error, not a paradox.
For physical or safety-critical planning, hard constraints, independent verification and conservative action limits remain necessary. No finite sample search certifies safety by itself.
Step 16: What if rollouts are random but the opponent is clever?
A strategy that beats a random opponent may lose badly against a strong opponent. The simulation policy matters because it shapes the rewards the tree learns from.
For adversarial games, evaluation must reflect alternating decisions and sensible opponents. Search value can be optimistic if the imagined opponent regularly makes implausible mistakes.
Stress-test against stronger policies and held-out game states rather than judging only by results against one simplistic simulation setup.
Step 17: Handling stochastic outcomes
Some environments produce random outcomes even after the same action. A search can sample those outcomes across repeated rollouts, provided the simulator’s distribution is well grounded.
An observed success rate such as 6 in 8 is a noisy estimate, not a certainty about the move’s true probability of success. More samples reduce some sampling uncertainty but cannot fix biased outcomes or missing events.
When rare bad outcomes matter, evaluating averages alone may conceal risk. Add appropriate constraints, tail-risk analyses or specialised risk-aware planning rather than making unwarranted safety claims.
Step 18: The difference between a tree and a graph
Different move sequences can sometimes reach the same underlying state. A plain search tree may store those paths as separate nodes, wasting work.
More advanced search can use transposition tables or other mechanisms to share information across equivalent states, but combining statistics requires consistent state definitions and handling of cycles.
An explanation should not casually imply all distinct-looking paths are genuinely different real-world situations.
Step 19: How MCTS compares with genetic algorithms
Genetic algorithms maintain populations of candidate solutions and explore them using selection, crossover and mutation. MCTS builds a partial decision tree and samples outcomes of action sequences.
Both are search or optimisation approaches, but they represent and explore possibilities differently. A genetic algorithm may suit parameter or schedule optimisation; MCTS is especially natural when the next choice leads to another state with new available actions.
Neither technique proves that a high numerical score is a safe or socially desirable result.
Step 20: Good uses and important limits
Board games and puzzles: planning from positions with known legal moves and results.
Simulation-based planning: evaluating sequences of actions in a validated environment model.
Strategy research: comparing search policies and action-selection rules with controlled experiments.
Teaching computational thinking: exploring averages, counts, sampling, uncertainty and search trees.
MCTS is less suitable when outcomes cannot be simulated credibly, legal actions are not well defined, or the cost of a mistaken real action is unacceptable without an external safety mechanism.
Five mistakes worth avoiding
- ‘Every possible branch is explored.’ No. MCTS selectively builds a partial tree.
- ‘Monte Carlo means the final decision is random.’ No. Random sampling often supplies evidence, but selection uses statistics.
- ‘The exploration score is the final move value.’ No. It includes a bonus intended to guide search.
- ‘More simulations always prove correctness.’ No. They can refine estimates under a flawed model.
- ‘Search and neural-network training are the same operation.’ No. Search explores actions; training changes learned model parameters.
Try it: choose which move deserves another test
- Record Move A: 8 visits and 6 successes. Its observed average reward is 0.75.
- Record Move B: 2 visits and 1 success. Its observed average reward is 0.50.
- With parent visit count N = 10 and c = 1, calculate A’s UCB-style score: 0.75 + √(ln10 ÷ 8), approximately 1.286.
- Calculate B’s score: 0.50 + √(ln10 ÷ 2), approximately 1.573.
- Explain why the algorithm explores B even though its average is lower.
- Simulate one more trial of B. Update its visits and successes for a win or loss, then explain why the next search selection can change.
- Finish by asking whether the score is a real-world probability. It is not: it is a value estimate plus an exploration bonus.
Frequently asked questions
What does MCTS stand for?
Monte Carlo Tree Search, a family of planning methods that uses sampled outcomes to guide selective exploration of possible actions.
What are its four phases?
Selection, expansion, simulation or rollout, and backpropagation.
Why does MCTS revisit a less promising action?
Exploration policies intentionally investigate under-sampled choices because their true value is more uncertain.
Does MCTS require a neural network?
No. It can use random simulations and explicit rules. Some advanced systems combine it with learned policy and value networks.
Is MCTS guaranteed to win?
No. Finite runs can choose poorly, and outcomes depend on the simulator, policy, reward definition and computational budget.
How is MCTS different from minimax?
Classical minimax search evaluates an adversarial game tree with explicit evaluation of alternatives; MCTS uses sampled trajectories and statistical action estimates, often exploring only a fraction of the full tree.
Your one-minute takeaway
Monte Carlo Tree Search uses repeated simulations to build a partial tree of action outcomes. Selection balances high values against unexplored alternatives, expansion adds a state, simulation estimates an outcome and backpropagation updates the statistics. The search is only as trustworthy as its rules, simulation and reward definition.
Trusted reading and connected articles
- Mastering Reinforcement Learning: MCTS — educational derivation of selection, expansion, rollout and backpropagation
- Artificial Intelligence Review: MCTS Methods and Applications — research survey of variants, limits and use cases
- How AI Learns by Trial, Error and Reward — reinforcement learning versus search
- How AI Searches for Better Solutions With Genetic Algorithms — a different search method
- How Hidden Markov Models Recognise Patterns in Sequences — probabilistic sequence analysis rather than tree search
- How AI Works: Complete Overview — the wider technical series
- Secondary 1 Mathematics Tutor Clementi — from worked arithmetic to mathematical reasoning