Knowledgeable Encoding and Querying of Endgame Databases

Abstract

Modern chess programs quickly become I/O-bound if they probe their external endgame databases not only at the root node but also at interior nodes of the search tree. This tendency increases at faster search speeds if the I/O speed does not scale accordingly. Hence, the foreseeable trends in CPU and I/O technology will not improve the probing but rather aggravate it. Instead of resorting to “quick and dirty” fixes such as stopping the accesses at a specific depth, our chess program DARKTOUGHT probes its 3-piece and 4-piece endgame databases everywhere in the search tree at full speed without any I/O delays. It does so by loading the entire databases into the main memory of its host system.

To this end, we introduce a new domain-dependent encoding technique that reduces the space consumption of all 3-piece and 4-piece endgame databases to roughly 15 Mbytes overall. A-priori studies of Edwards’ publicly available distance-to-mate tablebases provided the necessary feedback for our so-called knowledgeable encoding. We rely on the algorithmic recognition of rare exceptional endgame positions in order to achieve a compact representation of the stored data. The knowledgeable approach enables chess programs to pre-load all 3-piece and 4-piece endgame databases even on cheap personal computers with low memory capacities starting at 32 MBytes of RAM.