Yet another way of generating sliding attack masks

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

User avatar
vittyvirus
Posts: 646
Joined: Wed Jun 18, 2014 2:30 pm
Full name: Fahad Syed

Yet another way of generating sliding attack masks

Post by vittyvirus »

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(Bitboard occ, square_t sq)
  {
    occ &= Bitboards::RankMask[Square::rank_of(sq)];
	// 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
    return BetweenMask&#91;left_blocker&#93;&#91;right_blocker&#93;;
&#125;
  inline Bitboard file_attacks&#40;Bitboard occ, square_t sq&#41;
  &#123;
    occ &= Bitboards&#58;&#58;FileMask&#91;Square&#58;&#58;file_of&#40;sq&#41;&#93;;
	// mask forward occupancy
    Bitboard forward_occ = occ & (&#40;0xFFFFFFFFFFFFFFFFULL&#41; ^ (&#40;1ULL << &#40;sq+1&#41;) - 1&#41;); 
	// mask backward occupancy
    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
    return BetweenMask&#91;forward_blocker&#93;&#91;backward_blocker&#93;;
  &#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.
Top
User avatar
Fabio Gobbato
Posts: 217
Joined: Fri Apr 11, 2014 10:45 am
Full name: Fabio Gobbato

Re: Yet another way of generating sliding attack masks

Post by Fabio Gobbato »

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;
Top
Gerd Isenberg
Posts: 2250
Joined: Wed Mar 08, 2006 8:47 pm
Location: Hattingen, Germany

Re: Yet another way of generating sliding attack masks

Post by Gerd Isenberg »

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.
Top
Gerd Isenberg
Posts: 2250
Joined: Wed Mar 08, 2006 8:47 pm
Location: Hattingen, Germany

Re: Yet another way of generating sliding attack masks

Post by Gerd Isenberg »

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.
Top
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Yet another way of generating sliding attack masks

Post by bob »

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;
    occ &= Bitboards&#58;&#58;RankMask&#91;Square&#58;&#58;rank_of&#40;sq&#41;&#93;;
	// 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
    return BetweenMask&#91;left_blocker&#93;&#91;right_blocker&#93;;
&#125;
  inline Bitboard file_attacks&#40;Bitboard occ, square_t sq&#41;
  &#123;
    occ &= Bitboards&#58;&#58;FileMask&#91;Square&#58;&#58;file_of&#40;sq&#41;&#93;;
	// mask forward occupancy
    Bitboard forward_occ = occ & (&#40;0xFFFFFFFFFFFFFFFFULL&#41; ^ (&#40;1ULL << &#40;sq+1&#41;) - 1&#41;); 
	// mask backward occupancy
    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
    return BetweenMask&#91;forward_blocker&#93;&#91;backward_blocker&#93;;
  &#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.
This is old, and is the way most would have done direct attack computation prior to rotated bit boards. Rotated bit boards reduced the four steps (four different directions for a rook or bishop) to two, one for one complete ray, one for the other. Magic reduces that to one operation, getting all the attack bits with one lookup.
Top

Return to “Computer Chess Club: Programming and Technical Discussions”