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

		Obstruction Difference is another subtraction approach, proposed by Michael Hoffmann [1]. 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 siginificat one bit (LS1B) of the positive ray. The difference is finally intersected with the linemask, excluding the sliding piece itself from the attack set.
Man Ray, Obstruction, 1947 [2]

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, Gerd Isenberg
 * @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, mMS1B, ls1b, odiff;
   lower = pMask->lower & occ;
   upper = pMask->upper & occ;
   mMS1B = -C64(1) << bsr64(lower | 1); // ms1b of lower (at least bit zero)
   ls1b  = upper & -upper;
   odiff = 2 * ls1b + mMS1B; // x86 lea option due to add -ms1b
   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);
}

Since with two's complement i << x == - (-i << x), 2*high-low is done by add for the option to use x86 lea-instruction. The routine looks competitive for CPUs with fast bsr or 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, even for Visual C++.

Java

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

/*
 * @author Michael Hoffmann, Gerd Isenberg
 * @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 ls1b  = upper & -upper;
   long odiff = 2*ls1b + mMs1b;
   return longMasks[sq][line][2] & odiff;
}

One may also use unsigned shift right, to subtract the MS1B.

   long ms1b  = 0x8000000000000000 >>> Long.numberOfLeadingZeros (lower | 1);
   long ls1b  = upper & -upper;
   long odiff = 2*ls1b - ms1b;

How it works

Following bitboard diagrams demonstrate how it works with Little-Endian Rank-File Mapping, file attacks rook on d4 (27):

occupancy              fileMaskEx(d4)           occupancy d-file
 . . . 1 . 1 . .       . . . 1 . . . .          . . . 1 . . . .
 1 . 1 . . 1 1 .       . . . 1 . . . .          . . . . . . . .
 . 1 . 1 . . . 1       . . . 1 . . . .          . . . 1 . . . .
 . . . . . 1 . .       . . . 1 . . . .          . . . . . . . .
 . 1 . 1 . . . .   &   . . . . . . . .    =     . . . R . . . .
 . . . . . . 1 .       . . . 1 . . . .          . . . . . . . .
 1 1 . 1 . 1 . 1       . . . 1 . . . .          . . . 1 . . . .
 . . . 1 1 . 1 .       . . . 1 . . . .          . . . 1 . . . .
______________________________________
 
occupancy upper        occupancy lower
 . . . 1 . . . .       . . . . . . . .
 . . . . . . . .       . . . . . . . .
 . . . 1 . . . .       . . . . . . . .
 . . . . . . . .       . . . . . . . .
 . . . . . . . .       . . . . . . . .
 . . . . . . . .       . . . . . . . .
 . . . . . . . .       . . . 1 . . . .
 . . . . . . . .       . . . 1 . . . .
                   |
LS1B upper         v   lower | 1
 . . . . . . . .       . . . . . . . .
 . . . . . . . .       . . . . . . . .
 . . . 1 . . . .       . . . . . . . .
 . . . . . . . .       . . . . . . . .
 . . . . . . . .       . . . . . . . .
 . . . . . . . .       . . . . . . . .
 . . . . . . . .       . . . 1 . . . .
 . . . . . . . .       1 . . 1 . . . .
______________________________________
 
2* LS1B upper      -   MS1B (lower | 1)   =    2*LS1Bhigh-MS1Blow
 . . . . . . . .       . . . . . . . .         . . . . . . . .
 . . . . . . . .       . . . . . . . .         . . . . . . . .
 . . . . 1 . . .       . . . . . . . .         1 1 1 1 . . . .
 . . . . . . . .       . . . . . . . .         1 1 1 1 1 1 1 1
 . . . . . . . .   -   . . . . . . . .    =    1 1 1 1 1 1 1 1
 . . . . . . . .       . . . . . . . .         1 1 1 1 1 1 1 1
 . . . . . . . .       . . . 1 . . . .         . . . 1 1 1 1 1
 . . . . . . . .       . . . . . . . .         . . . . . . . .
 
 
2*LS1Bhigh-MS1Blow     fileMaskEx         =    fileAttacks
 . . . . . . . .       . . . 1 . . . .         . . . . . . . .
 . . . . . . . .       . . . 1 . . . .         . . . . . . . .
 1 1 1 1 . . . .       . . . 1 . . . .         . . . 1 . . . .
 1 1 1 1 1 1 1 1       . . . 1 . . . .         . . . 1 . . . .
 1 1 1 1 1 1 1 1   &   . . . . . . . .    =    . . . . . . . .
 1 1 1 1 1 1 1 1       . . . 1 . . . .         . . . 1 . . . .
 . . . 1 1 1 1 1       . . . 1 . . . .         . . . 1 . . . .
 . . . . . . . .       . . . 1 . . . .         . . . . . . . .

See also

• SBAMG

References

1. ^ DIRECT BITBOARD MOVEGENERATION by Michael Hoffmann, CCC, July 23, 2009
2. ^ IMAGINE - The Israel Museum's searchable collections database

What links here?

Up one Level