AlphaGo, Move 37, and What Self-Play Changed

AlphaGo beat Lee Sedol 4–1 in Seoul in March 2016, nineteen years after Deep Blue and about a decade earlier than most professionals expected. The method was Monte Carlo tree search guided by two neural networks, trained first on human games and then by self-play. It requires four properties that Go has and that almost nothing economically valuable has.

Why Go was the hard one

The standard explanation is the branching factor, and it is correct as far as it goes. A chess position offers roughly 35 legal moves; a Go position on a 19×19 board offers around 250 early on. Search trees grow as the branching factor to the power of the depth, so the same depth of search costs vastly more.

Search cost as branching factor to the power of depth

  chess, b ≈ 35 :   35^6  ≈ 1.8 × 10^9   positions at 6 ply
  go,    b ≈ 250:  250^6  ≈ 2.4 × 10^14  positions at 6 ply

  ratio at 6 ply ≈ 130,000×

Alpha-beta pruning reduces the effective branching factor to about
its square root when move ordering is good, which is what made deep
chess search feasible. It helps in Go too — and √250 ≈ 16 is still
worse than an unpruned chess tree.

But the branching factor is only half the problem, and the other half is the one that mattered. Chess has a workable hand-written evaluation function: material count plus a few dozen positional terms gets you a long way, because in chess the value of a position is substantially local and substantially material. Go has no such function. Whether a group of stones is alive or dead can depend on a stone played fifty moves ago on the other side of the board, and professional players describe their judgement of a position as intuition precisely because they cannot decompose it. There was nothing to write down.

That is why Deep Blue’s approach — enormous search over a hand-crafted evaluation — could not be pointed at Go. Both of its components fail. The evaluation function had to be learned, and the search had to be selective in a way alpha-beta is not.

Fan Hui, Lee Sedol, Ke Jie

1. October 2015, London. AlphaGo beat Fan Hui, the European champion and a 2-dan professional, 5–0 in formal games on a full board with no handicap. This was the first time a program had beaten a professional under those conditions, and it was kept confidential until publication.
2. January 2016. The result was published in Nature as Mastering the game of Go with deep neural networks and tree search. The paper is the reason the Lee Sedol match was arranged, and it is also the reason the match was a fair-ish test: the method was public before the match was played.
3. March 2016, Seoul. AlphaGo beat Lee Sedol 4–1. Lee had been among the strongest players in the world for a decade and had predicted before the match that he would win comfortably.
4. May 2017, Wuzhen. AlphaGo beat Ke Jie, then the world’s top-ranked player, 3–0. DeepMind retired AlphaGo from competition afterwards.

The architecture, in one paragraph: a policy network proposes plausible moves, trimming the 250-wide branching factor to a handful worth exploring; a value network estimates the probability of winning from a position without playing it out, replacing the hand-written evaluation Go does not admit; and Monte Carlo tree search uses both to decide where to spend its search budget. The policy network was initially trained on a large corpus of human amateur and professional games and then improved by playing against itself.

Move 37, and the number attached to it

In the second game of the Seoul match, AlphaGo played move 37: a shoulder hit on the fifth line, at a stage of the game where established Go theory says the third and fourth lines are correct. Commentators initially assumed it was a mistake or a mis-click. Lee Sedol left the room for a quarter of an hour before responding. The move turned out to be central to the game AlphaGo won.

The detail that makes it more than an anecdote is a number DeepMind published afterwards: AlphaGo’s own policy network — the component trained to predict what a human would play — assigned that move a probability of roughly one in ten thousand. The system knew it was a move humans do not make, and its search told it to play it anyway.

That combination is what made move 37 significant rather than merely strong. It is a concrete case of a system trained on human data producing something outside the distribution of that data and being right — not by luck, but because the search-and-evaluate loop had a criterion for correctness that did not route through human approval. Professional Go opening theory has since changed in response to machine play, including a general re-evaluation of moves on the fifth line, which is about as unambiguous a case of a program teaching a human field something as exists.

Move 78, and the game it lost

The fourth game is the one to study, and it is left out of most retellings because it complicates the story. Lee Sedol, already 0–3 down, played move 78 — a wedge into the middle of AlphaGo’s position that Go commentators promptly christened the divine move. AlphaGo’s evaluation of its own winning chances, which the broadcast displayed, remained high for several moves afterwards and then collapsed. It played a sequence of clearly weak moves and lost.

DeepMind’s explanation afterwards was that the value network had badly misjudged the position and did not recover for several moves. A system with superhuman average performance had a region of the state space in which its evaluation was not merely imperfect but confidently wrong, and a human found it under match conditions. Keep that in mind for the last section of this page, because it turned out not to be a one-off.

AlphaGo Zero and the removal of humans

In October 2017 DeepMind published Mastering the game of Go without human knowledge. AlphaGo Zero was given the rules and nothing else — no human games, no hand-crafted features, a single network producing both policy and value. Trained purely by self-play, it beat the version that had defeated Lee Sedol 100–0.

The result is stronger than the original in a way worth stating precisely. The human game corpus was not merely unnecessary; it was a handicap. Bootstrapping from human play started the system in a local region of strategy space that it then had to escape. Removing it produced a better player and, incidentally, one that rediscovered several standard human opening patterns on its own before discarding some of them.

AlphaZero, published two months later, generalised the same method to chess and shogi with no domain-specific changes beyond the rules, reaching top-engine strength in each. MuZero, in 2019, removed the rules as well, learning a model of the game’s dynamics from play. Each step is a real removal of hand-supplied knowledge, and the trajectory is one of the strongest pieces of evidence for the general claim that learned methods beat engineered ones given enough compute.

The four conditions, and the 2022 exploit

Self-play at this level needs four properties simultaneously. Naming them is the fastest way to see why the method did not spread to the problems people hoped it would.

The gap between that list and the world is why the decade after AlphaGo was dominated by language models trained on text rather than by reinforcement learning from self-play. Where self-play-like methods have since worked on language — for reasoning tasks with checkable answers, such as mathematics with a verifiable result or code with a test suite — it is because those tasks supply a cheap automatic verifier, which is the terminal reward property smuggled back in. The rest of the field is still waiting for it.

And there is a harder limit, established after the fact. In 2022, researchers published adversarial policies that beat superhuman Go programs, including strong open-source successors to AlphaGo, at high win rates. The attacking policies were not stronger at Go in any general sense; they were trained specifically to steer the game into a particular kind of circular group structure that the victim misevaluated. The exploit was subsequently shown to be simple enough for a human amateur to learn and execute against a program that beats professionals.

That result is the honest ending. Superhuman average performance in a closed game does not entail robustness even within that game, and the same distinction — average capability against worst-case behaviour — is the one every current safety and evaluation argument turns on. Move 78 was not an anomaly. It was the first observation of a property.