How Checkers Was Solved: The 18-Year Computer Search That Proved Perfect Play Ends in a Draw
The Short Answer: Perfect Checkers Is a Draw
In 2007, a University of Alberta team announced that standard 8×8 checkers had been weakly solved. After an 18-year project, its computers proved that neither side can force a victory from the normal starting position. If both players always choose a perfect move, the game inevitably ends in a draw.
That simple conclusion required one of the greatest computer searches ever devoted to a familiar board game. The researchers had to combine enormous endgame databases, intelligent search algorithms, specialized data compression and the work of dozens—and sometimes hundreds—of processors.
What Does It Mean to “Solve” Checkers?
Solving a game does not necessarily mean listing every possible match from beginning to end. Computer scientists generally describe three levels of solution:
- Ultraweak solution: The perfect-play result is known, but there is no complete strategy for achieving it.
- Weak solution: The result is known from the starting position, along with a strategy that can achieve it.
- Strong solution: The correct result—win, loss or draw—is known for every legal position.
Checkers was weakly solved. The researchers proved the value of the standard starting position and created a program that could guarantee at least a draw while playing either color. However, they did not calculate the perfect answer for every legal position that could ever appear on a board.
The result also applies specifically to English draughts, commonly called American checkers: the version played on an 8×8 board with 12 pieces per side, mandatory captures and short-moving kings. It does not automatically apply to every international variation of draughts.
Why a Small Board Created a Giant Problem
A checkers board has only 64 squares, and pieces use just 32 of them. That may appear manageable, especially when compared with chess. Yet checkers has roughly 500 billion billion possible positions, written mathematically as (5 \times 10^{20}).
Trying to examine all of those positions directly would have been wildly impractical. Even storing one tiny record for every position would have demanded an extraordinary amount of space.
The team therefore needed something smarter than brute force. Instead of exploring every conceivable game equally, it concentrated on positions that mattered to proving the result. This was similar in spirit to other famous computer-assisted achievements, such as the proof of the four-color theorem: the machine was not simply “thinking harder,” but systematically checking a carefully organized collection of cases.
The Birth of Chinook
The project began in 1989 under computer scientist Jonathan Schaeffer. His team at the University of Alberta created a checkers program named Chinook, initially with two goals: defeat the human world champion and eventually determine the true perfect-play result of the game.
Chinook used several forms of knowledge:
- A library of strong opening moves
- A program for searching future move sequences
- An evaluation system for estimating which positions were favorable
- Endgame databases containing exact results
In 1990, Chinook became the first computer program in any game to earn the right to challenge for a human world championship. Its opponent was Marion Tinsley, widely regarded as the greatest checkers player in history. Tinsley defeated Chinook in their 1992 match, demonstrating that the machine was extraordinarily strong but not yet perfect.
They met again in 1994. The first six games were draws, but Tinsley withdrew because of illness. Chinook received the Man-Machine World Championship title, although the unfinished match left the fascinating question of who would have prevailed unanswered.
The program later defeated leading player Don Lafferty in a 1995 match, winning one game and drawing 31. By 1996, the researchers considered Chinook stronger than any human and retired it from competition. The focus shifted from defeating people to proving checkers itself.
Working Backward From the End
The first major part of the solution was retrograde analysis, or working backward.
Imagine a position with only one checker remaining. Its result is usually straightforward. Once those simple positions are understood, a computer can analyze positions with two pieces, followed by three pieces, four pieces and so on.
For each position, the database records whether perfect play produces a win, loss or draw. When a later search reaches one of these known positions, the computer no longer needs to guess what happens next—it can look up the exact answer.
The Chinook team eventually calculated every legal position containing 10 or fewer pieces. This endgame database held approximately 39 trillion positions, compressed into about 237 gigabytes. The custom compression system packed an average of 154 positions into each byte while still allowing the search program to retrieve information quickly.
These databases were particularly valuable because captures are compulsory in checkers. Once jumping begins, pieces can disappear rapidly, bringing a complicated middle game into a completely understood 10-piece ending.
Searching Forward From the Opening
Knowing every small endgame was not enough. A normal game starts with 24 pieces, so the researchers also had to search forward from the opening.
This stage used two main components:
- A proof-tree manager selected the unresolved positions most important to the overall proof.
- Multiple proof solvers investigated those positions and returned exact or estimated results.
The manager used the new information to update its priorities and assign more work. Instead of treating all branches equally, the system kept asking: Which unanswered position would make the greatest contribution to completing the proof?
Traditional alpha-beta search helped eliminate branches that could not affect the final result. Strong lines from checkers literature were also used to guide the program toward promising areas, although the ultimate conclusion depended on computational proof rather than trust in human theory.
This combination of forward and backward analysis was the key. The forward search traveled down from the opening, while the databases reached upward from known endings. Once a searched line entered the 10-piece database, its final result became certain.
It resembles the approach behind the Eight Queens computing milestone: define the possibilities precisely, reject irrelevant branches and concentrate resources on the cases that still matter.
The Final Proof
Tournament checkers often uses randomly selected three-move openings to prevent players from repeatedly choosing the safest beginning. For the solution, the researchers proved the necessary results for 19 important three-move openings. Other openings were duplicates, could be transformed into equivalent positions or could be dismissed through search because they could not improve the first player’s result.
The final computation required an estimated (10^{14}) forward-search operations. Some analyzed lines extended 154 individual player moves, or “plies,” before additional searching connected them with a known database position. The researchers also ran consistency checks and independently verified parts of the calculation to reduce the possibility of programming or data errors.
On April 29, 2007, the computation finished: Black, the first player, could guarantee a draw, while White could also guarantee a draw against every possible opening move. The formal research article, appropriately titled Checkers Is Solved, was published online on July 19 and appeared in the September 14, 2007 issue of Science.
Does the Solution Make Checkers Pointless?
Not at all. Perfect play leads to a draw, but human play is rarely perfect.
The solution tells us that a forced win does not exist from the opening against flawless defense. It does not give an ordinary player an easy set of moves to memorize. Checkers remains filled with traps, sacrifices, forced jumps and positions in which the correct move is extremely difficult to recognize.
Even Chinook’s proof depended on databases and searches far beyond human memory. A player can therefore still win by creating difficult choices and taking advantage of an opponent’s error. In that sense, a solved game remains much like a puzzle with a known answer: knowing that an answer exists is very different from finding it yourself.
The same distinction appears in the story of God’s Number for the Rubik’s Cube. Proving that every scramble can be solved within a certain limit does not make every scramble easy.
Why Solving Checkers Was an Amazing Feat
The project lasted 18 years, although there was a pause between 1997 and 2001 while computing technology caught up with the team’s ambitions. At its 1992 peak, more than 200 processors were assigned simultaneously; during the final year, the project averaged around 50 computers working at once.
Its importance extended beyond the board. The project advanced research in parallel computing, search algorithms, database design and fast access to compressed information. It also demonstrated that a machine could move beyond playing brilliantly and produce a verifiable mathematical-style proof about an entire game.
Checkers may look simple enough to learn in minutes, but humanity needed decades of computer science, trillions of solved endings and an 18-year search to uncover its deepest secret:
With perfect play, nobody loses—and nobody wins.
