AlphaGo and Monte Carlo Tree Search

In one line: this page explains how AlphaGo cracked Go, the game that "cannot be searched" — the four-step structure of MCTS, the UCB1 formula, how policy and value networks "trade learning for compute," and the path by which AlphaZero and MuZero pushed "search × learning" to its limit. It is the second of the "big three of deep RL" in A Brief History of RL and the best entry point to Model-Based RL.

1. Why Go "Cannot Be Searched"

1. Two Numbers

First, the orders-of-magnitude gap between chess and Go:

Dimension	Chess	Go
Board	8×8 = 64 squares	19×19 = 361 points
Average branching factor (legal moves per turn)	~35	~250
State space (reachable positions)	~10^43	~10^170
Game length	~80 moves	~200+ moves
Rough total search-tree size	35^80 ≈ 10^123	250^200 ≈ 10^478

Two conclusions:

• Brute force is out: 10^170 dwarfs the number of atoms in the universe (~10^80), so "evaluate every position" is physically impossible.
• The killer app of classical game search is neutralized: Deep Blue's chess relied on an efficient static evaluation function + deep α-β pruning search. Go's evaluation function is notoriously hard to write — there is no reliable local criterion for "who is ahead in this corner"; and α-β pruning depends on board structure where "at least one move quickly decides the game," whereas Go positions must be judged globally and fuzzily.

After Deep Blue defeated Kasparov in 1997, Go was widely named "the next AI milestone," with the mainstream view being "another 10 years." AlphaGo got there in 2016 not through stronger brute-force search, but by using neural networks to point the search in the right direction — the very theme of this page.

2. A Palpable Difficulty: Ko and the Whole Board

Go's difficulty also shows in "locally correct ≠ globally correct": an exchange that looks like a local loss can buy global initiative; a ko fight involves counting ko threats across the whole board. Search must see very deep global consequences, while an evaluation function cannot give reliable scores for intermediate positions — which jams both the "evaluation" and the "search" links of the chain at once.

2. Classical MCTS: The Four-Step Structure and UCB1

1. The Four Steps of Monte Carlo Tree Search

Before AlphaGo, the strongest Go programs (around 2015) were built on MCTS (Monte Carlo Tree Search). The idea is to "use random simulation as the evaluation function": instead of writing a static evaluation function, play out from the current position to the end at random and use the win/loss result as the evaluation. Each iteration has four steps:

              Selection            Expansion            Simulation           Backpropagation
  ┌────────┐  walk down the tree  add a new child     play out at random    pass the result back
  │  root  │ ──► to the most      at the leaf ───────► from the new node ──► along the path,
  │  node  │    promising child   (one legal move)    to game end (rollout) updating each node's
  └────────┘    (UCB1 policy)                          → win/loss z         mean and visit count

• Selection: starting at the root, use the UCB1 formula at each level to pick the child "worth exploring," and walk down to a leaf.
• Expansion: add one legal move at the leaf as a new child node.
• Simulation: from the new child, use a fast random rollout policy to play to the end, yielding a win/loss z ∈ {+1, −1}.
• Backpropagation: propagate z back along the visited path, updating each visited node's average win rate and visit count.

2. UCB1: Optimism in the Face of Uncertainty

The core of the selection step is UCB1 (Auer et al., 2002) — the tree version of the multi-armed bandit principle "optimism in the face of uncertainty" (usually called UCT, Upper Confidence bounds applied to Trees, Kocsis & Szepesvári, 2006):

UCB1(s, a) = Q(s, a) + c · √( ln N(s) / N(s, a) )

Q(s,a)  = mean return (win rate) after playing move a at node s
N(s)    = total visit count of parent node s
N(s,a)  = visit count of child node (s,a)
c       = exploration constant (AlphaGo used c≈5)

The intuition: the first term is exploitation (pick high win rates), the second is exploration (children with few visits get a large UCB value). When N(s,a) is small, the second term dominates and encourages "try the roads less traveled"; as visits accumulate, that term decays and selection converges to high-win-rate moves. Conceptually, UCB1 belongs entirely to the Exploration and Exploitation framework; its mathematical link to multi-armed bandits is on the Multi-Armed Bandits page.

3. Before 2015: The Struggle of Go Programs

Before AlphaGo, the skill ceiling of Go programs had a clear coordinate system:

