Bitboards: A New Approach

P. San Segundo and R. Galán (Spain)


Knowledge representation, heuristic search, domain modelling, planning, artificial intelligence


A bitboard is essentially an unsigned integer whose bits have an underlying semantics. Originally developed for chess applications in the late 1960s its main use has lingered in that domain, a typical 64-bit bitboard encoding a particular condition of the 64 squares of the chessboard in a given position. In this paper we propose a completely new approach, in the belief that the obvious advantages of these dense structures can make themselves felt in AI domains. For that purpose we formalise bitboard encoding for simple propositional domains and include specific extensions for quantitative predicates and enumerable sets of simple logical propositions. We also deal briefly with complexity issues over information extraction, a cornerstone for bitboard architectures, showing that the modulus operator (%) allows tabulating knowledge for finding 1-bits in a very efficient and practically no space consuming way. We sincerely hope that this paper brings renewed interest in bitboards as a very powerful tool for modelling AI domains.

Important Links:

Go Back