CS PAPERS DEEP-READ · PAPER 55

AlphaGo: Deep Networks + Tree Search Crack Go

Silver et al. · DeepMind · Nature 2016

What did this paper do?

In early 2016, a team at Google's DeepMind unveiled AlphaGo — the first program to beat a professional Go player in formal games, with no handicap, on the full 19×19 board. Go had long been seen as the last great fortress in board-game AI; many expected machines to need another decade-plus. AlphaGo moved that timetable up all at once.

Why is Go so hard?

Chess fell to "Deep Blue" back in 1997, yet Go held out for nearly twenty more years. Two reasons. First, too many choices: at each turn there are two to three hundred legal points to play, and a game runs well over a hundred moves — the number of possible games dwarfs the atoms in the universe, so a chess-style "calculate every line to the end" is simply uncomputable. Second, good and bad are hard to tell apart: whether a group lives or dies, whose territory a region becomes, is often only settled much later — so even "who is ahead right now" is hard to quantify. No way to enumerate, no way to score: the classic methods stall.

The idea: two kinds of "feel" plus a bit of lookahead

Instead of enumerating, AlphaGo does what human masters do: use feel to narrow the choices, then read a few moves ahead. It trained two neural networks (both treating the board as an image). One is an "intuition network" — one glance at the board and it points out "only these few moves are worth considering," cutting two hundred-plus options down to a handful. The other is a "big-picture network" — one glance and it estimates "who's likely to win this game," without having to play it out to the end. With these two, the machine reads a limited number of moves ahead on only the promising options, and can still judge well.

How did it learn this feel?

In three stages, much like a person going from beginner to master. Step one, learn intuition from game records: feed in tens of millions of expert human moves so the "intuition network" learns "if a strong human were here, where would they most likely play." Step two, play itself: have it play thousands upon thousands of games against itself, encouraging the moves that won and using less the ones that lost — so it stops merely imitating humans and gets stronger from its own experience. Step three, train the big picture: use the win/loss outcomes of that self-play to teach the "big-picture network" to size up a position at a glance. Three steps in, the machine has both instinct and judgment.

What did it lead to?

AlphaGo first swept European champion Fan Hui 5–0 in October 2015, then beat top-tier world player Lee Sedol 4–1 in March 2016 — a landmark moment in AI history. More lasting is the recipe it proved: let neural networks supply "intuition and judgment," pair them with a selective search, and you can crack problems humans assumed required "inspiration." Its descendant AlphaGo Zero skipped human game records entirely, learned purely from self-play, and became stronger; later AlphaZero used the same recipe to master chess, shogi, and Go alike.

One honest note on cost: AlphaGo's win was not "cheap" — it drew on a huge amount of compute, over a thousand CPUs and hundreds of GPUs, and leaned on tens of millions of human games as a crutch first (that the later version needed no records and was stronger only shows the crutch wasn't essential).

Remember one thing

Go is hard because there are "too many choices, and no way to score a position." AlphaGo uses an "intuition network" to cut away most bad moves and a "big-picture network" to avoid reading to the end, paired with a selective lookahead — first learning from human records, then getting stronger through self-play. It was the first to beat a professional in full-board play, and it lit up the general path of "neural networks + search."

Want how the policy/value networks steer the search, the training pipeline, and the numbers? → switch to the deep read

In one sentence

AlphaGo uses two deep convolutional networks — a policy network ("which moves to consider") and a value network ("who wins this position") — to guide Monte Carlo Tree Search (MCTS). In Go, whose search space is roughly 250¹⁵⁰ and which resists any hand-built position score, it presses down the twin problems of "choice explosion" and "no way to evaluate" at once, and became the first program to beat a professional in full-board play with no handicap (5–0 over European champion Fan Hui, 2015) — a landmark for the deep-learning-plus-search paradigm.

Glossary

Go: two players alternate placing black and white stones on a 19×19 board (361 intersections), enclosing territory to win. Many legal moves, and outcomes often only clear far into the game — the acknowledged hardest perfect-information board game.
Game tree / exhaustive search: expand all branches of "I play here, you reply there…" into a tree; in principle, calculate to the end and you find the optimal move. But the branch count = (choices per move, breadth b) to the power of (depth d), about 250¹⁵⁰ for Go — impossible to enumerate.
Evaluation function: a function that scores a mid-game position ("who's ahead") so search need not reach the end. Easy to write for chess, extremely hard for Go.
Monte Carlo Tree Search (MCTS): the pre-AlphaGo state of the art — instead of enumerating, it "plays out to the end" randomly from the current position many times, using the win/loss statistics of those simulations to judge each move: try good moves more, bad ones less.
Convolutional network (CNN): a neural network good at images. AlphaGo treats the 19×19 board as a "picture" and extracts stone-pattern features layer by layer.
Supervised vs reinforcement learning: the former learns from "correct answers" (human moves); the latter has no answer key and improves by trial and error from the reward (win/loss) its own actions earn.
Elo rating: a score for the relative strength of players/programs; a ~400-point gap means roughly a 90% win rate for the stronger side.

