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.