Year	Program / event	Level
1997	Deep Blue defeats Kasparov	Go AI was nowhere near even amateur level
From 2008	MCTS-based programs such as Zen and Fuego	Roughly amateur 1–3 dan
2015–2016	Zen, Crazy Stone	Could barely beat a professional (9-dan Norimoto Yoda) with a four-stone handicap
March 2016	AlphaGo's first official match	Beat world champion Lee Sedol 4:1 at even games

A "four-stone handicap" means the professional starts with four stones already on the board — almost locking up the result. From "not even solid with four stones" to "beating the world champion at even games," AlphaGo raised Go AI by a full dan-class gap — a chasm that brute-force MCTS alone could never cross. Only "search × learning" could do it.

WARNING

The bottleneck of classical MCTS is the simulation step: a random rollout must play a full game (hundreds of moves) to the end, the evaluation noise is enormous, and random play completely ignores the local life-and-death of Go. The strongest pre-AlphaGo programs reached only about amateur 3–5 dan — nowhere near professional level. To make MCTS strong, you have to give its "selection" and "simulation" a brain.

3. AlphaGo: Trading Learning for Compute

AlphaGo (Silver et al., 2016, Nature) injected "learning" into two links of MCTS: a policy network tells selection "where to think," and a value network replaces the random rollout in the simulation step. It is trained in four steps.

1. The Three-Stage Training Pipeline

Stage 1  SL policy net p_σ     Stage 2  RL policy net p_ρ    Stage 3  value net v_θ
┌───────────────────────┐    ┌───────────────────────┐    ┌───────────────────────┐
│ Supervised learning:  │    │ Policy-gradient RL:   │    │ Win-rate regression:  │
│ input = 19×19×48      │    │ initialize from the   │    │ 30M positions from    │
│ feature planes        │──► │ SL net, play against  │──► │ RL-net self-play,     │
│ output = 361 move     │    │ itself / past         │    │ regress position →    │
│ probabilities         │    │ versions, fine-tune   │    │ win rate (replaces    │
│ data = ~30M KGS       │    │ with RL (~80% win     │    │ rollout)              │
│ positions (human      │    │ rate vs SL net)       │    │                       │
│ games)                │    │                       │    │                       │
└───────────────────────┘    └───────────────────────┘    └───────────────────────┘

Network	What it learns	Data	Role
SL policy net p_σ	P(move | position), a 13-layer CNN with ~28M parameters	~30M positions from human KGS games	Prior for MCTS selection, imitating human "intuition"
Fast rollout policy p_π	A minimal linear + feature policy, ~240K parameters, 1000× faster	Human games + pattern library	Generates positions during training; assists simulation
RL policy net p_ρ	Starting from p_σ, strengthened by policy gradients and self-play	Self-play (including a pool of past versions)	Trains the value network; the main prior of the final system
Value net v_θ	V(position) ≈ probability of winning from that position	30M positions from RL-net self-play	Replaces random rollout, giving search a "good evaluation"

TIP

None of AlphaGo's networks was invented from scratch: the SL network is plain supervised learning (on human games); the RL network is a direct application of Policy Gradient Methods; the value network regresses exactly the state value V from Value Learning. AlphaGo's real innovation was how to wire these networks into the search — not the networks themselves.

2. Search at Inference Time: PUCT

At inference time, each MCTS simulation in AlphaGo does three things:

1. Selection: instead of plain UCB1, use PUCT, guided by policy-network priors:

a* = argmax_a [ Q(s,a) + c · P(s,a) · √N(s)/(1+N(s,a)) ]

P(s,a) = prior probability from the policy network
(the policy network tells the search: "human/learned intuition says these points are worth considering")

2. Expansion: feed the leaf position to the policy network, obtain 361 move priors, and create new child nodes.
3. Evaluation: once a leaf is reached, instead of a random rollout to the end, score it directly with the value network and blend that with the rollout result:

V_mix = (1 − λ)·v_θ(s) + λ·z_rollout      (λ≈0.5 in the AlphaGo paper)

Why blend? The value network is fast but may carry systematic bias; the rollout is slow but unbiased (playing to the end is ground truth). The two complement each other, which is especially useful early in training. After many simulations, the search converges to a "prior-weighted majority vote" that produces the final move.

3. The Compute Ledger: What Learning Actually Saves

Link	Pure search (the Deep Blue way)	The AlphaGo way
Evaluation function	Hand-written, nearly impossible to cover Go	The value network learns from data and generalizes to unseen positions
Simulation depth	Every line played to the end — expensive	One value-network call per position — simulation becomes fast
Search width	Relies on pruning and raw compute	Policy-network priors focus attention on a handful of candidates
Essence	Trading compute for depth	Trading learning for compute: "knowing how to play" is compiled into network weights

