Checkers is solved

Chinook had taken the world title from humans in 1994. On 19 July 2007 Science published the paper that made the title permanent. Jonathan Schaeffer's group at the University of Alberta had spent eighteen years, using as many as two hundred computers at a time, computing the outcome of every checkers position with up to ten pieces, 39 trillion of them, and searching from the opening down to those positions. The result was a proof: with perfect play on both sides, checkers is a draw. No program and no person will ever beat a perfect player, and a perfect player exists.

Checkers has about 5 × 10²⁰ positions and is the largest game solved to date. Chess has around 10⁴⁴ and Go around 10¹⁷⁰, and neither will be solved this way. The paper marks the outer limit of what exhaustive search can do, and the moment the game-playing tradition that ran from Shannon to Deep Blue reached its natural end.

The tradition that replaced it, learning rather than enumerating, was already at work in TD-Gammon and would produce AlphaGo nine years later. Schaeffer, who had begun by trying to beat Marion Tinsley, ended by proving that Tinsley, who drew almost every game he did not win, had been playing perfectly.