AlphaGo, AlphaZero and MuZero: Search Meets Deep Learning

In March 2016, DeepMind's AlphaGo defeated Lee Sedol, one of the world's strongest Go players, 4–1 in Seoul — a milestone many experts had expected to be at least a decade away. Go's enormous branching factor (about 250 legal moves per position) and the difficulty of evaluating positions had defeated classical game-tree search. AlphaGo and its successors combined deep learning, reinforcement learning and Monte Carlo tree search (MCTS). Their design ideas — learned intuition guiding explicit search, and self-improvement through self-play — have influenced areas far beyond games.

Why Go was hard#

• Chess engines search deep trees with hand-crafted evaluation functions. In Go, the branching factor makes deep exhaustive search impossible, and nobody could write a good evaluation function: whether a group of stones is safe depends on subtle, global patterns.
• Humans rely on intuition (which moves look promising) and judgement (who is winning). AlphaGo learned both with neural networks.

AlphaGo (2016)#

Silver et al. (Nature, 2016) trained several networks operating on the 19×19 board:

1. Supervised policy network $p_\sigma$: a 13-layer CNN trained to predict expert human moves from about 30 million positions — reaching about 57% move-prediction accuracy.
2. RL policy network $p_\rho$: initialised from $p_\sigma$ and improved by policy-gradient self-play against earlier versions of itself.
3. Value network $v_\theta$: trained by regression to predict the game's winner from positions sampled from self-play games (one position per game to avoid overfitting correlated positions).
4. Fast rollout policy: a small, quick policy for simulating games to the end.

During play, MCTS used the policy network to prioritise promising moves and combined the value network with rollout outcomes to evaluate leaf positions. The famous move 37 in game 2 — a move human experts initially considered a mistake — showed the system finding strategies outside human convention.

AlphaGo Zero (2017): no human data#

AlphaGo Zero learned tabula rasa — from random play, knowing only the rules:

• A single residual network with two heads: a policy $\mathbf{p}$ and a value $v$, $(\mathbf{p}, v) = f_\theta(s)$.
• No rollouts: leaf evaluation used the value head only.
• Self-play with MCTS as a policy-improvement operator: at each move, MCTS guided by the current network produces visit counts $\boldsymbol{\pi}$ — a stronger policy than the raw network. The network is then trained to match those search probabilities and to predict the game outcome $z$:

This loop — search improves the policy, the network learns from search, better networks make search stronger — is a form of policy iteration with MCTS as the improvement step. After about three days of training, AlphaGo Zero defeated the version that beat Lee Sedol by 100 games to 0.

The search: PUCT#

MCTS selects actions within the tree by

balancing the estimated value $Q$ with an exploration bonus weighted by the network's prior $P$. (See the MCTS lecture in the Foundations track.) Dirichlet noise at the root encourages exploration during self-play.

import math

def puct_select(children, c_puct=1.5):
    """children: dict action -> {'N': visits, 'W': total value, 'P': prior}."""
    total = sum(ch["N"] for ch in children.values())
    def score(ch):
        q = ch["W"] / ch["N"] if ch["N"] else 0.0
        return q + c_puct * ch["P"] * math.sqrt(total + 1e-8) / (1 + ch["N"])
    return max(children, key=lambda a: score(children[a]))

print(puct_select({"a": {"N": 10, "W": 6.0, "P": 0.5}, "b": {"N": 1, "W": 0.2, "P": 0.3},
                   "c": {"N": 0, "W": 0.0, "P": 0.2}}))

AlphaZero (2018): one algorithm, three games#

The same algorithm, with minimal game-specific changes, learned chess, shogi and Go from scratch and defeated the strongest existing programs in each (Stockfish in chess, Elmo in shogi, AlphaGo Zero in Go) in the published matches. Its chess style — dynamic piece sacrifices, long-term positional play — attracted wide interest from grandmasters.

MuZero (2020): learning the rules too#

MuZero removed the need for a known simulator. It learns three functions: a representation mapping observations to a latent state, a dynamics function predicting the next latent state and reward, and a prediction function giving policy and value. MCTS runs entirely in the learned latent space. MuZero matched AlphaZero in board games and achieved strong results on Atari — bridging model-based planning and model-free learning.

Beyond games#

The AlphaZero/MuZero recipe has been applied to discovering faster matrix-multiplication algorithms (AlphaTensor), faster sorting routines adopted into a standard C++ library (AlphaDev), video-compression rate control, and chip floor-planning research. Its central lesson — combine learned intuition with explicit search, and let the system improve by playing against itself — also informs current work on reasoning in language models, where sampling and search at test time improve results.