Exhaustive and Heuristic Retrograde Analysis of the KPPKP Endgame

Abstract

Although the techniques for constructing chess endgame databases are well understood, it is a permanent challenge to extend the size of the endgames that can be computed with the resources currently available. Ken Thompson’s pioneering attack on 5-piece endgames was limited to those with at most one Pawn. Using our parallel retrograde analysis program RETROENGINE on a variety of hardware platforms, we have constructed all 111 databases necessary to compute the KPPKP endgame, i.e., King and two Pawns vs. King and Pawn.

Furthermore, we present a new approach called heuristic retrograde analysis that trades accuracy for space and time, i.e., it reduces the space and time needed to solve an endgame while accepting a small error rate. Experiments for the KPPKP endgame yielded reductions in the required space and time by factors of more than 50. The penalty incurred is that a (computer) player using the heuristic database plays suboptimally in less than 4 percent of the positions submitted.

The KPPKP database contains a wealth of interesting positions. We present 15 endgame studies of unconventional design and surprising difficulty.