Study guide · Robotics & reinforcement learning · 2016

Mastering the game of Go with deep neural networks and tree search

David Silver et al. · Nature

Go was the board game computers could not crack: too many possible moves to search and no good way to tell who is winning. AlphaGo trained one network to suggest promising moves and another to judge positions, and used them to steer a tree search. It beat the European champion Fan Hui 5–0 in October 2015, the first time a program beat a professional on a full board without handicap, a feat many expected to be at least a decade away.

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.

Number of move sequences in a full search, breadthdepth, shown as a power of ten. Chess and Go use the paper's figures (b ≈ 35, d ≈ 80; b ≈ 250, d ≈ 150). The third preset is purely illustrative: 10 candidate moves and 20 turns of lookahead, the kind of narrowing a move-suggesting network and a position-judging network make possible. For scale, 1080 is a commonly quoted estimate of the atoms in the observable universe.

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.

Everyday pictureA strong player glancing at a board "just sees" the two or three moves worth thinking about. The policy network is a learned version of that glance.

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.

Monte Carlo tree search with AlphaGo's selection rule (average result + bonus ∝ prior × √total visits / (1 + visits)), uniform priors and random-play-out evaluation. Bars: visits to each first move; the label gives its average win rate for the player choosing it. With 13 sticks the right move is to take 1 (leaving 12). With few walks the counts are noisy; with a few hundred the search concentrates on the winning move. When the pile is already a multiple of 4, every move loses against perfect play.

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.

Later refinementIn March 2016 an improved AlphaGo beat Lee Sedol, one of the best players in the world, 4–1. In 2017 AlphaGo Zero removed the human data, the hand-crafted input features and the rollouts entirely: a single network with a policy head and a value head, trained only by self-play, beat the earlier versions. AlphaZero then applied the same algorithm to chess and shogi as well, and MuZero (2019) learned without even being told the rules.

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.

Follow the idea

Built on: Nature DQN (2015)

Led to: AlphaZero (2017)