Image: Dietmar Rabich (CC BY-SA 4.0)Move 37, the Go move no human would have played
In the second game of the match in Seoul, on 10 March 2016, AlphaGo was playing Black against Lee Sedol, the winner of eighteen international titles. On its nineteenth move, the 37th of the game, it placed a stone on the fifth line of the board on the right side, a "shoulder hit" against a white stone. The commentators, professional players themselves, assumed a transmission error. Fifth-line shoulder hits are not played; the proverb says the fourth line is for influence and the third for territory, and the fifth is too high. Lee Sedol left the room for a quarter of an hour. AlphaGo won the game, and the match 4 to 1.
One in ten thousand
The number that made the move famous came from inside AlphaGo. Part of the system was a policy network, a convolutional network of the kind that recognizes photographs, trained on 30 million positions from games between strong human players to predict the next human move. Asked about move 37, the policy network put a probability of about 1 in 10,000 on it. The system that chose the move had itself estimated that a human player would almost never play it. It chose it anyway, because its other components had judged the move better than the ones humans would play.
That is the detail to understand, because it says what AlphaGo was. The policy network alone was a good imitator of human play and would have made a strong amateur. What won the match was a combination of three things, and the surprise of move 37 is a sign that the combination had gone somewhere the imitation could not.
Three parts
The first part was the policy network just described, which was then improved by playing millions of games against earlier versions of itself and learning from which moves led to wins, the reinforcement learning of Unit 12 applied to a board. The second was a value network, trained on 30 million positions from those self-play games to predict, from a position alone, the probability that Black wins. A position in Go cannot be scored by counting material, as a chess position roughly can, and a learned estimate of who is winning was what had been missing from Go programs for decades.
The third part was search. Monte Carlo tree search builds a tree of possible continuations from the current position, one move at a time, choosing which branch to extend by a rule that balances the moves the policy network likes against the moves whose results so far have been best, and scoring the leaves of the tree with the value network together with fast random playouts to the end of the game. Each move in the match was the result of this search exploring tens of thousands of positions, with the two networks telling it where to look and what it had found. Deep Blue, which beat Kasparov in 1997, had searched 200 million chess positions a second with a hand-written evaluation; AlphaGo searched far fewer and evaluated them with learned networks, because Go has about \(2 \times 10^{170}\) legal positions and a branching factor of about 250 against 35 for chess, and brute search has no chance.
Why the move was a surprise
The policy network's 1 in 10,000 was an estimate of human behaviour, learned from human games. The search looked past that prior, extended the branch anyway because the value network liked where it led, and found that the stone on the fifth line connected with the position in a way that paid off fifty moves later. The move was the product of self-play and search, two things that are not bound by the proverbs, applied to a position that the proverbs had got wrong. Professional players who studied the game afterwards came to call it a good move, and fifth-line shoulder hits appeared in professional play in the following years.
There is a symmetric moment in the match. In the fourth game, on 13 March, Lee Sedol played a wedge at move 78 that AlphaGo's networks had also rated as very unlikely, and it broke the program's position: AlphaGo's estimate of its own winning chance fell sharply over the next moves and it lost its only game. The move is remembered as the divine move, and the two together, 37 and 78, are the fairest summary of the match. Both players found moves the other's model of the game did not contain.
What it did and did not show
AlphaGo showed that a learned evaluation plus search could beat the best human at a game that had resisted computers for twenty years after chess fell, and that self-play could produce play that was not an imitation of its teachers. A year later, AlphaZero removed the human games altogether, starting from random play and the rules alone, and reached a higher level than AlphaGo in Go, chess, and shogi with one algorithm. The ideas, a policy, a value estimate, and a search guided by both, are the ones Unit 12 of the masterclass teaches on a gridworld, and they are not specific to board games.
What the match did not show is as important. Go is a game with perfect information, fixed rules, and a result that can be checked at the end, and millions of self-play games cost only electricity. A robot learning to grasp objects gets a few thousand attempts, each slow and each risking the hardware; a doctor gets none. The gap between what works when experience is free and what works when it is expensive is the central practical problem of reinforcement learning, and move 37 is an example of what the method can do when the gap does not exist.
The paper describing the system, "Mastering the game of Go with deep neural networks and tree search", was published in Nature in January 2016, before the match, and is available from the journal. Unit 12 of the AI Masterclass works value iteration and Q-learning by hand, explains the deep Q-network and Monte Carlo tree search, and tells the story of this match from the published record; Unit 2 explains why the search of Deep Blue could not have done it.


