University of Alberta announces that checkers is solved

What it means to solve a game

Checkers is a board game for two players, who take turns moving pieces and capturing the opponent's. Saying that such a game has been "solved" is a stronger claim than saying that a program plays it well. It means that, starting from the opening position, the result of the game is known with certainty, and that a strategy exists which guarantees that result no matter how the opponent moves. For checkers, the answer turned out to be a draw.

The announcement

On 19 July 2007 the University of Alberta announced that its computer scientists had solved checkers.^[1] The university's release said the result was published that day in the journal Science, and that the program behind it, Chinook, had been completed in late April 2007.^[1] The release put the scale of the work at 18 and a half years spent sifting through 500 billion billion checkers positions.^[1]

How the proof was built

Science reported that Jonathan Schaeffer set out to solve checkers in 1989, and that the proof was executed by hundreds of computers over nearly two decades.^[2] One core component was a database of all 39,000 billion arrangements with 10 or fewer pieces on the board.^[2] Tables of this kind work because, once few enough pieces remain, the value of every position can be worked out exactly and stored; the program then looks the answer up instead of searching for it, and the answers to larger positions can be assembled from the smaller ones. The University of Alberta release said an average of 50 computers, with more than 200 running at peak times, were used every day to compute the knowledge Chinook needed.^[1] Scientific American reported that Schaeffer said the program traced the final branches on 27 April 2007, completing an 18-year task.^[4]

The result

The release said Chinook may be played to a draw but will never be defeated.^[1] Science reported that if two players face off at checkers and neither makes a wrong move, the game will inevitably end in a draw.^[2] CBC quoted the Science article as saying that checkers is now solved and that perfect play by both sides leads to a draw, describing it as the most challenging popular game solved to date.^[3]

Why it matters

A solved game whose value is a draw has a particular shape. The first player cannot force a win, and neither can the second, because the best play on each side cancels out.^[2] For a program, the strongest claim that remains is a defensive one: it can be held to a draw, but it cannot be beaten, which is exactly how the Alberta release described Chinook.^[1] That also means the result does not take the game away from people. A human opponent who plays well enough can still come away with a draw; what the program rules out is losing.

The work also shows what an exhaustive computational answer looks like in practice. Rather than arguing about which plans are strong, the researchers enumerated positions and settled each one, at the cost of nearly two decades and a large pool of machines.^[2] The endgame database, the daily use of dozens of computers and the final branch traced in April 2007 are all parts of that single claim.^[1][4] The announcement placed checkers among the games whose outcome is no longer a matter of opinion, and CBC, quoting Science, called it the most challenging popular game solved to that point.^[3]