Endgame Databases and Efficient Index Schemes for Chess

Article type: Research Article

Authors: Heinz, E.A.^{a; 1}

Affiliations: [a] Karlsruhe, F.R. Germany

Note: [1] Institute for Program Structures and Data Organization (IPD), School of Computer Science, University of Karlsruhe, P.O. Box 6980, D-76128 Karlsruhe, F.R. Germany. Email: heinze@ira.uka.de. WWW=http://wwwipd.ira.uka.de/~heinze/.

Abstract: Endgame databases have become an integral part of modem chess programs during the past few years. Since the early 1990s two different kinds of endgame databases are publicly available, namely Edwards’ so-called tablebases and Thompson’s collection of 5-piece databases. Although Thompson’s databases enjoy much wider international fame, most current chess programs use tablebases because they integrate far better with the rest of the search. For the benefit of all those enthusiasts who intend to incorporate endgame databases into their own chess programs, this note describes the index schemes of Edwards’ tablebases and Thompson’s databases in detail, explains their differences, and provides a comparative evaluation of both. In addition we introduce new indexing methods that improve on the published state of the art and shrink the respective index ranges even further (especially for large databases and endgames with Pawns). This reduces the overall space requirements of the resulting databases substantially. We also propose several solutions for the problem of potential en-passant captures in endgame databases with at least one Pawn per side. Shortly after the initial submission of our original text for this note, Nalimov independently applied similar techniques as ours and even more advanced index schemes to his new tablebases which are now publicly available on the Internet, too. We briefly put his work into perspective as well.

DOI: 10.3233/ICG-1999-22104

Journal: ICGA Journal, vol. 22, no. 1, pp. 22-32, 1999