Is Checkers a Solved Game? The 18-Year Quest of Jonathan Schaeffer & Chinook

For centuries, checkers was considered an inexhaustible battle of human wits. With roughly 500 billion billion (5 × 10²⁰) possible legal positions, many mathematicians believed the game was too vast for any computer to calculate conclusively. Yet in July 2007, a historic headline reverberated across the scientific world when the journal Science published the landmark paper: "Checkers Is Solved". Led by Canadian computer scientist Dr. Jonathan Schaeffer, an 18-year computational Odyssey proved beyond mathematical doubt that flawless play by both sides inevitably leads to a draw. Here is the remarkable story of Chinook, retrograde analysis, and how checkers became the most complex game in history ever solved.

1. What Does "Solved Game" Actually Mean in Game Theory?

In computational mathematics, two-player perfect-information zero-sum games (like Tic-Tac-Toe, Connect Four, Chess, and Checkers) can be solved across three distinct tiers:

• Ultra-Weakly Solved: Proven that the first player wins, loses, or ties from the initial starting state, without providing an algorithm to execute the moves.
• Weakly Solved: An algorithm exists that guarantees a forced win or draw from the opening position against any opponent defense. (This is how Connect Four was solved by Victor Allis in 1988, and how Checkers was solved in 2007).
• Strongly Solved: An algorithm can instantly produce the mathematically optimal move from every single conceivable board state, even after blunder sequences.

2. The Mammoth Mathematical Scale of Checkers

3. The Epic Rivalry: Chinook vs. Marion Tinsley (1992–1994)

Before Checkers was completely solved, the software engine developed at the University of Alberta—named Chinook—competed against the greatest human checkers grandmaster in history: Dr. Marion Tinsley.

Tinsley was virtually superhuman. Over a legendary 45-year competitive career, he lost a grand total of only seven games out of thousands played. In 1992, Chinook faced Tinsley for the Man vs. Machine World Championship. Tinsley triumphed 4–2 with 33 draws. In their 1994 rematch, after six consecutive grueling draws, Tinsley was tragically forced to withdraw due to health complications (he was diagnosed with pancreatic cancer and passed away shortly after).

Chinook subsequently defeated grandmaster Don Lafferty, officially becoming the first artificial intelligence program in history to win a human world championship in any mind sport—predating Deep Blue’s victory over Garry Kasparov in chess by two years.

4. The Algorithmic Breakthrough: Endgame Tablebases & Proof Numbers

To definitively solve a game containing 5 × 10²⁰ states, Schaeffer’s team could not merely rely on brute-force forward search. They pioneered two breakthrough techniques:

A. Retrograde Endgame Databases (Tablebases)

Working backward from terminal win/loss/draw positions, computers calculated every possible position containing 10 pieces or fewer. This massive database comprised 39,271,258,813,439 (39 trillion) exact positions.

Whenever Chinook reached a position with 10 pieces remaining on the board, it did not need to calculate or guess: it simply looked up the result in its tablebase, playing with 100% infallible perfection.

B. Proof-Number Forward Search

From the starting board, Chinook performed intelligent heuristic tree searches designed to prove which initial opening moves led into verified draw states within the endgame tablebases. In 2007, the final bridging calculations were completed: Checkers was solved. The game is an inevitable draw under flawless play.

5. Does the Solution Ruin the Game for Human Players?

A common misconception is that solving a game makes it boring or obsolete. In reality, human play has thrived:

• The Vastness of Human Limitation: No human brain can memorize 39 trillion tablebase positions. In real matches, even grandmasters stumble into subtle positional inaccuracies.
• 3-Move Restriction Tournaments: In serious competition, players draw random cards dictating the first three plies. This eliminates theoretical draw book memorization and immediately plunges players into high-stakes tactical struggles.

6. How Next Checkers Move Brings Modern Solvers to Your Browser

Two decades ago, calculating deep checkers move trees required dedicated multi-CPU computing clusters. Today, our engine at Next Checkers Move brings sophisticated game-tree search directly into your smartphone or desktop browser:

• Bitboard Processing: Board states are mapped as 32-bit unsigned integers, allowing bitwise shifting operations (AND, OR, XOR) to test forced jumps in sub-nanosecond clock cycles.
• Alpha-Beta Pruning: Discards millions of irrelevant moves instantly, focusing computational depth strictly on critical tactical continuations.
• Zero Latency: All calculations execute 100% client-side via JavaScript Web Workers without sending data to remote servers.

7. Frequently Asked Questions (FAQ)