Introduction

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.

The Perfect Move

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">White (king + rook) always mates a lone Black king. The page builds a
real <b>endgame tablebase</b> by retrograde analysis, so it knows every position's
<b>distance to mate</b>. Click <b>Best move</b> to see perfect play, or
<b>New position</b> to try another setup.</p>
<div id="wrap">
  <div id="board" class="board"></div>
  <div class="side">
    <div class="verdict" id="verdict">Building tablebase…</div>
    <div class="dtm" id="dtm"></div>
    <div class="btns">
      <button id="best" type="button" disabled>Best move</button>
      <button id="reset" type="button" class="ghost">New position</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* ── A real King+Rook vs King endgame tablebase, built in the browser by
   retrograde analysis. Every position gets a verdict (win / draw) and the
   exact distance to mate. White (K+R) to move always wins this material.
   KRK is solved: max distance to mate is 16 moves. (Ströhlein 1970.) */
const N = 8;
const sq = (r, c) => r * 8 + c;
const rc = s => [Math.floor(s / 8), s % 8];
const FILES = 'abcdefgh';
const nm = s => FILES[s % 8] + (Math.floor(s / 8) + 1);
const adj = (a, b) => { const [r1,c1]=rc(a),[r2,c2]=rc(b); return Math.max(Math.abs(r1-r2),Math.abs(c1-c2))<=1; };
function kMoves(s){ const [r,c]=rc(s),o=[]; for(let dr=-1;dr<=1;dr++)for(let dc=-1;dc<=1;dc++){ if(!dr&&!dc)continue; const nr=r+dr,nc=c+dc; if(nr>=0&&nr<N&&nc>=0&&nc<N)o.push(sq(nr,nc)); } return o; }
function rMoves(s,occ){ const [r,c]=rc(s),o=[]; const D=[[1,0],[-1,0],[0,1],[0,-1]]; for(const [dr,dc] of D){ let nr=r+dr,nc=c+dc; while(nr>=0&&nr<N&&nc>=0&&nc<N){ const t=sq(nr,nc); o.push(t); if(occ.has(t))break; nr+=dr; nc+=dc; } } return o; }
function legalPos(wk,wr,bk){ return wk!==wr && wk!==bk && wr!==bk && !adj(wk,bk); }
// does the rook attack square `t`? white king can block; (black king is assumed off `t`)
function rookAttacks(wr,t,wk){ const [rr,rcc]=rc(wr),[tr,tc]=rc(t);
  if(rr!==tr && rcc!==tc) return false;
  if(rr===tr){ const lo=Math.min(rcc,tc),hi=Math.max(rcc,tc); for(let c=lo+1;c<hi;c++) if(sq(rr,c)===wk) return false; }
  else { const lo=Math.min(rr,tr),hi=Math.max(rr,tr); for(let r=lo+1;r<hi;r++) if(sq(r,rcc)===wk) return false; }
  return true; }
// black king moves; [-1, dest] = captures the (undefended) rook -> draw
function blackMoves(wk,wr,bk){ const o=[];
  for(const nb of kMoves(bk)){ if(nb===wk||adj(nb,wk))continue;
    if(nb===wr){ o.push([-1,nb]); continue; }
    if(rookAttacks(wr,nb,wk))continue;
    o.push([wr,nb]); }
  return o; }
function whiteMoves(wk,wr,bk){ const o=[],occ=new Set([wk,wr,bk]);
  for(const nk of kMoves(wk)){ if(nk===wr||nk===bk||adj(nk,bk))continue; o.push([nk,wr]); }
  for(const nr of rMoves(wr,occ)){ if(nr===wk||nr===bk)continue; o.push([wk,nr]); }
  return o; }

const id = (wk,wr,bk,t) => ((wk*64+wr)*64+bk)*2 + t;       // t: 0=White to move, 1=Black to move
const DTM = new Int16Array(64*64*64*2);
const LEGAL = [];
for(let wk=0;wk<64;wk++)for(let wr=0;wr<64;wr++)for(let bk=0;bk<64;bk++) if(legalPos(wk,wr,bk)) LEGAL.push([wk,wr,bk]);

