How Monte Carlo Tree Search Works
MCTS uses four stages: Selection, Expansion, Simulation, and Backpropagation.
A Search Iteration as a Loop
Monte Carlo Tree Search, or MCTS, combines tree search with simulation. It works on a partial game tree rather than waiting for the tree to contain every possible move. During one iteration, MCTS chooses where to explore, extends the partial tree, simulates a complete game, and sends the simulation result back through the part of the tree that the iteration traversed.
The fixed order is Selection, Expansion, Simulation, and Backpropagation. The order matters because each stage supplies the information needed by the next stage.
The Four-Stage Route
| Stage | Main action | What it contributes |
|---|---|---|
| Selection | Choose the most promising node in the current tree | Directs the next search effort |
| Expansion | Add one or more child nodes | Extends the partial game tree |
| Simulation | Perform a complete-game rollout using a rollout policy to select moves | Produces a game result |
| Backpropagation | Send the result through traversed links | Updates or initializes statistics in the partial tree |
The four connected stages of one MCTS iteration
The stages are connected, but they have different responsibilities. Selection operates on the tree that already exists. Expansion changes that tree by adding child nodes. Simulation evaluates a continuation by rolling out a complete game. Backpropagation records the result only along the relevant part of the partial tree.
Choosing Where to Explore
Selection begins inside the current partial game tree. It chooses the node that appears most promising for further exploration. This is an informed choice, not an arbitrary choice. The source section does not define the particular rule used to measure promise, so the essential idea is the role of Selection: it directs the next search effort toward one node already represented in the current tree.
Growing and Evaluating the Tree
After Selection identifies a promising node, Expansion adds one or more child nodes to it. Each new child is a leaf node of the partial game tree because its possible moves have not yet been visited while constructing that tree.
Simulation then starts from a leaf node, or from another node with an unvisited move. It performs a rollout of a complete game, using a rollout policy to select moves. The purpose of this stage is to produce a result that can later be used to update the partial tree.
Following Expansion into Simulation
Suppose Selection has chosen a node in a partial game tree, and the node has an unvisited move.
Expand: MCTS adds a child for the unvisited move. The new child is a leaf node of the partial game tree.
Start the rollout: MCTS begins Simulation from that leaf node.
Continue the game: The rollout policy selects moves until the simulation represents a complete game.
Record the result: The completed simulation supplies a result for Backpropagation.
Expansion changes the partial tree first; Simulation then produces the result that will be sent back through the traversed links.
Sending the Result Back
Backpropagation takes the result of the complete-game simulation and backs it up through the links in the partial game tree that the iteration traversed. At those links, MCTS updates or initializes statistics. This is how the result of a rollout becomes information that can influence later Selection decisions.
One Iteration in State
The clearest way to trace an iteration is to compare the partial game tree before and after it. Before the iteration, the tree contains the nodes and links already explored. After Selection, Expansion, Simulation, and Backpropagation, the tree has been extended and the relevant traversed links carry updated or initialized statistics.
Tracing the whole iteration
A partial game tree contains a root and several explored child links. Trace one new MCTS iteration.
Selection: MCTS identifies the most promising node in the current partial tree.
Expansion: MCTS adds one or more children to that selected node. Each new child is a leaf of the partial tree.
Simulation: MCTS starts from the new leaf, or from a node with an unvisited move, and performs a complete-game rollout using a rollout policy.
Backpropagation: MCTS sends the simulation result backward through the links traversed in the partial tree and updates or initializes their statistics.
The next iteration begins with a larger or more informed partial tree, because one child may have been added and statistics on the traversed links have been changed.
Common Misreadings
Treating the four stages as interchangeable.
The stages form a connected order: Selection, Expansion, Simulation, then Backpropagation.
Fix:
Use the sequence as a checklist: choose, add, roll out, update.Calling Selection an arbitrary node choice.
Selection is described as an informed choice of the most promising node in the current tree.
Fix:
Explain Selection by its role: directing exploration toward a promising node.Saying Expansion evaluates the game.
Expansion adds children; Simulation performs the complete-game rollout and produces the result.
Fix:
Keep tree growth and game evaluation as separate stages.Assuming Backpropagation stores statistics for every simulated state.
Statistics are maintained for links traversed in the partial game tree, not for corresponding links outside it.
Fix:
Trace the result backward only through the relevant links in the partial tree.Forgetting that a newly added child is a leaf of the partial tree.
Each new child is a leaf because its possible moves have not yet been visited while constructing the partial tree.
Fix:
Recognize the new child as the starting point for Simulation or further exploration.
Practice Check
A search process has selected a promising node, added a new child, and completed a rollout from that child. Which stage comes next, and what does it do?
Hints
- Recall the four-stage order.
- The next stage uses the result of the completed rollout.
- Its updates are limited to links traversed in the partial game tree.
Explain why a new child added during Expansion is called a leaf node of the partial game tree, even though Simulation may continue beyond it.
Hints
- Distinguish the partial game tree from the complete rollout.
- Ask whether the child's possible moves have already been visited while constructing the tree.
What do you think happens?
After a complete-game rollout has produced a result, which stage uses that result?
Reveal answer
Answer: Backpropagation
Backpropagation sends the simulation result backward through the links traversed in the partial game tree and updates or initializes their statistics.
Key Takeaways
- MCTS organizes its work into Selection, Expansion, Simulation, and Backpropagation.
- Selection makes an informed choice of a promising node in the current partial game tree.
- Expansion adds child nodes, and each new child is a leaf of the partial tree.
- Simulation performs a complete-game rollout from a leaf or a node with an unvisited move.
- Backpropagation sends the result backward through traversed links in the partial tree, updating or initializing their statistics.
Key Takeaways
- One MCTS iteration follows the order Selection, Expansion, Simulation, and Backpropagation.
- Selection chooses where the next exploration effort should be directed.
- Expansion grows the partial tree, while Simulation produces a complete-game result.
- Backpropagation updates or initializes statistics only on relevant links in the partial game tree.
- The next iteration uses the extended tree and the information gathered from earlier iterations.