Monte Carlo Tree Search — Section 5: Adversarial Search

Monte Carlo Tree Search (MCTS) builds a search tree asymmetrically: it expands more in promising regions and less in unpromising ones, guided by the statistics of rollout outcomes.

The four phases

Repeated thousands of times per move:

1. Selection: starting from the root, recursively pick child nodes by a tree policy (typically UCB1) until reaching a node with unexpanded children. 2. Expansion: add one or more children of that node. 3. Simulation (rollout): from the new node, play out a random (or weakly guided) game to the end. Record the winner. 4. Backpropagation: walk back up the tree, updating each node's visit count and win count.

UCB1 selection rule

\text{UCB1}(c) = \bar{X}_c + C \sqrt{\frac{\ln N_p}{N_c}}

$\bar{X}_c$ is the average reward at child $c$ . $N_c, N_p$ are visit counts. $C$ is the exploration constant. Trades off exploitation (children with high reward) and exploration (children with low visit count). Same structure as bandit problems.

Why MCTS works for huge games

Anytime: more time = better play; stop whenever.
No evaluation function needed (in the pure version) — the simulations produce their own "evaluation."
Asymmetric tree growth: deepens in the relevant parts of the state space, ignoring irrelevant subtrees.
Scales: parallelizable; doesn't need per-state hand-engineering.

AlphaGo's PUCT variant

AlphaGo replaces random rollouts with a neural value network and replaces uniform exploration with a policy network that biases selection toward moves the policy network finds plausible:

\text{PUCT}(c) = Q(c) + C \cdot \pi(c | s) \cdot \frac{\sqrt{N_p}}{1 + N_c}

The policy network does the exploration shaping; the value network does the evaluation. This combination broke Go in 2016 and went on to dominate chess, shogi, and many other games (AlphaZero, MuZero).

When MCTS is the right tool

High branching factor where alpha-beta doesn't scale.
No strong evaluation function (or one only computable from simulation outcomes).
Anytime requirements.
General-purpose game playing (the General Game Playing competition runs on MCTS variants).

What MCTS misses

Tactical sequences with very narrow correct lines (chess engines using alpha-beta still beat pure MCTS for that reason — AlphaZero solved this with the policy network).
Continuous action spaces (without discretization).
Adversarial environments where the opponent isn't well-modeled by rollouts.