In March 2016, AlphaGo defeated world champion Lee Sedol 4:1 in a five-game match in Seoul. In May 2017, AlphaGo Master swept Ke Jie 3:0 in Wuzhen. The two generations used different amounts of distributed compute, but the methodology was the same line.

4. Input Representation: 48 Feature Planes

A Go board has 19×19 = 361 points, and every AlphaGo network takes 48 feature planes of 19×19 as input, encoding a "position" as a tensor the network can consume. The features fall into roughly seven categories:

Feature group	Contents	Purpose
Stone color	Binary planes for black / white / empty points	Basic board state
Liberties	Liberty count of each string (1–4 and 4+)	Key to life-and-death and capturing races
Ko	Markers of ko locations	Rule-related
Legal moves	Whether a point is currently playable	Prevents illegal outputs
History	Snapshots of the last 8 positions	Captures dynamics and rules (ko, self-atari)
Constant planes	All-0 / all-1 planes, the side to move	Tells the network "whose turn it is"

Why this matters: the 48 feature planes are "the minimal encoding of Go domain knowledge" — they tell the network nothing about strategy, only the rules and history it needs to "read the board." The SL policy network learns human intuition from these 48 planes; the value network learns win-rate regression from the same representation. This "representation engineering" idea applies to any domain: feed in the information the rules require, and leave strategy to learning.

5. Distributed Compute Configurations

AlphaGo comes in two versions with very different compute configurations:

Version	Compute	Training	Result
Distributed AlphaGo (2016)	~1202 CPUs + 176 GPUs	Multi-machine parallel MCTS	Beat Lee Sedol
AlphaGo Zero (2017)	64 TPUs for self-play + 4 TPUs for training	~4.9M self-play games (72 hours)	Beat AlphaGo Master (the Ke Jie version)
AlphaZero (late 2017)	Same architecture as Zero, multiple games	Surpassed Zero on Go with ~700K games (~9 hours)	Beat Stockfish / Elmo

Note the punchline: Zero surpassed AlphaGo — trained on human games plus 30M positions — using less training data (700K games). It demonstrates the bootstrapping power of "search × learning" once again: high-quality games produced by search express the laws of play more "purely" than the entire corpus of human history.

4. AlphaZero: Removing Human Games

AlphaGo still relied on human games for SL pre-training. AlphaZero (Silver et al., 2017) proved this dependency can be removed:

AlphaZero's single network (f_θ: position → (move probabilities p, value v))

Self-play loop:
  the current network plays against itself (MCTS + itself for every move)
  ──► collect positions (s, search probabilities π_t, final outcome z)
  ──► objective: policy p_θ approaches π_t (supervised on self-play results)
  ──►            value v_θ approaches z
  ──► update θ, repeat

Key points:

• No human games and no knowledge beyond the rules — only the rules and the win/loss outcome.
• The policy objective is not "imitate humans" but imitate the results of its own search — search teaches the network, the network speeds up search, and the two spiral upward together. This is the purest form of the "search × learning" loop.
• A single network outputs both policy and value, sharing the feature-extraction layers.
• With identical code and hyperparameters, AlphaZero learned chess, shogi, and Go, beating the top programs of the day — Stockfish and Elmo — within 24 hours. On Go, about 9 hours / 700K self-play games sufficed to surpass all previous versions.

4. The AlphaZero Training Loop: Minimal Pseudocode

# AlphaZero training loop (pseudocode)
net = init_network()                      # single network: position → (policy p, value v)
replay = ReplayBuffer(capacity=500_000)  # self-play position cache
best = net                               # opponent is the "best-so-far" version (maintains diversity)

for iteration in range(2000):
    # self-play: generate games with the current net + MCTS
    for game in range(parallel_games):
        state = env.reset()
        while not env.done(state):
            π = MCTS_search(state, net)      # action distribution from net-guided search
            state, z = env.step(π)          # sample a move from π
            replay.add(state, π)            # store (position, search distribution)
    # training: supervise the net with (position → search dist π, outcome z)
    for _ in range(train_steps):
        s, π_target, z = replay.sample(128)
        p, v = net(s)
        loss = CE_loss(p, π_target) + (v - z) ** 2   # joint policy + value loss
        gradient_update(net, loss)
    # periodically pit "latest net vs historical best"; the winner becomes the new best
    if evaluate(net, best) > 0.55:
        best = net

Three details that are easy to skim past:

