LARGE ENDGAME DATABASES WITH LIMITED MEMORY SPACE

Article type: Research Article

Authors: Lincke, Thomas R.^{; 1} | Marzetta, Ambros^{; 2}

Affiliations: Zürich, Switzerland

Note: [1] ETH Zürich, CH-8092 Zürich. Email: thomas.lincke@inf.ethz.ch.

Note: [2] AWK Engineering AG, CH-8050 Zürich. Email: ambros.marzetta@inf.ethz.ch.

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.

DOI: 10.3233/ICG-2000-23302

Journal: ICGA Journal, vol. 23, no. 3, pp. 131-138, 2000