Simulation (rollout) is the phase in Monte Carlo Tree Search where, starting from a newly expanded node, a fast playout policy (often random or heuristic) is used to play the game or model the process until a terminal state is reached, generating a final outcome or reward. This computationally cheap playout provides a stochastic estimate of the long-term value of the node without a full, expensive search.
Reference
Simulation (Rollout)
Simulation, or rollout, is the Monte Carlo Tree Search (MCTS) phase where a fast playout policy is used to play from a node to a terminal state, generating a reward estimate.
MCTS PHASE
What is Simulation (Rollout)?
The simulation, or rollout, is a core phase of the Monte Carlo Tree Search (MCTS) algorithm responsible for estimating the value of a newly expanded game state.
The result of this simulated trajectory is then backpropagated up the tree to update the statistics of all ancestor nodes. While simple random playouts are common, more informed policies can drastically improve sample efficiency. This phase is distinct from the selection and expansion phases, focusing purely on outcome estimation rather than tree traversal or growth.
MONTE CARLO TREE SEARCH
Key Characteristics of the Simulation Phase
The simulation (or rollout) phase is where Monte Carlo Tree Search estimates the value of a newly expanded node by playing out the scenario to a terminal state using a fast, often random, policy.
01
Objective: Value Estimation
The core purpose is to generate a sample outcome (win/loss, reward) from the expanded node's state. This stochastic estimate, averaged over many rollouts, approximates the true expected value of that position. It provides the data point for the subsequent backpropagation phase.
- Key Metric: The Monte Carlo estimate is unbiased but can have high variance, especially with random playouts.
- Analogy: Like running a fast, approximate simulation of a business strategy to gauge its potential success, rather than a full, costly analysis.
02
The Playout Policy
MCTS PHASE
How the Simulation (Rollout) Phase Works
The simulation phase, also called a rollout, is the third step in a Monte Carlo Tree Search (MCTS) iteration where a fast policy is used to play out the scenario from a newly expanded node to a terminal state.
In the simulation (rollout) phase, the algorithm uses a playout policy—typically a fast, lightweight heuristic like random uniform selection—to sample a possible future from the newly expanded node until reaching a terminal state (e.g., game end). This default policy generates a final outcome, such as a win/loss or a scalar reward, without the computational cost of further tree expansion. The result provides a stochastic estimate of the node's value.
The rollout is a Monte Carlo sampling technique that estimates the long-term value of a state through repeated random forward play. While simple, this approach allows MCTS to evaluate positions in vast state spaces where exhaustive search is impossible. The efficiency of the rollout policy is critical, as it is executed thousands of times per search. More informed policies can reduce variance and improve convergence speed.
SIMULATION (ROLLOUT)
Frequently Asked Questions
A simulation, also called a rollout or playout, is the core estimation phase within the Monte Carlo Tree Search (MCTS) algorithm. This section answers key technical questions about its function, design, and optimization.
A simulation (rollout) is the phase in the Monte Carlo Tree Search (MCTS) algorithm where, starting from a newly expanded leaf node, a fast playout policy is used to sample a sequence of actions until a terminal state (e.g., game end) is reached, generating a final outcome or reward used to estimate the node's value.
This process is a form of Monte Carlo estimation, using random sampling to approximate the expected utility of a state when an exact calculation is computationally infeasible. The result—often a win/loss/draw signal or a numerical score—is then backpropagated up the tree to update the statistics of all ancestor nodes, refining the algorithm's understanding of which paths are promising.