4

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?

1
  • 1
    I assume you know this wiki?
    – Sleafar
    Mar 12, 2021 at 18:26

1 Answer 1

3

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.

3
  • I am confused about this subset = (subset - ROOK_ATTACK_MASKS[sq]) & ROOK_ATTACK_MASKS[sq]; line. How exactly is it supposed to work, because it doesn't for me?
    – Tom Gebel
    Dec 20, 2021 at 17:44
  • @TomGebel could you elaborate on what the issue is? Which programming language are you using? Dec 29, 2021 at 9:20
  • I am using C++. You claim that subset should turn into all possible permutations of the attack mask, but it does not when I try to replicate your example. The attack mask generation is definitely working correctly, I don't see where I could have made a mistake. No matter what square I am indexing, subset always turns to 1 and then to 0. Any ideas?
    – Tom Gebel
    Dec 30, 2021 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.