Abstract
In awari, a larger endgame database improves the playing strength of a game engine significantly, since even shallow searches reach positions where many stones have been captured. For example, in more than 15 percent of the positions reached by an 18-ply search from the start position, 14 or more of the 48 stones have already been captured.
It is unfortunate that (1) awari databases are large compared to today’s main memory sizes (the 36-stone database requires 17.5 GBytes), and (2) conventional database-calculation algorithms access the database in a non-local fashion, so that caching becomes useless and disk I/O becomes the bottleneck of the calculation.
In this paper we present a disk-I/O-efficient algorithm for awari endgame-database construction requiring one bit per position in main memory. Then we refine the algorithm by introducing a dual indexing scheme which increases disk-access locality and improves caching performance, so that even larger databases can be calculated.
With these algorithms, we calculated all databases up to the 35-stone database (13.5 GBytes) on a 1 GByte machine. The 36-stone (17.5 GBytes) and 37-stone databases (22.5 GBytes) are under construction.
Get full access to this article
View all access options for this article.