Attempts to create an automatic chess calculator date back to 1913. Chess engine software has had many optimisations and many minds involved in its evolution.

Last year I wrote on how chess programs track the position of every piece. This article is a slice of the chess engine research I compiled when constructing my own chess AI and covers how a chess engine resolves where a piece can move on the board.

You canplay against that chess engine here.

Bit Operations

So far we've covered how to use a 64 bit integer to track the positions of each piece and we've covered how to use bit operations to determine their type and colour.

Now the goal is to compute a 64 bit int that represents the potential positions that a piece can either move-to or attack. This number is called the "moveboard".

If we have a moveboard for a particular piece we can & the positions of the opposing pieces in order to get attacking positions and we can subtract the positions of all pieces in order to avoid moving a piece to an occupied position.

If we simplify this to a single position on the board. Given that we are able to move to this position, i.e. the moveboard is 1, and if we consider it occupied by the opposition, i.e. having a variable called "theirs" being 1.

Computing the attacks is determined by doing the following:

>>> moveboard & theirs
1

This tells us the position is a valid attack. If the opposition does not occupy that position (theirs == 0). Computing for attacks would result in 0. There's nothing to attack.

To compute valid moves, if theirs is 0 and ours is 1, we do the following:

>>> moveboard & ~(theirs | ours)
0

This indicates that we can't move to this position. If the result was 1 then it would be empty and it would be a valid position for our piece to move. If we use 64 bit integer instead of a single bit, as shown in the example, the processor can determine the valid moves and attacks across the entire board in a single operation.¹

Pawns

There's an edge case with pawns however, they do not use a moveboard to determine the valid moves and attacks as the positions a pawn may attack are different to where it may move. Despite this they are still relatively simple.

Given a pawn in the middle of the board we only need to shift it up to determine its set of moves and after subtracting occupied positions we can determine if the pawn can move ahead or not.

# Shifting up
pawn_position >> 8

To determine if that pawn can attack we shift the pawn twice, "up and left" as well as "up and right". We then check to see if the opposition occupies these positions, this will determine valid attacks for the pawn.

# Shifting "up & left" as well as "up & right"
pawn_position >> 7 && pawn_position >> 9

Knights

Things get more interesting when we compute valid moves and attacks for a knight, but how does a knight move?

The knight is interesting because it's the only piece that is unrestricted by the position of other pieces. I.e. it can jump over pieces to get to where it wants to go. A knight in the centre of the board can move to the following locations:

If we had a knight sitting on the ith index represented by the "bitboard" variable we can compute the moveboard for the knight by doing the following shifts:

(
    ((bitboard & NOT_H_FILE) >> 15)
    | ((bitboard & NOT_A_FILE) >> 17)
    | ((bitboard & NOT_GH_FILE) >> 6)
    | ((bitboard & NOT_AB_FILE) >> 10)
    | ((bitboard & NOT_H_FILE) << 17)
    | ((bitboard & NOT_A_FILE) << 15)
    | ((bitboard & NOT_GH_FILE) << 10)
    | ((bitboard & NOT_AB_FILE) << 6)
)

There are four knights on a chess board, so this calculation would need to be done 4 times for every new board state. Since the performance of a chess engine is largely determined by how far into the future it can look, reducing the number of calculations on each board state can enable the engine to perform a deeper search.

To avoid these computations, we can simply pre-compute the moveboard for every square on the chess board before the game begins. We can then provide the engine with a lookup table, mapping all positions to their moveboard. Avoiding the overhead of computing them during the game.

Sliding

We also do this for the sliding pieces on a chess board. The rooks, bishops and queens move in a way that are considered as sliding.

Again we pre-compute all these positions and store the result in a map, however this isn't the final moveboard for sliding pieces.

Pieces closer to a sliding piece block its path and unlike the knight sliding pieces can't jump over these obstructions. So the resulting bitmask can't be used to determine the valid moves and attacks on its own.

The bitmask is used to identify the potential blockers along a sliding piece's direction of movement. Indicated in orange below:

Once we have identified the potential blockers we use this value to map to the final moveboard. This allows us to look up any moveboard using all combinations of potential blockers during the game and avoids having to shift the piece's position along its sliding axis for every new board state.

As explained we can use a moveboard to compute the attacking positions (moveboard & theirs). As well as the valid positions for moving (moveboard & ~(theirs|ours)).

In summary the following steps are needed to find the attacking positions and moving positions for a rook:

1. Given the rook's position lookup the bitmask of an unobstructed rook. (index -> bitmask)
2. Use the unobstructed bitmask to find potential blockers given all the pieces on the board. (bitmask & (theirs|ours))
3. Using the locations of all the blockers lookup the final moveboard for the rook. (blockers -> moveboard).

Computing potential blockers can be simplified as there are positions on the board that would never block a sliding piece. Such as positions on the edge of the board.

Given a rook in any of the positions indicated in red we can ignore positions in black as having "potential blockers".

This reduces the overall number of potential blocker combinations we need to consider, improving the engine's start-up time and memory footprint.

We do the same for bishops, except these potential blockers are computed diagonally and finally we compute the moveboard for the queens by combining the outcomes of the rook and the bishop.

Playing Chess

