Keywords: pawn move, rank mask, mask shift, passant square, passant capture, king piece, piece move, piece bitboard, capture rank, capture mask, check, lookup, board, bitwise. Powered by TextRank.
Now, let's take a closer look at the heart of the problem in most chess libraries or engines: move generation. This is an integral part of the system that is called over and over again, so it's worth investing time in optimizing it as much as possible. Hardcore chess engines often optimize this down to the single assembly instruction level to squeeze out maximum performance.
I want to split move generation into two main categories:
The reason for this differentiation is that non-sliding piece moves can be easily defined using hardcoded lookup tables, without needing to consider blocking pieces. Since static pieces are easier to understand and model, let's start with those. Pawns, knights, and kings are the non-sliding pieces. Pawns and kings have special cases, such as double moves, castling, and en passant captures, but knights are relatively straightforward. You can simply create a lookup table that returns all the possible squares for a knight to jump to from a given square as a bitboard. While it's a bit tedious to do this manually, you can write a small Python script to generate the lookup dictionary and then copy/paste it into your code. Next, get the occupancy bitboard for friendly pieces and apply a bitwise AND operation with the complement of the friendly piece bitboard. This will give you the pseudo-legal moves.
let possibleMoves = AttackTable[.b1] let friends = board.occupancy(color: .white) let legalMoves = possibleMoves & ~friends
You can also use the enemy bitboard to calculate captures.
It's similar for the king. Precompute a lookup table for each square containing all the possible moves for the king. The only thing to watch out for is that the king shouldn't "wrap" around the board’s edges to the opposite files or ranks. While it's possible to compute these squares on the fly, I think it's worth the extra memory overhead to use a lookup table since it's faster. Again, performing a bitwise AND with the friendly occupancy board will give you the pseudo-legal squares for the king. These moves are pseudo-legal because you can't move into check, but that will be handled separately during move validation. We'll generate candidate moves and prune them later, which simplifies things significantly. The king has a special case for castling, which also needs to be handled. Castling requires tracking castling rights, which means the king and the rook involved in the castling must not have moved. These rights are tracked by some other entity (like a Board class), which clears them based on the player's move. The other rule is that you can't castle through or into check. This rule will be enforced during move pruning, so we just need to ensure the castling path isn’t under attack.
if board.canCastle(color: color, direction: .short),
board.isEmpty(square: shortCastlePath),
board.isEmpty(square: shortCastleHome),
!board.isAttacked(square: shortCastlePath, by: color.opposite)
{
// Set the bit for the short castling target square in the bitboard
}Pawns are the last non-sliding pieces. I want to consider pawn moves and captures separately. For pawn moves, we need to check if the square in front of the pawn is blocked. This is simple because we don't have to worry about pawns "falling off" the ranks, as pawns can't be on the first or last ranks (where they would be promoted). To compute a pawn move, create a mask from the pawn's source square and shift it left (or right, for black) by 8 bits. This shift corresponds to the square directly in front of the pawn. If this square is unoccupied (as tested using the occupancy board), we can mark it as a potential move in the result bitboard.
let friends = board.occupancy(for: color)
let enemies = board.occupancy(for: color.opposite)
let occupied = friends | enemies
let north = from.mask << 8
if north & occupied == 0 {
// Square is empty
}Pawns are allowed to move two squares on their first move. Since we can detect if the square in front of the pawn is empty, we just need to check that the pawn is on its home rank and that the double-move target square is also empty.
public static let rank2Mask: UInt64 = 0x000000000000FF00 public static let rank7Mask: UInt64 = 0x00FF000000000000
Using these masks, a bitwise AND operation on the pawn's source square will tell us if the pawn is on its home rank. Then we simply test the occupied board against a mask shifted by 16 bits left or right.
For regular pawn attacks, we check each diagonal (NW, NE) from the pawn. This can be done with a mask shifted left or right by 9 or 7 bits from the pawn’s source square. If this seems confusing, here’s an illustration:
... 00000000_00000010
Assume the bits above represent the 1st and 2nd ranks. (I know you can't have a pawn on the 1st rank, but for the sake of this example, let's place one there.) Since our bitboard representation is little-endian (with the least significant bit on the left), the bitboard above represents a pawn on b1. If you shift this bitboard left by 8 places, you get this:
... 00000010_00000000
Which corresponds to b2. If you shift it left by 7, you get:
... 00000001_00000000
Which corresponds to a2. Once we have the capture masks, we just need to test them against the enemy bitboard:
if from.mask << 7 & enemies != 0 {
result |= northEastSquareMask
}
// The same applies for the mask shifted by 9 bits.What happens if the pawn is on the A file and you shift it by 9? The capture will wrap around to the H file on the next rank, which is undesirable. To discard these types of wrap-around errors, we will mask the result with a rank mask. A rank mask is basically a pattern with all the bits of a rank set and the rest of the bits are 0. When we bitwise and this mask with the bitboard it will clear out any bits that are not on the rank. We need to adjust this mask to have all the bits on the capture rank set to 1.
We also need to handle en passant captures. The en passant opportunity is tracked by another entity in the system (like castling rights), and it lets us know which square presents an en passant opportunity. The specific rules for en passant will be addressed during move validation, but for move generation, it's enough to check whether the en passant square is one of the capture masks we created earlier. If they match, we can include the en passant square in the result.
That covers non-sliding piece move generation. Next, we'll look at sliding piece moves and how bitboards remove the need to loop over squares to compute attack vectors using binary arithmetic.
1110 words
Powered by TF-IDF/Cosine similarity
First published on 2024-09-25
Generated on Oct 9, 2024, 4:11 AM
Mobile optimized version. Desktop version.