Monte Carlo Tree Search

MCTS selection, expansion & rollouts

Simple Fundamental Explanation

Imagine you are playing Chess. You want to look 10 moves ahead.

Deterministic Search (Minimax): You calculate every single possible move you can make, then every possible response your opponent can make, and so on. By move 10, there are trillions of possibilities. Your brain freezes.
Monte Carlo Tree Search (MCTS): You look at the board and think, “What are the 3 most logical moves right now?” You pick one. Instead of calculating the rest of the game perfectly, you just vividly imagine playing the rest of the game completely at random as fast as you can. You do this 1,000 times for each of the 3 moves. If Move A resulted in a random victory 700 times, and Move B resulted in a random victory 200 times, you confidently play Move A.

MCTS is a probabilistic search algorithm that combines the precision of tree search with the power of random sampling. It focuses its computational power entirely on the most promising branches of the future, completely ignoring terrible moves, allowing AI to play hyper-complex games like Go.

Deep Dive: How It Works Under the Hood

MCTS builds a search tree of possible future states. It runs a loop of four distinct phases millions of times per second.

1. Selection

Starting at the current board state (the root node), the AI navigates down the tree by picking the “best” child node at each step. It balances Exploitation (picking moves that historically win) and Exploration (picking moves it hasn’t tried much yet).

2. Expansion

Once it reaches a node that hasn’t been fully explored (a leaf node), it adds one or more new child nodes (possible next moves) to the tree.

3. Simulation (Rollout)

From this new node, the AI plays out the rest of the game to the very end using a “fast rollout policy” (often just picking moves completely at random, or using a lightweight neural network). It reaches a terminal state (Win, Loss, or Draw).

4. Backpropagation

The result of the simulation (e.g., +1 for a win, -1 for a loss) is passed back up the tree. Every node the AI visited during the Selection phase gets its “Win Score” and “Visit Count” updated.

Visual Diagram

[ Root Node: Current Board ]
Visits: 100, Wins: 60

      |-----> [ Move A ] (Visits: 80, Wins: 55)  <-- Exploitation (Looks good)
      |
      |-----> [ Move B ] (Visits: 15, Wins: 4)
      |
      |-----> [ Move C ] (Visits: 5, Wins: 1)    <-- Exploration (Needs more data)
                    |
              (Expansion)
              [ Move C1 ]
                    |
              (Simulation: AI plays randomly to the end)
              Result: LOSS (-1)
                    |
              (Backpropagation: Move C and Root Node update their stats)

Practical Example: AlphaGo

The board game Go has an average branching factor of 250 (you have 250 possible moves every turn). Chess has about 35. Because $25 0^{150}$ (the number of possible Go games) is larger than the number of atoms in the universe, traditional deterministic AI failed completely at Go for decades.

In 2016, DeepMind’s AlphaGo beat the world champion Lee Sedol using MCTS. AlphaGo enhanced standard MCTS with Deep Neural Networks:

Policy Network: Instead of expanding all 250 possible moves, it used a neural network to predict the top 5 most human-like moves, restricting the width of the tree.
Value Network: Instead of playing a random simulation all the way to the end of the game (which takes too long), it used a second neural network to look at the board state 10 moves in the future and output a probabilistic guess: “White has a 75% chance of winning from here.”

By guiding the probabilistic tree search with neural intuition, AlphaGo achieved superhuman intelligence.

The Mathematics: Equations and In-Depth Analysis

The UCT Formula (Upper Confidence Bound for Trees)

The absolute core of MCTS is the mathematical equation used during the Selection phase to balance Exploitation and Exploration. It is based on the Multi-Armed Bandit problem.

The most famous formula is UCT. For a given node, the AI selects the child node $i$ that maximizes:

U C T = \frac{W _{i}}{N _{i}} + c \frac{ln ( N )}{N _{i}}

Explanation of the terms:

Exploitation Term ( $\frac{W _{i}}{N _{i}}$ ):
- $W_{i}$ is the number of wins recorded under child $i$ .
- $N_{i}$ is the number of times child $i$ has been visited.
- This is simply the win rate (e.g., 80%). The AI naturally wants to pick nodes with high win rates.
Exploration Term ( $c \frac{l n ( N )}{N _{i}}$ ):
- $N$ is the total number of times the parent node has been visited.
- $c$ is the exploration parameter (e.g., theoretically $2$ ).
- Notice the denominator $N_{i}$ . If a child node has not been visited very often, $N_{i}$ is very small. Dividing by a small number makes the entire exploration term massive.
- This mathematically forces the AI to occasionally pick moves with terrible win rates, just in case they lead to a brilliant, hidden trap 20 moves later.

As the AI runs millions of simulations, $N$ grows, and the exploration term ensures no stone is left unturned. However, the branches that actually contain winning moves will naturally accumulate massive visit counts $N_{i}$ , causing the search tree to grow highly asymmetrical, plunging deeply into the most promising futures while completely ignoring the bad ones. This probabilistic pruning is what makes MCTS so astonishingly efficient.

Lab

Monte Carlo Tree Search on a tiny game tree: each iteration runs selection (UCT), expansion, random simulation, and backpropagation. Tune exploration c and watch Move A outrank the trap branch C→C1.

Exploration constant (c)c = 1.40

Batch iterations (preset runner)60 iterations

RNG seedseed 42

UCT at root (higher bar = higher score). Unvisited children score ∞ until expanded.

Phase: —

RootN=0 · W=0

│

Move AN=0 · W=0

Move BN=0 · W=0

Move CN=0 · W=0

└ C only →

Move C1N=0 · W=0

With c=1.40 and 0 root visits, will Move A have more visits than Move C (UCT should favor the 78% leaf over the C→C1 trap)?

UCT = W/N + c√(ln N_parent / N). Last path: root.