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 , 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 , initialized from and improved by policy gradients in self-play against randomly chosen earlier versions; it won more than 80% of its games against ;
- a value network , trained by regression on the outcomes of self-play games of , using one position per game, from 30 million games, because positions within a game are strongly correlated and led to overfitting;
- a rollout policy , a linear softmax over local patterns: only about 24% accurate, but some thousand times faster (2 μs per move against 3 ms).
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 reads the stones of the last few positions and the side to move, and outputs move probabilities and a value . Training alternates two phases:
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 positionsThe temperature 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.
This is approximate policy iteration. Given the network's policy and value, MCTS returns a stronger policy : search is a policy-improvement operator. Training toward distills the improvement into the network, and training 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?
The Elo model predicts that a player rated points higher has the expected score
Invert it at the observed score , counting wins plus half the draws per game:
For 89–11, . A 100–0 score has no finite estimate, but a one-sided 95% bound (, so ) 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, , 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.
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 , so . 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
The objective is concave in , since . Add a multiplier for the constraint :
Setting the derivative in to zero gives the solution in closed form, up to one scalar:
Positivity forces . On that range falls from to as grows, so exactly one normalizes it, found by a one-dimensional search such as bisection:
Read the limits. With strong regularization, stays close to the prior ; as , and concentrates on . Search moves from imitating the prior toward greedy improvement as visits accumulate, at a pace set by :
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 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 , 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, , 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.
In the original AlphaGo, which model supplied the prior probabilities used in tree search?
- The RL policy network, the strongest player
- The value network
- The SL policy network trained on expert games
- 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.
In AlphaGo Zero, what is the policy head trained to predict?
- The move a human expert would play
- The visit-count distribution produced by MCTS from that position
- The move with the highest value-head estimate
- 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 . 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.
In the regularized-policy view of AlphaZero, what happens to the search policy as the number of simulations grows?
- It converges to the network prior
- It becomes uniform over legal moves
- It is unaffected by
- It concentrates on the actions with the highest , as the regularization weight vanishes
Show the answer
D. It concentrates on the actions with the highest , as the regularization weight vanishes
maximizes . With strong regularization it stays close to the prior; as the value term dominates and concentrates on .
What does MuZero add to AlphaZero?
- It learns a model of the dynamics in a latent space, so it can plan without being given the rules
- It replaces tree search with pure policy-gradient training
- It returns to training on human expert games
- 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).