Obstruction Difference

Home * Board Representation * Bitboards * Sliding Piece Attacks * Obstruction Difference

Man Ray - Obstruction, 1947

Obstruction Difference,
a subtraction approach to determine sliding piece attacks with bitboards, proposed by Michael Hoffmann . The idea is to get disjoint positive and negative ray masks of the occupancy, and to subtract the most significant one bit of the negative ray from the doubled least significant one bit (LS1B) of the positive ray. The difference is finally intersected with the linemask, excluding the sliding piece itself from the attack set. However, in 2022, Daniel Infuehr found a faster solution to calculate the obstruction difference: subtract the most significant one bit of the negative ray from the the positive ray obstruction, followed by the symmetric difference to flip all positive ray obstruction bits for the proper result .

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 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 isolation of the LS1B is the intersection of a bitboard with its two's complement, the MS1B is not that simple to extract, and requires a fast 64-bit BitScanReverse, f.i. x86-64 bsr with throughput in the one cycle range, as with Intel's Core 2 or Nehalem architecture, or Leading Zero Count, f.i. x86-64 lzcnt on AMD K10 or Intel Nehalem CPUs.

C Code

The routine works for all lines, ranks, files, diagonals and 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.

Code samples and bitboard diagrams rely on Little endian file and rank mapping.

/*
 * @author Michael Hoffmann, Daniel Infuehr
 * @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, ms1B, odiff;
   lower = pMask->lower & occ;
   upper = pMask->upper & occ;
   ms1B = C64(0x8000000000000000) >> lzcnt(lower | 1); // ms1b of lower (at least bit zero)
   // ls1b  = upper & -upper;
   // odiff = 2 * ls1b - ms1B; 
   odiff = upper ^ (upper - ms1B); // Daniel Infuehr's improvement
   return pMask->lineEx & odiff; // (pMask->lower | pMask->upper) & odiff;
}

To use it that way:

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);
}

The routine looks competitive for CPUs with fast 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.

Java

Java programmers may rely on Long.numberOfLeadingZeros, where the 64-bit JVM may use appropriate machine instructions.

/*
 * @author Michael Hoffmann, Daniel Infuehr
 * @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 odiff = upper ^ (upper - mMs1b);
   return longMasks[sq][line][2] & odiff;
}

See also

• SBAMG

Forum Posts

• DIRECT BITBOARD MOVEGENERATION by Michael Hoffmann, CCC, July 23, 2009
• Re: Sliding Piece Algorithm by Abstract Syntax Tree Sifting [RELEASE] by Daniel Infuehr, CCC, April 17, 2022
• Re: Comparison of all known Sliding lookup algorithms [CUDA] by Daniel Infuehr, CCC, April 24, 2022

References

Up one Level