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.
Get full access to this article
View all access options for this article.