AlphaGo: Search Plus Intuition

Seoul, March 2016. The program AlphaGo played five games against the 9-dan professional Lee Sedol and won four. Go has more variations than any computer can count, and the strongest programs before it played at the level of a strong amateur. AlphaGo joined two things: neural networks that judge where a move is worth playing and who is ahead, and a tree search that reads deep only along those moves. The board on the left holds the position after move 37 of game 2; on the study board at the right, a far smaller search of the same kind is really running.

Try it

Chapters · 11

01Why Go Is Hard
02Two Networks
03A Search Tree
04Choosing a Move
05Playing Itself
06Move 37
07Move 78
08From Zero
09AlphaZero and MuZero
10What Changed, What Didn’t
11The Bench

Scroll

01

Why Go Is Hard

The board has 19 × 19 = 361 points. A game runs to about 150 moves, with about 250 choices at each. Counted that way, there are some 250¹⁵⁰ possible games.

The legal positions have been counted too: about 2.08 × 10¹⁷⁰. No computer can work through them one by one.

Chess programs score a position with a hand-written formula and search many moves ahead. Deep Blue beat Kasparov that way in 1997. Go has no such formula: whether a group lives or how much a wall is worth is hard to write as rules. From 2006 programs judged positions by finishing the game with random moves instead, and improved fast, but in 2015 they still played at the level of a strong amateur.

361 points · about 250 choices a move · about 150 moves a game · about 2.08 × 10¹⁷⁰ legal positions

02

Two Networks

The policy network answers: where would a strong player move? AlphaGo’s had 13 layers, learned from 30 million positions of games played online, and guessed the human’s next move 57% of the time, against 44% for the best before it.

The value network answers: who will win from here? It looks at a position and gives one number, the chance that the side to move wins.

The study board carries the same two things, from a small network this page trained on a 7 × 7 board: the taller the brass pin on a point, the more the network leans towards playing there; the dial reads Black’s chance of winning.

Study board: the small network’s prior (pins) and value (dial), computed on the page

03

A Search Tree

Networks misjudge, so AlphaGo also reads ahead. It runs Monte Carlo tree search: again and again, it starts from the position on the board, walks down the tree, adds one new position where the tree ends, judges it, and carries the result back up the path.

On the way down, each fork takes the move with the best Q plus U. Q is the move’s average result so far; U is a bonus, larger for moves the network rates highly and the search has rarely tried, and shrinking as they are tried.

The brass tree on the study board is what this page’s search has really grown. Each branch is a move, rising from the point where it is played; the thicker the branch, the more often the search passed through it. In this position the network likes E5 best (43%) and ranks A5 only fourth (8%). For the first 18 simulations E5 has the most visits, then E6, and from the 85th on, A5.

Q + U, U = c · P · √ΣN ⁄ (1 + N) · study board: one new position per simulation

04

Choosing a Move

When the search stops, AlphaGo plays the move visited most. Many visits mean the move was tested again and again and kept holding up.

The distributed AlphaGo ran on 1,202 CPUs and 176 GPUs. Yet in its games against Fan Hui it evaluated thousands of times fewer positions than Deep Blue did against Kasparov: Deep Blue averaged about 126 million positions a second, while AlphaGo’s networks kept its search on a few moves.

On the study board, after 800 simulations A5 has 74% of the visits, and E5, the network’s favourite, 19%. The prior decides where to look first; the visits decide the move.

Study board: visits per point after 800 simulations · A5 74% · E5 19%, computed on the page

05

Playing Itself

Learning from people was only the start. AlphaGo set its policy network against earlier versions of itself, strengthening the moves that won and weakening those that lost: reinforcement learning. Afterwards the network, with no search at all, won more than 80% of its games against the one it started from.

The value network also learned from self-play: 30 million positions, each from a different game, so that it could not memorise whole games.

The study board’s small network was made the same way: from random weights, it played itself under this page’s rules and search, and each generation was trained again on the new games. After 60 generations and 12,000 games, at 128 simulations a move its search won 50 of 60 games against random-playout search; at 512 a move, 37.

The study network: self-play games, and its win rate against random-playout search, trained for this page

06

Move 37

10 March 2016, game 2. AlphaGo, playing Black, put its 37th move at P10: a shoulder hit on White 36, on the fifth line from the right edge. By AlphaGo’s own data, the chance that a human would play it was about one in ten thousand. It played it anyway.

After 211 moves, Lee Sedol resigned.

One in ten thousand says how likely a person was to play it, not how good it is. A move with a low prior is still chosen when the search shows it is good.

Game 2 · Black 37 · P10 · chance a human plays it about 1 ⁄ 10,000 (AlphaGo’s estimate)

07

Move 78

13 March 2016, game 4, with Lee Sedol as White. On move 78 he wedged into a gap in Black’s stones at L11, in the centre. By AlphaGo’s estimate, this move too had about a one in ten thousand chance of being played by a human.