Now that we are able to compute the set of possible moves and attacks for each piece on the chessboard. Picking a piece at random and picking one of the positions from it's set of move and set of attacks will allow a computer to play against us.

This chess engine would still make illegal moves. To play a legal game of chess we would need to consider if the king is in check or if moving a piece might result in your own king being in check.

Finally; in-order-to implement all legal chess moves we would need to extend our move sets to include pushing the pawn twice when it is on its starting position, en passant and the ability to castle your king.

It might be more interesting, however, to dive into how a chess engine evaluates the board state so that it can make an informed decision when it moves a chess piece.

While exploring an interesting game engine which compiles python code to WASM; I thought, there's no better way to have fun than to write a chess engine. This was the start of a one month long project which led me to create my own chess AI.

Chess programming is a topic that has been written about extensively, it has been a proving ground for some of the first AI researchers and even today it is still used as a benchmark for techniques in applied research.

This article is the first part in a series of three in which I attempt to distill some insight into the application of algorithms in software, namely chess programming. In the hopes that it may inspire how you approach solving similar problems in the future.

Bit Operations

If you've ever done some leetcoding or any other live algorithm style interview prep in software engineering you might have come across the odd question on bit operations and wondered if you'll ever need to actually do these in your day to day job. I'm not here to answer that, but I am here to show you how it applies to chess programming.

Firstly what are bit operations:

a bitwise operation operates on a bit string, a bit array or a binary numeral at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operations and directly supported by the processor.

Wikipedia

Essentially bitwise operations are physical operations that are embedded into the processor, they consist of your logical AND, OR, XOR and bit shifts. The mathematical operations that you're familiar with (such as Add, Subtract etc.) are all built upon bitwise operations.

Here's an example of a NOT operation:

NOT 0111  (decimal 7)
  = 1000  (decimal 8)

And an example of an AND operation:

    1010 (decimal 5)
AND 1100 (decimal 12)
  = 1000 (decimal 8)

We can see these operations supported in python:

>>> 0b1100 & 0b1010
8
>>> bin(0b1100 & 0b1010)
'0b1000'

There's two ways we can shift bits. (Left and right) Here's an example in python:

>>> # Left
>>> bin(0b0010 << 1)
'0b100'

>>> # Right
>>> bin(0b0010 >> 1)
'0b1'

Explaining how the processor does addition is out of scope of this blog post, but put together some of these bit operators and you've got yourself a function that can do addition.

Bitboards

Back to the chess:

We are doing all of this essentially to get as close to the processor as possible, since we want the most performance out of a computer as we can by avoiding any unnecessary operations.

In chess programming we will use a single number to keep track of all the positions of pieces on the board. This is what we call a "bitboard". We will have a few bitboards to maintain the game's state. The first one will be 'board' which tracks all the pieces. At the start of the game this number will be: 0xFFFF00000000FFFF. Which is hexadecimal for 18446462598732906495. If we print the binary form of this number and format it over 8 rows we get the following:

 Bitboard:

8  1 1 1 1 1 1 1 1
7  1 1 1 1 1 1 1 1
6  0 0 0 0 0 0 0 0
5  0 0 0 0 0 0 0 0
4  0 0 0 0 0 0 0 0
3  0 0 0 0 0 0 0 0
2  1 1 1 1 1 1 1 1
1  1 1 1 1 1 1 1 1
   a b c d e f g h

There are a few other bitboards to track during a game of chess. There will be 2 boards for each colour (white and black). And there will be a bitboard for each type (6). Which gives us a total of 9 bitboards, or 9 numbers to cover the entire game state of chess. Here's two more examples of bitboards, one for pawns and one for white pieces:

>>> pawns = 0x00FF00000000FF00
>>> white = 0x000000000000FFFF

Now we can uses these three numbers to give us the answer to some questions for example; Where are all the white pawns?

>>> board & pawns & white
65280

 Bitboard (65280):

8  0 0 0 0 0 0 0 0
7  0 0 0 0 0 0 0 0
6  0 0 0 0 0 0 0 0
5  0 0 0 0 0 0 0 0
4  0 0 0 0 0 0 0 0
3  0 0 0 0 0 0 0 0
2  1 1 1 1 1 1 1 1
1  0 0 0 0 0 0 0 0
   a b c d e f g h

During a game of chess you'll use these to calculate which pieces are under attack. (e.g. given: knightsmove & theirpieces the result will be 0 if there's no piece under threat). We can also use these bitboards workout where the valid moves are with moves & ~board. (Moves and not board).

A chess AI that's looking 4 moves ahead will have ~5mil positions to consider, so having these operations done on a low level can help boost the performance of the software. The more you squeeze out of performance the more accurate your chess AI will be, because this improves it's ability to look into the future.

Beyond Chess

In summary learning about how bitboards are applied to chess programming has allowed me to understand how bit operations can be applied practically in software. Before I dived into learning how chess is programmed I had only imagined keeping track of the board state using several objects and an array, however I now see there's more than one way to crack an egg; the board state egg.

I hope the article helps to providing insight into practical applications of bit operators and leaves them to be considered as valuable for solving technical problems or at least reminds software engineers that we have them in our toolbelt.

Further Reading

• Stockfish
• Chess Programming