Go Has More Positions Than the Universe Has Atoms

Computer chess was solved in the usual sense in 1997, when Deep Blue beat Kasparov. Computer Go took another two decades. The reason is the search space. Chess has a branching factor around 35 — that's how many moves you can make on an average turn. Go, played on a 19×19 grid, has a branching factor near 250. Depth times breadth blows up fast.

The exact number of legal Go positions was computed in 2016 by John Tromp and a group of collaborators using a custom SAT-based search on a high-end workstation. The answer: 2.08 × 10^170. For comparison, the number of atoms in the observable universe is estimated around 10^80. Go is not large; it is astronomically beyond brute force. Alpha-beta search, the technique that cracked chess, runs out of time before it runs out of board.

DeepMind's AlphaGo, which beat Lee Sedol in March 2016, avoided the problem by not trying to enumerate. It combined a policy network trained on human games (to narrow candidate moves) with a value network (to score positions) and Monte Carlo tree search (to look ahead probabilistically, not exhaustively). The program played moves no human had ever played, including move 37 in game two — a shoulder hit on the fifth line that commentators initially called a mistake. It was a novel winning move.

AlphaGo Zero, a follow-up that trained only against itself with no human games, beat the version that beat Lee Sedol 100–0 after 40 days of training. The more general descendant, AlphaZero, was then applied to chess and shogi with the same architecture, achieving top-level play in 24 hours of training. Go wasn't harder than chess because the rules were worse. It was harder because a lookup table the size of the universe isn't enough to cheat with.