Lecture 06.3: Monte Carlo Tree Search (MCTS)

While Alpha-Beta pruning is highly effective for games like Chess, it still relies on exploring an exponentially growing tree. For incredibly complex games like Go, brute-force search—even with pruning—is computationally infeasible.

Monte Carlo Tree Search (MCTS) is a best-first search algorithm that uses random simulations to make decisions in massive state spaces. It prioritizes nodes that are more likely to lead to an optimal solution, drastically reducing unnecessary exploration without needing complex domain-specific heuristic knowledge.

The Four Steps of MCTS

MCTS figures out the best move by repeating a four-step process until computation time runs out. It learns the policy of the game iteratively.

1. Selection

Starting at the root, the algorithm traverses down the tree by selecting child nodes that maximize a specific policy formula (usually UCB1). It continues until it reaches a leaf node (a node that hasn't been fully expanded yet).

2. Expansion

If the selected leaf node does not represent a terminal state (game over), the algorithm expands the tree by adding one (or more) valid child nodes corresponding to available actions.

3. Simulation (Rollout)

From the newly expanded node, the algorithm plays out a completely random game (a "rollout") all the way to a terminal state to evaluate the outcome.

4. Backpropagation

The result of the random simulation (e.g., Win = 1, Loss = 0) is backpropagated up the exact path taken during Selection. Every node on that path updates its statistics:

• $t_i$: Total value/reward of the node increases.
• $n_i$: Number of visits to the node increases by 1.

---

The UCB1 Formula: Balancing Exploration and Exploitation

During the Selection phase, MCTS must decide which node to traverse. It uses the Upper Confidence Bound applied to Trees (UCB1) formula to strike a balance between exploiting known winning paths and exploring unvisited nodes:

$\text{UCB1}(S_i) = \frac{t_i}{n_i} + C \sqrt{\frac{\ln(N)}{n_i}}$

Where:

• $t_i$: Total reward from child node $S_i$.
• $n_i$: Number of times child node $S_i$ has been visited.
• $N$: Total number of visits to the parent node.
• $C$: Exploration constant (frequently set to $\sqrt{2}$).

Breaking Down the Formula

1. Exploitation Term: $\frac{t_i}{n_i}$
   This represents the average reward of choosing node $S_i$. It guides the algorithm to prefer actions that have performed well in past simulations.

2. Exploration Term: $C \sqrt{\frac{\ln(N)}{n_i}}$
   This acts as an uncertainty bonus for less-visited nodes:

   • Because $n_i$ is in the denominator, nodes visited infrequently receive a large score boost, encouraging exploration.
   • Because $\ln(N)$ is in the numerator, the exploration pressure gradually grows as the parent node receives more visits.

[!NOTE] If a node has never been visited ($n_i = 0$), its UCB1 value is considered $\infty$, guaranteeing that MCTS evaluates unvisited children before exploiting existing high-performing branches.

---

Step-by-Step Example of MCTS

Let's walk through a concrete execution trace of MCTS, demonstrating how the tree expands and how UCB1 values are calculated.

Initial State

We start with a root node $S_0$ and two child nodes $S_1$ and $S_2$:

• Root $S_0$: visited $n_0 = 2$ times, total reward $t_0 = 43$.
• Child $S_1$: visited $n_1 = 1$ time, total reward $t_1 = 25$.
• Child $S_2$: visited $n_2 = 1$ time, total reward $t_2 = 18$.

---

Step 1: Rollout 1 (Playout Outcome = 40)

1. Selection (at Root $S_0$)

To choose between $S_1$ and $S_2$, we calculate their UCB1 scores (using exploration constant $C = 2$ and parent visits $N = n_0 = 2$):

• $\text{UCB1}(S_1) = \frac{25}{1} + 2\sqrt{\frac{\ln(2)}{1}} \approx 25 + 2(0.832) \approx 26.66$
• $\text{UCB1}(S_2) = \frac{18}{1} + 2\sqrt{\frac{\ln(2)}{1}} \approx 18 + 2(0.832) \approx 19.66$

Since $\text{UCB1}(S_1) > \text{UCB1}(S_2)$, we select and traverse to $S_1$.

2. Expansion (at $S_1$)

• Because $S_1$ has been visited ($n_1 = 1 > 0$) and is a leaf, we expand it.
• We expand $S_1$ by adding three children: $S_3$ (left), $S_4$ (middle), and $S_5$ (right). All are initialized to $t_i = 0, n_i = 0$.

3. Tie-Breaking

• Since all three children have $n_i = 0$, their UCB1 scores are infinite.
• By tie-breaking rule (prefer rightmost node), we select $S_5$.

4. Rollout & Backpropagation

• A random playout from $S_5$ yields outcome 40.
• We backpropagate the reward of 40 up the path $S_5 \rightarrow S_1 \rightarrow S_0$:
  • $t_5 \leftarrow 40, n_5 \leftarrow 1$
  • $t_1 \leftarrow 25 + 40 = 65, n_1 \leftarrow 2$
  • $t_0 \leftarrow 43 + 40 = 83, n_0 \leftarrow 3$

---

Step 2: Rollout 2 (Playout Outcome = 20)

1. Selection (at Root $S_0$)

We evaluate UCB1 with parent visits $N = n_0 = 3$:

• $\text{UCB1}(S_1) = \frac{65}{2} + 2\sqrt{\frac{\ln(3)}{2}} \approx 32.5 + 2(0.741) \approx 33.98$
• $\text{UCB1}(S_2) = \frac{18}{1} + 2\sqrt{\frac{\ln(3)}{1}} \approx 18 + 2(1.048) \approx 20.10$

Since $\text{UCB1}(S_1) > \text{UCB1}(S_2)$, we traverse to $S_1$.

2. Selection (at $S_1$)

For $S_1$'s children ($N = n_1 = 2$):

• $\text{UCB1}(S_3) = \infty$ ($n_3 = 0$)
• $\text{UCB1}(S_4) = \infty$ ($n_4 = 0$)
• $\text{UCB1}(S_5) = \frac{40}{1} + 2\sqrt{\frac{\ln(2)}{1}} \approx 40 + 2(0.832) \approx 41.66$

Breaking the tie between $S_3$ and $S_4$ by preferring the right node selects $S_4$.

3. Rollout & Backpropagation

• A random playout from $S_4$ yields outcome 20.
• Backpropagating 20 up $S_4 \rightarrow S_1 \rightarrow S_0$:
  • $t_4 \leftarrow 20, n_4 \leftarrow 1$
  • $t_1 \leftarrow 65 + 20 = 85, n_1 \leftarrow 3$
  • $t_0 \leftarrow 83 + 20 = 103, n_0 \leftarrow 4$