Slider attack mask generation without table lookup
Posted: Sun May 24, 2015 4:22 pm
Let's jump straight to the code:
What we actually do (very simplified version)
1. Get the index of the first blocker behind this square.
2. Mask this square and the next square for subtraction.
3. Subtract it (and the square on which the piece resides) from the occupancy. This will give you required attacks in both directions.
3. 'Xor' it with occupancy to also target the first blocker (and to so some other stuff too).
4. 'And' it with the file mask... and Bingo!
I 'discovered' this technique months ago, but was not able to post it because the motherboard of my laptop needed to be repaired (repaired it just today!). This works for diagonals and anti diagonals as well. I measured the speed for rook attacks on MSVC++ with BitScanReverse64() and _byteswap_uint64() intrinsics but the results were not too encouraging:
1. It took 8.31 secs for 1000000000 or so rounds. (Writing this from memory, I recorded the timings but not the no. of rounds, and I'm too lazy to redo the timings...)
2. Magic Bitboards took 6.39 secs for the same thing (sometimes less than 6 secs!)
3. Hyperbola Quintessence is faster for file attacks
I feel that there is scope for improvement. Even if it doesn't get faster than Magic Bitboards or HQ, it'd atleast make up a good replacement of Kindergarden Bitboards for Hyperbola Quintessence.
Code: Select all
Bitboard rank_attacks(int sq, Bitboard occ) {
static const Bitboard OuterSquares = 0x8181818181818181ULL;
assert(!(occ & (1ULL << sq))); // occ must not mask sq
occ = (occ | OuterSquares) & RankMask[rank_of(sq)];
return ((occ - ((3ULL << msb(occ & ((1ULL << sq) - 1))) | (1ULL << sq))) ^ occ) & RankSqMask[sq];
}
Bitboard file_attacks(int sq, Bitboard occ) {
static const Bitboard OuterSquares = 0xFF000000000000FFULL;
assert(!(occ & (1ULL << sq))); // occ must not mask sq
occ = (occ | OuterSquares) & FileMask[file_of(sq)];
return ((occ - ((3ULL << msb(occ & ((1ULL << sq) - 1))) | (1ULL << sq))) ^ occ) & FileSqMask[sq];
}
1. Get the index of the first blocker behind this square.
2. Mask this square and the next square for subtraction.
3. Subtract it (and the square on which the piece resides) from the occupancy. This will give you required attacks in both directions.
3. 'Xor' it with occupancy to also target the first blocker (and to so some other stuff too).
4. 'And' it with the file mask... and Bingo!
I 'discovered' this technique months ago, but was not able to post it because the motherboard of my laptop needed to be repaired (repaired it just today!). This works for diagonals and anti diagonals as well. I measured the speed for rook attacks on MSVC++ with BitScanReverse64() and _byteswap_uint64() intrinsics but the results were not too encouraging:
1. It took 8.31 secs for 1000000000 or so rounds. (Writing this from memory, I recorded the timings but not the no. of rounds, and I'm too lazy to redo the timings...)
2. Magic Bitboards took 6.39 secs for the same thing (sometimes less than 6 secs!)
3. Hyperbola Quintessence is faster for file attacks
I feel that there is scope for improvement. Even if it doesn't get faster than Magic Bitboards or HQ, it'd atleast make up a good replacement of Kindergarden Bitboards for Hyperbola Quintessence.