Concepts / How Monte Carlo Tree Search Works

How Monte Carlo Tree Search Works

Monte Carlo Tree Search, or MCTS, combines tree search with simulation.

  • Programming

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.

Key point

The fixed order is Selection, Expansion, Simulation, and Backpropagation. The order matters because each stage supplies the information needed by the next stage.

SelectionChoose a promising nodeExpansionAdd child nodesSimulationComplete-game rolloutBackpropagationUpdate traversed linksPartial game treeUpdated informationselected nodenew leafsimulation resultupdated statistics
What happens as one MCTS iteration moves through all four stages and returns updated information to the partial tree?

The Four-Stage Route

StageMain actionWhat it contributes
SelectionChoose the most promising node in the current treeDirects the next search effort
ExpansionAdd one or more child nodesExtends the partial game tree
SimulationPerform a complete-game rollout using a rollout policy to select movesProduces a game result
BackpropagationSend the result through traversed linksUpdates 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.

RootCurrent game stateNode ACandidateNode CMost promisingNode BCandidatechildchildselected path
How does Selection move from the root through child nodes to choose which node should be explored next?

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.

Selected nodeExploration pointNew childLeaf nodeComplete gameMoves selected by rolloutpolicyGame resultSimulation outputExpansionstart from leafproduces
How does Expansion add a child to the partial tree, and how does Simulation continue from that child to produce an outcome?
Worked example

Following Expansion into Simulation

Suppose Selection has chosen a node in a partial game tree, and the node has an unvisited move.

  1. 1
    Expand

    MCTS adds a child for the unvisited move. The new child is a leaf node of the partial game tree.

  2. 2
    Start the rollout

    MCTS begins Simulation from that leaf node.

  3. 3
    Continue the game

    The rollout policy selects moves until the simulation represents a complete game.

  4. 4
    Record the result

    The completed simulation supplies a result for Backpropagation.

Result

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.

Simulation resultComplete-game outcomeLeaf linkStatistics updated orinitializedSelected-path linkStatistics updatedRoot linkStatistics updatedback upcontinue backwardcontinue backward
How does the simulation result travel backward through selected nodes, and where do statistics change?

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.

RootExisting treeChild AExisting linkRootUpdated statisticsChild AUpdated statisticsNew childNew leaf nodeexisting child linkexisting link updatedchild added
What changes in the tree structure and node statistics before and after one MCTS iteration?
Worked example

Tracing the whole iteration

A partial game tree contains a root and several explored child links. Trace one new MCTS iteration.

  1. 1
    Selection

    MCTS identifies the most promising node in the current partial tree.

  2. 2
    Expansion

    MCTS adds one or more children to that selected node. Each new child is a leaf of the partial tree.

  3. 3
    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.

  4. 4
    Backpropagation

    MCTS sends the simulation result backward through the links traversed in the partial tree and updates or initializes their statistics.

Result

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

  • Common mistake

    Treating the four stages as interchangeable.

    What it looks like

    Describing Simulation before Selection or Backpropagation before a simulation result exists.

    Why it fails

    The stages form a connected order: Selection, Expansion, Simulation, then Backpropagation.

    Do this instead

    Use the sequence as a checklist: choose, add, roll out, update.

  • Common mistake

    Calling Selection an arbitrary node choice.

    What it looks like

    Choosing any node without considering whether it is promising.

    Why it fails

    Selection is described as an informed choice of the most promising node in the current tree.

    Do this instead

    Explain Selection by its role: directing exploration toward a promising node.

  • Common mistake

    Saying Expansion evaluates the game.

    What it looks like

    Claiming that adding a child itself produces the complete-game result.

    Why it fails

    Expansion adds children; Simulation performs the complete-game rollout and produces the result.

    Do this instead

    Keep tree growth and game evaluation as separate stages.

  • Common mistake

    Assuming Backpropagation stores statistics for every simulated state.

    What it looks like

    Maintaining statistics for links visited during the rollout even when those links are outside the partial game tree.

    Why it fails

    Statistics are maintained for links traversed in the partial game tree, not for corresponding links outside it.

    Do this instead

    Trace the result backward only through the relevant links in the partial tree.

  • Common mistake

    Forgetting that a newly added child is a leaf of the partial tree.

    What it looks like

    Treating a new child as though all of its possible moves have already been visited.

    Why it fails

    Each new child is a leaf because its possible moves have not yet been visited while constructing the partial tree.

    Do this instead

    Recognize the new child as the starting point for Simulation or further exploration.

Practice Check

EASY

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.
MEDIUM

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?

  • Selection

  • Expansion

  • Simulation

  • Backpropagation

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

  1. 1
    MCTS organizes its work into Selection, Expansion, Simulation, and Backpropagation.
  2. 2
    Selection makes an informed choice of a promising node in the current partial game tree.
  3. 3
    Expansion adds child nodes, and each new child is a leaf of the partial tree.
  4. 4
    Simulation performs a complete-game rollout from a leaf or a node with an unvisited move.
  5. 5
    Backpropagation sends the result backward through traversed links in the partial tree, updating or initializing their statistics.

At a glance

  • 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.

Related Topics

Related concepts

More concepts starting with H