Checkers

Checkers — English draughts — fits on an 8×8 board with twelve pieces a side and rules a child learns in minutes. Pieces step diagonally, jumps are mandatory, reach the far row and you crown a king. That's almost the whole game.

And yet that tiny rulebook unfolds into roughly 5×$10^{20}$ legal positions — five hundred billion billion. For most of history nobody knew the answer to the simplest possible question: if both players play perfectly, who wins?

In 2007 we finally found out. The answer turned out to be wonderfully anticlimactic: with perfect play on both sides, checkers is a draw. Getting there meant confronting a gap that runs through all of computer science — the gap between checking a move and solving the whole game.

Here is a tiny checkers endgame. It is Red to move, and a mandatory jump is available. Click the move you think wins, then check it — verifying a single line is instant.

<p class="hint">{{hint}}</p>
<div id="board" class="board"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="check" type="button">{{btn_check}}</button>
  <button id="count" type="button">{{btn_count}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.board { display: grid; grid-template-columns: repeat(8, 38px); gap: 0; margin: .4rem 0;
         width: max-content; border: 2px solid #1d3557; border-radius: 6px; overflow: hidden; }
.sq { width: 38px; height: 38px; display: flex; align-items: center; justify-content: center;
      font: 700 16px ui-monospace, monospace; position: relative; }
.light { background: #efe6d2; }
.dark { background: #7d5a3c; }
.target { cursor: pointer; box-shadow: inset 0 0 0 3px #2a9d8f; }
.target:hover { box-shadow: inset 0 0 0 3px #1f7a6f; }
.piece { width: 26px; height: 26px; border-radius: 50%; display: flex; align-items: center;
         justify-content: center; font: 700 13px system-ui; color: #fff; }
.red { background: #e63946; border: 2px solid #b32430; }
.black { background: #2b2b2b; border: 2px solid #000; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the asymmetry. Checking one move is trivial: play it out and read the result. But pressing Count the game tree estimates how many positions a full solver must reach from the opening — and the number balloons past anything you could ever enumerate by hand. That gulf between checking a line and searching every line is exactly why solving checkers took eighteen years of computer time.

How hard is checkers, really? It depends on what you mean by "solve."

• Checking one move or one line is easy: apply the rules, see who is left standing.
• Solving the standard 8×8 game means proving the value of the opening position under perfect play. There are about 5×$10^{20}$ legal positions — far too many to store, let alone search naïvely.
• It's solved. In 2007 Jonathan Schaeffer and his team announced that their program Chinook had weakly solved checkers after roughly 18 years of computation. They built a perfect endgame database for all positions with ≤10 pieces (39 trillion positions) and searched forward from the start. The verdict: perfect play is a draw.
• The general case is EXPTIME-complete. Standard checkers is a fixed board, so it is "just" a finite (if gigantic) search. But generalized checkers on an n×n board was proved EXPTIME-complete by Robson (1984) — provably requiring exponential time, like generalized chess.

That is the punchline: a game small enough to solve outright still hides an exponential core. Make the board bigger and the difficulty is no longer practical but provable — there is no shortcut, ever.

Solving checkers was never really about checkers. The machinery built along the way shows up everywhere two sides take turns and one tries to outplan the other:

• Game AI and search: minimax, alpha-beta pruning and transposition tables — sharpened on checkers and chess — underpin every classical game engine.
• Endgame databases: pre-computing perfect answers for small subproblems and reusing them is a template for any large lookup-and-search system.
• Planning and verification: deciding whether some strategy guarantees a goal against an adversary is the same shape as model-checking and automated planning.
• Knowing the limit: checkers proves a problem can be enormous yet finite-and-solvable, while chess — EXPTIME-complete in general — marks where provable intractability begins.

Understand how checkers fell and you understand adversarial search, the engine behind game AI and a cousin of the questions in P vs NP.

Checkers carries a quiet lesson. Verifying a single move is effortless; proving the value of the whole game took eighteen years and the search of half a sextillion positions — only to discover that, played perfectly, neither side can win.

So the next time a game feels simple, remember the gap. Checking is cheap, solving can be astronomical, and for boards just a little larger than 8×8 the cost stops being merely huge and becomes provably exponential — a wall that no cleverness can climb.