## Yet another way of generating sliding attack masks

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
vittyvirus
Posts: 646
Joined: Wed Jun 18, 2014 12:30 pm

### Yet another way of generating sliding attack masks

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.

Fabio Gobbato
Posts: 156
Joined: Fri Apr 11, 2014 8:45 am
Full name: Fabio Gobbato
Contact:

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

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;
``````

Gerd Isenberg
Posts: 2192
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

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

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.

Gerd Isenberg
Posts: 2192
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

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

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.

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

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

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