Chess programming with bitboards part 1

Keywords: lowest set bit, bit number, chess programming, square set, piece bit, piece bitboard, king bit, king bitboard, board, position, create, zero, method. Powered by TextRank.

Chess Programming: Diving into Bit Manipulation

Chess programming is a hobby I have pursued for some time now. I have implemented a PGN parser with recursive variation support and a chess modeler that loads the game and validates moves. I attempted to create a chess engine, but I don’t think it went very well. I always opted for the most comprehensible approach rather than the most efficient one. Now, for a change, I’m going to dive into the world of bit manipulation to understand the mechanics of hardcore chess programming.

A Recap

The straightforward approach to chess programming involves modeling the pieces, the board, and the squares. One common method is to keep an 8x8 matrix to represent the board, where pieces occupy specific spaces. When computing the moves for a piece, you would iterate from the piece's position on the board through each of the squares and generate possible moves. This process requires significant computational power, and no serious engine can remain competitive with such an implementation. Search depth is critical in classical chess engines; you need fast move generation and validation to search deeply.

Introducing Bitboards

The first concept to tackle is the bitboard. As the name suggests, a bitboard is a string of bits representing the board. Since a chessboard has 64 squares, and an Int64 has 64 bits—one for each square—this mapping works perfectly. The idea is to assign a bitboard to each piece of each color and set the corresponding bits in the Int64 that reflect the position of that piece on the board. Here’s an example:

0000_0000 | 0000_0000 | 0000_0000 | 0000_0000 | 0000_0000 | 0000_0000 | 0000_0000 | 0000_0000

In this 64-bit number, the least significant bit (LSB) is the square a1. The next bit to the left represents b1, and so on. If this were a white king bitboard and the king were in its starting position, it would look like this:

0000_0000 | 0000_0000 | 0000_0000 | 0000_0000 | 0000_0000 | 0000_0000 | 0000_0000 | 0001_0000

The king is on e1. The advantage of working with bitboards is that you can use the bitwise OR operation to create masks. For example, if you OR all the black piece bitboards together, you create a mask that marks all the squares occupied by black pieces. If you OR every bitboard, you get the occupancy bitboard, indicating all the occupied squares.

Since my implementation is in Swift, it’s important to note that not all languages provide the utilities that Swift does, but the concepts remain the same.

Creating a Square Abstraction

To start, it’s helpful to have an abstraction for a Square . Even though we won’t use a Square object for storage, we still need to compute the index of a bit in the bitboard that corresponds to the file and rank of a square. It’s also useful to have utility functions, such as creating a bitmask for the square, which is a 64-bit number with only the bit corresponding to that square set.

Next, a Bitboard class serves as a nice abstraction. Since this is just a UInt64 , I prefer to typealias it and create utility methods in an extension to set and clear bits and define masks for ranks and files. Getting the set bits as Square objects is also convenient. Here are some useful masks for selecting files and ranks:

public static let rank1Mask: UInt64 = 0x00000000000000FF
public static let rank8Mask: UInt64 = 0xFF00000000000000
public static let fileAMask: UInt64 = 0x0101010101010101
public static let fileHMask: UInt64 = 0x8080808080808080

The rank1Mask has 1's on the first rank from A to H, while the fileAMask has 1's on the first file from 1 to 8. These masks come in handy for checking borders or selecting a specific rank or file to work with.

Tricky Methods Explained

Here’s one tricky method I want to explain: getting the squares for the set bits in the board.

var positions = [Int]()
var num = self
while num != 0 {
    let bitPosition = num.trailingZeroBitCount
    positions.append(bitPosition)
    num &= num - 1 // Remove the lowest set bit
}
return positions.map { Square[$0 / 8, $0 % 8] }

This method scans the board from a1 to h1, then a2 to h2, and so on. We find the lowest set bit by counting the number of trailing zeros after that bit. We save this position for later and clear that bit. How does this work? The expression x - 1 sets the lowest bit from x to zero and also sets all the trailing zeros to 1. For example:

  1000_1000 = x
  0000_0001 = 1

Since we can’t subtract 1 from 0, we need to borrow from the lowest set bit, changing x to:

  1000_0111 = x
  0000_0001 = 1

We clear the lowest set bit, but in the process, we set the bits to the left of it. Now we can subtract:

  1000_0111 = x
  0000_0001 = 1
--------------- (-)
  1000_0110

Next, if we AND it with the original number:

  1000_1000 = x
  1000_0110 = x - 1
--------------- (&)
  1000_0000

This cancels out the unwanted set bits and records the position. The next position is again the lowest set bit. This process continues until we reach zero, and the positions array contains the positions that were set. There are other ways to achieve this as well; for instance, you could keep a counter that increments when the last bit is zero and add the counter to the list if it’s 1, rotating the number right until it reaches zero.

Printing the bitboard in an 8x8 format is also helpful for visualization. This is straightforward with Swift, as it allows printing a binary string. You can split that string into chunks of 8 for display.

This is all for today. I plan to write about computing moves for the King and Knight pieces next, followed by how to compute moves for sliding pieces.

Metadata

960 words

Chess programming with bitboards part 1

Metadata

Similar posts