Blockers and Beyond

From Chessprogramming wiki
Jump to: navigation, search

Home * Board Representation * Bitboards * Sliding Piece Attacks * Blockers and Beyond

Blockers and Beyond,
a general bitboard technique to determine not only sliding piece attacks, but also king and knight attacks. The technique was introduced by Fabien Letouzey within his first release of the open source engine Senpai 1.0 in March 2014 [1] [2], but already devised in the mid 2000s, and applied in Fabien's private bitboard engine Chess-64 [3]. He found it simple and elegant with the endgame in mind [4], and dubbed it "blocker loop", a term already coined by Fritz Reul in the context of his non bitboard architecture [5], thus the editor's proposal of "Blockers and Beyond" [6] .

How it works

The routine gets the pre-calculated attack-set on the otherwise empty board by looking up a two-dimensional array indexed by piece kind and origin square. Further, the occupancy of the whole board is intersected by a piece-kind and origin square specific blocker and beyond (b&b) mask, which is always empty for none sliding pieces. For sliders, the b&b mask almost equals the attack-set, except that the redundant most outer squares with no more ray-squares behind are cleared. Serializing the intersection with clearing all bits on the ray from the origin behind the potential blocker square finally determines the sliding attack set, whether it is a bishop, rook or queen.

Of course, if there are multiple pieces on a ray, the routine performs multiple ray-resets with different lengths, which are redundant for the outer pieces beyond the first blocker without affecting the result. Despite the loop and branch issues, the routine has a tiny loop body, skips empty rays, has no conditional code on the (sign of) the ray-direction, and is quite competitive, specially in rook, bishop and queen endings with high mobility.

Sample C Source

[7]

U64 arrPieceAttacks[6][64];
U64 arrBlockersAndBeyond[6][64];
U64 arrBehind[64][64];

U64 pieceAttacks(int pc, int f, U64 occupied) {
   assert(pc != piece::PAWN);

   U64 ts = arrPieceAttacks[pc][f];
   for (U64 b = occupied & arrBlockersAndBeyond[pc][f]; b != 0; b &= (b - 1)) {
      int sq = bitScanForward(b);
      ts &= ~arrBehind[f][sq];
   }
   return ts;
} 

For a queen on d4, with up to 27 attacked squares, the blockers and beyond cardinality of all eight rays is 19:

 pieceAttacks[q][d4]   blockers&beyond[q][d4]
 . . . 1 . . . 1       . . . . . . . .
 1 . . 1 . . 1 .       . . . 1 . . 1 .
 . 1 . 1 . 1 . .       . 1 . 1 . 1 . .
 . . 1 1 1 . . .       . . 1 1 1 . . .
 1 1 1 Q 1 1 1 1       . 1 1 Q 1 1 1 .
 . . 1 1 1 . . .       . . 1 1 1 . . .
 . 1 . 1 . 1 . .       . 1 . 1 . 1 . .
 1 . . 1 . . 1 .       . . . . . . . .

See also

Forum Posts

External Links

John McLaughlin, Billy Cobham, Rick Laird, Jan Hammer, Jerry Goodman

References

  1. Senpai 1.0 (new engine) by Fabien Letouzey, CCC, March 17, 2014
  2. Senpai Chess Engine - Computer Chess Programming hosted by Steve Maughan
  3. Personal communication with Fabien Letouzey, March 20, 2014
  4. Re: Senpai 1.0 (new engine) by Fabien Letouzey, CCC, March 17, 2014
  5. Fritz Reul (2009). New Architectures in Computer Chess. Ph.D. Thesis, Chapter 2 Non-Bitboard Architectures.
  6. Re: Senpai 1.0 (new engine) by Gerd Isenberg, CCC, March 17, 2014
  7. adapted to common CPW types and style from Senpai 1.0 source bit_t piece_attacks_from(int pc, int f, const board::Board & bd), senpai_10.cpp, line 1867

Up one Level