1. The search distribution π is a "soft label": the network learns "what MCTS search thinks the move should be," not the game outcome itself. This keeps learning tightly glued to search.
2. The opponent is the historical best, not the latest net: the newest net tends to "fossilize" (it only plays one style against itself); playing past versions preserves exploratory diversity — one of AlphaZero's key improvements over AlphaGo Zero.
3. Joint loss: policy cross-entropy and value MSE backpropagate together, sharing the feature-extraction layers — the engineering implementation of "one network doing two jobs."

INFO

AlphaGo Zero (October 2017, Nature) first proved "starting from scratch" on the 19×19 board; AlphaZero (December 2017, arXiv) generalized it across games. The difference: Zero used random opening moves to boost diversity, while AlphaZero uses a pool of past versions as opponents (consistent with AlphaGo's RL network). This page refers to both collectively as "the AlphaZero family."

5. MuZero: Learning the Environment Too

AlphaZero assumes "the rules are fully known" (transitions and rewards are deterministic and free). MuZero (Schrittwieser et al., 2020, Nature) removes even that assumption:

AlphaZero:  real environment (rules) → search → act
MuZero:     learned latent state s_t ──► dynamics model g(s,a)→s' ──► prediction f→(p,v)
            search inside the "learned world model", never touching the real environment

• MuZero learns only "dynamics" (the next latent state) and "prediction" (policy and value) in latent space, and runs MCTS inside the learned world model.
• With the same method it plays Atari, Go, chess, and shogi — reaching SOTA on Atari at the time and AlphaZero-level play on Go.
• Its significance is extending "search × learning" to tasks where the environment is unknown: as long as you can learn a good enough model from data, you can search inside that model. This is exactly the theme of the Model-Based RL page, and the source of robotics' and autonomous driving's interest in MuZero.

2. MuZero's Engineering Details and Later Variants

MuZero's engineering has a few details worth a close look:

Component	What it learns	Why it's needed
Representation function h(s_t)	Real observation → latent state	Latent space is more predictable than raw observations
Dynamics function g(s, a)	Latent state → next latent state + immediate reward	The learned "rules"
Prediction function f(s)	Latent state → (policy p, value v)	Priors and evaluation for MCTS
MCTS runs in latent space	Expand with g, evaluate with f	Never touches the real environment

Key design: MuZero's reward is also learned in latent space (g outputs an immediate-reward prediction) and accumulated inside MCTS — so it does not even need to know the reward function, only the final score signal (such as the game score). This makes it applicable where "the rules are unknown."

Later variants (the frontier thread):

• Sample-Efficient MuZero: reaches the same level with far fewer interactions — data efficiency first;
• MuZero Unplugged: extends MuZero to purely offline data (offline RL meets search);
• Simplified AlphaZero-style variants (e.g. EfficientZero): add a self-supervised consistency loss to further cut training requirements.

Together these works point to one conclusion: "learn the environment, then search in it" is among the most promising routes to break the data-efficiency bottleneck in the 2020s. For the latest progress, see the Frontier Papers page.

6. The General Principles of "Search × Learning"

Abstracting from the AlphaGo family, we get three transferable principles of complementarity:

Principle	How it shows up	Engineering implication
Learning speeds up search	Policy priors focus search on a few candidates; the value network replaces expensive simulation	For any decision problem with "expensive evaluation / many candidates," learn a guide first
Search corrects learning	The distribution of search winners is used as the training target (AlphaZero's π_t)	The learner need not imitate humans — it can imitate "a stronger version of itself"
A perfect model is an amplifier	With exact rules and cheap simulation, search has almost no ceiling	Where a simulator exists, the ceiling of RL + search is far above pure learning

The boundaries of applicability are equally clear:

• It requires an exact, replayable model (rules, a simulator). In most real-world RL tasks the model has error, and imagination bias amplifies mistakes (see the "model error trap" in Model-Based RL).
• It requires enumerable actions. AlphaGo's actions are simply the 361 intersections; continuous action spaces (robot joints, steering angles) have no natural "branches on a tree," so MCTS needs extra machinery for continuous action.

WARNING

Don't let AlphaGo's "miracle" mislead you into "RL has solved decision-making." Its success rested on three privileged conditions: a perfect model of the rules, a millisecond-level simulator, and an extremely dense win/loss signal. The real world (robotics, trading, medicine) often has none of the three. To feel the gap, compare Robotics Control and Sim2Real with RL in Financial Trading.

7. Using MCTS on Your Own Task: An Engineering Decision Checklist

If you want to apply "search × learning" to your own problem (scheduling, game AI, planning), this decision checklist helps you judge whether it's worth it:

Decision point	Check	If the answer is "yes"
Model	Are the rules / simulator exact and resettable?	Only then does searching "in the tree" make sense
Actions	Are actions enumerable (discrete or discretizable)?	Otherwise MCTS needs a continuous-action extension
Simulation	Is the cost of evaluating one action manageable?	If too expensive, learn a value network to replace simulation
Prior	Do you already have a signal for "which move is more likely good"?	If so, train a policy network as the prior
Data	Can you mass-produce self-play / simulation samples?	If not, "search × learning" runs out of fuel

The two most common failure modes:

1. Forcing MCTS onto non-enumerable actions: tree search on continuous control must handle infinitely many branches, and AlphaGo's UCB formula simply breaks — one reason robotics and autonomous driving rarely use MCTS (see Robotics Control and Sim2Real).
2. Model error amplified by search: for search to "look 1000 moves ahead," every transition must be correct; with even slight model bias, the deeper the search, the worse the nonsense — the MCTS form of the "imagination bias" trap on the Model-Based RL page.

Three Sentences for Engineers

• Exact simulator + discrete actions + a well-defined win/loss makes MCTS × learning an unbeatable combo (games, mathematical proofs, formal planning).
• When the model is inaccurate, search depth is a liability, not an asset — better a short-sighted learned policy than a deep search through hallucinated futures.
• Where the UCB1 prior comes from decides the ceiling: AlphaGo used a policy network; industrial scheduling can use any scorer. The key is that "the prior must be clearly better than uniform random."

8. Lessons and Limits

1. Lessons

• Representation engineering beats brute compute: AlphaGo invented no new search algorithm; it packed "knowledge" into the network's priors and evaluations, turning an existing search algorithm from "playing blind" into "searching with intuition." When AlphaProof and AlphaGeometry solved mathematical problems with a "symbolic engine + RL" in 2024, it was the same paradigm extended (see RL in Science and Biomedicine).
• Self-play is a data engine: AlphaZero proved that self-play without human data can produce knowledge beyond humans. This is RL's most distinctive advantage over supervised learning — interaction generates data.
• Evaluation "creates" knowledge: the value network compresses a target that cannot be computed directly (the final outcome) into a differentiable function — the general engine of deep RL.

2. Limits

• It does not transfer directly to imperfect-information games: AlphaGo assumes both sides see everything. Poker and hidden-information games need different methods (the CFR family), which also explains the difficulty of "non-stationarity" on the Multi-Agent RL page.
• It solves one task at a time: what AlphaZero generalizes is the "framework," not "one model that plays every game" (MuZero is still trained and tested on a single game).
• The learning cost is high: the distributed AlphaGo system used thousands of CPUs and GPUs; AlphaGo Zero used 64 TPUs for self-play. Reproduction is prohibitively expensive for ordinary teams.

Further Reading

• Model-Based RL and World Models — MuZero, Dreamer, and TD-MPC push "learning the environment" further, including the model-error trap.
• Value Learning: From Dynamic Programming to DQN — the full mechanical foundation of the value network v_θ and Q-learning.
• Policy Gradient Methods — how the RL policy network p_ρ is trained.
• Core Paper Reading — a close, section-by-section reading of Silver's AlphaGo papers, with "how to answer in an interview."
• A Brief History of RL — AlphaGo's coordinates in the deep RL explosion around 2016.
• Exploration and Exploitation — the optimism principle behind UCB1 and its evolution in deep RL.
• RL in Science and Biomedicine — how AlphaGeometry and AlphaProof inherit "search × learning" for mathematical reasoning.

References

• Silver, D., et al. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587), 484–489.
• Silver, D., et al. (2017). Mastering the game of Go without human knowledge. Nature, 550(7676), 354–359.
• Silver, D., et al. (2018). Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. arXiv:1712.01815. (AlphaZero)
• Schrittwieser, J., et al. (2020). Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model. Nature, 588(7839), 604–609. (MuZero; arXiv:1911.08265)
• Kocsis, L., & Szepesvári, C. (2006). Bandit Based Monte-Carlo Planning. ECML 2006. (UCT)
• Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, 47, 235–256. (UCB1)
• Browne, C., et al. (2012). A Survey of Monte Carlo Tree Search Methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1), 1–43.
• Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. (For MCTS and self-play, see Chapter 16 and related chapters.)