How to generate this preinitialized array for magic bitboards?

Question

I am currently trying to make my chess engine faster, and am looking at implementing magic bitboards for my sliding piece attack generation. I am using a bitboard representation of the chessboard with the a1 square being the furthest right bit, and h8 being the furthest left. I am looking at this site:

https://rhysre.net/fast-chess-move-generation-with-magic-bitboards.html#:~:text=A%20bitboard%20is%20simply%20a,and%20bit%2063%20%3D%20h8)

Specifically the code snippet found towards the bottom of the page that reads:

  U64 getBishopAttacksMagic(int square, U64 blockers) {
  // Mask blockers to only include bits on diagonals
  blockers &= BISHOP_MASKS[square];

  // Generate the key using a multiplication and right shift
  U64 key = (blockers * BISHOP_MAGICS[square]) >> (64 - BISHOP_INDEX_BITS[square]);

  // Return the preinitialized attack set bitboard from the table
  return BISHOP_TABLE[square][key];
}

I already have Shallow blues magic numbers(each number corresponding to a square), and I already have pre initialized attack masks for the bishop piece stored in a 64 length array(again each number corresponding to a square). So i know how to get the key. But how do I generate the last array which takes the key, "BISHOP_TABLE" array? I do not understand how to generate that 2d array given an attack mask and magic number for each square. Thank you for your help in advance.

Answer 1

For each square, you need to generate every permutation of blocking pieces inside the bishop mask. For example, using this mask for the square e4 (#28):

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

since there are 9 set bits, there are 2^9 = 512 different patterns of blocking pieces. The permutation number 339 (as binary = 0b101010011) looks like this:

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

Bits are read from right (lsb) to left (msb) in the number and are set in the mask from the a file to the h file, 1st rank to 8th. Permutation 0 is an empty board and 511 (0b111111111) is the full mask.

Here's a method that takes a permutation number along with the bishop mask and returns the corresponding blockers bitboard:

private static long blockersPermutation(int iteration, long mask) {
    long blockers = 0;

    while (iteration != 0) {
        if ((iteration & 1) != 0) {
            int shift = Long.numberOfTrailingZeros(mask);
            blockers |= (1L << shift);
        }

        iteration >>>= 1;
        mask &= (mask - 1); // used in Kernighan's bit count algorithm
        // it pops out the least significant bit in the number
    }

    return blockers;
}

Using this we can calculate the keys with both the magic numbers and the blockers, and we can create their corresponding values, the attack masks.

For each permutation of blocking pieces, create the corresponding attack mask and store it in the table. Include the blocking pieces and the squares on the side of the board in the mask. The attack mask for the blockers #339 on square #28 is:

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

Here's a Java method to initialize the 64 bishop lookup tables:

private final long[][] BISHOP_LOOKUP = new long[64][512];

private static int getFile(int square) {
    return square % 8;
}

private static int getRank(int square) {
    return square / 8;
}

private static int getSquare(int rank, int file) {
    return rank * 8 + file;
}

// just like the code snippet, generates the key
private static int transform (long blockers, long magic, int shift) {
    return (int) ((blockers * magic) >>> (64 - shift));
}

private void initBishopLookup() {
    for (int square = 0; square < 64; square++) {
        long mask = BISHOP_MASKS[square];
        int permutationCount = (1 << Long.bitCount(mask));

        for (int i = 0; i < permutationCount; i++) {
            long blockers = blockersPermutation(i, mask);
            long attacks = 0L;
            int rank = getRank(square), r;
            int file = getFile(square), f;

            for (r = rank + 1, f = file + 1; r <= 7 && f <= 7; r++, f++) {
                attacks |= (1L << getSquare(r, f));
                if ((blockers & (1L << getSquare(r, f))) != 0) {
                    break;
                }
            }

            for (r = rank - 1, f = file + 1; r >= 0 && f <= 7; r--, f++) {
                attacks |= (1L << getSquare(r, f));
                if ((blockers & (1L << getSquare(r, f))) != 0) {
                    break;
                }
            }

            for (r = rank - 1, f = file - 1; r >= 0 && f >= 0; r--, f--) {
                attacks |= (1L << getSquare(r, f));
                if ((blockers & (1L << getSquare(r, f))) != 0) {
                    break;
                }
            }

            for (r = rank + 1, f = file - 1; r <= 7 && f >= 0; r++, f--) {
                attacks |= (1L << getSquare(r, f));
                if ((blockers & (1L << getSquare(r, f))) != 0) {
                    break;
                }
            }

            int key = transform(blockers, BISHOP_MAGICS[square], Long.bitCount(mask));

            BISHOP_LOOKUP[square][key] = attacks;
        }
    }
}

This uses plain magic bitboards with fixed size lookup tables, all of length 512 when masks with less set bits could fit in less space. Like on square b1 the mask uses 5 bits on the diagonal and the table could fit in an array of length 2^5 = 32. We're wasting (512 - 32) * (8 bytes per 64 bits number) / 1024 bytes per Kio = 3.75Kio for this square. Plain magic bitboards take 2Mib of memory for rooks and 256Kib for bishops, using fancy magic bitboards can reduce the total to ~800Kib. It's not really needed though, 2.25Mib of memory is small.