Writing a Chess Engine: Move Generation
This is the first of a two-part article about my experience writing a chess engine from scratch. Generally speaking, a chess engine can be broken down into two separate components: a move generator which enumerates all possible moves for a given position and the actual brains of the engine which picks which move to make. Here I’ll talk in detail about the mechanics of move generation and why I think it’s so interesting.
I’ll start this article by saying that, at first glance, move generation doesn’t seem like a very interesting problem. I told one of my TAs that I was working on a chess engine and found move generation to be particularly interesting, to which they responded “don’t you just loop through all the pieces and make moves for them??”. This was my initial reaction too, but as we’ll soon see this is actually a very interesting problem that has lots of elegant and technically interesting solutions.
I’ve decided to write this engine in Rust - chess engines are computationally intensive applications which benefit from a systems-focused language. If you aren’t very familiar with Rust I recommend reading my previous post about The Rust Programming Language.
Board Representation
The first consideration when creating a move generator is deciding on a board representation. To the uninitiated this might seem like an obvious choice, no? If I were in a job interview and someone asked me to design a chess board class I would almost certainly have picked some sort of 2D array structure. After all, a chess board is an 8x8 grid. If you’re going to go this route, it would probably be more convenient to use a 1D array instead. The reason for this is it allows you to easily calculate moves for pieces by using offsets. For example, if you picked the A1 squre to be index 0 and A2 to be index 8 (using something called Little-Endian Rank-File mapping) then you could define a single pawn push by shifting the index by 8. Likewise, north west and north east pawn captures would shift the index by 7 and 9, respectively.
While such a solution is certainly viable there is in fact a more elegant solution - bitboards. The idea of a bitboard is simple, instead of using an array to represent the board we use a 64-bit unsigned-integer, which very conveniently has the same number of bits as there are squares on a chess board. We maintain a set of bitboards, one for each piece, where a 1 represents the presence of a piece at that square. So, for example, a bitboard representing the white pawns in the starting position would look like this (note that I’ve replaced 0’s with dots to improve readability)
W Pawns
........
........
........
........
........
........
11111111
........
We can calculate moves for a position by performing bitshifts on the bitboard. If we wanted to push all pawns forward one square, we could simply shift all bits left by 8
W Pawns
........ ........
........ ........
........ ........
........ << 8 = ........
........ ........
........ 11111111
11111111 ........
........ ........
Accounting for other pieces on the board is very simple. Suppose we had another bitboard which represented all empty squares on the board like so
Empty Squares
11111111
111.1111
11.....1
..1.....
11111.11
1111..11
........
11111111
Then we could find all pawn pushes in the current position by shifting our pawn bitboard to the left by 8 and taking the bitwise AND with our empty empty squares.
W Pawns Shifted Empty Pushed
........ ........ 11111111 ........
........ ........ 111.1111 ........
........ ........ 11.....1 ........
........ << 8 = ........ & ..1..... = ........
........ ........ 11111.11 ........
........ 11111111 1111..11 1111..11
11111111 ........ ........ ........
........ ........ 11111111 ........
Or, if you wanted to imagine it in pseudo-code
func generate_single_pawn_pushes(Board b):
let our_pawns = b.get_our_pawns()
let empty_squares = !b.get_all_pieces()
let pushed_pawns = (our_pawns << 8) & empty_squares
This code is beautifully simple and almost declarative in nature. It’s also very easy to apply certain filters and criteria when generating moves. If we wanted to change our function to exclude pawn promotions (perhaps we wanted to handle that logic separately) then we could simple change the first line and not grab pawns that are on the 7th rank.
...
let our_pawns = b.get_our_pawns() & !RANK7_BITBOARD;
...
The real advantage behind bitboards, however, is that most modern processors are able to perform bitwise operations in parallel. That means that we can generate a bitboard for all pawns in just one operation. Using an array we would have to iterate over the entire board, identifying each pawn and performing lookups to see if moves are valid.
Pseudo-Legal vs Legal Move Generation
Another consideration when creating a move generator is whether or not you want to generate strictly legal moves or pseudo-legal moves. In the world of chess programming, the set of pseudo-legal moves is defined as a subset of legal moves where the only difference is that some moves might leave your king in check. Writing a legal move generator is more challenging than writing a pseudo-legal move generator since it requires identifying what pieces are pinned and moving them in such a way that they don’t leave your king in check. Some chess engines avoid legal move generation by deferring legal move checking until the next phase of the engine - picking a move. The idea there is that each position is assigned a value which represents how strong the position is. We could assign the king an infinite value and thus avoid positions which would result in the opposing player capturing our king (the details of this will become clear in the next article about position evaluation and move selection). While this solution is certainly viable it assumes a certain coupling between the move generator and the position evaluator which I would like to avoid. So, for our purposes let’s assume that we are going to write a legal move generator.
The next question is when to calculate legal moves. One option is to generate legal moves as we go - before recording any pawn move we would first determine it’s validity and omit it from our generated move list if it would leave our king in check. Another option is to first generate all pseudo-legal moves and then filter out any moves which are ruled illegal. I prefer the later option, since it allows us to develop our engine incrementally and test it more thoroughly at each step, plus it has the benefit of minimizing the scope of each task and making our program more readable. I’ve seen some claims that this approach is slower than only generating legal moves to begin with. However, Stockfish, one of the world’s top chess engines, uses this pattern. If Stockfish does it I think it’s good enough for my weekend project.
Implementation: Pawn Pushes
To see how this looks in reality let’s write some code that generates all single and double pawn pushes for a given position. In the interest of simplicity, we’ll leave out pushes which result in promotions since the logic for extracting moves from them is slightly different.
For some context, I’ve defined a structure which I’ve named BoardState which represents the state of a chess game.
If you’re familiar with FEN notation, this is basically just a structure which encapulalates the game state - the position of pieces, whether there is an
En Passant capture, which color is going next, etc.
Interally, the BoardState structure maintains the position of the pieces using 8 bitboards.
Two bitboards represent the pieces for each player and the other 6 represent all pieces of each type.
If we wanted to find all of white’s pawns we could simply do a bitwise AND of the white bitboard and the pawn bitboard.
Let’s start with some basic setup, our function will take a BoardState reference as a parameter and return a list of all pseudo-legal pawn pushes from this position.
fn gen_pawn_pushes(pos: &BoardState) -> Vec<Move> {
let our_color = pos.active_color();
let our_pawns = pos.bb(PieceType::Pawn, our_color) & !RANK7;
let empty_squares = !pos.bb_all_pieces();
let single_pushes = our_pawns.shift(NORTH) & empty_squares;
...
}
I think it’s absolutely marvelous how simple this code ends up being!
Who would have thought that you could generate pawn moves on a chess board without any loops!!
The idea behind this code is pretty simple, we grab all of our pawns which aren’t on the 7th rank (recall that we are excluding promotions for now),
we shift our bitboard north, and we take a bitwise AND with all of the empty squares on the board.
Thus, our single_pushes bitboard is now a bitboard that represents the state of our pieces pushed forward one square.
Now, generating double pawn pushes is actually fairly simple based off of this existing code:
let single_pushes = our_pawns.shift(NORTH) & empty_squares;
let double_pawns = single_pushes & RANK3;
let double_pushes = double_pawns.shift(NORTH) & EMPTY_SQUARES;
...
You could perhaps simplify this function be delegating single and double pawn pushes to separate functions, but for our purpose this will do for now.
We’re not quite done, however… we still haven’t returned a list of all possible moves! Although bitboards do a very nice job of making new bitboards, they’re less helpful to work with when it comes to actually extracting moves. For this purpose we need to implement some sort of procedure for taking a bitboard which represents moves in a certain direction and extracts moves from them.
We can take advantage of some nice bit-twidling hacks to make this operation fairly simple and efficient.
Since our bitboard is just a 64-bit unsigned integer, we can use the trailing_zeros function provided as part of the Rust language to quickly identify where pieces are on our board.
In fact, finding the number of trailing zeros in an integer doesn’t require any looping (see here).
So, we could extract moves from our bitboard using a function like this:
fn extract_moves(mut bitboard: Bitboard, offset: i8) -> Vec<Move> {
let moves: Vec<Move> = Vec::new();
while bitboard != 0 {
let index = bitboard.trailing_zeros() as u8;
bitboard = bitboard.clear_bit(index);
let m = Move {
to: index,
from: index as i8,
};
moves.push(m);
}
}
Unfortunately, avoiding loops altogether is going to be impossible. However, that loop will only iterate as many times as there are moves (if there are 8 pawn moves recorded we only have to loop 8 times). So, even though we are doing some looping, we’re still avoiding looping over all 64 bits like we would have for an array-based implementation.
There are a number of optimizations to be had here (particularly in how we store moves), but for now this is sufficient in order to learn how we can generate pawn moves using bitboards.
I’ll leave out the details regarding move generation for the king and knight. Since neither of these pieces slide we can follow the same pattern that we did for generating pawn moves. In fact, generating pseud-legal moves for the king is extremely easy given that he has no promotions, en passant captures, double moves, etc. This will leave us some time to talk about a much more interesting problem - sliding piece generation.
Sliding Piece Generation: Classical Approach
Generating moves for sliding pieces (i.e. rooks, bishops, and queens) is much more difficult than for the other pieces. Pause and think for a moment about what problems might come from using bitboards to generate moves for sliding pieces.
One of the first things that may have crossed your mind is that performing bitshifts is more difficult since we have to do them more than once. For instance, taking the rook bitboard and shifting it left by 8 bits (i.e. the north direction) would only result in us generating a single move!
Rooks
........ ........
........ ........
........ ........
........ ........
........ << 8 = .1......
.1...... ........
........ ........
........ ........
If we wanted a bitboard with all possible moves we’d have to shift it again by 16, 24, 32,… until we’ve reached the top of the board. We could of course just iterate over all possible offsets (i.e. 16, 24, 32 for the north direction) and apply them to our bitboard. But, as we’ve see, looping is a bit of an anti-pattern with bitboards and something we hope to avoid.
Another difficulty lies in determining blockers for a position. A rook can only slide until it hits a piece of it’s own color or until it captures an opponents piece.
Both of these are tricky problems to solve. There are countless ways that people have implemented sliding move generation for bitboards. Here, I’m going to introduce what the chess programming wiki calls the “classical approach” as I think it’s quite simple and easy to follow.
The first idea behind this approach is to pre-generate a two-dimensional table of rays (a ray is just a bitboard). The table is indexed on one axis by the square we’re on and on the other axis by the direction that we want to move (N, S, E, W for rooks).
Let’s understand this more by considering an example using rooks. Suppose that we have a board with a single rook on d4, like so.
........
........
........
........
...1....
........
........
........
In our table we would first do a lookup for the square d4. This would return to us another lookup table that contains four different bitboards - one for sliding moves in each direction. So, for example, the bitboard in the north direction would look like this.
...1....
...1....
...1....
...1....
........
........
........
........
Note that our ray does not include the square which we’re indexing with.
This seems to nicely solve our problem of having to calculate multiple moves at once. We can treat our lookup ray like our shifted board and use this to calculate moves. However, we still have the issue of determining blockers.
Fortunately for us, we’ve actually already learned the tools necessary to determine blockers. Let’s take our bitboard example from earlier with a rook on d3 and suppose that there are black pieces on d6, d8, and g8. Our setup would look like this
Rook Ray Enemies
........ ...1.... ...1..1.
........ ...1.... ........
........ ...1.... ...1....
........ ...1.... ........
........ ...1.... ........
...1.... ........ ........
........ ........ ........
........ ........ ........
The goal here is to represent that the piece on d6 can can be captured since it’s the first piece that we run into. However, our rook cannot move to d7 nor can it capture on d8 since it is blocked by the piece on d6. Let’s do a bitwise AND with our ray bitboard and our enemy’s bitboard This would give us the following
Ray Enemies Blockers
...1.... ...1..1. ...1....
...1.... ........ ........
...1.... ...1.... ...1....
...1.... & ........ = ........
...1.... ........ ........
........ ........ ........
........ ........ ........
........ ........ ........
Now our goal is to extract only the bit on d6 from this bitboard.
Thinking back to when we implemented move extraction we used Rust’s builtin
trailing_zeros function to identify the next 1 on our bitboard.
We can use the same logic here - since the indecies are increasing as we move up the board
then the 1 with the lowest index on the blockers bitboard (also known as the least significant bit)
will be the blocker.
This information will give us another index. We can now perform another lookup against our table to get the ray attack from this blocker square.
Blocker Ray
...1....
...1....
........
........
........
........
........
........
Now, if we take the XOR of our blocker ray and our original attacking ray we get the following:
Blocker Ray Ray Final Ray
...1.... ...1.... ........
...1.... ...1.... ........
........ ...1.... ...1....
........ ^ ...1.... = ...1....
........ ...1.... ...1....
........ ........ ........
........ ........ ........
........ ........ ........
This gives us a final bitboard which represents all possible attacks for the rook in the north direction with blocking pieces on d6 and d8.
Sliding Piece Generation: Magic Bitboards
The classical approach for sliding piece generation is fairly straightforward and efficient. However, by making a few key observations we can greatly improve the performance of our algorithm.
Let’s start by determining some inefficiencies with our previous solution. One obvious improvement would be to avoid doing four separate lookups - one for each direction. Rather than looking up the north, south, east, and west rays and calculating moves separately it would be nice if we could do it all in one step. Additionally, it would be preferred to not identify the least/most significant bits and extract blockers using that method.
To do this, let’s start with an extremely naive idea and make optimizations. In a perfect world, we could maintain a massive table that maps every possible board configuration and square to the relevant possible moves for the rook. For example, let’s say we had the following board:
Board Possible Moves
1....... ...1....
.1...1.. ...1....
....1... ...1....
.1...... --Perform Lookup--> ...1....
...R..1. 111.111.
.1...... ...1....
...1.... ...1....
......1. ........
Now, such a table would be infeasibly massive. For every possible square we would need a table which contains the relevant moves for every possible board configuration. This is something like 2^64 entries.
However, we can already start to trim down this number quite a bit. The first key observation to make is that not all of the pieces on the board matter. In our previous example, adding a piece on A1 would have no effect on the possible moves that we can make. In other words, only the pieces which intersect with the rays of the rook (i.e. north/south/east/west to the edge of the board) are relevant. So let’s start by identifying only the meaningful pieces on our board by doing a bitwise AND with the ray attacks of the rook like so.
Board Attacks Relevant Pieces
1....... ........ ........
.1...1.. ...1.... ........
....1... ...1.... ........
.1...... & ...1.... = ........
...R..1. .11.111. ......1.
.1...... ...1.... ........
...1.... ...1.... ...1....
......1. ........ ........
Ideally we would like to identify the possible moves using the relevant pieces board as a key.
However, in it’s current state this key is no better than the previous key that we tried to use - it’s still the whole board, this time with more zeros.
However, we can reason that there are a lot of unneeded bits here.
There are only 10 bits which have any meaning to us since those are the only squares that can possibly intersect our Attacks bitboard.
In other words, what we’d like to do is somehow extract only the relevant 10 bits that overlap with our attack bitboard.
To do this we’ll use something called a magic number. A magic number is one with the following property: when multiplied by our relevant pieces board it causes all 10 of those bits to end up at the 10 upper-most bits in our board. Visually, it looks like this:
Relevant Key
........ ..1..1..]
........ ..].....
........ ........
........ * magic number = ........
......1. .garbage
........ ........
...1.... ........
........ ........
We don’t care what the bits are after the 10th bit (which I’ve surrounded with square braces), all we care about are those 10 upper most bits. We could then shift our bitboard right by 54 bits and isolate only these bits. Now, don’t try to wrap your brain too hard around how this works. After all, they’re named magic bitboards. Rather, reason that the purpose of this multiplication is to help us isolate the only bits relevant to the square we want to identify moves for.
So far we’ve made great progress. Since we now have a new key to use for our table it means that our table is down from 2^64 entries to 2^10. That’s just 1024 entries!
Now let’s embark upon the journey of actually finding magic numbers. As it turns out, this process is relatively simple using a brute-force approach. Let’s begin by just picking a random 64-bit number to be our magic number. Then we’ll iterate over every possible bitboard configuration for the relevant pieces. Based on that configuration we identify the index using the technique I showed above (multiplying and shifting). We’ll then place the relevant attack mask into that table at the given index. If the index is already occupied AND the attack mask at that index is different we know our magic number is invalid. If it’s the same, however, we can continue. Once we’ve identified that all configurations for the relevant pieces are correctly mapped we know we’ve found a valid magic number. Let’s make this concrete by putting this in pseudo-code
func gen_magic_index(bitboard, magic_number):
return (bitboard * magic_number) >> 54
func gen_magic_number(square):
occupancy_combos[4096] = all possible occupancies on relevant squares
attack_combos[4096] = attack mask for each occupancy above
lookup_table[4096] = init with all zeros
forever:
magic_number = random 64-bit integer
clear lookup_table
for each occupancy in occupancy_combos
let index = gen_magic_index(occupancy, magic_number)
if lookup_table[index] == 0
lookup_table[index] = attack_combos[occupancy]
else if lookup_table[index] != attack_combos[occupancy]
fail this iteration
return magic_number
There’s a few key things I’d like to point out here to make this more clear.
The naming here can be a bit tricky, so I’ll try to clarify here.
The occupancy_combos is an array which enumerates all possible configurations of pieces on the relevant squares
(recall the relevant squares are those which intersect with our attack ray).
The attack_combos can be thought of as a truth table which maps the occupancy to the possible attacks associated with that.
The lookup_table maps the index generated by our magic number multiplication/shift to the possible attacks.
Perhaps surprising is the fact that this code runs very fast. I can generate all 128 magic-numbers in just about a second on my Thinkpad X1 Carbon.
Before we wrap-up our discussion on magic bitboards I should point out a few more things. First is that not every square is going to require 10 bits of information to map. For instance, a rook on A1 needs 12 bits of information to uniquely identify it’s index. However, in some instances we need fewer bits. A bishop on b7, for instance, only requires 6!
Magic bitboards turn out to be highly effective in practice. They have a relatively high memory footprint but require virtually no work to calculate during runtime. This time/space tradeoff ends up massively benefiting us since the required tables are small enough to be efficiently indexed into. Stockfish, one of the world’s strongest chess engines, uses magic bitboards.
Determining Move Legality
As it currently stands we have all the functionality for generating pseudo-legal moves (I’ve ommitted some discussion about castling since I don’t find it particularly interesting). Our next step is to filter out moves that are illegal. As a reminder, a pseudo-legal move is also a legal move so long as it does not leave our king in check once the turn is over.
First, let’s consider the case where the piece moved is our king. Such a move is legal so long as the destination square is not attacked by any opposing pieces. When first writing this function I had the thought that we could iterate through all the opponent’s pieces and generate pseudo-legal moves for them - if any of them overlap with the destination square of our king then our move is illegal. However, this is unnecessarily expensive. To come up with a better solution we need to make a key observation - (almost) all moves in chess are symmetrical. In other words, a knight can move from A1 to B3 and also from B3 to A1. The reason this matters is that we can simply generate moves starting from the king’s square and work backwards - any squares owned by our opponent that overlap with pieces of the relevant mask are potential attackers and hence render that move illegal.
To do this, let’s treat the king as a super piece and generate all attacks from the king’s destination square.
This will generate a bitboard of all possible occupancies.
We can then do a simple bitwise AND with the opponent’s pieces to determine if anyone is actually attacking that square.
Let’s make this more concrete by looking at an example.
Suppose that our king is on E1, and the attacks_to bitboard represents all possible attackers to that square
King attacks_to(rook)
........ ....1...
........ ....1...
........ ....1...
........ ....1...
........ ....1...
........ ....1...
........ ....1...
....K... 1111.111
Now, doing a bitwise AND with the opponent’s rooks will tell us if any rooks are attacking us and hence render that move illegal.
Next, let’s consider the case where the piece moved is not our king. This is going to be a much trickier task - not only are there numerous cases to consider, but also doing so efficiently is challenging.
Our first step should be determining whether or not our king is in check. If the king is attacked two or more times our move is going to be illegal - this is called a double check and the only legal move in this situation is to move our king. If the king is in check by one piece then we must either capture that piece or block the incoming attack - but keep in mind that in doing so we must not also expose our king to another incoming attack. Finally, if our king is not in check at all we are free to make any move so long as our piece is not pinned. However, being pinned doesn’t mean we can’t make any moves. Rather, we can only move so long as the move is aligned with the attacking ray. Let’s break these cases down one at a time.
First and foremost, let’s determine the pieces that are putting our king in check.
We’ve actually already done the work for this - we can use the same attacks_to bitboard that we generated earlier for the king’s current square to determine the number of attackers
and count the number of non-zero bits.
This will immediately tell us the number of attackers and help us narrow down our cases.
Next, in the case of zero or one attackers, we will need to determine if our piece is pinned. This is one of the most tricky and expensive parts of legal move determination. One of the most efficient ways to solve this problem is to pre-calculate all pinned pieces for a position. Suppose, for example, we had a board like so:
........
..r...q.
.....b..
..B.....
...P....
..K.....
........
........
Our bishop on C5 is pinned by the rook on C7, and our pawn on D4 is pinned by the bishop on F6, but not by the queen on G7. So, how do we determine which pieces are pinned? One approach, which is viable but sub-optimal in terms of efficiency, is to loop through all of the opponent’s pinning pieces (i.e. rooks, bishops, and queens) and generate attacks towards the king (we can do this by keeping a lookup of bitboards between two squares and using that as the mask for the attacking bitboard). If the ray intersects any of our pieces we can try removing that piece and doing the lookup again - if the ray extends to our king’s square then the piece was pinned. This requires a number of lookups, but also recreating our position with just a single piece removed, which isn’t ideal. However, using this idea of symmetry that we established earlier we can get a much more elgant solution.
The idea here is to again do a lookup for all of the opponent’s pinning pieces towards our king. However, we also do a lookup starting at our king and with the same attacks as the attacking piece (i.e. diagonal for bishops, rank/file for rooks). If these two rays overlap, they will do so on a single square which is a blocking piece. Let’s use this example above to help visualize this:
King Rooks Mask
........ ..1..... ........ ........
........ 11.111.. ........ ........
........ ..1..... ........ ........
..1..... & ..1..... & ........ = ..1.....
..1..... ........ ........ ........
11K11111 ........ ........ ........
..1..... ........ ........ ........
..1..... ........ ........ ........
The presence of a non-zero bit on C5 tells us that this piece is pinning!
Clearly this is more efficient than our previous idea of removing a piece and doing another lookup.
That approach would required 2n magic lookups where n is the number of potential pinning pieces.
This approach, however, only requires n+2 magic lookups - one for each potential pinner and two for the king in the bishop/rook direction.
Next comes the question of determining whether or not a move for a pinned piece is legal. We can solve this very simply by making a key observation - such a move is legal only if the king is aligned on on the same ray as the start and ending square of the move. Since we already know a piece is pinned we already have all the necessary information about which direction it’s pinned from - the direction towards the king. Thus, we can again maintain a lookup table that contains rays across the bitboard between any two squares. We can do a lookup based on the source/destination square of that move and see if the king is also on that ray. If it is, the move is legal. Otherwise, the move is illegal. Let’s make this clear with an example - I’ve marked the source/destination squares of the bishop from the previous problem with S/D
Between[S][D] King
........ .....1.. ........
..r..... ....1... ........
........ ...1.... ........
..S..... -> ..1..... & ........
........ .1...... ........
D.K..... 1....... ........
........ ........ ........
........ ........ ........
Since there is no overlap, this immediately tells us that the pinned move is illegal and hence we can remove this move.
The final case to consider is when our king is attacked by a single piece.
Our first job is to determine whether or piece is pinned and.
If our piece is not pinned, we must either block or capture the attacking piece.
We can use this same between bitboard as above to create an attack between the attacking piece and our king.
So long as our destination square aligns with this ray, our move is legal.
Testing Correctness
Validating chess move generation is typically done through something called a perft test. The basics of this test are fairly simple - we give our generator some position and an arbitrary depth to search to. The generator enumerates all moves to that depth and counts the number of leaf nodes. We can then cross reference our numbers with existing move generators to gain confidence about our program.
Development Notes
Writing a chess move generator is a fairly difficult endeavour - there are lots of edge cases to consider and many components that work together and rely on each other. One thing that I found particularly helpful during development was using an existing chess library to check my work. I picked python-chess since it has a similar implementation to my project - it uses bitboards and differentiates between pseudo-legal and legal move lists. I wrote a set of utility scripts available here which allowed me to double check my work and provide me with reliable data during unit testing. For example, these scripts allowed me to determine how many pawn moves exist for a given FEN, which I could use as an assertion in my pawn code unit tests.
The Chess Programming Wiki can be a helpful resource during development. Many of the pages are hard to follow or under-developed, but it is a very useful recourse for learning about the existence of certain concepts and pointing you in the right direction.
I frequently used this site to generate random FENs during testing.