AlphaGo’s move 79 was a mistake. Its value network still put its chances at around 70% at move 79, and only dived around move 87. At move 180 AlphaGo resigned: the only human win of the five.

A search reads deep only where it thinks it is worth it. A brilliant move with a very low prior can get too few visits and be missed.

Game 4 · White 78 · L11 · value around 70% at move 79, diving around move 87

08

From Zero

AlphaGo Zero, in 2017, saw no human games. It began with random moves and learned only by playing itself; one network gave both policy and value; its input was just the black and white stones; and its search no longer finished games at random.

Every search became a teacher: the policy learned to match the search’s visit shares π, the value to match the game’s final result z. The loss is (z − v)² − πᵀ log p + c‖θ‖².

After 3 days and 4.9 million games of self-play, it beat the version that had played Lee Sedol 100 games to 0.

(z − v)² − πᵀ log p + c‖θ‖² · 3 days · 4.9 million games · 100 : 0

09

AlphaZero and MuZero

AlphaZero, in 2018, learned chess, shogi and Go with one algorithm; only the rules changed. Over 1,000 games of chess against Stockfish it won 155, lost 6 and drew the rest, searching about 60,000 positions a second to Stockfish’s 60 million.

MuZero, in 2020, was not even given the rules. It learns its own model: from a state and an action, it predicts the next hidden state, the reward, the policy and the value, and runs the same tree search inside those learned states.

It matched AlphaZero at Go, chess and shogi, and set a new record on 57 Atari games.

AlphaZero (2018): chess · shogi · Go · MuZero (2020): a model it learns itself

10

What Changed, What Didn’t

Go is not solved. Nobody knows how a game on the 19 × 19 board ends when both sides play perfectly. Only small boards, such as 5 × 5, have been worked out completely.

Programs stronger than people still have blind spots. In 2023 a specially trained opponent found a weakness in KataGo, the top open-source Go program, and won more than 97% of games against it at superhuman settings. An amateur who learned the trick won 14 of 15 games against a top program.

People have changed. A study that scored 5.8 million professional moves from 1950 to 2021 with a program found that after 2016 human decisions became clearly better, and new moves more common.

19 × 19 Go is unsolved · 5 × 5 is solved

11

The Bench

The study board’s search runs for real in the background. The slider sets the number of simulations; the guide is the network (as in AlphaGo Zero) or random playouts (as before AlphaGo); the position can be changed. The readouts give each point’s visits and the search’s estimate of the chance to win.

Try thisOn the bench, switch the guide to random playouts. At the same 200 simulations, are the visits still as concentrated?

What the model leaves out

The study board is 7 × 7, scored by area (stones on the board plus empty points that touch only one colour) with a komi of 9, and only simple ko is checked. Its network is a small two-layer perceptron trained by self-play under the page’s rules (docs/plates/alphago/train.mjs), thousands of times smaller than AlphaGo Zero’s 40-block residual network, and far weaker. The tree shows every move tried at the root; past 300 simulations, deeper leaves visited only once are left out of the drawing, though the readout’s node count includes them. Random playouts never fill the player’s own eyes. The big board holds a real game record, but no network or search numbers: few of AlphaGo’s outputs from the match were ever published, among them the one in ten thousand for move 37.

Common misreadings

AlphaGo was not brute force: against Fan Hui it evaluated thousands of times fewer positions than Deep Blue had, because its networks kept the search on a few moves. Go is not solved either: nobody knows the result of perfect play, and the strongest programs still have weaknesses people have found. A win rate is an estimate by the network and the search, not a worked-out result. The one in ten thousand for move 37 is AlphaGo’s estimate of the chance that a human would play it, not a judgement of the move.

Common questions · 4

Why is Go hard for computers?: The board has 19 × 19 = 361 points. A game runs to about 150 moves, with about 250 choices at each.
01Why Go Is Hard
How does AlphaGo choose a move?: When the search stops, AlphaGo plays the move visited most. Many visits mean the move was tested again and again and kept holding up.
04Choosing a Move
What does “one in ten thousand” mean for move 37?: One in ten thousand says how likely a person was to play it, not how good it is. A move with a low prior is still chosen when the search shows it is good.
06Move 37
Has AI solved Go?: Go is not solved. Nobody knows how a game on the 19 × 19 board ends when both sides play perfectly.
10What Changed, What Didn’t

Sources

Data

The game records are AlphaGo vs Lee Sedol, games 2 and 4 (Seoul, March 2016), from Andries Brouwer’s collection at CWI, checked move for move against Go Game Guru’s records of 2016 and the diagrams in Wikipedia. The 7 × 7 study board, its rules, its search and its small network are the site’s own: src/topics/alphago/go.js, mcts.js and net.js, trained by self-play with docs/plates/alphago/train.mjs.

The text, pictures and models on this page are licensed CC BY-NC 4.0: free to use and adapt for teaching and other non-commercial purposes, with credit to world.lapla.si. Third-party material listed above keeps its own licence.