Page 1 of 1

### Yet another way of generating sliding attack masks

Posted: Mon Mar 09, 2015 11:38 am
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:

Code: Select all

``````inline Bitboard rank_attacks&#40;Bitboard occ, square_t sq&#41;
&#123;
// mask occupancy on left side,
Bitboard left_occ = occ & (&#40;1ULL << sq&#41; - 1&#41;;
// mask occupancy on right side
Bitboard right_occ = occ & (&#40;0xFFFFFFFFFFFFFFFFULL&#41; ^ (&#40;1ULL << sq&#41; - 1&#41;);
// Get the first left blocker's index
square_t left_blocker = Bitboards&#58;&#58;msb&#40;left_occ&#41;;
// Get the first right blocker's index
square_t right_blocker = Bitboards&#58;&#58;lsb&#40;right_occ&#41;;
// return the attack mask with all bits from left blocker's index to right blocker's
// index set
&#125;
inline Bitboard file_attacks&#40;Bitboard occ, square_t sq&#41;
&#123;
Bitboard forward_occ = occ & (&#40;0xFFFFFFFFFFFFFFFFULL&#41; ^ (&#40;1ULL << &#40;sq+1&#41;) - 1&#41;);
Bitboard backward_occ = occ & (&#40;1ULL << sq&#41; - 1&#41;;
// Get the forward blocker's index
square_t forward_blocker = Bitboards&#58;&#58;lsb&#40;forward_occ&#41;;
// Get the backward blocker's index
square_t backward_blocker = Bitboards&#58;&#58;msb&#40;backward_occ&#41;;
// return the attack mask with all bits from first forward blocker's index to first
// backward blocker's index set
&#125;
inline Bitboard rook_attacks&#40;Bitboard occ, square_t sq&#41;
&#123;
// Ensure own square is not masked
return &#40;rank_attacks&#40;occ, sq&#41; | file_attacks&#40;occ, sq&#41;) ^ &#40;1ULL << sq&#41;;
&#125;
``````
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.

### Re: Yet another way of generating sliding attack masks

Posted: Mon Mar 09, 2015 12:08 pm
A similar idea but without arrays is the one that I used in my didactic engine:

Code: Select all

``````/* return the bitboard with the rook destinations */
static inline TBB GenRook&#40;uint64_t sq,TBB occupation&#41;
&#123;
TBB piece = 1ULL<<sq;
occupation ^= piece; /* remove the selected piece from the occupation */
TBB piecesup=&#40;0x0101010101010101ULL<<sq&#41;&&#40;occupation|0xFF00000000000000ULL&#41;; /* find the pieces up */
TBB piecesdo=&#40;0x8080808080808080ULL>>&#40;63-sq&#41;)&&#40;occupation|0x00000000000000FFULL&#41;; /* find the pieces down */
TBB piecesri=&#40;0x00000000000000FFULL<<sq&#41;&&#40;occupation|0x8080808080808080ULL&#41;; /* find pieces on the right */
TBB piecesle=&#40;0xFF00000000000000ULL>>&#40;63-sq&#41;)&&#40;occupation|0x0101010101010101ULL&#41;; /* find pieces on the left */
return ((&#40;0x8080808080808080ULL>>&#40;63-LSB&#40;piecesup&#41;))&&#40;0x0101010101010101ULL<<MSB&#40;piecesdo&#41;)) |
(&#40;0xFF00000000000000ULL>>&#40;63-LSB&#40;piecesri&#41;))&&#40;0x00000000000000FFULL<<MSB&#40;piecesle&#41;)))^piece;
/* From every direction find the first piece and from that piece put a mask in the opposite direction.
Put togheter all the 4 masks and remove the moving piece */
&#125;

/* return the bitboard with the bishops destinations */
static inline TBB GenBishop&#40;uint64_t sq,TBB occupation&#41;
&#123;	/* it's the same as the rook */
TBB piece = 1ULL<<sq;
occupation ^= piece;
TBB piecesup=&#40;0x8040201008040201ULL<<sq&#41;&&#40;occupation|0xFF80808080808080ULL&#41;;
TBB piecesdo=&#40;0x8040201008040201ULL>>&#40;63-sq&#41;)&&#40;occupation|0x01010101010101FFULL&#41;;
TBB piecesle=&#40;0x8102040810204081ULL<<sq&#41;&&#40;occupation|0xFF01010101010101ULL&#41;;
TBB piecesri=&#40;0x8102040810204081ULL>>&#40;63-sq&#41;)&&#40;occupation|0x80808080808080FFULL&#41;;
return ((&#40;0x8040201008040201ULL>>&#40;63-LSB&#40;piecesup&#41;))&&#40;0x8040201008040201ULL<<MSB&#40;piecesdo&#41;)) |
(&#40;0x8102040810204081ULL>>&#40;63-LSB&#40;piecesle&#41;))&&#40;0x8102040810204081ULL<<MSB&#40;piecesri&#41;)))^piece;
&#125;
``````

### Re: Yet another way of generating sliding attack masks

Posted: Mon Mar 09, 2015 2:14 pm
vittyvirus wrote: 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.
The Obstruction Difference by Michael Hoffmann also works with extraction of both blockers, but calcs the bitmasks (1 << square) , and uses the line-masked difference rather than a between lookup. Due to the "| 1", this works without conditions if there is no blocker on a ray of a line.

### Re: Yet another way of generating sliding attack masks

Posted: Mon Mar 09, 2015 2:23 pm
Fabio Gobbato wrote:A similar idea but without arrays is the one that I used in my didactic engine:

Code: Select all

``````/* return the bitboard with the rook destinations */
static inline TBB GenRook&#40;uint64_t sq,TBB occupation&#41;
&#123;
TBB piece = 1ULL<<sq;
occupation ^= piece; /* remove the selected piece from the occupation */
TBB piecesup=&#40;0x0101010101010101ULL<<sq&#41;&&#40;occupation|0xFF00000000000000ULL&#41;; /* find the pieces up */
TBB piecesdo=&#40;0x8080808080808080ULL>>&#40;63-sq&#41;)&&#40;occupation|0x00000000000000FFULL&#41;; /* find the pieces down */
TBB piecesri=&#40;0x00000000000000FFULL<<sq&#41;&&#40;occupation|0x8080808080808080ULL&#41;; /* find pieces on the right */
TBB piecesle=&#40;0xFF00000000000000ULL>>&#40;63-sq&#41;)&&#40;occupation|0x0101010101010101ULL&#41;; /* find pieces on the left */
return ((&#40;0x8080808080808080ULL>>&#40;63-LSB&#40;piecesup&#41;))&&#40;0x0101010101010101ULL<<MSB&#40;piecesdo&#41;)) |
(&#40;0xFF00000000000000ULL>>&#40;63-LSB&#40;piecesri&#41;))&&#40;0x00000000000000FFULL<<MSB&#40;piecesle&#41;)))^piece;
/* From every direction find the first piece and from that piece put a mask in the opposite direction.
Put togheter all the 4 masks and remove the moving piece */
&#125;

/* return the bitboard with the bishops destinations */
static inline TBB GenBishop&#40;uint64_t sq,TBB occupation&#41;
&#123;	/* it's the same as the rook */
TBB piece = 1ULL<<sq;
occupation ^= piece;
TBB piecesup=&#40;0x8040201008040201ULL<<sq&#41;&&#40;occupation|0xFF80808080808080ULL&#41;;
TBB piecesdo=&#40;0x8040201008040201ULL>>&#40;63-sq&#41;)&&#40;occupation|0x01010101010101FFULL&#41;;
TBB piecesle=&#40;0x8102040810204081ULL<<sq&#41;&&#40;occupation|0xFF01010101010101ULL&#41;;
TBB piecesri=&#40;0x8102040810204081ULL>>&#40;63-sq&#41;)&&#40;occupation|0x80808080808080FFULL&#41;;
return ((&#40;0x8040201008040201ULL>>&#40;63-LSB&#40;piecesup&#41;))&&#40;0x8040201008040201ULL<<MSB&#40;piecesdo&#41;)) |
(&#40;0x8102040810204081ULL>>&#40;63-LSB&#40;piecesle&#41;))&&#40;0x8102040810204081ULL<<MSB&#40;piecesri&#41;)))^piece;
&#125;
``````
Very nice calculation method without any lookup.

### Re: Yet another way of generating sliding attack masks

Posted: Mon Mar 09, 2015 3:28 pm
vittyvirus wrote: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:

Code: Select all

``````inline Bitboard rank_attacks&#40;Bitboard occ, square_t sq&#41;
&#123;
// mask occupancy on left side,
Bitboard left_occ = occ & (&#40;1ULL << sq&#41; - 1&#41;;
// mask occupancy on right side
Bitboard right_occ = occ & (&#40;0xFFFFFFFFFFFFFFFFULL&#41; ^ (&#40;1ULL << sq&#41; - 1&#41;);
// Get the first left blocker's index
square_t left_blocker = Bitboards&#58;&#58;msb&#40;left_occ&#41;;
// Get the first right blocker's index
square_t right_blocker = Bitboards&#58;&#58;lsb&#40;right_occ&#41;;
// return the attack mask with all bits from left blocker's index to right blocker's
// index set
&#125;
inline Bitboard file_attacks&#40;Bitboard occ, square_t sq&#41;
&#123;
Bitboard forward_occ = occ & (&#40;0xFFFFFFFFFFFFFFFFULL&#41; ^ (&#40;1ULL << &#40;sq+1&#41;) - 1&#41;);
Bitboard backward_occ = occ & (&#40;1ULL << sq&#41; - 1&#41;;
// Get the forward blocker's index
square_t forward_blocker = Bitboards&#58;&#58;lsb&#40;forward_occ&#41;;
// Get the backward blocker's index
square_t backward_blocker = Bitboards&#58;&#58;msb&#40;backward_occ&#41;;
// return the attack mask with all bits from first forward blocker's index to first
// backward blocker's index set