SBAMG
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
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
- ↑ SBAMG - Completing Hyperbola Quintessence by Syed Fahad, CCC, April 10, 2016