How do I complete this implementation of magic bitboards?

Question

I'm currently coding a chess engine in C++, and have run into a bit of trouble with my magic bitboard implementation.

So far, I have a function that calculates blockerBoards (all the possible pieces that can block the rook or the bishop).

From there, I have the following code to take these blockerBoards and convert them into attack tables:

bitset<M> mBishopAttacks[64][512]; // 256 K
bitset<M> mRookAttacks[64][4096]; // 2048K

bitset<M> bishopAttacks(bitset<M> blockerBoard, int sq) {
    unsigned long long index = blockerBoard.to_ullong();
    index *= bishopMagics[sq];
    index >>= 64-9
    return mBishopAttacks[sq][index]; //outputs corresponding attack board
}

Note that I got the array of magic numbers, bishopMagics[64], from somewhere on the web.

How do I initialize these attack tables, mBishopAttacks and mRookAttacks? Currently, they are empty. Do I simply have to calculate the attack tables for each possible permutation of blockers?

Answer 1

It is probably most efficient if I paste my code from my chess move generator on GitHub.

int ROOK_ATTACK_SHIFTS[64];
Bitboard ROOK_ATTACK_MASKS[64];
Bitboard ROOK_ATTACKS[64][4096];

void initialise_rook_attacks() {
    Bitboard edges, subset, index;

    for (Square sq = a1; sq <= h8; ++sq) {
        edges = ((MASK_RANK[AFILE] | MASK_RANK[HFILE]) & ~MASK_RANK[rank_of(sq)]) |
            ((MASK_FILE[AFILE] | MASK_FILE[HFILE]) & ~MASK_FILE[file_of(sq)]);

        ROOK_ATTACK_MASKS[sq] = (MASK_RANK[rank_of(sq)]
            ^ MASK_FILE[file_of(sq)]) & ~edges;

        ROOK_ATTACK_SHIFTS[sq] = 64 - pop_count(ROOK_ATTACK_MASKS[sq]);

        subset = 0;
        do {
            index = subset;
            index = index * ROOK_MAGICS[sq];
            index = index >> ROOK_ATTACK_SHIFTS[sq];
            ROOK_ATTACKS[sq][index] = get_rook_attacks_for_init(sq, subset);
            subset = (subset - ROOK_ATTACK_MASKS[sq]) & ROOK_ATTACK_MASKS[sq];
        } while (subset);
    }
}

Some comments:

• For each square, the bitboard stored in the attacks table is determined by a complicated cycling algorithm. You start with an empty bitboard subset, then manipulate it using the magics and the masks generated previously. This gives you an index. You then initialise the attacks table at ROOK_ATTACKS[sq][index] as the bitboard of slider moves from that square, using the initial value of subset as the occupation bitboard. subset is then updated using the masks, and the loop continues. The nature of the magic numbers is that, starting with subset=0, you will cycle through all 4096 indices (not in order), and subset will turn into the correct "representative" occupation bitboard for all 4096 of these.

• The value of "9" while bitshifting to calculate the index should not be hardcoded. Instead, it should depend on whether the piece is in the centre, on an edge or in a corner, which is what ROOK_ATTACK_MASKS and ROOK_ATTACK_SHIFTS are for. I believe excluding these is a little-known bug

• Once you have generated the occupation/blockers bitboard for a particular index (running from 0 to 4095 for rooks), you can generate the sliding moves to initialise the attacks matrix in any way you want. I personally used hyperbola quintessence, but using a simple flood fill poses no problems, it's all pregenerated anyway

Unfortunately the chess programming wiki does not seem to be very useful on these matters; you are best off reading the original works and talkchess posts by Pradyumna Kannan et al.