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 see who wins.

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.

$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 (usually set to $\sqrt{2}$).

Breaking Down the Formula

1. Exploitation Term: $\frac{t_i}{n_i}$ This is the average reward of choosing the node. 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 a bonus for unvisited nodes.

• Because $n_i$ (visits to the specific child) is in the denominator, nodes that haven't been visited often get a massive score boost, forcing the algorithm to explore them.
• Because $\ln(N)$ (total parent visits) is in the numerator, the pressure to explore slowly increases over time as the parent is visited more frequently.

If a node has never been visited ($n_i = 0$), its UCB1 value is considered infinite, guaranteeing that MCTS will expand unexplored nodes before heavily exploiting successful ones.

---

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$. A snapshot of the statistics is:

• 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$):

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

Since $UCB1(S_1) > UCB1(S_2)$, we select and traverse to $S_1$.

2. Expansion (at $S_1$)

• Because $S_1$ has already been visited ($n_1 = 1 > 0$) and is a leaf, we must expand it.
• Rule: The branching factor increases by 1 for each level of depth. Since depth 0 has 2 options, depth 1 has $2 + 1 = 3$ options.
• 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 (always prefer the right node), we choose the rightmost child: $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$

The tree state after Rollout 1:

---

Step 2: Rollout 2 (Playout Outcome = 20)

1. Selection (at Root $S_0$)

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

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

Since $UCB1(S_1) > UCB1(S_2)$, we traverse to $S_1$.

2. Selection (at $S_1$)

Since $S_1$ is not a leaf node, we evaluate UCB1 for its children ($N = n_1 = 2$):

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

$S_3$ and $S_4$ are tied with infinite UCB1. We break the tie by preferring the right node (between left $S_3$ and middle $S_4$, the right one is $S_4$). We traverse to $S_4$.

3. Rollout & Backpropagation

• A random playout from $S_4$ yields outcome 20.
• We backpropagate the reward of 20 up the path $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$

The final tree state after Rollout 2: