Occupancy of any Line
Home * Board Representation * Bitboards * Sliding Piece Attacks * Occupancy of any Line
Line Occupancy [1] 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.
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]:
In 32-bit mode, assembly programmers may collapse files to register AL in five instructions, saving » 32 and » 8:
Collapsed Ranks
For a line along files (as well as diagonals or anti-diagonals), a little more trickery is needed:
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:
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
or in 32-bit mode:
Collapsed Ranks
or dedicated for files
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 Cinnamon
- 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? ( Wayback Machine, August 20, 2018)