Study guide · Robotics & reinforcement learning · 2017

Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm

David Silver et al. · Science 2018

Does a game-playing program need human expertise at all? AlphaZero starts from random play, is told only the rules, and learns purely by playing against itself. Within hours of training it beat the world-champion programs in chess (Stockfish) and shogi (Elmo), and the previous AlphaGo Zero in Go, with one algorithm and one set of settings for all three games.

The paper in four sentences

AlphaZero uses one neural network that looks at a position and gives two answers: which moves look promising, and how likely it is to win from here.

To choose a move it runs a lookahead search guided by those answers; the search's final choice is usually better than the network's first instinct.

It learns only from games against itself: the network is trained to predict what its search would play and who actually won, so each round of training makes the next round of search stronger.

Starting from random play and given only the rules, the same algorithm beat the strongest chess program after 4 hours of training, the strongest shogi program in under 2, and AlphaGo Lee in 8.

Idea · Introduction

No human games, no human tricks

For decades the best chess programs were built from human knowledge: carefully hand-tuned rules for judging positions ("a bishop is worth about three pawns"), opening books of known good starts, endgame tables, and a fast search that looks at tens of millions of positions per second. Stockfish, the 2016 world computer chess champion, is the pinnacle of that approach. Elmo, a champion shogi program (shogi is Japanese chess, played on a 9 × 9 board, where captured pieces can be dropped back in), works similarly.

AlphaGo had beaten top humans at Go using neural networks, but it first learned from 30 million human positions and used Go-specific inputs. Its successor AlphaGo Zero dropped the human games. AlphaZero goes further: the same program, with no game-specific knowledge beyond the rules, for three very different games.

Everyday pictureImagine learning chess with no teacher, no books and no opponents but yourself. You know only how the pieces move and what counts as a win. Every insight you end up with, you discovered by playing yourself millions of times.

TakeawayThe question: how far can pure self-play get, with no human games, no opening books and no hand-written evaluation?

Idea · Methods: self-play

The self-improvement loop

The network gives two outputs for any position: a policy (a probability for each legal move) and a value (expected result, from −1 for a loss through 0 for a draw to +1 for a win). On its own the network is a quick instinct. A search that uses it, imagining moves and replies and asking the network to judge where they lead, makes much better decisions than the instinct alone, because it checks the instinct against what actually happens a few moves later.

That gap is what drives learning. During self-play each move is chosen by search, and the network is then trained so that its instinct (policy) matches what the search preferred, and its value matches who actually won the game. A better network makes the search better, which produces better training targets, and so on.

Below, a miniature version of exactly this loop learns the stick game from the AlphaGo guide: take 1, 2 or 3 sticks, and whoever takes the last stick wins. The "network" is just a table with a policy and a value for each pile size, starting completely uninformed.

A toy re-run of the AlphaZero recipe, not the paper's code. Each move is chosen by a small search (AlphaZero's selection rule, leaves judged by the table's own value, no random play-outs), sampled in proportion to visit counts. After each game, every visited pile's policy moves 20% of the way towards the search's visit distribution, and its value moves towards the actual result. Top: the move each pile now prefers (green = correct, red = wrong, grey = losing pile where no move wins) and the value's sign. With 8 walks it learns perfect play in a few dozen games; with 2 or 3 walks the search barely improves on the instinct and learning stalls.

TakeawaySearch turns a weak instinct into a better decision; training turns that decision into a better instinct. Repeat, and the program teaches itself.

Check yourself
Where do the training targets come from, if there are no human games?
From the program's own search (for the policy) and the final results of its own games (for the value).
Why does too little search stall learning in the toy?
If the search hardly looks ahead, its choice is no better than the network's instinct, so training just copies the instinct back to itself and nothing improves.

Idea · Methods: differences from AlphaGo Zero

One algorithm, three games

AlphaZero is essentially AlphaGo Zero made general. Go cannot be drawn, but chess and shogi can, so the value predicts the expected result rather than a probability of winning. Go looks the same if you rotate or mirror the board, and AlphaGo Zero exploited that to multiply its data; chess and shogi do not, so AlphaZero does not use that trick.

AlphaGo Zero also kept a "champion" network and only replaced it when a new version won 55% of a test match. AlphaZero simply keeps one network and updates it continuously. And it uses the same settings for all three games, except for how much random noise is added to encourage exploring different openings, which is scaled to the typical number of legal moves.

The network sees the board as a stack of simple layers (where each piece type is, plus the last few positions), and outputs a probability for every conceivable move: 4,672 move types in chess, 11,259 in shogi and 362 in Go (every point plus "pass").

TakeawayRemove everything Go-specific (symmetry tricks, no-draw assumption, per-game tuning) and the same loop works for chess and shogi too.

Idea · Fig. 1 · Table 1

Results: champions within hours

Training used 5,000 first-generation TPUs (Google's AI chips) to play self-play games and 64 second-generation TPUs to train the network. Measured on a rating scale during training, AlphaZero overtook Stockfish after 4 hours, Elmo after less than 2 hours, and AlphaGo Lee after 8 hours. Full training took 9 hours for chess, 12 for shogi and 34 for Go.

In 100-game matches at one minute per move, it did not lose a single chess game to Stockfish (28 wins, 72 draws), won 90 of 100 against Elmo, and beat the 3-day-trained AlphaGo Zero 60 to 40.

Results from AlphaZero's side. Preprint: 100-game matches at 1 minute per move against Stockfish (chess), Elmo (shogi) and the 3-day AlphaGo Zero (Go), Table 1 of arXiv:1712.01815. Science (2018): 1,000 chess games against Stockfish 8 at 3 hours per game plus 15 seconds per move, as reported in the published version.

TakeawaySelf-play alone, in hours of (massively parallel) training, produced the strongest player in all three games.

Idea · Table S4 · Fig. 2 · Discussion

Searching less, but better

The most surprising number: in chess AlphaZero looked at about 80 thousand positions per second, while Stockfish looked at about 70 million, nearly a thousand times more. In shogi it was 40 thousand against Elmo's 35 million. AlphaZero's network makes each position far more expensive to evaluate, but its judgement lets it focus the search on the lines that matter. Its strength also grew faster than its rivals' when given more thinking time.

Chess players noticed something else: with no opening book, AlphaZero independently discovered many of the best-known human openings and played them frequently during its training.

Later refinementThe 2017 preprint was criticised for its chess conditions: a fixed minute per move, a year-old Stockfish, and small hash tables. The peer-reviewed Science paper (2018) replayed the match over 1,000 games at a standard time control and still won clearly (155 wins, 6 losses, 839 draws). MuZero (2019–2020) went one step further and learned to plan without being told the rules, also mastering Atari. Open-source projects (Leela Zero for Go, Leela Chess Zero) reproduced the approach, and Stockfish itself later added a neural evaluation (NNUE).

TakeawayA thousand times fewer positions, chosen by a learned judgement, beat brute force. The published version answered the main criticisms of the preprint.

Follow the idea

Built on: AlphaGo (2016)