Note: [1] Hewlett-Packard Laboratories. 1501 Page Mail Road, Palo Alto, CA 94304-1126, USA. Email: ren_wu@hp.com.
Note: [2] Queen Mary and Westfield College, Mile End Road, London, El 4NS, England. Email: don@dcs.qmw.ac.uk.
Note: [3] For comparison, the same computation took about 92 hours on a Pentium Pro 200 PC with 128 MB of memory a few years back.
Abstract: In this paper, we discuss and compare algorithms used to generate endgame databases, focussing on resource consumption, particularly space requirements. We present a fast, memory-efficient retrograde algorithm that was used to generate Chinese-chess endgame databases. It only requires 1 bit per position of RAM, while still producing the full-depth information in the final file on disc. In comparison, earlier published algorithms need either a byte per position in RAM, produce only win/draw information, or slow down tremendously swapping parts of the data to and from disc. We compare and contrast algorithms published to date, based on their need for RAM, disc space and CPU time. As an indication of where the combination of algorithm improvements and hardware advances have now taken the state of the art, we give an example and some estimates. A pair of 10-pieces Chinese-chess endgame databases with size of 1GB each was constructed by this algorithm in about 13 hours on a 1GHz PIII machine with 256 MB memory3. The authors estimate that their algorithm makes it possible to produce a 5-men (western) chess endgame database in matter of hours on a similar desktop PC. The algorithm also makes it feasible to produce 6-men chess endgame databases on such hardware, assuming 20GB of available disk space.
DOI: 10.3233/ICG-2001-24303
Journal: ICGA Journal, vol. 24, no. 3, pp. 147-159, 2001
