Implementing Bitboards: a Discussion about Optimization of Chess Engines
If you've ever played chess somewhat seriously, you've probably noticed that engines rule the world of chess. Every serious player relies on them to perform at least some form of analysis on their own games, the top players use them religiously to train, and it seems like every player has had at some point in their life one of those boards where you can play against a computer.
There was always something magical about those engines (at least as a kid). Even now that I know a thing or two about computers, I've always wondered how engines could look at thousands of positions in an instant and always give a somewhat accurate assessment of the position. Well, after a thorough investigation of the Chess Programming Wiki, I have put together at least some parts of this puzzle.
To keep it simple, engines can be decomposed into 3 modules:
- Move generation
- Search
- Evaluation
Each module offers many opportunities for optimization and clever algorithms, but as I was interested in possibly building an engine from the ground up, I had to look up first how to represent a chess position and how to navigate from one position to another. Thus, I naturally explored how to generate moves.
Move generation may be the most critical module of an engine. If it takes too long to generate all the possible moves from a given position, it will be hard for the engine to 'see' very far ahead, and I would be very limited with my 'time budget' to give an accurate evaluation of the position. For those not so familiar with chess, time is of the essence: each player has limited time to make their move, ranging from less than a second to possibly an hour or more. Even if there is no time constraint, waiting all day long for your opponent to make a move doesn't make for a very fun activity.
Unsurprisingly, this problem has been solved a long time ago, and while there are quite a few ways to generate moves and represent a position, one solution seems to stand above all else: bitboards.
A bitboard is simply a 64-bit integer (preferably unsigned), where each bit represents a square of the chessboard. A one-bit could signify the presence of a piece on a certain square, while a zero-bit means that the square is not occupied. This seems like a match made in heaven, as there are exactly 64 squares on a chessboard. Unfortunately, we cannot just use a simple bitboard for everything as we lose too much information. At a minimum, we have to use 12 bitboards, one for each piece type, and we multiply that by 2 to differentiate between black and white. As we'll see later, bitboards can be used to do much more than just store the position of a piece, and we'll need way more than 12 bitboards.
Now, if we look at the bitboard for white knights, we'd have an integer where the position of one-bits denotes the position of our knights. For instance, if we decide to read a chess board from left to right, top to bottom (i.e., the first bit is for the a8 square, and the last bit is for h1), the integer 00 00 00 00 00 04 00 40 (I will use hexadecimal to keep things manageable) would represent the following:
Bitboards have one key advantage over other solutions: doing operations on them is very fast because we're just doing a lot of bit manipulation. We can leverage the fact that we're dealing with a 64-bit integer to make things quite fast. Now, let's keep the position of our knights in mind and see how we could generate some moves. First, we will pick a direction where we want to move, let's say down and to the left (from e5 to g4 for instance).
We have to look at the bitboard containing our knights, and we first have to filter out the knights that cannot do this maneuver. For this, we have to eliminate all the knights that may be on the first rank, and all the knights that are on the g- and h-file. Doing so is actually quite intuitive; we can use a bitboard that represents the first rank (i.e., a bitboard where the last 8 bits are all one-bits), and bitboards that represent the g- and h-file. Then, we do an 'and' operation on all of these boards, we apply the 'not' operation, and we do an 'or' between the resulting bitboard and the botboard containing our knights. This should give us a board board1 where only our knight on f3 remains. Finally, we can shift all the bits from board1 to the right 10 times to get the landing square for our knight.
Now let's imagine that this is the complete position:
It is actually not too hard to see that our knight on f3 can only move to h2 under 2 conditions:
- The square is available
- The white king cannot be captured in the next move by black
For simplicity's sake, I will only check the first condition. The case of the knight is actually very easy to compute, we just have to make sure that the landing square is not occupied by either a white piece or the black king (in chess, capturing the enemy king is not allowed). To do so, we can 'and' all the bitboards that contain white pieces together with the bitboard that has the position of the black king. Then, we can apply the 'not' operator on this result that we will call board2.
Finally, computing board1 and board2 gives us all the moves that our knights can do in this specific direction.
In the end, we've only had to do about 10 bitwise operations to compute this result, and doing this 8 times gives us all the possible moves that our knights can do.
Now, it seems like the problem is nearly solved, and we can generate all the possible moves in a given position, but there is still one last issue: how can we generate the moves for the sliding pieces (i.e., bishops, rooks and queens)?
Let's first take a look at how to compute the horizontal moves for a rook to get an intuition on how to proceed:
Here, we can see that our rook on e5 can move to c5, d5 and f5. To make our life easier, let's perform some right shifts, such that the fifth rank is pushed at the bottom of our bitboard. Now, we know that our rook is on e5, and if we encode the position of all the other pieces on the same rank as a one-bit, we get an 8-bit integer that gives us the state of the rank. We can then use a lookup table, using the e5 square and our 8-bit integer as indexes, to get a pre-computed bitboard that gives us all the potential moves that our rook can do. (in this case, the bitboard will have ones in the squares c5, d5, f5 and g5)
Now, because we didn't differentiate between the white and black pieces, we have to perform an additional operation to eliminate the g5 square, but this should be trivial.
The problem now is that treating files is not as straightforward, but we still have another trick up our sleeve: rotated bitboards! Basically, we rotate our bitboard by 90° and we do what we just did, then we inverse the rotation to get all the possible veritcal moves.
The algorithm for doing a rotation is, unfortunately, quite mysterious (but it looks really fast!):
public static long mirrorHorizontal(long bitBoard) {
final long k1 = 0B0101010101010101010101010101010101010101010101010101010101010101L;
final long k2 = 0B0011001100110011001100110011001100110011001100110011001100110011L;
final long k4 = 0B0000111100001111000011110000111100001111000011110000111100001111L;
long mirroredBBoard = ((bitBoard >>> 1) & k1) | ((bitBoard & k1) << 1);
mirroredBBoard = ((mirroredBBoard >>> 2) & k2) | ((mirroredBBoard & k2) << 2);
mirroredBBoard = ((mirroredBBoard >>> 4) & k4) | ((mirroredBBoard & k4) << 4);
return mirroredBBoard;
}
public static long flipDiagA8H1(long bitBoard) {
final long k1 = 0B1010101000000000101010100000000010101010000000001010101000000000L;
final long k2 = 0B1100110011001100000000000000000011001100110011000000000000000000L;
final long k4 = 0B1111000011110000111100001111000000001111000011110000111100001111L;
long flippedBoard = bitBoard;
long temp = bitBoard ^ (bitBoard << 36);
flippedBoard ^= (k4 & (temp ^ (bitBoard >>> 36)));
temp = k2 & (flippedBoard ^ (flippedBoard << 18));
flippedBoard ^= temp ^ (temp >>> 18);
temp = k1 & (flippedBoard ^ (flippedBoard << 9));
flippedBoard ^= temp ^ (temp >>> 9);
return flippedBoard;
}
public static long rotate90cc(long bitBoard) {
return BitBoardUtility.mirrorHorizontal(BitBoardUtility.flipDiagA8H1(bitBoard));
}Dealing with bishops is trickier. The bitboard has to be rotated by 45°, meaning that, if we rotate clockwise, the last bit represents the h1 square, the next two bits represent the g1-h2 diagonal, the next 3 will be the f1-h3 diagonal and so on...
Then the same technique can be applied, push the diagonal that we're interested in to the bottom, and use a lookup table to get the squares that we can attack.
Because the queen combines both the bishop and the rook, the same techniques can be applied to it.
Going further
Of course, we can push optimization a bit further. Nowadays, most of the state-of-the-art engines (including Stockfish) use magic bitboards. The basic idea is that we use a hashing function on our board and then we use that as an index to find the possible moves in a big table. The name comes from the fact that hashing requires some kind of magic number. This technique is supposedly faster by about 20%, as there are fewer computations. We could also use precomputed tables to get all the possible moves for a knight given its starting square (this saves us the trouble of filtering out the wrong knights and doing right and left shift operations).
I could only go so far in such an article, but I would encourage anyone that is interested to look up the Chess Programming Wiki, this video and its sequel to get a deeper understanding of how everything is tied up together.