Where it sits

The authors are David Silver, Aja Huang, and colleagues at Google DeepMind; the paper "Mastering the Game of Go with Deep Neural Networks and Tree Search" appeared in Nature (January 2016). It inherits two lines: Tesauro's TD-Gammon (1990s, a neural network plus self-play mastering backgammon) and the MCTS programs that dominated computer Go after 2006 (Crazy Stone, Zen, Pachi — but only to strong-amateur level). It launches AlphaGo Zero (2017, pure self-play, no human records), AlphaZero (one algorithm for chess/shogi/Go), and MuZero (learns the game rules too).

The problem and the motivation

A game program's classic weapon is minimax search: expand the game tree, assume both sides play optimally, and back up the best move now. Its cost explodes with tree size — roughly breadth b to the power of depth d. Chess, at b≈35, d≈80, is already large, but with "a good evaluation function plus heavy pruning," Deep Blue beat Kasparov in 1997.

Go pushes two things to the limit at once. First, breadth explosion: b≈250, d≈150, a search space near 250¹⁵⁰, with about 10¹⁷⁰ legal positions — more than the atoms in the observable universe. Enumeration is hopeless. Second, no way to evaluate: whether a group lives, whose a framework becomes, is often decided only much later, and humans can't write a reliable mid-game score — which is exactly what pruning and stopping search early depend on.

The strongest prior computer Go took the MCTS route: no scoring, but "play out to the end" randomly from the current position thousands of times, using simulated win rates as the evaluation. This lifted strength from weak to strong-amateur, but stayed well short of professional — because random rollouts are too crude both to pick where to dig deeper and to estimate the position. AlphaGo's motivation: use deep networks to supply exactly what MCTS lacked — "where to go" and "who will win."

Fig 1 · Two scissors: the policy network cuts "moves worth considering" from ~250 to a handful (breadth), the value network estimates the winner at a glance (depth), so search need not reach the end.

The core idea

Two networks: one for "where to go," one for "who wins"

AlphaGo treats the 19×19 board (plus move history, liberties, and other features) as a multi-channel "image" fed to two kinds of convolutional network:

Policy network: input a position, output a "probability map" — how likely each legal point is to be played. It compresses two hundred-plus choices into "a handful worth considering," attacking breadth explosion.
Value network: input a position, output a single number — the probability that the side to move wins, playing from here. With it, search can score any position it reaches without playing to the end, attacking depth explosion.

Three-stage training: imitate humans → self-play → learn to evaluate

The networks' feel is fed in by stages (see Fig 2):

① SL policy network: supervised learning on about 30 million positions from expert human games, predicting "which move a human plays next." Accuracy about 57% (prior best ~44%) — intuition that nearly matches strong players in one shot.
② RL policy network: starting from the SL network, play repeatedly against earlier versions of itself, adjusting weights by policy gradient from win/loss — raise the probability of winning moves, lower losing ones. This turns "imitate humans" into "play to win": the improved RL version beats the SL version over 80% of the time, and with no search at all, on this one network alone it beats the strong open-source program Pachi (~85% win rate).
③ Value network: regression on RL self-play outcomes to learn "given a position, the probability of eventually winning." Key detail: the 30 million training positions are each taken from a different game — because adjacent positions within one game are highly similar, using them all would make the network "memorize games" rather than "understand positions" (overfitting).

