25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * Sliding Piece Attacks * SBAMG''' '''SBAMG''', (Subtraction based Attack Mask Generation)<br/> a subtrac..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * SBAMG'''
'''SBAMG''', (Subtraction based Attack Mask Generation)<br/>
a subtraction based approach proposed by [[Syed Fahad]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=59845 SBAMG - Completing Hyperbola Quintessence] by [[Syed Fahad]], [[CCC]], April 10, 2016</ref> 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 [[On an empty Board#NegativeRays|negative ray]] [[Direction|direction]] ([[General Setwise Operations#TheMostSignificantOneBitMS1B|most significant one bit]] of lower ray [[Occupancy|occupancy]]) from the line [[Occupancy|occupancy]], to [[General Setwise Operations#ExclusiveOr|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|nibble]] sample calculating the [[Ranks|rank]] aka [[Byte|byte]] attacks of a rook illustrates the technique:
<pre>
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
</pre>
=C Code=
The routine works for all lines, [[Ranks|ranks]], [[Files|files]], [[Diagonals|diagonals]] and [[Anti-Diagonals|anti-diagonals]] by applying appropriate line-masks, and could therefor used as a generalized routine with a line-direction parameter. Signature and [[BitScan#Bitscanreverse|BitScanReverse]] (bsr64) similar to [[Obstruction Difference]].
{{MappingHint}}
<pre>
/*
* @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;
}
</pre>
To use it that way:
<pre>
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);
}
</pre>
=See also=
* [[Hyperbola Quintessence]]
* [[Obstruction Difference]]
* [[Subtracting a Rook from a Blocking Piece]]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=56468 Slider attack mask generation without table lookup] by [[Syed Fahad]], [[CCC]], May 24, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=59845 SBAMG - Competing Hyperbola Quintessence] by [[Syed Fahad]], [[CCC]], April 10, 2016 ยป [[Hyperbola Quintessence]]
* [http://www.talkchess.com/forum/viewtopic.php?t=62159 Subtraction based Attack Mask Generation] by [[Syed Fahad]], [[CCC]], November 16, 2016
=References=
<references />
'''[[Sliding Piece Attacks|Up one Level]]'''
'''SBAMG''', (Subtraction based Attack Mask Generation)<br/>
a subtraction based approach proposed by [[Syed Fahad]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=59845 SBAMG - Completing Hyperbola Quintessence] by [[Syed Fahad]], [[CCC]], April 10, 2016</ref> 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 [[On an empty Board#NegativeRays|negative ray]] [[Direction|direction]] ([[General Setwise Operations#TheMostSignificantOneBitMS1B|most significant one bit]] of lower ray [[Occupancy|occupancy]]) from the line [[Occupancy|occupancy]], to [[General Setwise Operations#ExclusiveOr|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|nibble]] sample calculating the [[Ranks|rank]] aka [[Byte|byte]] attacks of a rook illustrates the technique:
<pre>
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
</pre>
=C Code=
The routine works for all lines, [[Ranks|ranks]], [[Files|files]], [[Diagonals|diagonals]] and [[Anti-Diagonals|anti-diagonals]] by applying appropriate line-masks, and could therefor used as a generalized routine with a line-direction parameter. Signature and [[BitScan#Bitscanreverse|BitScanReverse]] (bsr64) similar to [[Obstruction Difference]].
{{MappingHint}}
<pre>
/*
* @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;
}
</pre>
To use it that way:
<pre>
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);
}
</pre>
=See also=
* [[Hyperbola Quintessence]]
* [[Obstruction Difference]]
* [[Subtracting a Rook from a Blocking Piece]]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=56468 Slider attack mask generation without table lookup] by [[Syed Fahad]], [[CCC]], May 24, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=59845 SBAMG - Competing Hyperbola Quintessence] by [[Syed Fahad]], [[CCC]], April 10, 2016 ยป [[Hyperbola Quintessence]]
* [http://www.talkchess.com/forum/viewtopic.php?t=62159 Subtraction based Attack Mask Generation] by [[Syed Fahad]], [[CCC]], November 16, 2016
=References=
<references />
'''[[Sliding Piece Attacks|Up one Level]]'''
