USING BITBOARDS FOR MOVE GENERATION IN SHOGI

Article type: Research Article

Authors: Grimbergen, Reijer¹

Affiliations: Yamagata, Japan

Note: [1] Department of Informatics, Yamagata University, Yamagata, Japan. Email: grim@yz.yamagata-u.ac.jp

Abstract: In this paper it will be explained how to use bitboards for move generation in shogi. In chess, bitboards have been used in most strong programs because of the easy representation of a chess board by a single 64-bit integer. For shogi, a less efficient representation has to be used because a shogi board has 81 squares instead of 64. A representation with an array of three integers is proposed, where each integer represents 27 squares of the board. This representation is then used for move generation in a similar way to the methods used in chess, for example by using rotated bitboards for generating the moves of the sliding pieces Rook and Lance. For generating the moves of the Bishop, rotated bitmaps are not completely satisfactory and a different method using the alignment of diagonals is proposed for move generation. A comparison of the move-generation speed between using bitboards and the more common method of using attack tables showed that even without using hardware-dependent optimizations the move-generation speed of the shogi program SPEAR using bitboards was more than 40% faster than the move generation using attack tables.

DOI: 10.3233/ICG-2007-30103

Journal: ICGA Journal, vol. 30, no. 1, pp. 25-34, 2007