A minimal fast rollout policy was also trained separately: only ~24% accurate, but about a thousand times faster (~2 microseconds vs the policy network's ~3 milliseconds), used purely for "fast simulation to the end" inside the search — trading accuracy for speed.

Fig 2 · Training pipeline: teach "intuition" from human records (SL policy net), sharpen it into "play to win" via self-play (RL policy net), then train "big-picture" judgment from self-play outcomes (value net).

Plugging the networks into MCTS: the four-step loop

When actually playing, AlphaGo runs a round of network-guided MCTS for every move. Each edge in the search tree (a "position → move") stores three numbers: action value Q (how good this move is on average), visit count N (how many times tried), and prior probability P (the policy network's "how worth considering"). Each round has four steps:

Select: from the root downward, pick the edge with the largest Q + u, where the exploration term u is proportional to P/(1+N) — favoring both good moves (high Q) and promising, under-tried ones (high P, small N), balancing exploit and explore.
Expand: reaching a new position, use the policy network to compute priors P over its moves and attach it to the tree.
Evaluate: estimate the new position's value as a weighted average of two opinions — the value network's direct judgment v, and the win/loss z from a fast rollout to the end, mixed as (1−λ)·v + λ·z (λ=0.5 worked best in the paper: one steady, one sharp, complementary).
Back up: propagate this evaluation along the path just taken, updating each edge's Q and N.

After thousands of such rounds, the final move is the one with the highest visit count N — not the highest value, because "repeatedly chosen by the search" is itself evidence of robustness. The beauty: the policy network makes search deepen only on a few good moves, the value network lets it skip reaching the end every time, and together they squeeze an astronomical search into a computable range.

Fig 3 · Network-guided MCTS: select (max Q+u) → expand (policy prior P) → evaluate (value v mixed with rollout z) → back up (update Q, N), looped thousands of times.

Key results

The margins were lopsided. Distributed AlphaGo beat the strongest other Go programs of the day (Crazy Stone, Zen, Pachi, Fuego) 494 of 495 games (99.8%), and still won a large share even giving 4 handicap stones. The real watershed was October 2015: AlphaGo beat European Go champion Fan Hui (2-dan professional) 5–0 — the first time a program beat a professional on a full 19×19 board with no handicap. Its Elo was around 3140, far above other programs (~1900–2500).

Ablations showed each part's worth: the policy network alone (no search) was already strong-amateur; evaluation from the value network alone, or from fast rollouts alone, was decent, but mixing the two (λ=0.5) was clearly strongest; removing either network cut strength markedly. (After publication, in March 2016 AlphaGo beat top-tier player Lee Sedol 4–1, whose game-two "Move 37" became famous for its creativity — but that match is outside this paper.)

Why it mattered

Go had been AI's acknowledged "moonshot," widely expected to hold out for another decade-plus; AlphaGo brought it forward by a generation. Its depth isn't "it won at Go" but the general paradigm it proved: let deep networks supply "intuition (policy)" and "judgment (value)" to guide a selective search — any problem with self-play and a clear win/loss signal might fall this way. This path led directly to AlphaGo Zero (2017: drop all human records, learn from scratch by self-play, and surpass the original), AlphaZero (one algorithm across chess, shogi, Go), and MuZero (learn the rules too); it also made "deep reinforcement learning + search" a template for later breakthroughs (protein structure, chip floorplanning, plasma control) and pushed AI to the center of public attention.

Limitations and criticism

Extremely expensive compute: the distributed version that beat Fan Hui used about 1,202 CPUs and 176 GPUs; training cost was enormous too. This was not a "clever little program" but "clever plus massive compute."
Reliance on human records as a crutch: the original needed 30 million human games to get started. Ironically, a year later AlphaGo Zero — using no human records — was stronger, showing human data was not only unnecessary but in a sense a limitation.
A tightly constrained paradigm: the method thrives on "perfect information, deterministic, discrete, clear win/loss" games; it doesn't transfer directly to imperfect information (e.g. poker), continuous control, or real tasks with no clear reward — it needs a fast-simulatable model/rules.
Not invulnerable: Lee Sedol clawed back game four with "Move 78," exposing brittleness against surprise positions; later (2022) research found blind spots in AlphaGo-style programs via adversarial play, letting even amateurs win — "superhuman" strength still has holes in robustness.

The essentials

① In one line: use a policy network (which moves to consider) plus a value network (who wins) to guide Monte Carlo Tree Search — the first program to beat a professional in full-board Go.

② The pain: Go's search space is ~250¹⁵⁰ (breadth explosion) and no reliable hand-built mid-game evaluation exists (no pruning / early stopping) — both enumeration and classic evaluation fail.

③ Two scissors: the policy network cuts away most bad moves (breadth), the value network estimates the winner at a glance (depth), squeezing an astronomical search into a computable range.

④ Three-stage training: SL policy (learn from human records, 57% acc.) → RL policy (self-play, policy gradient, play to win) → value network (regress on self-play outcomes, one position per game to avoid overfitting); plus a very fast rollout policy for simulation.

⑤ Search: each edge stores Q, N, P; select on Q+u (u∝P/(1+N)) → expand → evaluate (value v mixed with rollout z at λ=0.5) → back up; play the most-visited move.

⑥ Results: 494/495 wins vs other programs; 5–0 over 2-dan pro Fan Hui in 2015 (first full-board win over a professional); 4–1 over Lee Sedol after publication.

⑦ Impact: cracked Go a generation early; founded the "networks give intuition + judgment to guide search" paradigm, spawning AlphaGo Zero / AlphaZero / MuZero — a deep-RL landmark.

⑧ Limits: expensive compute (thousands of CPUs / hundreds of GPUs); reliance on human records (later shown a crutch by the Zero version); fits only perfect-information problems; robustness blind spots (Lee Sedol game four, later adversarial attacks).