Move Generation for Chess Engines
I've always enjoyed playing chess, and after watching this video, I got hooked on the idea of building my own engine. I originally started one in Java, but that project fizzled out. Recently, I’ve reengaged with the idea—this time in C++ using bitboards.
Along the way, I’ve found the process incredibly fascinating and educational. I also came up with a clever hybrid approach for generating moves for sliding pieces. It’s not instant like a full magic bitboard solution, but it’s pretty close.
I did however, in my research, manage to (unsurprisingly) find an even better method without touching magic bitboards. If you'd like, you can check that out as well here. With that said, this is my old implementation :)
Board Representation
I'm not sure if you watched the above video, but in case you didn't, a common way of representing a chess board programatically is to use a 64 bit integer due to the fact that a chess board has 64 squares (8x8).
- Binary
// 64 bits or in our case, a programatic representation of a chess board
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 0 0 0 0 0 0
0 0 0 0 0 0 0 0
On top of having 64 bits, we could think of each bit as having an index between 0 and 63:
- Binary
56 57 58 59 60 61 62 63
48 49 50 51 52 53 54 55
40 41 42 43 44 45 46 47
32 33 34 35 36 37 38 39
24 25 26 27 28 29 30 31
16 17 18 19 20 21 22 23
8 9 10 11 12 13 14 15
0 1 2 3 4 5 6 7
That means that if we wanted to place a pawn on square 35 for example, we would flip bit 35 to 1:
- Chess
// Our bit representation of a pawn on square 35
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 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
Pretty straight forward right? I don't want to dig into the logistics of board representation in this post too much. I moreso wanted to focus on move generation, and with that--move generation for sliding pieces.
Almost "magic" bit boards
The thing with chess engine is that you want it to be fast. At the end of the day, the thing has to evaluate millions of positions in fractions of a second. Thankfully, bitwise operations are about as fast as it gets in terms of performance. But that raises the issue: "How do we avoid for loops when generating moves for sliding pieces?" In other words, how can we slide a piece down it's path, and using only bitwise operations, ensure that we stop at the first blocking piece?
Now there are magic bitboards. Then there's for looping however there is a third less talked about hybrid approach that I've begun to implement and I think is pretty crafty.
Take the following board position into consideration:
- Chess
// Pieces -> P: Pawn, R -> Rook
. . . P . . . .
. . . . . . . .
. . . . . . . .
. . . R . . P .
. . . P . . . .
. . . P . . . .
. . . . . . . .
. . . . . . . .
// Or our bitboard
. . . 1 . . . .
. . . . . . . .
. . . . . . . .
. . . 1 . . 1 .
. . . 1 . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
Note* For reference, throughout the rest of the post, I'm not going to include friendly pieces I will discuss friendly pieces at the end.
First thing we can do is pre generate all the possible moves depending on which square we're on and the direction IE North, East, South, and West. If we were on square 35 for example, the 4 different boards would look like this:
- Chess
// North
. . . 1 . . . .
. . . 1 . . . .
. . . 1 . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
// East
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . 1 1 1 1
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
// South
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . 1 . . . .
. . . 1 . . . .
. . . 1 . . . .
. . . 1 . . . .
// West
. . . . . . . .
. . . . . . . .
. . . . . . . .
1 1 1 . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
And then if we had a rook on square 35, we could combine all of them to get all of our possible moves:
- Chess
// Rook moves in rookmoves[35]
. . . 1 . . . .
. . . 1 . . . .
. . . 1 . . . .
1 1 1 R 1 1 1 1
. . . 1 . . . .
. . . 1 . . . .
. . . 1 . . . .
. . . 1 . . . .
// Rook moves in rookmoves[60]
1 1 1 1 . 1 1 1
. . . . 1 . . .
. . . . 1 . . .
. . . . 1 . . .
. . . . 1 . . .
. . . . 1 . . .
. . . . 1 . . .
. . . . 1 . . .
Now that we've gone through, what we can do is we can take our rooks pre-generated moves, get the bitboard for square 35, and & bitwise operate them with our opponents pieces. This means that we get all of the blocking pieces on our rays:
- Chess
// Blocking pieces
. . . 1 . . . .
. . . . . . . .
. . . . . . . .
. . . . . . 1 .
. . . 1 . . . .
. . . 1 . . . .
. . . . . . . .
. . . . . . . .
The "magic" part in my opinion is that with this information alone, we can actually perform a bitwise operation to determine what the closest piece is. To make this a little easier to visualize, take our original 64 bit integer and flatten it out, and seperate the blocking pieces for each direction:
- Chess
// North blocking pieces
. . . 1 . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
// Flattened
. . . 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
// East blocking pieces
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . 1 .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
// Flattened
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
// South blocking pieces
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . 1 . . . .
. . . 1 . . . .
. . . . . . . .
. . . . . . . .
// Flattened
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . . 1 . . . . . . . . . . . . . . . . . . . .
// West blocking pieces
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
// Flattened
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Specifically with the "South blocking pieces", you can see that if we want to get the first blocker. All we really need to do is get the left most bit. However with the North direction it's flipped. We actually want to get the right most bit.
Once we have the left most and right most bits, we can create a mask to mask out the correct section of the 64 bit int to effectively remove squares that we can't actually travel to. The flow would look a little something like this:
- Chess
// South blocking pieces
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . 1 . . . .
. . . 1 . . . .
. . . . . . . .
. . . . . . . .
// Original generated moves for south
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . 1 . . . .
. . . 1 . . . .
. . . 1 . . . .
. . . 1 . . . .
// Flattened blockers
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . . 1 . . . . . . . . . . . . . . . . . . . .
// Flattened original
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . .
// Mask using left most bit
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
// & mask and original moves
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
// Board for legal moves
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . 1 . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
Badda bing bada boom. Just like that, using nothing but bitwise operations, we can calculate moves near instantly. Now it's not quite as quick as a magic bitboard per se, but it is significantly faster than a for loop. Now with that said, you would also do the exact same thing for friendly pieces. The only difference is that depending on the direction, you'll have to shift the bit 1 square closer to the piece by 8 bits for example if you were on a north or south ray. And then either 1 for east and west rays, 7 for NE/SE and 9 for NW/SE.