AlphaGo is DeepMind's Go-playing system, which combines two convolutional networks with Monte Carlo tree search. In October 2015 it became the first program to beat a professional without handicap, the European champion Fan Hui, 5–0 (Silver et al., 2016, p. 488); in March 2016 it defeated Lee Sedol, one of the world's best players, 4–1, with more than two hundred million people watching (M. Mitchell, 2019, ch. 9).
The problem
In chess there are about 35 legal moves per turn and a game lasts about 80; in Go, about 250 and 150 (Silver et al., 2016, p. 484). Exhaustive search is impossible, and nobody had managed to write a good evaluation function either: experts explain their choices with notions such as "influence" or "stability" that resist being turned into rules (Buckner, 2024, p. 52; M. Mitchell, 2019, ch. 9). In 1997 one enthusiast predicted it might take a hundred years for a machine to beat a human (M. Mitchell, 2019, ch. 9).
How it works
AlphaGo reads the board as a 19 × 19 image with 48 feature planes, just as a vision network reads a photo (Silver et al., 2016, p. 484). Its training has four pieces (2016, pp. 485–486):
- A 13-layer policy network, trained by supervised learning on about 30 million positions from the KGS server, predicts an expert's move with 57% accuracy.
- A fast policy, linear and far less accurate, picks each move in 2 microseconds (the network takes 3 milliseconds) and is used to simulate whole games.
- The policy network is then improved by reinforcement learning, playing against earlier versions of itself; with no search at all, it already won 85% of its games against Pachi, the strongest open-source program.
- A value network learns to predict the winner from 30 million positions, each taken from a different self-play game, so that it cannot memorize whole games.
At play time, the search uses the policy network to decide which branches to explore (less breadth) and evaluates each leaf by mixing the value network with a fast rollout to the end of the game (less depth). A curious detail: the supervised network guided the search better than the reinforced one, "presumably" because humans propose a more diverse beam of moves (Silver et al., 2016, p. 486). The distributed version used 1,202 CPUs and 176 GPUs (2016, p. 487).
What changed
Deep Blue explored over 200 million moves per second, with heuristics and an opening library supplied by experts (Buckner, 2024, p. 51). Against Fan Hui, AlphaGo evaluated thousands of times fewer positions than Deep Blue had against Kasparov, choosing them with one network and assessing them with another, an approach its authors call "perhaps closer to how humans play" (Silver et al., 2016, p. 489). The debt to AlexNet is direct: the same kind of network that recognizes objects in photos recognizes shapes on the board (Buckner, 2024, p. 119).
In the second game against Lee, move 37 baffled the commentators; Lee left the room and took nearly fifteen minutes to reply (Buckner, 2024, p. 63). The policy network estimated that a human would play it with a probability below 1 in 10,000 (2024, p. 226).
Its evolved form, AlphaGo Zero, did without human games altogether: it learned by self-play alone and beat the version that had defeated Lee 100–0 (Silver et al., 2017). With AlphaZero, the method was extended to chess and shogi (M. Mitchell, 2019, ch. 9). In real time and with hidden information, the line continued with AlphaStar.
Limits
In the fourth game, Lee found his own unexpected move, move 78, and AlphaGo did not seem to realize what was happening (M. Mitchell, 2019, ch. 9). The system needed far more experience than a human: about 30 million games against itself, whereas Lee cannot have played more than 50,000 in his whole life (Buckner, 2024, p. 144). It is opaque: one can inspect the tree, but not why the network values a position as it does (2024, pp. 62–63). And it is narrow: Chollet (2019) noted that neither AlphaGo nor AlphaZero had found any application outside board games (2019, sec. I.3.5).