Occupancy of any Line
Home * Board Representation * Bitboards * Sliding Piece Attacks * Occupancy of any Line
Occupancy of any Line,
unlike rank attacks, the problem arises for files and diagonals how to get scattered occupancies to consecutive bits of a dense lookup index. In the past, prior to early 2000, 64-bit multiplication was unfeasible - much too slow.
Contents
Avoiding Multiplication
Rotated Bitboards
One solution was the invention of 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 rotate by 90 degrees and pseudo rotate by 90 degrees.
Collapsed Files
Other techniques were about to hash the masked line with parallel prefix shifts to collapse ranks, diagonals or anti-diagonals along the files [2] [3]:
int collapsedFilesIndex(U64 b) { b |= b >> 32; b |= b >> 16; b |= b >> 8; return b & 0xFF; }
In 32-bit mode, assembly programmers may collapse files to register AL in five instructions, saving >> 32 and >> 8:
or eax, edx mov edx, eax shr eax, 16 or eax, edx or al, ah
Collapsed Ranks
For a line along files (as well as diagonals or anti-diagonals), a little more trickery is needed:
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; }
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:
int collapsedRanksIndex(U64 b, enumFile file) { b = b >> file; b &= C64(0x0101010101010101): b |= b >> 7; b |= b >> 14; b |= b >> 28; return b & 0xFF; }
Using Multiplication
Recent 64-bit processors, such as core 2 or K8 have a amazingly fast 64-bit multiplication, so that flip- or rotation-tricks as mentioned in diagonals to rank or flip about the diagonal are competitive nowadays.
Collapsed Files
int collapsedFilesIndex(U64 b) { const U64 aFile = C64(0x0101010101010101); return (b * aFile) >> 56; }
or in 32-bit mode:
int collapsedFilesIndex(U64 b) { unsigned int folded = (unsigned int)b | (unsigned int)(b >> 32); return (folded * 0x01010101) >> 24; }
Collapsed Ranks
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; }
or dedicated for files
int collapsedRanksIndex(U64 b, enumFile file) { const U64 aFile = C64(0x0101010101010101); const U64 antiDia = C64(0x0102040810204080); b = b >> file; return ((b & aFile) * antiDia) >> 56; }
Those techniques are actually used in Kindergarten bitboards, considering the inner six bits for a denser lookup.
See also
- Flipping, Mirroring and Rotating of Rank, File and Diagonal
- Kindergarten Bitboards
- Magic Bitboards
- Rotated Bitboards
- Sliding Piece Attacks in OliThink
Forum Posts
- Re: Rotated bitboards by Urban Koistinen, rgcc, October 31, 1997
- Re: Some thoughts on Dann Corbit's rotated alternative by Steffan Westcott, CCC, March 03, 2006
- Kindergarten bitboards without multiplying by Piotr Cichy, CCC, August 07, 2009 » Kindergarten Bitboards
External Links
- Bit Gather Via Multiplication by Vlad Petric, Dr. Petric's Technical Blog, September 17, 2013 [4]
References
- ↑ Besetzt! (Occupied) - Toilet exhibition at Umspannwerk Recklinghausen, today RWE Technology museum in Recklinghausen, Germany, and part of The Industrial Heritage Trail of the Ruhr area - Row of occupied portable toilets, Photo by Gerd Isenberg, September 16, 2016
- ↑ Re: Rotated bitboards by Urban Koistinen, rgcc, October 31, 1997
- ↑ Re: Some thoughts on Dann Corbit's rotated alternative by Steffan Westcott, CCC, March 03, 2006
- ↑ Demystifying the Magic Multiplier?