Piece Movement Part 1: Lookup Tables

What is a lookup table?

In the previous post we looked at how a chess board is represented with bitboards. But, how does a chess engine actually know where the pieces can move? This is often calculated whenever we need them, but this results in doing the same math again every time a piece move from that square. High performance engines want to avoid doing the same math multiple times.

A lookup table is a pre-calculated array of attack bitboards. Since a Knight/King on a square will always attack the same squares regardless of the other pieces on the board, we can calculate attack bitboards for each square at startup and save this for later inside of an array. This makes moving pieces a lot faster as it now just has to do a lookup rather than any calculations.

Pawns are a bit different because their attack patterns depend on colour, so engines usually store two pawn lookup tables: one for white and one for black.

ulong whitePawnAttacks[64];
ulong blackPawnAttacks[64];

Calculating a Knight's Attack

To understand how and why we use these here is an example of how to calculate a Knight's move.

1. Create a bitboard mask where only the knights starting position is 1.

2. Shift this bit for each possible move direction while using file masks to avoid wrap around.

Here is some example code of this.

ulong CalculateKnightAttacks(int square) {
    ulong knight = 1UL << square;
    ulong attacks = 0;

    // Move 2 up and 1 left (Check if not on A file to avoid wrap-around)
    if ((knight & NotAFile) != 0) attacks |= (knight << 15);
    
    // Move 1 up and 2 left (Check if not on A or B file)
    if ((knight & NotABFile) != 0) attacks |= (knight << 6);

    // Repeat for all 8 possible directions
    return attacks;
}

Why are they beneficial?

Even though bitwise operations are fast, doing many of these every time we move a piece is not ideal. High performance engines search millions of positions or even more each turn so this adds up. A lookup table reduces computation code down to 0(1) time complexity, which is very fast. This turns calculations every turn into a simple lookup.

ulong moves = _knightLookupTable[27];

The Limitations

This can only be done with the non-sliding pieces, knight, pawn, and the king, due to sliding pieces move can be blocked by other pieces. This would result in a huge array which would be quite slow. For this we can use magic bitboards which will be in the next post.

Piece Type	Calculation Method
Pawn, Knight, King	Lookup Tables
Rook, Bishop, Queen	Magic Bitboards