Is Checkers Solved? Yes, and Here Is What That Means
Yes. Checkers is a solved game. In 2007 Jonathan Schaeffer’s team at the University of Alberta published a proof in Science that if both players make no mistakes, a game of checkers ends in a draw. The work was built on their checkers program, Chinook.
That answer covers one game: 8×8 American checkers, which is the same game as English draughts. Other checkers games are a different story, and so is chess.
What does “solved” mean?
A game is solved when we know the result with perfect play. Nobody has to guess any more whether the first player wins, the second player wins, or it’s a draw.
There are levels to it. Checkers is what the paper calls weakly solved. The team knows the result from the starting position, and they have a strategy that reaches it. They didn’t work out the best move for every position that could ever appear on the board. For checkers that would be a much bigger job, as the numbers below show.
The result wasn’t a surprise. The paper says grandmaster players had suspected a draw for decades, and the proof turned that suspicion into a fact.
Which checkers is solved?
Only American checkers, also called English draughts. That’s the game with 12 men a side on the dark squares of an 8×8 board. The paper sums up its rules as men moving forward one square diagonally, kings moving forward or backward one square, and a forced-capture rule. You can read the full rules on our American checkers rules page.
The other draughts games are not solved. That includes International draughts on its 10×10 board, plus Russian, Brazilian and the other variants we host. Several of them give kings the power to fly across the board in one move, and the 10×10 game has 20 men a side instead of 12. The 2007 proof says nothing about any of them.
How was checkers solved?
With a lot of computers and a lot of time. According to the paper, dozens of computers worked on the problem almost continuously from 1989. At the peak, in 1992, more than 200 processors were on the job at once. The proof was finished and published in 2007, 18 years after the work began.
The team called checkers the most challenging popular game to be solved to date, roughly a million times as complex as Connect Four.
So did AI solve checkers? A computer program did, but not by learning to play well and calling that a solution. It ran a proof. Playing well and proving the result are different jobs. Chess programs have done the first for years, and chess is still unsolved.
What is Chinook?
Chinook is the checkers program built by Schaeffer’s team at the University of Alberta in Edmonton, Canada. The proof grew out of it. Before the proof, Chinook was the world man-machine checkers champion in the 1990s.
Its great opponent was Marion Tinsley. The Science paper calls him the greatest checkers player that ever lived. His record included only three losses between 1950 and 1991. In 1992 Tinsley played Chinook for the world title and narrowly beat it. The two met again in 1994, and Tinsley withdrew partway through the rematch because of illness.
If checkers had nothing in it, no one could have stayed that far ahead of every other strong player for four decades.
How many positions are there in checkers?
About 500 billion billion. The paper gives the figure as 5 × 1020 possible positions.
That’s the count people usually quote, and it’s a count of positions, not of complete games. A position is one layout of pieces on the board. A game is a whole sequence of moves, and many different games pass through the same positions. We don’t have a sourced figure for the number of possible checkers games, so we won’t make one up.
The weak solution is what made the job possible. The team didn’t need to settle all 5 × 1020 positions. They needed enough of them to prove the result from the start.
Does that mean every game of checkers is a draw?
No. It means a game between two perfect players is a draw. People aren’t perfect, and neither are most programs.
Picture a normal game. On move 14 you make a quiet move that leaves a man loose. Because capture is compulsory, your opponent can offer a piece you have to take, and the reply jumps two of yours. Now you’re a man down. Perfect play would have drawn that game. Your play didn’t. The proof doesn’t change who wins at your kitchen table.
It does change what a loss means. In a solved game there’s always a move that holds the draw, so every lost game has a mistake in it somewhere. If you’re stuck on how a game ends when you can’t move at all, that has its own rule: see what happens when you have no moves left.
Is chess solved?
No. Chess has not been solved, and the checkers team didn’t expect it to be soon. Their paper puts the number of chess positions somewhere between 1040 and 1050, which makes checkers roughly the square root of chess. Given the effort checkers took, Schaeffer’s team wrote that chess “will remain unsolved for a long time, barring the invention of new technology”.
| Checkers (8×8 American) | Chess | |
|---|---|---|
| Solved? | Yes, weakly, in 2007 | No |
| Result with perfect play | Draw | Unknown |
| Possible positions | About 5 × 1020 | 1040 to 1050 (Schaeffer); about 4.8 × 1044 (Tromp and Österlund) |
One number gets mixed up a lot. Claude Shannon’s famous 10120 from 1950 is a lower bound on the number of possible chess games, not positions.
Chess programs like Deep Blue and Deep Fritz already play at a superhuman level, yet the paper describes them as heuristic programs that “are not perfect”. A heuristic is a rule of thumb for judging a position. That’s the gap between playing better than any person and playing perfectly. Checkers has crossed it. Chess hasn’t.
None of that stops chess being a great game to play badly with someone you like. If that’s the plan tonight, you can play chess with a friend for free. We compare the two games in full in checkers vs chess.
Can you play against a perfect checkers engine?
Not on this site.
Our checkers solver finds a strong move for any position you set up. But it isn’t Chinook, and it doesn’t look anything up in the 2007 proof. It searches ahead up to 12 half-moves (six moves for each side) within a 4-second budget and reports the best move it found. That’s a strong move, not a proven one, and in a sharp position a deeper search could disagree.
Our Hard AI uses the same engine with a shallower search of six half-moves. It makes the kind of mistakes a perfect player never would, which is good news if you want a game you can actually win.
A solved game is still worth playing. The proof lives inside a computer. You can’t memorize it, and at the board you still have to find every move yourself. Start a game of checkers against the computer or a friend and see how close to perfect you can get.
Sources:
- Schaeffer, J. et al., “Checkers Is Solved”, Science 317 (2007), pp. 1518-1522: the draw result, weak solution, 5 × 1020 positions, 1989-2007 computation, Chinook, Marion Tinsley’s record and matches, chess position estimate
- Wikipedia: Shannon number: Shannon’s 10120 lower bound on chess games, Tromp and Österlund’s chess position estimate