Home * Board Representation * Bitboards * Sliding Piece Attacks * SBAMG

SBAMG, (Subtraction based Attack Mask Generation)
a subtraction based approach proposed by Syed Fahad ^[1] which combines techniques used in Subtracting a Rook from a Blocking Piece aka o^(o-2r) and Obstruction Difference. The idea is to subtract three times the closest blocker in negative ray direction (most significant one bit of lower ray occupancy) from the line occupancy, to exclusive or that difference with the line occupancy again: o^(o-3cbn). Three times is necessary, since we need not only to subtract the next highest neigbouring square of the closest blocker for the borrow propagation, but the blocker square itself. The line occupancy excludes the sliding piece itself, and equivalently the final result is again restricted by the line-mask excluding the square of the attacker. Outer squares of the line occupancy, which don't affect resulting line attacks, are always set to avoid conditional code.

Sample

A two nibble sample calculating the rank aka byte attacks of a rook illustrates the technique:

•                    binary     hex  dez
  bit-index          7654 3210  
  blockers and rook  .b.. r.bb
  occ (without rook) 0100 0011  0x43  67
  cbn                0000 0010  0x02   2 
  occ-3cbn           0011 1101  0x3d  61
  occ^(occ-3cbn)     0111 1110  0x7e 126
  attacks (/rook)    0111 0110  0x76 118

C Code

The routine works for all lines, ranks, files, diagonals and anti-diagonals by applying appropriate line-masks, and could therefor used as a generalized routine with a line-direction parameter. Signature and BitScanReverse (bsr64) similar to Obstruction Difference.

Code samples and bitboard diagrams rely on Little endian file and rank mapping.

/*
 * @author Syed Fahad, Gerd Isenberg
 * @param  U64 occ occupancy of the board
 * @param  SMasks* a mask structure by square and line
 * @return line attacks from that square
 */
U64 lineAttacks(U64 occ, const SMasks *pMask) {
   occ &= pMask->lineEx;
   occ |= pMask->outer;
   int bsq = bsr64(occ & pMask->lower);
   U64 cbnx3 = C64(3) << bsq; // or lookup
   occ = occ ^ (occ - cbnx3);
   return occ & pMask->lineEx;
}

To use it that way:

struct SMasks
{
   U64 lower;  // 1 for sq 0, otherwise (1 << sq) - 1
   U64 lineEx; // excluding (1 << sq)
   U64 outer;  // outer & 1 must be 1 to avoid calling bsr(0)
} masks[64][4]; // needs initialization
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   return lineAttacks(occ, masks[sq] + 0) | lineAttacks(occ, masks[sq] + 1);
}
U64 bishopAttacks(U64 occ, enumSquare sq) {
   return lineAttacks(occ, masks[sq] + 2) | lineAttacks(occ, masks[sq] + 3);
}

See also

• Hyperbola Quintessence
• Obstruction Difference
• Subtracting a Rook from a Blocking Piece

Forum Posts

• Slider attack mask generation without table lookup by Syed Fahad, CCC, May 24, 2015
• SBAMG - Competing Hyperbola Quintessence by Syed Fahad, CCC, April 10, 2016 » Hyperbola Quintessence
• Subtraction based Attack Mask Generation by Syed Fahad, CCC, November 16, 2016

References

1. ^ SBAMG - Completing Hyperbola Quintessence by Syed Fahad, CCC, April 10, 2016

What links here?

Up one Level