Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

AlphaGo & AlphaZero

When search meets learned value and policy networks.

In March 2016 a program beat Lee Sedol, one of the world's best Go players, 4–1, a milestone widely expected to be years away. Less than two years later its successor learned Go from the rules alone and beat it 100–0. Underneath is a clean idea: approximate policy iteration in which tree search improves a network, and the network guides the search.

What you’ll learn

  • Describe AlphaGo's pipeline: supervised and self-play policy networks, a value network, a rollout policy, and how MCTS combined them.
  • Write AlphaGo Zero's self-play loop and loss, and interpret it as approximate policy iteration with MCTS as the policy-improvement operator.
  • Derive the regularized-policy-optimization view of AlphaZero's visit distribution (Grill et al., 2020).
  • Read the results quantitatively, converting match scores to Elo, and say what these systems do and do not show.

AlphaGo (2016): four networks and a search

AlphaGo (Silver et al., 2016) trained four models, all but the last of them deep convolutional networks over the board:

  • an SL policy network pσ(a∣s)p_\sigma(a\mid s), 13 layers, trained by supervised learning on 30 million positions from expert games on the KGS server to predict the expert's move, with 57% accuracy;
  • an RL policy network pρp_\rho, initialized from pσp_\sigma and improved by policy gradients in self-play against randomly chosen earlier versions; it won more than 80% of its games against pσp_\sigma;
  • a value network vθ(s)v_\theta(s), trained by regression on the outcomes of self-play games of pρp_\rho, using one position per game, from 30 million games, because positions within a game are strongly correlated and led to overfitting;
  • a rollout policy pπp_\pi, a linear softmax over local patterns: only about 24% accurate, but some thousand times faster (2 μs per move against 3 ms).
at=arg max⁡a(Q(st,a)+u(st,a)),u(s,a)∝P(s,a)1+N(s,a),V(sL)=(1−λ) vθ(sL)+λ zLa_t=\argmax_a\big(Q(s_t,a)+u(s_t,a)\big),\qquad u(s,a)\propto\frac{P(s,a)}{1+N(s,a)},\qquad V(s_L)=(1-\lambda)\,v_\theta(s_L)+\lambda\,z_L
Search in AlphaGo. The priors PP came from the SL policy network, which worked better in search than the stronger RL network, presumably because human experts consider a more diverse set of promising moves. A leaf sLs_L was valued by mixing the value network with the outcome zLz_L of one fast rollout; λ=0.5\lambda=0.5 worked best. (The paper's exact bonus also scales with the parent's visit count.)

AlphaGo beat the European champion Fan Hui 5–0 in October 2015 and Lee Sedol 4–1 in March 2016. Its distributed version used 1,202 CPUs and 176 GPUs. The ablations told a clear story: each component helped, and the value network and the rollouts were complementary, the mix beating either alone.

AlphaGo Zero (2017): learning from self-play alone

AlphaGo Zero (Silver et al., 2017) removed the human data, the rollouts and the hand-crafted input features. A single residual network fθ(s)=(p,v)f_\theta(s)=(\mathbf p,v) reads the stones of the last few positions and the side to move, and outputs move probabilities p\mathbf p and a value v∈[−1,1]v\in[-1,1]. Training alternates two phases:

text
repeat:
    # self-play: generate data with the current network
    for each game:
        at each state s:
            run MCTS from s with PUCT, guided by f_θ     # 1,600 simulations, no rollouts
            π(· | s) ∝ N(s, ·)^(1/τ)                     # visit counts → improved policy
            play a ~ π(· | s); store (s, π)
        label every stored (s, π) with the outcome z, from the view of s's player
    # training: fit the network to what the search found
    update θ by SGD on (z − v)² − πᵀ log p + c‖θ‖² over recent self-play positions

The temperature τ\tau is 1 for the first moves of each game, for diversity, and near 0 afterwards. Dirichlet noise added to the root priors keeps self-play exploring.

L(θ)=(z−vθ(s))2  −  π⊤log⁡pθ(s)  +  c ∥θ∥2\loss(\theta)=\big(z-v_\theta(s)\big)^2\;-\;\boldsymbol\pi^\top\log\mathbf p_\theta(s)\;+\;c\,\lVert\theta\rVert^2
Squared error to the game outcome for the value head, cross-entropy to the search's visit distribution for the policy head, and weight decay.

This is approximate policy iteration. Given the network's policy and value, MCTS returns a stronger policy π\boldsymbol\pi: search is a policy-improvement operator. Training p\mathbf p toward π\boldsymbol\pi distills the improvement into the network, and training vv toward self-play outcomes evaluates the improved policy. Anthony, Tian and Barber (2017) proposed the same scheme independently, under the name expert iteration.

