Big questions
Is checkers solved?
Yes. In 2007, after 18 years of computing, a team at the University of Alberta proved that checkers is a draw if neither side makes a mistake. Here’s what they proved, how they did it, and why it changes nothing about the game you play.
Short answer
Yes, checkers is solved. In 2007, Jonathan Schaeffer’s team at the University of Alberta proved that if both sides play perfectly, checkers is a draw. A computer that follows their proof can never lose. But the proof took 18 years of computing and no person could ever learn it, so for people the game is as open as it ever was.
- 2007The year checkers was proved a draw
- 18 yearsOf computing, starting in 1989
- 5×10²⁰Possible positions in checkers
- 19Openings that had to be solved
What “solved” means
A game is solved when we know who wins if nobody makes a mistake. There are three levels:
- Ultra-weakly solved: we know the result with perfect play, but not how to reach it.
- Weakly solved: we know the result, and have a way of playing from the start that’s sure to reach it. Checkers is solved this way.
- Strongly solved: we know the result of every position that can come up. Checkers endings with 10 pieces or fewer are solved this way.
So the proof doesn’t give the best move in every checkers position. It gives a way to play from the start without ever losing, as either side, and the exact result of every ending with up to 10 pieces.
How they did it
The work began in 1989, when Jonathan Schaeffer’s team started building Chinook, a program meant to beat the world champion. Computers ran on the problem almost without a break from then until 2007. At the peak, in 1992, more than 200 processors were working on it at once.
They came at the game from both ends:
- From the end, backwards. Starting with one piece on the board, then two, then three, they worked out the result of every position with up to 10 pieces: about 39 trillion of them.
- From the start, forwards. A search looked for lines of play from the opening that run into those databases, so that neither side can steer the game away.
This works because of the forced jump. Since you have to take, pieces come off the board fast, and a game soon gets down to 10 pieces or fewer. Here’s the most common way it happens:
How many checkers positions there are
By the number of pieces on the board. Each line up is ten times more than the one below.
Every result known
Pieces on the board
10 pieces or fewer: in the databasesMore than 10: searched only where needed
Point at or tap a bar to see its number. Altogether there are 500,995,484,682,338,672,639 positions, about 5×10²⁰.
See all the numbers
| Pieces | Positions |
|---|---|
| 1 | 120 |
| 2 | 6,972 |
| 3 | 261,224 |
| 4 | 7,092,774 |
| 5 | 148,688,232 |
| 6 | 2,503,611,964 |
| 7 | 34,779,531,480 |
| 8 | 406,309,208,481 |
| 9 | 4,048,627,642,976 |
| 10 | 34,778,882,769,216 |
| 11 | 259,669,578,902,016 |
| 12 | 1,695,618,078,654,976 |
| 13 | 9,726,900,031,328,256 |
| 14 | 49,134,911,067,979,776 |
| 15 | 218,511,510,918,189,056 |
| 16 | 852,888,183,557,922,816 |
| 17 | 2,905,162,728,973,680,640 |
| 18 | 8,568,043,414,939,516,928 |
| 19 | 21,661,954,506,100,113,408 |
| 20 | 46,352,957,062,510,379,008 |
| 21 | 82,459,728,874,435,248,128 |
| 22 | 118,435,747,136,817,856,512 |
| 23 | 129,406,908,049,181,900,800 |
| 24 | 90,072,726,844,888,186,880 |
| All | 500,995,484,682,338,672,639 |
From Schaeffer et al., Science, 2007, Table 1.
Even so, only a tiny part of the game had to be searched: about 10¹⁴ positions out of 5×10²⁰. And they needed to solve just 19 openings. There are roughly 300 ways a game can start over its first three moves, but more than 100 of them are the same positions reached in a different order, and the rest could be shown not to matter.
Why it doesn’t matter for your game
Knowing the answer isn’t knowing the moves
The proof is a tree of about 10 million positions, each one standing for a search of 10 million more. No one can memorise that, and you can’t look it up in the middle of a game. Knowing that perfect play draws doesn’t tell you how to find a perfect move.
People make mistakes, and mistakes decide games
Marion Tinsley, the greatest checkers player there has ever been, lost only three games between 1950 and 1991. Even he made the odd losing slip. At every other level, the game goes to whoever slips less, and the proof can’t change that.
Computers have beaten us at chess for decades
Deep Blue beat the world chess champion in 1997, and today’s chess programs are far stronger than any person. Chess is as popular as ever. What makes a game fun is playing someone at your own level, not knowing that a perfect machine exists.
Solved isn’t the same as easy
Tic-tac-toe is solved too. You can learn to play it perfectly in an afternoon, which is why adults don’t play it. Checkers took computers 18 years. That’s the difference between a game that’s solved and a game that’s over.
Strong players already knew it was close
For over a century, top checkers has been close to a draw. Since the 1930s, America’s main tournaments have drawn the first three moves at random, a system called the three-move restriction. Each pair of players plays the opening twice, swapping sides, so they play a wide range of positions instead of the safest ones. The 2007 proof confirmed what the best players had long believed.
Is chess solved?
No, and it won’t be for a long time. By John Tromp’s estimate, chess has about 4.8×10⁴⁴ legal positions, around 10²⁴ times as many as checkers. The team that solved checkers wrote that, given how much checkers took, chess will stay unsolved for a long time unless new technology comes along.
Checky’s own endgame database
Checky’s engine uses the same idea on a smaller scale. It knows the exact result of every position with five pieces or fewer, about 156 million of them, all worked out from scratch. When a Checky game review says an ending was won, it was.
Sources
- Jonathan Schaeffer, Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu and Steve Sutphen, “Checkers Is Solved”, Science 317, 1518–1522 (2007). doi.org/10.1126/science.1144079
- The Chinook project, University of Alberta. webdocs.cs.ualberta.ca/~chinook
- John Tromp’s estimate of the number of legal chess positions.
Questions people ask
Who solved checkers?
Jonathan Schaeffer and his team at the University of Alberta, with their program Chinook. They announced the proof in the journal Science in 2007.
Is checkers always a draw?
Only if both players are perfect. One mistake from either side can lose the game, and people make them all the time.
Can you still win at checkers?
Yes. Solved means a perfect player can’t lose. No person plays perfectly, so games between people are won and lost as they always have been.
Is chess solved?
No. Chess has around 10²⁴ times as many positions as checkers, and it isn’t expected to be solved any time soon.
What other games are solved?
Connect Four, Nine Men’s Morris, Go-Moku, Qubic and Awari, among others. At the time it was solved, checkers was the hardest popular game to be solved, around a million times as complex as Connect Four.
Who goes first in the perfect game?
It doesn’t matter. The proof shows that either side can force at least a draw, whichever colour they play.
