Exhaustive and Heuristic Retrograde Analysis of the KPPKP Endgame

Article type: Research Article

Authors: Wirth, C. | Nievergelt, J.^{; 1}

Affiliations: Zürich, Switzerland

Note: [1] ETH Zürich, Institute für Theoretische Informatik, CH-8092 Zürich, Switserland. Email: wirthc@inf.ethz.ch, jn@inf.ethz.ch.

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.

DOI: 10.3233/ICG-1999-22202

Journal: ICGA Journal, vol. 22, no. 2, pp. 67-80, 1999