Monte Carlo Tree Search

Step through how search trees are expanded, simulated, and scored.

Game Rules

Two players take turns adding 1 or 2 to a running sum. The player who makes the sum exactly 10 wins; exceeding 10 loses immediately.

Starting sum is 0.
Players alternate turns, with Player A starting.
Each turn, a player must add either 1 or 2 to the sum.
The goal is to make the sum exactly 10.
If a player makes the sum exceed 10, they lose immediately.

Game State

Add 1 or 2. Hitting 10 wins; exceeding 10 loses.

Sum

Turn

Player A

Status

In Progress

Current Phase

Selection

Traverse using UCT.

Expansion

Create one new child.

Simulation

Roll out a random game.

Backpropagation

Update visits and wins.

Statistics

Total simulations

Tree depth

Nodes

Node Details

Click a node to see details.

Controls

Simulation speed (ms)

Exploration constant (c)

ExploitationExploration

Visualization Guide

Node Colors

Green indicates high win rate, blue is neutral, and red is low win rate.

Node Information

The number inside a node is the current sum. Text below shows win rate and total visits. Highlighted links show the current selection path.

The UCT Formula

MCTS balances moves that already look good with moves that still need exploration.

UCT = \underset{exploitation}{\frac{w_{i}}{n_{i}}} + \underset{exploration}{c \sqrt{\frac{\ln N}{n_{i}}}}

Exploitation Term

The exploitation term $\frac{w_{i}}{n_{i}}$ favors moves that have worked well in the past. Higher win rates lead to higher values.

Exploration Term

The exploration term $c \sqrt{\frac{\ln N}{n_{i}}}$ ensures all moves are tried occasionally. Increases for rarely-visited nodes and decreases with more visits.

Technical Notes

Notes carried over from the original visual, tuned for the new site.

1. Selection

Starting from the root, MCTS selects child nodes using UCT until reaching a leaf node or a node with unexpanded moves.

Exploitation prefers nodes with high win rates.
Exploration gives less-visited nodes a chance.

2. Expansion

If the selected node has unvisited moves, the tree creates one new child. This gradually builds the tree in promising directions.

3. Simulation

From the new node, a rollout plays the game to completion. This gives a fast estimate of the position value.

4. Backpropagation and UCT

Visits and wins are updated from the simulated node back to the root. $UCT = \frac{wins}{visits} + c \sqrt{\frac{\ln (parent visits)}{visits}}$ .

Implementation note

MCTS is an agentic pattern: search, simulate, score, and use feedback to allocate more compute to promising branches.