Bitboards
(aka bitmaps)
Introduction and some History
Manipulating Bitboards
Move Generation using Bitboards
How Djinn Utilizes Bitboards
Introduction and some History
Bitboards
are all the rage these days thanks to Robert Hyatt and his open-source
program Crafty. Aspiring chess programmers are bombarded with the
term, but it's
rarely explained. Discussions on rotated
bitboards only exacerbate the situation, since they are even less
understood than plain vanilla bitboards. Before we delve too
deeply into the technical aspects of bitboards (or bitmaps as they are
often called) we should review a bit of their history. It's widely accepted that Kaissa, a Russian chess
program circa. 1977, was the first bitboard-based program.
David Slate and Lawrence Atkin, of Chess 4.5 fame, discovered the idea
independently while at Northwestern University.
Fundamentally, bitboards are
nothing more than a
different way to represent the chess board (i.e. an alternative
data representation). What makes them intriguing, is the unique
way they take advantage of the modern computer's architecture.
Without getting too technical, all computers are based on the binary or
base 2
numbering system. For comparison, the mathematics we use in our
everyday lives, is a decimal system or base 10 (not coincidentally,
derived from the fact that we have 10 fingers to count on).
Unlike a decimal number, which can assume 10 distinct values, a binary number can assume only one of two
states, either 1 or 0. Like a light switch, it is either on or
off. These individual binary switches are referred to as "bits". For convenience, bits
are grouped into bytes and words of length 8 and 32 respectively.
It is possible for the length of a byte or word to vary, but most architectures stick with a length of 8 and 32.
Computers support boolean operations
and logic. Boolean logic is named after its inventor,
George Boole
who was born Nov. 2, 1815 in Lincolnshire, England (long before the
first digital computer was a gleam in anyone's eye)! If you'll
bear with me a bit I'll explain why we care about George Boole and his
slightly odd logic. Boolean logic supports a number of
fundamental operations which operate
very nicely on the binary bits of a computer. The most important
operations are logical AND, OR and XOR. Rather than using words
to describe their operation, mathematicians and engineers use a diagram
known as a truth table, shown below (note, A and B are the
two input bits that we are performing the boolean operation on).
A
|
B
|
AND
|
OR
|
XOR
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
What this is telling us is that if we apply the logical AND
operation to two bits the result is 0 unless both bits are 1.
Conversely, if we apply the logical OR operation to two bits the result
is 1 if either bit is set to 1. Finally, the XOR operation tells
us that one, but not both bits must be set to a 1 if we want a 1.
The XOR
operator has the interesting and useful property that if it is applied
twice we get back the original number. We'll take advantage of
this property later when we examine the operation of the program's hash
table. The last boolean operation that we need is the NOT
operator (represented by the '~' tilde symbol). A logical NOT, or
complement, of a byte or word inverts the individual bits of the
value. For example, 10010111 complemented would be 01101000.
Bitboards
take advantage of the serendipitous fact that a chess
board is composed of 64 squares, which is a multiple of eight.
Utilizing this bit of luck, it is possible to represent the state of
the
chess board using a set of bitboards. For example, a bitboard
representing the location of all the pieces on their original squares
would look like this internally.
11111111
11111111 00000000 00000000 00000000 00000000 11111111 1111111
Granted this is a bit
obtuse, but the computer has no problem
understanding it. Reformatting the bitboard makes clear the
relationship between the pieces and the individual bits.
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
|
Another example of information that could be stored is "...all the
squares attacked by a white knight on D4".
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
In truth, the type of
information that can be represented is only limited by the
programmer's imagination. As you become more comfortable
with bitboards, novel and interesting ways of using them will become
readily apparent.
For example, Djinn regularly extracts the following types of information:
- Which enemy pieces are attacked by the side with the right to move?
- Which pawns can move to the 6th, 7th and 8th ranks?
- Which enemy pieces are in the same quadrant as the king?
- Is the king in the square of a passed pawn, etc.?
Modern
computers perform boolean logic exceedingly fast. The latest microprocessors from Intel and AMD can perform millions of boolean operations per
second! We can use these operators to quickly extract information
about the board and pieces. An example, if we have the following
two bitboards,
Bishop
attack from D5
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
0 |
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
|
|
Black pawns initial
position
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
| 1 |
1 |
1 |
1 |
1 |
1 |
1 |
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
we can quickly extract the black pawns subject to capture by the white
bishop by applying the AND operator. ANDing the two bitboards
produces a bitboard of all the black pawns under attack by the
bishop. We can use this information to generate the pawns subject to capture by the bishop.
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
Of course, the obvious and valid question is "... so what, how do I
extract this information?" That's the subject of the next section.
