MOVE GENERATION WITH PERFECT HASH FUNCTIONS

Article type: Research Article

Authors: Fenner, Trevor | Levene, Mark¹

Affiliations: London, U.K.

Note: [1] School of Computer Science and Information Systems, Birkbeck College, University of London, London WC1E 7HX, U.K. Email: {trevor,mark}@dcs.bbk.ac.uk

Abstract: We present two new perfect hashing schemes that can be used for efficient bitboard move generation for sliding pieces in chess-like board games without the need to use rotated bitboards. Moreover, we show that simple variations of these schemes give minimal perfect hashing schemes. The new method is applicable provided N, the number of k-bit spaced positions that may be set to 1, is not more than k + 1. In chess, for a Rook’s movement along a file N = k = 8; for a Bishop’s movement N ≤ 8, and k = 9 for a north-east diagonal and k = 7 for a north-west diagonal. The results of computational experiments comparing the efficiency of move generation with the standard method show that using the hashing scheme gives an average improvement of approximately 40%. The schemes we suggest are simple, efficient, and easy to understand and implement.

DOI: 10.3233/ICG-2008-31102

Journal: ICGA Journal, vol. 31, no. 1, pp. 3-12, 2008