25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * Sliding Piece Attacks * Occupancy of any Line''' FILE:Besetzt20160916.JPG|border|right|thumb|Line Occ..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * Occupancy of any Line'''
[[FILE:Besetzt20160916.JPG|border|right|thumb|Line Occupancy <ref>[https://de-de.facebook.com/umspannwerk.recklinghausen/posts/10153757793891429 Besetzt!] (Occupied) - [https://en.wikipedia.org/wiki/Toilet Toilet] exhibition at [https://de.wikipedia.org/wiki/Umspannwerk_Recklinghausen Umspannwerk Recklinghausen], today [https://en.wikipedia.org/wiki/RWE RWE] [https://en.wikipedia.org/wiki/Technology_museum Technology museum] in [https://en.wikipedia.org/wiki/Recklinghausen Recklinghausen], Germany, and part of [[Arts#IndustrialHeritageTrail|The Industrial Heritage Trail]] of the [https://en.wikipedia.org/wiki/Ruhr Ruhr area] - Row of occupied [https://en.wikipedia.org/wiki/Toilet#Others portable toilets], Photo by [[Gerd Isenberg]], September 16, 2016</ref> ]]
'''Occupancy of any Line''',<br/>
unlike [[First Rank Attacks|rank attacks]], the problem arises for [[Files|files]] and [[Diagonals|diagonals]] how to get scattered [[Occupancy|occupancies]] to consecutive [[Bit|bits]] of a dense lookup index. In the past, prior to early 2000, 64-bit [[General Setwise Operations#Multiplication|multiplication]] was unfeasible - much too slow.
=Avoiding Multiplication=
==Rotated Bitboards==
One solution was the invention of [[Rotated Bitboards|rotated bitboards]] - to keep and maintain three additional rotated occupied bitboards, with consecutive bits for the appropriate rays. Similar to the bit-layout mentioned in [[Flipping Mirroring and Rotating#Rotationby90degreesClockwise|rotate by 90 degrees]] and [[Flipping Mirroring and Rotating#PseudoRotationby45degrees|pseudo rotate by 90 degrees]].
<span id="CollapsedFiles"></span>
==Collapsed Files==
Other techniques were about to hash the masked line with [[Parallel Prefix Algorithms|parallel prefix shifts]] to collapse [[Ranks|ranks]], [[Diagonals|diagonals]] or [[Anti-Diagonals|anti-diagonals]] along the [[Files|files]] <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/YvFagyuVogw/2vNJw_qT8IYJ Re: Rotated bitboards] by [[Urban Koistinen]], [[Computer Chess Forums|rgcc]], October 31, 1997</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=491079 Re: Some thoughts on Dann Corbit's rotated alternative] by [[Steffan Westcott]], [[CCC]], March 03, 2006</ref>:
<pre>
int collapsedFilesIndex(U64 b) {
b |= b >> 32;
b |= b >> 16;
b |= b >> 8;
return b & 0xFF;
}
</pre>
In 32-bit mode, assembly programmers may collapse files to register AL in five instructions, saving >> 32 and >> 8:
<pre>
or eax, edx
mov edx, eax
shr eax, 16
or eax, edx
or al, ah
</pre>
<span id="CollapsedRanks"></span>
==Collapsed Ranks==
For a line along [[Files|files]] (as well as [[Diagonals|diagonals]] or [[Anti-Diagonals|anti-diagonals]]), a little more trickery is needed:
<pre>
int collapsedRanksIndex(U64 b) {
b |= b >> 4;
b |= b >> 2;
b |= b >> 1;
b &= C64(0x0101010101010101):
b |= b >> 7;
b |= b >> 14;
b |= b >> 28;
return b & 0xFF;
}
</pre>
If it is exclusively about to collapse files to ranks, one can save the first three parallel prefix shifts, but shift right by file-index:
<pre>
int collapsedRanksIndex(U64 b, enumFile file) {
b = b >> file;
b &= C64(0x0101010101010101):
b |= b >> 7;
b |= b >> 14;
b |= b >> 28;
return b & 0xFF;
}
</pre>
<span id="Multiplication"></span>
=Using Multiplication=
Recent 64-bit processors, such as [https://en.wikipedia.org/wiki/Intel_Core_2 core 2] or [https://en.wikipedia.org/wiki/Athlon_64 K8] have a amazingly fast 64-bit [[General Setwise Operations#Multiplication|multiplication]], so that flip- or rotation-tricks as mentioned in [[Flipping Mirroring and Rotating#DiagonalstoRanks|diagonals to rank]] or [[Flipping Mirroring and Rotating#FlipAbouttheDiagonal|flip about the diagonal]] are competitive nowadays.
==Collapsed Files==
<pre>
int collapsedFilesIndex(U64 b) {
const U64 aFile = C64(0x0101010101010101);
return (b * aFile) >> 56;
}
</pre>
or in 32-bit mode:
<pre>
int collapsedFilesIndex(U64 b) {
unsigned int folded = (unsigned int)b | (unsigned int)(b >> 32);
return (folded * 0x01010101) >> 24;
}
</pre>
==Collapsed Ranks==
<pre>
int collapsedRanksIndex(U64 b) {
const U64 aFile = C64(0x0101010101010101);
const U64 antiDia = C64(0x0102040810204080);
b |= b >> 4; // No masking needed
b |= b >> 2; // " "
b |= b >> 1; // " "
return ((b & aFile) * antiDia) >> 56;
}
</pre>
or dedicated for files
<pre>
int collapsedRanksIndex(U64 b, enumFile file) {
const U64 aFile = C64(0x0101010101010101);
const U64 antiDia = C64(0x0102040810204080);
b = b >> file;
return ((b & aFile) * antiDia) >> 56;
}
</pre>
Those techniques are actually used in [[Kindergarten Bitboards|Kindergarten bitboards]], considering the [[First Rank Attacks#TheOuterSquares|inner six bits]] for a denser lookup.
=See also=
* [[Flipping Mirroring and Rotating#RankFileAndDiagonal|Flipping, Mirroring and Rotating of Rank, File and Diagonal]]
* [[Kindergarten Bitboards]]
* [[Magic Bitboards]]
* [[Rotated Bitboards]]
* [[OliThink#SlidingPieceAttacks|Sliding Piece Attacks]] in [[OliThink]]
=Forum Posts=
* [https://groups.google.com/d/msg/rec.games.chess.computer/YvFagyuVogw/2vNJw_qT8IYJ Re: Rotated bitboards] by [[Urban Koistinen]], [[Computer Chess Forums|rgcc]], October 31, 1997
* [https://www.stmintz.com/ccc/index.php?id=491079 Re: Some thoughts on Dann Corbit's rotated alternative] by [[Steffan Westcott]], [[CCC]], March 03, 2006
* [http://www.talkchess.com/forum/viewtopic.php?t=29296 Kindergarten bitboards without multiplying] by [[Piotr Cichy]], [[CCC]], August 07, 2009 » [[Kindergarten Bitboards]]
=External Links=
* [http://drpetric.blogspot.com/2013/09/bit-gathering-via-multiplication.html Bit Gather Via Multiplication] by [[Vlad Petric]], [http://drpetric.blogspot.com/ Dr. Petric's Technical Blog], September 17, 2013 <ref>[https://chessprogramming.wikispaces.com/share/view/64439740 Demystifying the Magic Multiplier?]</ref>
=References=
<references />
'''[[Sliding Piece Attacks|Up one Level]]'''
[[FILE:Besetzt20160916.JPG|border|right|thumb|Line Occupancy <ref>[https://de-de.facebook.com/umspannwerk.recklinghausen/posts/10153757793891429 Besetzt!] (Occupied) - [https://en.wikipedia.org/wiki/Toilet Toilet] exhibition at [https://de.wikipedia.org/wiki/Umspannwerk_Recklinghausen Umspannwerk Recklinghausen], today [https://en.wikipedia.org/wiki/RWE RWE] [https://en.wikipedia.org/wiki/Technology_museum Technology museum] in [https://en.wikipedia.org/wiki/Recklinghausen Recklinghausen], Germany, and part of [[Arts#IndustrialHeritageTrail|The Industrial Heritage Trail]] of the [https://en.wikipedia.org/wiki/Ruhr Ruhr area] - Row of occupied [https://en.wikipedia.org/wiki/Toilet#Others portable toilets], Photo by [[Gerd Isenberg]], September 16, 2016</ref> ]]
'''Occupancy of any Line''',<br/>
unlike [[First Rank Attacks|rank attacks]], the problem arises for [[Files|files]] and [[Diagonals|diagonals]] how to get scattered [[Occupancy|occupancies]] to consecutive [[Bit|bits]] of a dense lookup index. In the past, prior to early 2000, 64-bit [[General Setwise Operations#Multiplication|multiplication]] was unfeasible - much too slow.
=Avoiding Multiplication=
==Rotated Bitboards==
One solution was the invention of [[Rotated Bitboards|rotated bitboards]] - to keep and maintain three additional rotated occupied bitboards, with consecutive bits for the appropriate rays. Similar to the bit-layout mentioned in [[Flipping Mirroring and Rotating#Rotationby90degreesClockwise|rotate by 90 degrees]] and [[Flipping Mirroring and Rotating#PseudoRotationby45degrees|pseudo rotate by 90 degrees]].
<span id="CollapsedFiles"></span>
==Collapsed Files==
Other techniques were about to hash the masked line with [[Parallel Prefix Algorithms|parallel prefix shifts]] to collapse [[Ranks|ranks]], [[Diagonals|diagonals]] or [[Anti-Diagonals|anti-diagonals]] along the [[Files|files]] <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/YvFagyuVogw/2vNJw_qT8IYJ Re: Rotated bitboards] by [[Urban Koistinen]], [[Computer Chess Forums|rgcc]], October 31, 1997</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=491079 Re: Some thoughts on Dann Corbit's rotated alternative] by [[Steffan Westcott]], [[CCC]], March 03, 2006</ref>:
<pre>
int collapsedFilesIndex(U64 b) {
b |= b >> 32;
b |= b >> 16;
b |= b >> 8;
return b & 0xFF;
}
</pre>
In 32-bit mode, assembly programmers may collapse files to register AL in five instructions, saving >> 32 and >> 8:
<pre>
or eax, edx
mov edx, eax
shr eax, 16
or eax, edx
or al, ah
</pre>
<span id="CollapsedRanks"></span>
==Collapsed Ranks==
For a line along [[Files|files]] (as well as [[Diagonals|diagonals]] or [[Anti-Diagonals|anti-diagonals]]), a little more trickery is needed:
<pre>
int collapsedRanksIndex(U64 b) {
b |= b >> 4;
b |= b >> 2;
b |= b >> 1;
b &= C64(0x0101010101010101):
b |= b >> 7;
b |= b >> 14;
b |= b >> 28;
return b & 0xFF;
}
</pre>
If it is exclusively about to collapse files to ranks, one can save the first three parallel prefix shifts, but shift right by file-index:
<pre>
int collapsedRanksIndex(U64 b, enumFile file) {
b = b >> file;
b &= C64(0x0101010101010101):
b |= b >> 7;
b |= b >> 14;
b |= b >> 28;
return b & 0xFF;
}
</pre>
<span id="Multiplication"></span>
=Using Multiplication=
Recent 64-bit processors, such as [https://en.wikipedia.org/wiki/Intel_Core_2 core 2] or [https://en.wikipedia.org/wiki/Athlon_64 K8] have a amazingly fast 64-bit [[General Setwise Operations#Multiplication|multiplication]], so that flip- or rotation-tricks as mentioned in [[Flipping Mirroring and Rotating#DiagonalstoRanks|diagonals to rank]] or [[Flipping Mirroring and Rotating#FlipAbouttheDiagonal|flip about the diagonal]] are competitive nowadays.
==Collapsed Files==
<pre>
int collapsedFilesIndex(U64 b) {
const U64 aFile = C64(0x0101010101010101);
return (b * aFile) >> 56;
}
</pre>
or in 32-bit mode:
<pre>
int collapsedFilesIndex(U64 b) {
unsigned int folded = (unsigned int)b | (unsigned int)(b >> 32);
return (folded * 0x01010101) >> 24;
}
</pre>
==Collapsed Ranks==
<pre>
int collapsedRanksIndex(U64 b) {
const U64 aFile = C64(0x0101010101010101);
const U64 antiDia = C64(0x0102040810204080);
b |= b >> 4; // No masking needed
b |= b >> 2; // " "
b |= b >> 1; // " "
return ((b & aFile) * antiDia) >> 56;
}
</pre>
or dedicated for files
<pre>
int collapsedRanksIndex(U64 b, enumFile file) {
const U64 aFile = C64(0x0101010101010101);
const U64 antiDia = C64(0x0102040810204080);
b = b >> file;
return ((b & aFile) * antiDia) >> 56;
}
</pre>
Those techniques are actually used in [[Kindergarten Bitboards|Kindergarten bitboards]], considering the [[First Rank Attacks#TheOuterSquares|inner six bits]] for a denser lookup.
=See also=
* [[Flipping Mirroring and Rotating#RankFileAndDiagonal|Flipping, Mirroring and Rotating of Rank, File and Diagonal]]
* [[Kindergarten Bitboards]]
* [[Magic Bitboards]]
* [[Rotated Bitboards]]
* [[OliThink#SlidingPieceAttacks|Sliding Piece Attacks]] in [[OliThink]]
=Forum Posts=
* [https://groups.google.com/d/msg/rec.games.chess.computer/YvFagyuVogw/2vNJw_qT8IYJ Re: Rotated bitboards] by [[Urban Koistinen]], [[Computer Chess Forums|rgcc]], October 31, 1997
* [https://www.stmintz.com/ccc/index.php?id=491079 Re: Some thoughts on Dann Corbit's rotated alternative] by [[Steffan Westcott]], [[CCC]], March 03, 2006
* [http://www.talkchess.com/forum/viewtopic.php?t=29296 Kindergarten bitboards without multiplying] by [[Piotr Cichy]], [[CCC]], August 07, 2009 » [[Kindergarten Bitboards]]
=External Links=
* [http://drpetric.blogspot.com/2013/09/bit-gathering-via-multiplication.html Bit Gather Via Multiplication] by [[Vlad Petric]], [http://drpetric.blogspot.com/ Dr. Petric's Technical Blog], September 17, 2013 <ref>[https://chessprogramming.wikispaces.com/share/view/64439740 Demystifying the Magic Multiplier?]</ref>
=References=
<references />
'''[[Sliding Piece Attacks|Up one Level]]'''
