In 2007, a team led by Jonathan Schaeffer at the University of Alberta announced that the game of checkers had been solved. Their paper “Checkers Is Solved,” published in Science (Vol. 317, No. 5844, pp. 1518-1522, 19 July 2007), proved that when both players play perfectly, the game ends in a draw. The project’s own page summarizes the outcome simply: “Perfect Play: Draw!”
Solving the game meant determining the guaranteed result from the starting position assuming no mistakes by either side. This was an enormous computation. Checkers has roughly 500 billion billion possible positions (about 5 x 10^20), making it on the order of a million times more complex than Connect Four. The proof was the product of work that ran almost continuously from 1989, using dozens of computers over 18 years, built on the Chinook program that had earlier challenged human world champions.
The achievement was a landmark in the long line of work connecting game-playing to artificial intelligence, a thread that runs from Arthur Samuel’s pioneering checkers program in the 1950s through Deep Blue’s chess victory in 1997. Where Deep Blue beat the best human, Chinook went further for checkers: it did not just play well, it exhausted the game’s possibilities and proved the answer. Checkers remains one of the most complex games ever solved.