// ── Retrograde analysis: start at checkmate (distance 0), propagate outward. ──
function build(){ DTM.fill(-1);
  for(const [wk,wr,bk] of LEGAL) if(rookAttacks(wr,bk,wk) && blackMoves(wk,wr,bk).length===0) DTM[id(wk,wr,bk,1)]=0;
  let changed=true;
  while(changed){ changed=false;
    for(const [wk,wr,bk] of LEGAL){ const i=id(wk,wr,bk,0); if(DTM[i]>=0)continue;
      let best=9999;
      for(const [a,b] of whiteMoves(wk,wr,bk)){ if(!legalPos(a,b,bk))continue; const v=DTM[id(a,b,bk,1)]; if(v>=0)best=Math.min(best,v+1); }
      if(best<9999){ DTM[i]=best; changed=true; } }
    for(const [wk,wr,bk] of LEGAL){ const i=id(wk,wr,bk,1); if(DTM[i]>=0)continue;
      const bm=blackMoves(wk,wr,bk); if(!bm.length)continue;
      let worst=-1,all=true;
      for(const [nwr,nb] of bm){ if(nwr<0){ all=false; break; } const v=DTM[id(wk,nwr,nb,0)]; if(v<0){ all=false; break; } worst=Math.max(worst,v); }
      if(all && worst>=0){ DTM[i]=worst; changed=true; } } }
}
const dtmWTM = (wk,wr,bk) => DTM[id(wk,wr,bk,0)];
function bestWhite(wk,wr,bk){ let best=null,bv=9999;
  for(const [a,b] of whiteMoves(wk,wr,bk)){ if(!legalPos(a,b,bk))continue; const v=DTM[id(a,b,bk,1)];
    if(v>=0 && v<bv){ bv=v; best=[a,b]; } }
  return best?{wk:best[0],wr:best[1],dtm:bv}:null; }
function bestBlack(wk,wr,bk){ let best=null,bv=-1;       // Black defends: drag the mate out as long as possible
  for(const [nwr,nb] of blackMoves(wk,wr,bk)){ if(nwr<0)continue; const v=dtmWTM(wk,nwr,nb);
    if(v>bv){ bv=v; best=[nwr,nb]; } }
  return best?{wr:best[0],bk:best[1],dtm:bv}:null; }

// ── State + rendering ──
let pos = { wk: sq(2,4), wr: sq(0,0), bk: sq(6,4) };   // wKe3, Ra1, bKe7 (a mate in 11)
const $ = i => document.getElementById(i);
function render(){
  const b=$('board'); b.innerHTML='';
  for(let r=7;r>=0;r--)for(let c=0;c<8;c++){ const s=sq(r,c);
    const d=document.createElement('div'); const light=(r+c)%2===0;
    d.className='sq '+(light?'light':'dark');
    if(s===pos.wk)d.textContent='♔'; else if(s===pos.wr)d.textContent='♖'; else if(s===pos.bk)d.textContent='♚';
    b.appendChild(d); }
}
function status(){
  const v=dtmWTM(pos.wk,pos.wr,pos.bk);
  const vd=$('verdict'), dt=$('dtm');
  if(v>=1){ vd.textContent=`WIN for White`; vd.className='verdict win';
    dt.textContent=fmt(`Distance to mate: %v%%v2%`, { v: v, v2: v===1?' move':' moves' }); $('best').disabled=false; }
  else if(v===0){ vd.textContent=`Checkmate — White wins`; vd.className='verdict win';
    dt.textContent=`Distance to mate: 0`; $('best').disabled=true; }
  else { vd.textContent=`Draw (rook just hangs / stalemate)`; vd.className='verdict draw';
    dt.textContent=`No forced mate from here`; $('best').disabled=true; }
}
function bestMove(){
  const w=bestWhite(pos.wk,pos.wr,pos.bk); if(!w)return;
  const from = w.wk!==pos.wk ? fmt(`K%nm%→%nm2%`, { nm: nm(pos.wk), nm2: nm(w.wk) }) : fmt(`R%nm%→%nm2%`, { nm: nm(pos.wr), nm2: nm(w.wr) });
  pos.wk=w.wk; pos.wr=w.wr; render();
  // mate?
  if(DTM[id(pos.wk,pos.wr,pos.bk,1)]===0){ $('log').textContent=fmt(`White: %from%  — checkmate!`, { from: from }); status();
    console.log(`Mate! Tablebase distance was 0 after`,from); return; }
  // Black plays its best (longest) defence
  const blk=bestBlack(pos.wk,pos.wr,pos.bk);
  let line=fmt(`White: %from% (mate in %dtm%)`, { from: from, dtm: w.dtm });
  if(blk){ pos.bk=blk.bk; line+="\n" + fmt(`Black: K…→%nm%`, { nm: nm(blk.bk) }); }
  render(); status(); $('log').textContent=line;
  console.log(line.replace('\n',' | '));
}
function randomWin(){
  let wk,wr,bk;
  do{ wk=Math.floor(Math.random()*64); wr=Math.floor(Math.random()*64); bk=Math.floor(Math.random()*64); }
  while(!legalPos(wk,wr,bk) || dtmWTM(wk,wr,bk)<2 || dtmWTM(wk,wr,bk)>14);
  pos={wk,wr,bk}; render(); status(); $('log').textContent='';
}
$('best').addEventListener('click',bestMove);
$('reset').addEventListener('click',randomWin);

// Build off the main thread feel: render board first, then compute.
render();
setTimeout(()=>{ const t0=Date.now(); build();
  console.log(`Tablebase built in`,Date.now()-t0,`ms over`,LEGAL.length,`legal positions`);
  status(); $('best').disabled=false; $('log').textContent=`Tablebase ready. White: K+R, Black: lone king.`; }, 30);
Result
Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

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

Comments

Loading comments...

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