Yet another way of generating sliding attack masks
Posted: Mon Mar 09, 2015 12:38 pm
What we do is that we use lsb and msb to get the blocker indexes, and use table lookup to extract things.
Let's begin with rank attacks. Suppose:
occupancy: 11000101, rook: 00010000 (square #3 from the right side)
Now, we will generate masks on the left side of occupancy. First, we mask out the left side:
Left side occupancy: 11000000
Now, get the most significant bit index, to get the index of the first right blocker: 1.
Similarly, right side occupancy: 00000101. Find LSB index in this case, to get first right blocker index : 5.
Use table lookup to generate the attack mask, i.e. rank_attack_table[1][5] = 01111100
Now, simple xor with rook bb to get: 01101100, which is the required attack mask.
One advantage is that we don't need separate tables for bishop and rook attacks. Something like BetweenMask[64][64] would work. It would take 64*64*8/1024 = 32 kB of memory.
Here's the code for rook attacks:
The disadvantage is that explicit check is needed whether there isn't a right or left blocker. The above code fails in those cases. The code for bishops is somewhat similar.
Let's begin with rank attacks. Suppose:
occupancy: 11000101, rook: 00010000 (square #3 from the right side)
Now, we will generate masks on the left side of occupancy. First, we mask out the left side:
Left side occupancy: 11000000
Now, get the most significant bit index, to get the index of the first right blocker: 1.
Similarly, right side occupancy: 00000101. Find LSB index in this case, to get first right blocker index : 5.
Use table lookup to generate the attack mask, i.e. rank_attack_table[1][5] = 01111100
Now, simple xor with rook bb to get: 01101100, which is the required attack mask.
One advantage is that we don't need separate tables for bishop and rook attacks. Something like BetweenMask[64][64] would work. It would take 64*64*8/1024 = 32 kB of memory.
Here's the code for rook attacks:
Code: Select all
inline Bitboard rank_attacks(Bitboard occ, square_t sq)
{
occ &= Bitboards::RankMask[Square::rank_of(sq)];
// mask occupancy on left side,
Bitboard left_occ = occ & ((1ULL << sq) - 1);
// mask occupancy on right side
Bitboard right_occ = occ & ((0xFFFFFFFFFFFFFFFFULL) ^ ((1ULL << sq) - 1));
// Get the first left blocker's index
square_t left_blocker = Bitboards::msb(left_occ);
// Get the first right blocker's index
square_t right_blocker = Bitboards::lsb(right_occ);
// return the attack mask with all bits from left blocker's index to right blocker's
// index set
return BetweenMask[left_blocker][right_blocker];
}
inline Bitboard file_attacks(Bitboard occ, square_t sq)
{
occ &= Bitboards::FileMask[Square::file_of(sq)];
// mask forward occupancy
Bitboard forward_occ = occ & ((0xFFFFFFFFFFFFFFFFULL) ^ ((1ULL << (sq+1)) - 1));
// mask backward occupancy
Bitboard backward_occ = occ & ((1ULL << sq) - 1);
// Get the forward blocker's index
square_t forward_blocker = Bitboards::lsb(forward_occ);
// Get the backward blocker's index
square_t backward_blocker = Bitboards::msb(backward_occ);
// return the attack mask with all bits from first forward blocker's index to first
// backward blocker's index set
return BetweenMask[forward_blocker][backward_blocker];
}
inline Bitboard rook_attacks(Bitboard occ, square_t sq)
{
// Ensure own square is not masked
return (rank_attacks(occ, sq) | file_attacks(occ, sq)) ^ (1ULL << sq);
}