VERIFICATION OF ENDGAME DATABASES

Abstract

This article studies the verification of endgame databases using algorithms with limited memory space. To verify a constructed endgame database, the value of each position is checked for consistency against the values of the successor positions. Hence, a trivial implementation of this algorithm needs to access the database content randomly. A graph-theoretical technique called vertex-partitioning is proposed to divide an endgame database into several partitions. The positions in a partition have the good property that their successor positions are all in a relatively small proportion of the created partitions. Therefore, only a small portion of the database needs to be loaded into the main memory at one time while verifying all positions in a partition. Performance results in verifying Chinese chess endgame databases using this method are given. Our technique is a generalization of previous approaches used in saving memory during the construction of endgame databases. The technique can be exploited, too, in other similar games, such as Western chess. Moreover, the technique can be applied to save the amount of memory used in the initialization phase of retrograde analysis when constructing endgame databases.