25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * Sliding Piece Attacks * Obstruction Difference''' FILE:ManRayObstruction.jpg|border|right|thumb|link=..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * Obstruction Difference'''
[[FILE:ManRayObstruction.jpg|border|right|thumb|link=http://www.imj.org.il/en/collections/194569?itemNum=194569
| [[Arts#Ray|Man Ray]] - Obstruction, 1947 <ref>[http://www.imj.org.il/en/collections/194569?itemNum=194569 Man Ray - Obstruction, 1947]], [https://en.wikipedia.org/wiki/Israel_Museum The Israel Museum]</ref> ]]
'''Obstruction Difference''',<br/>
a subtraction approach to determine sliding piece attacks with bitboards, proposed by [[Michael Hoffmann]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=29087 DIRECT BITBOARD MOVEGENERATION] by [[Michael Hoffmann]], [[CCC]], July 23, 2009</ref>. The idea is to get disjoint [[On an empty Board#PositiveRays|positive]] and [[On an empty Board#NegativeRays|negative ray masks]] of the [[Occupancy|occupancy]], and to subtract the [[General Setwise Operations#TheMostSignificantOneBitMS1B|most significant one bit]] of the negative ray from the doubled [[General Setwise Operations#TheLeastSignificantOneBitLS1B|least siginificat one bit]] (LS1B) of the positive ray. The difference is finally intersected with the linemask, excluding the [[Sliding Pieces|sliding piece]] itself from the attack set.
=Empty Sets=
If there is no obstruction inside the positive ray, we simply subtract from zero, aka borrow from the hidden 2^64 bit, same if doubling results in an empty set. If there is no obstruction inside the negative ray, we need at least to subtract one. With neither blocker available, the difference is the universal set -1 (~0), and we end up with the linemask, excluding the sliding piece, which are all [[On an empty Board|attacks on the otherwise empty board]]. Therefor, to subtract at least '1', oring '1' is required if the negative ray occupancy is empty. Since setting the least significant bit does not affect any MS1B extraction, it can be done unconditionally on the negative ray.
=Isolation=
While [[General Setwise Operations#LS1BIsolation|isolation of the LS1B]] is the intersection of a bitboard with its [[General Setwise Operations#TheTwosComplement|two's complement]], the [[General Setwise Operations#TheMostSignificantOneBitMS1B|MS1B]] is not that simple to extract, and requires a fast 64-bit [[BitScan#Bitscanreverse|BitScanReverse]], f.i. [[x86-64]] [[x86-64#gpinstructions|bsr]] with throughput in the [[BitScan#x86Timing|one cycle range]], as with [[Intel|Intel's]] [https://en.wikipedia.org/wiki/Intel_Core_2 Core 2] or [https://en.wikipedia.org/wiki/Nehalem_%28microarchitecture%29 Nehalem architecture], or [[BitScan#LeadingZeroCount|Leading Zero Count]], f.i. [[x86-64]] [[x86-64#gpinstructions|lzcnt]] on [[AMD]] [https://en.wikipedia.org/wiki/AMD_K10 K10] or [[Intel]] Nehalem CPUs.
=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, or in [[C]] even passing a pointer to a structure with three (or multiples for several lines in parallel) bitboards per square and line, upper- and lower rays and the union of both.
[[include page="MappingHint"]]
<pre>
/*
* @author Michael Hoffmann, 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) {
U64 lower, upper, mMS1B, ls1b, odiff;
lower = pMask->lower & occ;
upper = pMask->upper & occ;
mMS1B = -C64(1) << bsr64(lower | 1); // ms1b of lower (at least bit zero)
ls1b = upper & -upper;
odiff = 2 * ls1b + mMS1B; // x86 lea option due to add -ms1b
return pMask->lineEx & odiff; // (pMask->lower | pMask->upper) & odiff;
}
</pre>
To use it that way:
<pre>
struct SMasks
{
U64 lower;
U64 upper;
U64 lineEx; // lower | upper
} masks[64][4]; // 6 (4) KByte, 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>
Since with two's complement i << x == - (-i << x), 2*high-low is done by add for the option to use [http://www.cs.virginia.edu/%7Eevans/cs216/guides/x86.html x86 lea-instruction]. The routine looks competitive for CPUs with fast [[x86-64#gpinstructions|bsr]] or [[x86-64#gpinstructions|lzcnt]] but has problems on processors with slow bitScan or 32-bit processors. Register usage is moderate and should suffice all x88-64 scratch registers for two lines, even for [https://en.wikipedia.org/wiki/Visual_C%2B%2B Visual C++].
=Java=
[[Java]] programmers may rely on [http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Long.html#numberOfLeadingZeros%28long%29 Long.numberOfLeadingZeros], where the 64-bit [https://en.wikipedia.org/wiki/Java_virtual_machine JVM] may use appropriate machine instructions.
<pre>
/*
* @author Michael Hoffmann, Gerd Isenberg
* @param long occ occupancy of the board
* @param int sq 0..63
* @param int line 0..3 for rank, file, dia, antidia
* @return line attacks from that square
*/
long lineAttacks(long occ, int sq, int line) {
long lower = longMasks[sq][line][0] & occ;
long upper = longMasks[sq][line][1] & occ;
long mMs1b = 0x8000000000000000 >> Long.numberOfLeadingZeros (lower | 1);
long ls1b = upper & -upper;
long odiff = 2*ls1b + mMs1b;
return longMasks[sq][line][2] & odiff;
}
</pre>
One may also use unsigned shift right, to subtract the MS1B.
<pre>
long ms1b = 0x8000000000000000 >>> Long.numberOfLeadingZeros (lower | 1);
long ls1b = upper & -upper;
long odiff = 2*ls1b - ms1b;
</pre>
=How it works=
Following bitboard diagrams demonstrate how it works with [[Square Mapping Considerations#LittleEndianRankFileMapping|Little-Endian Rank-File Mapping]], file attacks rook on d4 (27):
<pre>
occupancy fileMaskEx(d4) occupancy d-file
. . . 1 . 1 . . . . . 1 . . . . . . . 1 . . . .
1 . 1 . . 1 1 . . . . 1 . . . . . . . . . . . .
. 1 . 1 . . . 1 . . . 1 . . . . . . . 1 . . . .
. . . . . 1 . . . . . 1 . . . . . . . . . . . .
. 1 . 1 . . . . & . . . . . . . . = . . . R . . . .
. . . . . . 1 . . . . 1 . . . . . . . . . . . .
1 1 . 1 . 1 . 1 . . . 1 . . . . . . . 1 . . . .
. . . 1 1 . 1 . . . . 1 . . . . . . . 1 . . . .
______________________________________
occupancy upper occupancy lower
. . . 1 . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . 1 . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . 1 . . . .
. . . . . . . . . . . 1 . . . .
|
LS1B upper v lower | 1
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . 1 . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . 1 . . . .
. . . . . . . . 1 . . 1 . . . .
______________________________________
2* LS1B upper - MS1B (lower | 1) = 2*LS1Bhigh-MS1Blow
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . 1 . . . . . . . . . . . 1 1 1 1 . . . .
. . . . . . . . . . . . . . . . 1 1 1 1 1 1 1 1
. . . . . . . . - . . . . . . . . = 1 1 1 1 1 1 1 1
. . . . . . . . . . . . . . . . 1 1 1 1 1 1 1 1
. . . . . . . . . . . 1 . . . . . . . 1 1 1 1 1
. . . . . . . . . . . . . . . . . . . . . . . .
2*LS1Bhigh-MS1Blow fileMaskEx = fileAttacks
. . . . . . . . . . . 1 . . . . . . . . . . . .
. . . . . . . . . . . 1 . . . . . . . . . . . .
1 1 1 1 . . . . . . . 1 . . . . . . . 1 . . . .
1 1 1 1 1 1 1 1 . . . 1 . . . . . . . 1 . . . .
1 1 1 1 1 1 1 1 & . . . . . . . . = . . . . . . . .
1 1 1 1 1 1 1 1 . . . 1 . . . . . . . 1 . . . .
. . . 1 1 1 1 1 . . . 1 . . . . . . . 1 . . . .
. . . . . . . . . . . 1 . . . . . . . . . . . .
</pre>
=See also=
* [[SBAMG]]
=References=
<references />
'''[[Sliding Piece Attacks|Up one Level]]'''
[[Category:Man Ray]]
[[FILE:ManRayObstruction.jpg|border|right|thumb|link=http://www.imj.org.il/en/collections/194569?itemNum=194569
| [[Arts#Ray|Man Ray]] - Obstruction, 1947 <ref>[http://www.imj.org.il/en/collections/194569?itemNum=194569 Man Ray - Obstruction, 1947]], [https://en.wikipedia.org/wiki/Israel_Museum The Israel Museum]</ref> ]]
'''Obstruction Difference''',<br/>
a subtraction approach to determine sliding piece attacks with bitboards, proposed by [[Michael Hoffmann]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=29087 DIRECT BITBOARD MOVEGENERATION] by [[Michael Hoffmann]], [[CCC]], July 23, 2009</ref>. The idea is to get disjoint [[On an empty Board#PositiveRays|positive]] and [[On an empty Board#NegativeRays|negative ray masks]] of the [[Occupancy|occupancy]], and to subtract the [[General Setwise Operations#TheMostSignificantOneBitMS1B|most significant one bit]] of the negative ray from the doubled [[General Setwise Operations#TheLeastSignificantOneBitLS1B|least siginificat one bit]] (LS1B) of the positive ray. The difference is finally intersected with the linemask, excluding the [[Sliding Pieces|sliding piece]] itself from the attack set.
=Empty Sets=
If there is no obstruction inside the positive ray, we simply subtract from zero, aka borrow from the hidden 2^64 bit, same if doubling results in an empty set. If there is no obstruction inside the negative ray, we need at least to subtract one. With neither blocker available, the difference is the universal set -1 (~0), and we end up with the linemask, excluding the sliding piece, which are all [[On an empty Board|attacks on the otherwise empty board]]. Therefor, to subtract at least '1', oring '1' is required if the negative ray occupancy is empty. Since setting the least significant bit does not affect any MS1B extraction, it can be done unconditionally on the negative ray.
=Isolation=
While [[General Setwise Operations#LS1BIsolation|isolation of the LS1B]] is the intersection of a bitboard with its [[General Setwise Operations#TheTwosComplement|two's complement]], the [[General Setwise Operations#TheMostSignificantOneBitMS1B|MS1B]] is not that simple to extract, and requires a fast 64-bit [[BitScan#Bitscanreverse|BitScanReverse]], f.i. [[x86-64]] [[x86-64#gpinstructions|bsr]] with throughput in the [[BitScan#x86Timing|one cycle range]], as with [[Intel|Intel's]] [https://en.wikipedia.org/wiki/Intel_Core_2 Core 2] or [https://en.wikipedia.org/wiki/Nehalem_%28microarchitecture%29 Nehalem architecture], or [[BitScan#LeadingZeroCount|Leading Zero Count]], f.i. [[x86-64]] [[x86-64#gpinstructions|lzcnt]] on [[AMD]] [https://en.wikipedia.org/wiki/AMD_K10 K10] or [[Intel]] Nehalem CPUs.
=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, or in [[C]] even passing a pointer to a structure with three (or multiples for several lines in parallel) bitboards per square and line, upper- and lower rays and the union of both.
[[include page="MappingHint"]]
<pre>
/*
* @author Michael Hoffmann, 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) {
U64 lower, upper, mMS1B, ls1b, odiff;
lower = pMask->lower & occ;
upper = pMask->upper & occ;
mMS1B = -C64(1) << bsr64(lower | 1); // ms1b of lower (at least bit zero)
ls1b = upper & -upper;
odiff = 2 * ls1b + mMS1B; // x86 lea option due to add -ms1b
return pMask->lineEx & odiff; // (pMask->lower | pMask->upper) & odiff;
}
</pre>
To use it that way:
<pre>
struct SMasks
{
U64 lower;
U64 upper;
U64 lineEx; // lower | upper
} masks[64][4]; // 6 (4) KByte, 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>
Since with two's complement i << x == - (-i << x), 2*high-low is done by add for the option to use [http://www.cs.virginia.edu/%7Eevans/cs216/guides/x86.html x86 lea-instruction]. The routine looks competitive for CPUs with fast [[x86-64#gpinstructions|bsr]] or [[x86-64#gpinstructions|lzcnt]] but has problems on processors with slow bitScan or 32-bit processors. Register usage is moderate and should suffice all x88-64 scratch registers for two lines, even for [https://en.wikipedia.org/wiki/Visual_C%2B%2B Visual C++].
=Java=
[[Java]] programmers may rely on [http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Long.html#numberOfLeadingZeros%28long%29 Long.numberOfLeadingZeros], where the 64-bit [https://en.wikipedia.org/wiki/Java_virtual_machine JVM] may use appropriate machine instructions.
<pre>
/*
* @author Michael Hoffmann, Gerd Isenberg
* @param long occ occupancy of the board
* @param int sq 0..63
* @param int line 0..3 for rank, file, dia, antidia
* @return line attacks from that square
*/
long lineAttacks(long occ, int sq, int line) {
long lower = longMasks[sq][line][0] & occ;
long upper = longMasks[sq][line][1] & occ;
long mMs1b = 0x8000000000000000 >> Long.numberOfLeadingZeros (lower | 1);
long ls1b = upper & -upper;
long odiff = 2*ls1b + mMs1b;
return longMasks[sq][line][2] & odiff;
}
</pre>
One may also use unsigned shift right, to subtract the MS1B.
<pre>
long ms1b = 0x8000000000000000 >>> Long.numberOfLeadingZeros (lower | 1);
long ls1b = upper & -upper;
long odiff = 2*ls1b - ms1b;
</pre>
=How it works=
Following bitboard diagrams demonstrate how it works with [[Square Mapping Considerations#LittleEndianRankFileMapping|Little-Endian Rank-File Mapping]], file attacks rook on d4 (27):
<pre>
occupancy fileMaskEx(d4) occupancy d-file
. . . 1 . 1 . . . . . 1 . . . . . . . 1 . . . .
1 . 1 . . 1 1 . . . . 1 . . . . . . . . . . . .
. 1 . 1 . . . 1 . . . 1 . . . . . . . 1 . . . .
. . . . . 1 . . . . . 1 . . . . . . . . . . . .
. 1 . 1 . . . . & . . . . . . . . = . . . R . . . .
. . . . . . 1 . . . . 1 . . . . . . . . . . . .
1 1 . 1 . 1 . 1 . . . 1 . . . . . . . 1 . . . .
. . . 1 1 . 1 . . . . 1 . . . . . . . 1 . . . .
______________________________________
occupancy upper occupancy lower
. . . 1 . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . 1 . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . 1 . . . .
. . . . . . . . . . . 1 . . . .
|
LS1B upper v lower | 1
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . 1 . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . 1 . . . .
. . . . . . . . 1 . . 1 . . . .
______________________________________
2* LS1B upper - MS1B (lower | 1) = 2*LS1Bhigh-MS1Blow
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . 1 . . . . . . . . . . . 1 1 1 1 . . . .
. . . . . . . . . . . . . . . . 1 1 1 1 1 1 1 1
. . . . . . . . - . . . . . . . . = 1 1 1 1 1 1 1 1
. . . . . . . . . . . . . . . . 1 1 1 1 1 1 1 1
. . . . . . . . . . . 1 . . . . . . . 1 1 1 1 1
. . . . . . . . . . . . . . . . . . . . . . . .
2*LS1Bhigh-MS1Blow fileMaskEx = fileAttacks
. . . . . . . . . . . 1 . . . . . . . . . . . .
. . . . . . . . . . . 1 . . . . . . . . . . . .
1 1 1 1 . . . . . . . 1 . . . . . . . 1 . . . .
1 1 1 1 1 1 1 1 . . . 1 . . . . . . . 1 . . . .
1 1 1 1 1 1 1 1 & . . . . . . . . = . . . . . . . .
1 1 1 1 1 1 1 1 . . . 1 . . . . . . . 1 . . . .
. . . 1 1 1 1 1 . . . 1 . . . . . . . 1 . . . .
. . . . . . . . . . . 1 . . . . . . . . . . . .
</pre>
=See also=
* [[SBAMG]]
=References=
<references />
'''[[Sliding Piece Attacks|Up one Level]]'''
[[Category:Man Ray]]
