Endgame Tablebases

Full chess is monstrously hard — the number of possible games dwarfs the atoms in the universe, and no machine will ever brute-force it from the start. Yet the end of the game tells a very different story.

Strip the board down to a few pieces and something remarkable happens: the position is no longer a mystery to be judged by feel. It has a definitive answer. With a king, a rook and a lone enemy king, the side with the rook always wins — and a computer can tell you the fastest forced checkmate down to the exact move.

These answers live in endgame tablebases: precomputed tables that label every legal position as a win, draw or loss, along with the distance to mate. For up to seven pieces the work is finished. This is one of the few places in all of computation where we can honestly say: this game is solved.

Here is a textbook ending: White king and rook against a lone Black king. This position is a forced win, and a tablebase knows exactly how fast. Each white piece can move; for every legal move the panel shows the verdict the tablebase would assign — and the distance to mate if you play it.

<p class="hint">{{hint}}</p>
<div id="wrap">
  <div id="board" class="board"></div>
  <div class="side">
    <div class="verdict" id="verdict">{{building}}</div>
    <div class="dtm" id="dtm"></div>
    <div class="btns">
      <button id="best" type="button" disabled>{{btn_best}}</button>
      <button id="reset" type="button" class="ghost">{{btn_new}}</button>
    </div>
    <div class="log" id="log"></div>
  </div>
</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; }
#wrap { display: flex; gap: 1rem; flex-wrap: wrap; align-items: flex-start; }
.board { display: grid; grid-template-columns: repeat(8, 34px); grid-template-rows: repeat(8, 34px);
         border: 2px solid #1d3557; border-radius: 6px; overflow: hidden; }
.sq { display: flex; align-items: center; justify-content: center; font-size: 22px; user-select: none; position: relative; }
.sq.light { background: #eef2f6; } .sq.dark { background: #b9c6d3; }
.sq.mark::after { content: ""; position: absolute; width: 12px; height: 12px; border-radius: 50%;
                  background: rgba(10,125,51,.55); }
.side { min-width: 200px; flex: 1; }
.verdict { font-size: 1.05rem; font-weight: 700; color: #1d3557; min-height: 1.5em; }
.verdict.win { color: #0a7d33; } .verdict.draw { color: #b8860b; }
.dtm { font-size: .95rem; color: #444; margin: .25rem 0 .7rem; min-height: 1.2em; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
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:disabled { opacity: .5; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }
.log { font: 13px ui-monospace, monospace; color: #555; white-space: pre-line; line-height: 1.5; }

// Code not found

Click Best move and the engine always picks a move that mates in the fewest moves — never wandering, never stalling. That is what a solved ending means: there is nothing to calculate at the board, only a perfect answer to look up. Press New position to drop the kings somewhere else and watch the verdict update instantly.

How do you solve an ending? You work backwards — a technique called retrograde analysis.

• Start from the end. List every checkmate position. Those are wins in zero moves.
• Step back one move. Any position from which the winning side can reach a known win is a win; mark its distance to mate. Any position where every move only leads to wins for the opponent is a loss.
• Repeat until nothing changes. When the labels stop spreading, every position with that piece set is tagged win, draw or loss, with exact distance.

This was solved long ago and steadily extended: Thomas Ströhlein computed the first endgames in 1970; Ken Thompson published five- and six-piece tablebases in the 1980s–1990s; and the Lomonosov (2012) and Syzygy (complete by 2018) projects finished all seven-piece endgames. The eight-piece frontier is still being computed — the tables grow enormous fast.

The catch is scale. The full game of chess is EXPTIME-complete (proven for the n×n generalization by Fraenkel and Lichtenstein, 1981), so solving it from the opening is hopeless. Tablebases win only because the endgame shrinks the board to a tractable handful of pieces — the same wall that makes chess intractable in general is exactly what they sidestep.

"Work backwards from the goal until every state is labeled" is a pattern far bigger than chess:

• Perfect endgame play: every serious chess engine consults tablebases, turning approximate evaluation into certainty once few pieces remain.
• Solving whole games: the same backward sweep, scaled up, let Jonathan Schaeffer's team solve checkers in 2007 — proving the game is a draw with perfect play.
• Study and theory: tablebases have overturned human endgame "wisdom," revealing forced wins that take hundreds of moves and exposing positions no one believed were winnable.
• Formal verification: backward-reachability — "from which states can a bad state be reached?" — is exactly how model checkers verify hardware and protocols.

Understand retrograde analysis and you've met backward reachability, the engine behind solved games and the cousin of the search at the heart of chess and the broader question of P vs NP.

Chess as a whole may never be solved, but its endings already are. By marching backwards from checkmate, retrograde analysis hands us a complete oracle for every position with up to seven pieces: win, draw or loss, with the exact number of moves to the end.

It is a rare and beautiful thing in this field — a hard problem with a finished answer. The intractable wall of full chess is still there, but in the endgame we have climbed all the way over it, and on the other side every move has a perfect reply waiting in a table.