The paper in four sentences
In Go there are about 250 legal moves per turn and games last about 150 moves, so looking ahead through every possibility is hopeless, and judging a position by eye is notoriously hard.
AlphaGo first trains a "policy network" to predict expert moves from 30 million positions, then improves it by playing against earlier versions of itself, and trains a "value network" to predict the winner from any position.
During a game it runs a lookahead search that only considers moves the policy network likes, and judges where each line leads by combining the value network's opinion with quick simulated play-outs to the end of the game.
The result won 494 of 495 games against the strongest Go programs and beat a professional player 5–0.
Idea · Introduction
Why Go was so hard
Game programs traditionally search: imagine each possible move, then each reply, and so on, and pick the move whose future looks best. The number of lines to consider grows as (moves per turn) multiplied by itself once per turn of lookahead. The paper puts chess at about 35 moves per turn over about 80 turns, and Go at about 250 moves per turn over about 150 turns.
Two things make the search manageable. You can cut the breadth by only looking at sensible moves, and you can cut the depth by stopping early and estimating who is ahead. Chess programs had good hand-written estimates (count the material, check king safety). In Go, nobody could write a reliable rule for "who is winning" in the middle of the game. AlphaGo replaces both cuts with learned neural networks.
TakeawaySearch explodes as breadth to the power of depth. Go needs both cut, and neither cut could be hand-written well.
Idea · Supervised learning of policy networks
Step 1: learn to guess what an expert would play
A Go board is a 19 × 19 grid, so it can be fed to a network like a small image. AlphaGo's policy network is a 13-layer convolutional network (the same kind that recognises pictures; see AlexNet) that takes the board and outputs a probability for every point: "how likely is a strong player to play here?"
It was trained on 30 million positions from games on the KGS Go server and learned to predict the expert's actual move 57% of the time, against 44.4% for the best earlier attempts. That sounds modest, but there are around 250 legal moves to choose from, and often several good ones.
A second, much smaller rollout policy does the same job far more crudely (24.2% accuracy) but about a thousand times faster: 2 microseconds per move instead of 3 milliseconds. It is used to play quick games to the end during search.
TakeawayThe policy network narrows the search: it tells the program which few moves deserve attention.
Idea · Reinforcement learning of policy and value networks
Step 2: practise against yourself, then learn to judge
Imitating humans only gets you human habits. So a copy of the policy network then played games against randomly chosen earlier versions of itself, and was nudged towards moves from games it won and away from moves in games it lost. This reinforcement learning stage produced a policy that beat the imitation-only version in more than 80% of games, and beat Pachi, a strong open-source Go program that runs 100,000 simulated games per move, in 85% of games while doing no search at all.
Then came the piece that had been missing in Go for decades: a value network, which looks at a position and predicts the probability of winning. It was trained on 30 million positions, each taken from a different self-play game. (Taking many positions from the same game made it memorise games instead of learning to judge, because neighbouring positions in a game share the same final result.) One glance from the value network was nearly as accurate as playing out many quick games with the strong policy, at 15,000 times less computation.
TakeawaySelf-play turns an imitator into a stronger player, and its games teach a value network to judge positions, which cuts the depth of search.
Check yourself
- Why use only one position from each self-play game to train the value network?
- Positions from one game are very similar and share the same outcome, so the network can memorise the game rather than learn general judgement. One position per game removes that shortcut.
- Which network cuts the breadth of search, and which cuts the depth?
- The policy network cuts breadth (which moves to try); the value network cuts depth (stop and estimate instead of playing to the end).
Idea · Searching with policy and value networks · Fig. 3
Step 3: search, guided by intuition
At game time, AlphaGo runs Monte Carlo tree search. It repeatedly walks down a tree of possible moves from the current position. At each step it picks the move that balances two things: how well that move has done in earlier walks, and an exploration bonus that is large for moves the policy network likes and shrinks as a move gets tried more. When it reaches a position not yet in the tree, it adds it and judges it by mixing the value network's guess with the result of one fast rollout game. That result is passed back up the path, updating the averages.
After thousands of walks, it plays the move that was visited most often. Below, the same kind of search plays a tiny game: from a pile of sticks, players take 1, 2 or 3 in turn, and whoever takes the last stick wins. (The winning trick is to leave your opponent a multiple of 4.) Here every move gets an equal prior and leaves are judged only by random play-outs, so you can watch search alone find the answer.
TakeawayThe search spends its effort where the policy network points and where earlier walks found good results, and plays the move it explored most.
Idea · Evaluating the playing strength · Fig. 6
Beating a professional, and what came next
Against the strongest commercial and open-source Go programs, the single-machine version of AlphaGo won 494 of 495 games. The distributed version ran on 1,202 CPUs and 176 GPUs. In October 2015 it played Fan Hui, a professional 2 dan and European champion in 2013, 2014 and 2015, and won the formal match 5–0 (the informal faster games went 3–2). It was the first time a computer program had beaten a professional player in an even game on the full 19 × 19 board.
A striking detail: during the match AlphaGo evaluated thousands of times fewer positions than Deep Blue did against Kasparov in chess. It searched less, but much more selectively.
TakeawayLearned intuition plus selective search reached professional strength years ahead of predictions, and the next versions showed the human data was not needed at all.
Abstract, restated
Go has long been viewed as the most challenging classic game for AI because of its enormous search space and the difficulty of evaluating positions and moves. Value networks evaluate positions and policy networks select moves; they are trained by supervised learning from human expert games and reinforcement learning from self-play. Without lookahead, the networks play at the level of state-of-the-art Monte Carlo tree search programs that simulate thousands of random games. Combined with MCTS in a new search algorithm, AlphaGo achieved a 99.8% win rate against other Go programs and defeated the European Go champion 5–0, the first time a computer program defeated a human professional in the full-sized game. Nature 529, 484–489 (28 January 2016).
Section · Fig. 1 · Eqs. 1–3 · Methods
The training pipeline
SL policy network pσ. Input: a 19 × 19 × 48 stack of feature planes (stone colour, liberties, ladder status, move history and so on). Architecture: first layer 5 × 5 convolutions with k filters, then 3 × 3 layers, 13 layers in all, ending in a softmax over board points; the match version used k = 192. Trained on 30 million KGS positions (29.4 million in Methods) by stochastic gradient ascent on log-likelihood of the human move:
Test accuracy 57.0% with all features (55.7% with raw board and history only) versus a previous state of the art of 44.4%; training took about 3 weeks for 340 million steps on 50 GPUs. Small accuracy gains translated into large gains in playing strength (Fig. 2a). The rollout policy pπ is a linear softmax over fast, local pattern features: 24.2% accuracy, 2 μs per move versus 3 ms.
RL policy network pρ. Initialised to σ; plays against an opponent drawn at random from a pool of earlier iterations (to avoid overfitting to the current policy), with terminal reward zt = ±1 and REINFORCE:
10,000 minibatches of 128 games on 50 GPUs for one day. pρ wins more than 80% against pσ, and 85% against Pachi with no search (the previous best supervised network won 11% against Pachi).
Value network vθ(s) ≈ vpρ(s). Same architecture as the policy network but with a single tanh output, trained by regression to the game outcome:
Trained naively on full KGS games it overfitted (MSE 0.19 train, 0.37 test) because successive positions are strongly correlated. The fix: 30 million distinct positions, each from a separate self-play game, generated by playing U ∼ unif{1, 450} moves with pσ, one uniformly random move, then pρ to the end; MSE 0.226 train, 0.234 test. A single evaluation approaches the accuracy of Monte Carlo rollouts with pρ using 15,000 times less computation (Fig. 2b).
Section · Fig. 3 · Eqs. 4–5 · Methods: search algorithm
Asynchronous policy and value MCTS
Each edge (s, a) stores an action value Q, visit count N and prior probability P. Each simulation descends from the root choosing
a variant of PUCT, with cpuct = 5. The bonus is proportional to the prior but decays with repeated visits, so search begins by following the policy and gradually prefers moves with high value. At a new leaf sL, priors are set from pσ(a|sL) (computed asynchronously on GPU), and the leaf is evaluated by mixing
where zL is the outcome of one fast rollout with pπ. Backup: N(s, a) counts the simulations through the edge and Q(s, a) is the mean of V(sL) over them. The move played is the most visited at the root. Many CPU threads search in parallel; a virtual loss (nvl = 3) temporarily discourages threads from exploring the same line.
A surprise: the SL network pσ worked better than the stronger RL network pρ as the source of priors, presumably because humans select a diverse beam of promising moves whereas RL optimises for the single best move. The value network trained from pρ's games, however, was better than one derived from pσ.
Section · Fig. 4 · Fig. 6 · Extended Data Tables 6–8
Playing strength
| Program | Elo (Ext. Data Table 6) |
|---|---|
| AlphaGo, distributed (1,202 CPUs, 176 GPUs) | 3140 |
| AlphaGo, single machine (48 CPUs, 8 GPUs) | 2890 |
| Crazy Stone | 1929 |
| Zen | 1888 |
| Pachi | 1298 |
| Fuego | 1148 |
| GnuGo | 431 |
Single-machine AlphaGo won 494 of 495 games (99.8%) in an internal tournament against these programs. Even with four handicap stones given to the opponent it won 77%, 86% and 99% against Crazy Stone, Zen and Pachi. The distributed version won 77% against single-machine AlphaGo.
Fan Hui (Fig. 6). 5–9 October 2015, five formal games (1 hour main time plus byoyomi) won 5–0, and five informal shorter games won 3–2. Fan Hui is a professional 2 dan and won the European championship in 2013, 2014 and 2015. During the match AlphaGo evaluated thousands of times fewer positions than Deep Blue did against Kasparov, compensating with selection by the policy network and evaluation by the value network.
Check yourself
- Why does mixing value network and rollouts (λ = 0.5) beat either alone?
- They are complementary: the value network approximates the outcome of play by the strong but slow pρ, while rollouts give a noisy but exact-to-the-end result from the weak fast pπ. Their errors differ, so averaging helps.
- Why are the root's visit counts, not its Q-values, used to pick the move?
- Visits are a robust summary: a move's Q can be high by chance after few visits, but a move visited most often has been repeatedly preferred by the search after accounting for exploration.
Section · Discussion and lineage
Limitations and lineage
- Human data and features. The SL stage depends on a large corpus of expert games, and the inputs include hand-crafted Go features (liberties, ladders).
- Heterogeneous pipeline. Four separately trained components (SL, rollout, RL policy, value) with different roles; the RL policy is not even used in play.
- Compute. Training used tens of GPUs for weeks, and the strongest version ran on 1,202 CPUs and 176 GPUs.
- Opponent strength. Fan Hui was a 2-dan professional; the match against a top player came later.
Reference
Glossary
- pσ, pρ, pπ
- SL policy, RL policy and fast rollout policy.
- vθ
- Value network predicting the outcome from a position.
- MCTS
- Monte Carlo tree search: repeated simulations that grow a search tree and average results.
- PUCT
- Selection rule adding a prior-weighted exploration bonus to each move's mean value.
- Rollout
- A fast simulated game to the end, used to evaluate a leaf.
- λ
- Mixing weight between value network and rollout result.
- Virtual loss
- Temporary penalty on a line being searched by one thread, to spread threads out.
- Elo
- Rating scale where a 200-point gap corresponds to about a 76% expected score.
- Dan
- Go rank; professional ranks run from 1 to 9 dan.