After 3 days and 4.9 million self-play games, a 20-block version beat AlphaGo Lee 100–0. A 40-block version trained for 40 days beat AlphaGo Master, which had itself won 60–0 in online games against top professionals, by 89–11. How large are those gaps?

DerivationFrom match scores to Elo
  1. E(Δ)=11+10−Δ/400E(\Delta)=\frac{1}{1+10^{-\Delta/400}}

    The Elo model predicts that a player rated Δ\Delta points higher has the expected score

  2. Δ=400log⁡10p1−p\Delta=400\log_{10}\frac{p}{1-p}

    Invert it at the observed score pp, counting wins plus half the draws per game:

  3. Δ89–11=400log⁡100.890.11≈363,Δ100–0 ≳ 400log⁡100.970.03≈600\Delta_{89\text{–}11}=400\log_{10}\tfrac{0.89}{0.11}\approx363,\qquad \Delta_{100\text{–}0}\ \gtrsim\ 400\log_{10}\tfrac{0.97}{0.03}\approx600

    For 89–11, p=0.89p=0.89. A 100–0 score has no finite estimate, but a one-sided 95% bound (p100≥0.05p^{100}\ge0.05, so p≥0.97p\ge0.97) puts the gap above about 600 points:

AlphaZero (2018): one algorithm, three games

AlphaZero (Silver et al., 2018) applied the AlphaGo Zero algorithm to chess, shogi and Go with few changes:

  • outcomes include draws, z∈{−1,0,+1}z\in\{-1,0,+1\}, and the value head predicts the expected outcome;
  • no data augmentation by board symmetries, which chess and shogi lack;
  • one network updated continually, instead of each new network having to beat the current best in an evaluation match before it generates data;
  • the same hyperparameters for all three games, except that the root's Dirichlet noise is scaled to the typical number of legal moves.

It beat the champion programs Stockfish (chess) and Elmo (shogi), and a three-day version of AlphaGo Zero (Go), while evaluating roughly a thousand times fewer positions per second than Stockfish: far fewer positions, chosen far more selectively.

Predict before you look

AlphaZero's 1,000-game chess match against Stockfish ended with 155 wins, 6 losses and 839 draws. What Elo difference does that score imply?

Show the answer

52

The score is p=(155+839/2)/1000=0.5745p=(155+839/2)/1000=0.5745, so Δ=400log⁡10(0.5745/0.4255)≈52\Delta=400\log_{10}(0.5745/0.4255)\approx52. A lopsided 155-to-6 count of decisive games is worth only about 50 Elo points because most games were drawn: at this level, draws compress rating gaps.

What the search computes

DerivationSolving the regularized problem
  1. L(y,α)=∑aqaya+λN∑aπθ(a)log⁡ya−α(∑aya−1)\mathcal L(y,\alpha)=\sum_a q_a y_a+\lambda_N\sum_a\pi_\theta(a)\log y_a-\alpha\Big(\sum_a y_a-1\Big)

    The objective is concave in yy, since −DKL(πθ∥y)=∑aπθ(a)log⁡ya+const-\KL(\pi_\theta\|y)=\sum_a\pi_\theta(a)\log y_a+\text{const}. Add a multiplier α\alpha for the constraint ∑aya=1\sum_ay_a=1:

  2. qa+λN πθ(a)ya−α=0⟹πˉ(a)=λN πθ(a)α−qaq_a+\frac{\lambda_N\,\pi_\theta(a)}{y_a}-\alpha=0\qquad\Longrightarrow\qquad \bar\pi(a)=\frac{\lambda_N\,\pi_\theta(a)}{\alpha-q_a}

    Setting the derivative in yay_a to zero gives the solution in closed form, up to one scalar:

  3. ∑aλN πθ(a)α−qa=1,α>max⁡aqa\sum_a\frac{\lambda_N\,\pi_\theta(a)}{\alpha-q_a}=1,\qquad \alpha>\max_a q_a

    Positivity forces α>max⁡aqa\alpha>\max_aq_a. On that range ∑aπˉ(a)\sum_a\bar\pi(a) falls from +∞+\infty to 00 as α\alpha grows, so exactly one α\alpha normalizes it, found by a one-dimensional search such as bisection:

  4. λN=c N∣A∣+N →  N→∞   0\lambda_N=c\,\frac{\sqrt N}{|A|+N}\ \xrightarrow[\;N\to\infty\;]{}\ 0

    Read the limits. With strong regularization, πˉ\bar\pi stays close to the prior πθ\pi_\theta; as N→∞N\to\infty, λN∼c/N→0\lambda_N\sim c/\sqrt N\to0 and πˉ\bar\pi concentrates on arg max⁡aqa\argmax_aq_a. Search moves from imitating the prior toward greedy improvement as visits accumulate, at a pace set by cc:

