Occupancy of any Line

Home * Board Representation * Bitboards * Sliding Piece Attacks * Occupancy of any Line

Line Occupancy

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.

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 :

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

References

Up one Level