Reinforcement Learning and Self-Play

How Trial, Error, and Temporal-Difference Credit Discover Superhuman Moves

On March 10, 2016, inside the Four Seasons Hotel in Seoul, eighteen-time world Go champion Lee Sedol sat across a wooden board from Aja Huang. Huang was the engineer placing stones for DeepMind's AlphaGo program during Game 2 of their five-game match. On Move 37, AlphaGo instructed Huang to place a black stone on the fifth line of the right side. It was a shoulder hit into empty territory where centuries of East Asian Go proverb dictated that stones on the fifth line are too high to claim territory and too low to build central influence. Lee Sedol stared at the board for twelve minutes, stood up, and walked out of the room before returning to lose the game. Watching in the commentary room, three-time European champion Fan Hui marveled at the play, noting that he had never seen a human play such an unconventional yet striking move.

A model trained strictly by imitating human grandmasters could never discover Move 37. In fact, AlphaGo's own supervised human-imitation network calculated that a human professional would play that fifth-line stone less than once in ten thousand turns. Breaking past the ceiling of human demonstration requires reinforcement learning, where an agent learns an action policy by interacting with an environment and adjusting its internal value estimates to maximize cumulative future reward.

The lineage of self-play reinforcement learning began in 1959 at IBM, when engineer Arthur Samuel programmed an IBM 701 vacuum-tube computer to play checkers against itself. Because the final win or loss signal arrives only at the end of a sixty-move game, a learning system needs a way to judge mid-game boards long before the match ends. Samuel updated the score of each mid-game board position toward the score of the board position that occurred a few moves later.

In 1988, Richard Sutton formalized this bootstrapping mechanism as temporal-difference (TD) learning. When an agent moves from state $s_t$ to $s_{t+1}$ and receives immediate reward $r_t$ under discount factor $\gamma$, the temporal-difference prediction error $\delta_t$ measures the discrepancy between consecutive value estimates:

Whenever the successor position $V(s_{t+1})$ turns out stronger than expected, $\delta_t$ is positive, and gradient updates push the earlier valuation $V(s_t)$ upward immediately without waiting for the end of the episode. In 1992, IBM researcher Gerald Tesauro combined temporal-difference bootstrapping with a multi-layer neural network to build TD-Gammon. Starting from completely random weights with zero human strategy programmed in, TD-Gammon played 1.5 million games of backgammon against itself. When world champions like Bill Robertie examined TD-Gammon's play, they found the neural network slotting checkers on points human manuals forbade. Mathematical rollouts proved the machine was right, overturning decades of human opening theory.

AlphaGo scaled this self-play loop to the $10^{170}$ board positions of Go by pairing two deep neural networks with Monte Carlo tree search. A policy network narrowed the vast branching factor to a handful of high-probability candidate moves, while a value network $V(s)$ estimated the whole-board win probability from any mid-game configuration. Move 37 was selected because the value network and tree search recognized that a quiet stone on the right wing would interlock with a tactical battle across the center fifty moves later. Today, the same reinforcement-learning loop powers reasoning models that verify their own mathematical proofs and computer code through trial and error. When DeepMind's successor program AlphaZero was given only the bare rules of Go with zero human games to study, it defeated the version of AlphaGo that beat Lee Sedol by one hundred games to zero after seventy-two hours of self-play.