This view explains the visit-count targets: the policy head is trained toward a KL-regularized improvement of itself, much like the trust-region updates of policy-gradient methods (see Trust Regions: TRPO & PPO). It also suggests a fix: Grill et al. train on πˉ\bar\pi itself instead of the visit counts, which helps most when simulations are few and the counts are coarse.

Key takeaways

  • AlphaGo (2016) combined a supervised policy network as search prior, a value network trained on self-play outcomes and fast rollouts inside MCTS, and beat Lee Sedol 4–1.
  • AlphaGo Zero (2017) learned from self-play alone with one residual network: MCTS visit counts are the policy targets and game outcomes the value targets, which is approximate policy iteration with search as the improvement operator.
  • AlphaZero (2018) ran the same algorithm on chess, shogi and Go. Scores convert to Elo by Δ=400log⁡10p1−p\Delta=400\log_{10}\frac{p}{1-p}, so 89–11 is about 363 points, while 155 wins and 6 losses with 839 draws is only about 52.
  • AlphaZero's visit distribution tracks a KL-regularized policy improvement, πˉ(a)=λNπθ(a)/(α−qa)\bar\pi(a)=\lambda_N\pi_\theta(a)/(\alpha-q_a), which moves from the prior toward greedy action as simulations grow (Grill et al., 2020).
  • MuZero learns the model as well; superhuman self-play agents can still have exploitable blind spots, and no convergence theory covers the full method.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

In the original AlphaGo, which model supplied the prior probabilities P(s,a)P(s,a) used in tree search?

  1. The RL policy network, the strongest player
  2. The value network
  3. The SL policy network trained on expert games
  4. The fast rollout policy
Show the answer

C. The SL policy network trained on expert games

The SL network's broader distribution over plausible moves made a better prior for search than the sharper RL network, even though the RL network beat it head to head. The RL network's main role was to generate the self-play games that trained the value network.

Question 2

In AlphaGo Zero, what is the policy head trained to predict?

  1. The move a human expert would play
  2. The visit-count distribution produced by MCTS from that position
  3. The move with the highest value-head estimate
  4. A uniform distribution over legal moves
Show the answer

B. The visit-count distribution produced by MCTS from that position

The targets are the search probabilities π∝N1/τ\boldsymbol\pi\propto N^{1/\tau}. Because search improves on the raw network, imitating it improves the network, which then improves the next search: policy iteration with search as the improvement step.

Question 3

In the regularized-policy view of AlphaZero, what happens to the search policy πˉ\bar\pi as the number of simulations NN grows?

  1. It converges to the network prior πθ\pi_\theta
  2. It becomes uniform over legal moves
  3. It is unaffected by NN
  4. It concentrates on the actions with the highest qq, as the regularization weight λN∼c/N\lambda_N\sim c/\sqrt N vanishes
Show the answer

D. It concentrates on the actions with the highest qq, as the regularization weight λN∼c/N\lambda_N\sim c/\sqrt N vanishes

πˉ\bar\pi maximizes q⊤y−λNDKL(πθ∥y)q^\top y-\lambda_N\KL(\pi_\theta\|y). With strong regularization it stays close to the prior; as λN→0\lambda_N\to0 the value term dominates and πˉ\bar\pi concentrates on arg max⁡aqa\argmax_aq_a.

Question 4

What does MuZero add to AlphaZero?

  1. It learns a model of the dynamics in a latent space, so it can plan without being given the rules
  2. It replaces tree search with pure policy-gradient training
  3. It returns to training on human expert games
  4. It replaces the neural networks with handcrafted evaluation functions
Show the answer

A. It learns a model of the dynamics in a latent space, so it can plan without being given the rules

MuZero learns a representation, a dynamics function and a prediction function, and runs MCTS inside the learned latent space. It matched AlphaZero in Go, chess and shogi and set a new state of the art on Atari, where no simulator of the rules is given to the planner.

Further reading

  • D. Silver et al., "Mastering the game of Go with deep neural networks and tree search," Nature 529 (2016), 484–489.
  • D. Silver et al., "Mastering the game of Go without human knowledge," Nature 550 (2017), 354–359.
  • D. Silver et al., "A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play," Science 362 (2018), 1140–1144.
  • J. Schrittwieser et al., "Mastering Atari, Go, chess and shogi by planning with a learned model," Nature 588 (2020), 604–609.
  • J.-B. Grill et al., "Monte-Carlo tree search as regularized policy optimization," Proceedings of ICML (2020).