Introduction

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×102010^{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.

Find the Forced Move

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">Red (R) to move. In checkers, a capture is <b>mandatory</b> whenever one is available — so here Red has exactly one legal move. Pick the move you think is forced, then check it. Verifying one move is instant; searching the whole game is not.</p>
<div id="board" class="board"></div>
<div class="status" id="status">Click a highlighted destination for the Red piece.</div>
<div class="btns">
  <button id="check" type="button">Check my move</button>
  <button id="count" type="button">Count the game tree</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A tiny checkers endgame. Board is 8x8; only dark squares are playable.
    // Red moves UP the board (toward row 0). A jump is MANDATORY when available,
    // so in this position Red has exactly one legal move: jump the Black piece.
    // CHECKING that move is instant. SOLVING the full game means searching the
    // whole game tree — and "Count the game tree" estimates how astronomical that
    // is. Standard 8x8 checkers has ~5e20 positions; it was solved (Schaeffer,
    // 2007) to be a draw. Generalized n x n checkers is EXPTIME-complete.
const SIZE = 8;
// r,c (row from top). Red jumps from (5,2) over Black at (4,3) landing on (3,4). r,c (row from top). Red jumps from (5,2) over Black at (4,3) landing on (3,4).
const RED = { r: 5, c: 2 };
const BLACK = { r: 4, c: 3 };
const LANDING = { r: 3, c: 4 };       // the unique forced destination
const TRAP = { r: 4, c: 1 };          // a tempting but ILLEGAL simple step (jump is mandatory)

let pick = null; // {r,c} chosen destination

function isDark(r, c) { return (r + c) % 2 === 1; }

function render() {
  const b = document.getElementById('board'); b.innerHTML = '';
  for (let r = 0; r < SIZE; r++) for (let c = 0; c < SIZE; c++) {
    const sq = document.createElement('div');
    sq.className = 'sq ' + (isDark(r, c) ? 'dark' : 'light');
    // playable highlighted destinations: the legal landing and the illegal trap
    const isLanding = r === LANDING.r && c === LANDING.c;
    const isTrap = r === TRAP.r && c === TRAP.c;
    if (isLanding || isTrap) {
      sq.classList.add('target');
      sq.addEventListener('click', () => {
        pick = { r, c };
        setStatus('Move selected. Press "Check my move".', '');
        render();
      });
    }
    if (r === RED.r && c === RED.c) sq.appendChild(piece('red', 'R'));
    else if (r === BLACK.r && c === BLACK.c) sq.appendChild(piece('black', 'B'));
    else if (pick && pick.r === r && pick.c === c) {
      const p = piece('red', 'R'); p.style.opacity = '0.5'; sq.appendChild(p);
    }
    b.appendChild(sq);
  }
}
function piece(cls, txt) {
  const p = document.createElement('div'); p.className = 'piece ' + cls; p.textContent = txt; return p;
}
function setStatus(t, cls) {
  const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls;
}

// The ONLY legal move is the mandatory jump to LANDING (capturing Black).
function isForcedMove(p) { return !!p && p.r === LANDING.r && p.c === LANDING.c; }

function check() {
  if (!pick) { setStatus('Pick a destination square first.', 'bad'); return; }
  if (isForcedMove(pick)) {
    setStatus('Correct — the jump is forced and captures Black. Red wins this endgame.', 'ok');
  } else {
    setStatus('Illegal: a capture is available, so the jump is mandatory. Try the other square.', 'bad');
  }
}

// Estimate the size of the game tree from the opening with a simple branching
    // model: average branching factor ~6, average game length ~70 plies.
function count() {
  const b = 6, plies = 70;
  // log10 of b^plies = plies * log10(b) log10 of b^plies = plies * log10(b)
  const log10 = plies * Math.log10(b);
  const mantissa = Math.pow(10, log10 - Math.floor(log10)).toFixed(1);
  const exp = Math.floor(log10);
  setStatus(fmt('A rough game tree from the start: ~%mantissa% x 10^%exp% lines. The full position count (~5 x 10^20) was solved in 2007 — it is a draw.', { mantissa: mantissa, exp: exp }), 'ok');
  console.log(fmt('Game-tree estimate: ~%mantissa%e%exp%e lines; checkers solved = DRAW (Schaeffer 2007).', { mantissa: mantissa, exp: exp }));
}

document.getElementById('check').addEventListener('click', check);
document.getElementById('count').addEventListener('click', count);
document.getElementById('reset').addEventListener('click', () => {
  pick = null; setStatus('Click a highlighted destination for the Red piece.', ''); render();
});
render();
Result
Console

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.

The Real Complexity

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×102010^{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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/checkers/Content licensed under CC BY-NC 4.0.