Checkers Was Solved. Is the Game Dead?
In 2007 a team of researchers announced that checkers had been solved. With perfect play from both sides, every game ends in a draw. Did that kill the game? This page tells the story of Chinook, the man who beat it, and what solving a game really means.
Published .
What does it mean to solve a game
When people hear that a game has been solved, they often imagine an unbeatable supercomputer. That is not what it means. A solved game is one where the result can be proven, assuming both players always choose the best possible move.
Tic-tac-toe is the simple example. If both players make their best choices, neither can force a win, and every perfect game ends in a draw. Checkers has the same kind of answer, but the road to it was far longer. The game has roughly five hundred billion billion legal positions, which is 5 followed by 20 zeros.
Researchers proved that from the standard starting position, perfect play by both sides always ends in a draw. The technical name is a weak solution. It means the result of the starting position is known, not that the computer holds a move for every possible position.
Beating the best human is a different achievement. Deep Blue beat Garry Kasparov in 1997, and AlphaGo beat Lee Sedol in 2016, yet neither chess nor Go has been solved. Checkers reached the rarer point where the opening position has a proven outcome.
Chinook and Marion Tinsley
The story began in 1989 at the University of Alberta in Canada. Computer scientist Jonathan Schaeffer started a project to build a checkers program that could beat the greatest human players. It was called Chinook. It combined expert opening knowledge, deep search and large databases of endgame positions.
In 1990 Chinook finished second at the United States National Championship, behind only Marion Tinsley. That made it the first computer program to qualify for a human world championship.
Tinsley was widely regarded as the greatest checkers player who ever lived. Across decades of play he lost almost no games at all. Their first match for the world title came in 1992 and Tinsley won, 4 games to 2 with 33 draws. They met again in 1994. Every completed game was a draw, and then Tinsley withdrew because of illness. Chinook became the Man-Machine World Champion, but at a heavy price, since Tinsley died the following year.
After defending the title in 1995, the team made a new decision. They would stop chasing titles and try something bolder, solving checkers itself.
How the proof was built
The team started at the end of the game. They worked out every position with only a few pieces left, then every position with a few more, and so on, building a database of known results. Each new result was used to classify positions one step earlier. This method is called retrograde analysis, because it works backward from the ending.
Step by step, the known results were pushed back toward the opening. After years of computing, the starting position itself could finally be classified. Neither side can force a win. On 19 July 2007 Schaeffer and his colleagues published their paper, Checkers Is Solved, in the journal Science.
- 1989. Chinook begins at the University of Alberta.
- 1990. Chinook finishes second at the US National Championship.
- 1992. Tinsley beats Chinook, 4 wins to 2.
- 1994. A rematch of draws ends when Tinsley withdraws, and Chinook becomes the Man-Machine World Champion.
- 2007. The paper Checkers Is Solved is published.
So is checkers dead
No. A proof assumes perfect play, and humans do not play perfectly. Every decision is shaped by experience, pressure and intuition, and sometimes by a simple mistake. One small error can change a whole game. The proof tells us what should happen, not what usually happens.
Whether you are learning your first capture or playing for a championship, you are not facing perfect mathematics. You are facing another person. That is why tournaments are still exciting, and why you can play a close game against a friend tonight.
It also helps to know how the proof fits with other games. Chess has so many more positions that a full proof is far beyond what is practical today. Go is even bigger, and programs like AlphaGo became superhuman by learning from data, not by proving every possibility. Winning at a game and proving it are different things.
The Chinook project shows what decades of patient research, clear mathematics and raw computing power can answer. The result is a landmark in the history of artificial intelligence. Mathematics may know the destination, but the journey still belongs to the players.
Watch Checkers Was Solved in motion
The same story as an animated video, with a short version.
The animated story. About six minutes. Watch on YouTube
The 45 second version. Watch on YouTube
Sources for Checkers Was Solved
- Schaeffer et al., Checkers Is Solved, Science, 19 July 2007
- Wikipedia, Chinook (draughts program)
- Wikipedia, Marion Tinsley