Wikispaces : chessprogramming - items matching description

Attack and Defend Maps

GerdIsenberg — Sat, 05 Nov 2016 09:18:44 GMT

Home * Programming * Data * Attack and Defend Maps

		Attack and Defend Maps, also called Attack Tables, refer to data-structures, most often arrays, containing attack or defend information for every pawn or piece and/or the transposed information for each square, which pieces control, that is either attack or defend it. These Maps are useful for evaluation purposes such as safe mobility, SEE and of course move generation. While the piece centric attack information, a set of attacked squares per piece, is often encoded as bitboard, there are more alternatives for storing the square centric information, about attacking pieces.
Samuel Bak - Sheltering Myths, 1998 ^[1]

Maintaining Attacks

Incremental Update

The piece centric and/or square centric information is often initialized at the root and updated incrementally during the search while making and unmaking moves. The idea is that a move has often only a local influence on the attack tables, and that it is usually cheaper to change only those squares which changed from- or to-attacks, rather than all squares from scratch. This is especially true during the opening or early middlegame phase, but does become more expensive in the late middlegame or endings with sliding pieces, especially queens.

On the Fly

Programmers like Joël Rivat ^[2], Robert Hyatt ^[3], Ed Schröder and Gerd Isenberg avoid or have abandoned incrementally updated attack tables and rely on the paradigm to process information if needed. A lot of nodes don't need the attack information at all, or only a small part of it. With all the hash tables, incremental update tends to do some unnecessary work, considering the update costs in "worst case" positions, f.i. queen endings, where one move change the attack information of many squares.

On the other hand, if attack tables are available, one should utilize the information as much as possible for a smarter search and evaluation to gain exponentially. Anyway, one has to be careful with too complicated data structures and update code.

Implementations

Classical Approach

The square centric classical approach with bitboards was used in Chess 4.5 and descibed by Larry Atkin and David Slate ^[4] . The incrementally updated attack tables, from which most move generation is done, are called ATKFR and ATKTO. ATKFR is a set of 64 bitboards which give, for each square, all the squares attacked by the piece, if any, that resides on the square. ATKTO (Square Attacked By) is the transpose of ATKFR, giving for each square, the locations of all pieces that attack that square. For instance the square E4 (T) is attacked by a black rook at E8, a black knight at F6, and defended by a white rook at E1 and a white pawn at D3 ^[5] :

attacks_to[E4]
 . . . . 1 . . .
 . . . . . . . .
 . . . . . 1 . .
 . . . . . . . .
 . . . . T . . .
 . . . 1 . . . .
 . . . . . . . .
 . . . . 1 . . .

Alternatives

There are several alternatives for keeping the square centric information what pieces attack each particular square.

Piece-Sets

A Square Attacked By bitboard aka ATKFR as possible union-set of multiple pawns and pieces of either side require intersections with piece bitboards, or bitscanned square lookups, to determine which pieces and how many attack or defend.

Based on a fixed piece-type and bit-position relation with usual material dispositions (for each side, no more than one queen, two rooks, one bishop per square color, two knights), 32-bit Piece-Sets already inherit the information which pieces (and how many of both sides) attack a particular square, one can even imagine a 16-bit lookup inside a 64KByte table to get an denser attack indicator/count byte for each color a lá Ed Schröder. MS-DOS IsiChess maintained an array of 64 32-bit piece-sets for every square, and an array of up to 32 attack-to bitboards for every piece. However working with piece-sets requires an additional indirection via a Piece-list to get the square of that piece.

Ed's lookup

As described by Ed Schröder in Evaluation in REBEL ^[6] , Rebel uses two board tables for both sides, one byte entry each, the three lower bits contain an attack counter, while the five upper bits indicate the presence of least one pawn or piece attacking/defending:

+------+------+------+------+------+------+------+------+
| BIT0 | BIT1 | BIT2 | BIT3 | BIT4 | BIT5 | BIT6 | BIT7 |
+------+------+------+------+------+------+------+------+
|      Number of     | PAWN |KNIGHT| ROOK | QUEEN| KING |
|      ATTACKERS     |      |BISHOP|      |      |      |
+------+------+------+------+------+------+------+------+

The information might be inaccurate in some cases since it loses some information if multiple pieces of one kind are involved. However, since SEE might be erroneous anyway due to pins, x-rays or overloaded pieces, Ed's scheme seems sufficient for practical purposes - and it is fast. Each byte (for both sides) can act as index inside pre-calculated three-dimensional table to perform an SEE by looking up a target piece or square, attack- and defend-byte:

char see_table [14][256][256];   // 14*64 K = 896 KByte
 
see = see_table[Piece][attackByte][defendByte];

While the counter might be updated incrementally, the piece indicators as possible union of multiple pieces (i.e. two knights and one bishop) is not that simple to update, thus Ed generates those tables in evaluation on the fly by scanning the pieces of the board.

Direction wise

An other alternative to incremental updated attack tables is motivated by direction wise fill algorithms like Kogge-Stone for sliding pieces, and that one may hide memory latencies from probes of the transposition table. Especially pawn attacks are cheap to determine on the fly, and likely reduce the set of capture targets of least valuable pieces defended by pawns, which are otherwise object of Quiescence Search or SEE.

Forums Posts

1995 ...

Chess programming using bitboards by Joël Rivat, rgcc, August 18, 1995
Attack Tables by Roberto Waldteufel, CCC, October 20, 1998

2000 ...

Counting attacked squares: how? by Leen Ammeraal, CCC, January 24, 2002
attacks_from[] and attacks_to[] info by Nagendra Singh Tomar, CCC, October 21, 2002
Attack tables by Andreas Herrmann, CCC, November 20, 2002
The Zappa Attack Table Code by Anthony Cozzie, CCC, May 05, 2004
bitboards and incrementally updated attack tables by Eric Oldre, CCC, June 30, 2004
Attack table by Anonymous, Winboard Forum, October 06, 2004

2005 ...

Attack table musings by GeoffW, Winboard Forum, February 11, 2005
Incremental updating for positional evaluation by Steven Edwards, CCC, March 27, 2008
Piece attacks count by Marco Costalba, CCC, May 18, 2009 » Population Count

2010 ...

Incrementally-updated attack map by Harm Geert Muller, April 21, 2014 » Incremental Updates

References

^ The Game of War from Samuel Bak - represented by Pucker Gallery since 1969
^ Chess programming using bitboards by Joël Rivat, rgcc, August 18, 1995
^ Speed of Move Generator by Valavan Manohararajah, rgcc, August 15, 1995, post 5 by Robert Hyatt where he mentions on the fly generation with rotated bitboards
^ David Slate and Larry Atkin (1977). CHESS 4.5 - The Northwestern University Chess Program. Chess Skill in Man and Machine (ed. Peter W. Frey), pp. 82-118. Springer-Verlag, New York, N.Y. 2nd ed. 1983. ISBN 0-387-90815-3. Reprinted (1988) in Computer Chess Compendium
^ Rotated bitmaps, a new twist on an old idea by Robert Hyatt
^ Evaluation in REBEL (hanging pieces) from How Rebel Plays Chess by Ed Schröder, also available as pdf

What links here?

Page	Date Edited
Andreas Herrmann	Nov 7, 2014
Arasan	Apr 8, 2018
Attack and Defend Maps	Nov 5, 2016
Bebe	Dec 23, 2017
Bitboards	Nov 14, 2017
BlackBishop	Nov 7, 2014
Board Representation	Dec 11, 2017
Bruja	Feb 3, 2015
CAPS	Dec 23, 2017
Check	Feb 1, 2018
Chess (Program)	Dec 22, 2017
Chess 0.5	Nov 20, 2016
Chest	Mar 3, 2015
Combinatorial Logic	Apr 6, 2017
Constellation	Oct 2, 2016
DanChess	Jun 17, 2012
Data	Nov 26, 2017
Deflection	May 21, 2011
Diablo	May 17, 2016
Dorpsgek	Apr 2, 2018
Double Attack	Oct 22, 2014
Encoding Moves	Mar 27, 2016
Eugen	Jan 7, 2016
Eugenio Castillo Jiménez	Jul 23, 2017
Eye Movements	Jul 22, 2015
Floyd	Sep 11, 2016
Golch	Dec 7, 2017
Gromit	Apr 5, 2017
Hagrid	Apr 12, 2016
Horizon	Mar 17, 2013
Incremental Updates	Sep 6, 2017
Interception	May 21, 2011
Interference	May 20, 2011
Joker NL	Sep 15, 2017
José Carlos Martínez Galán	Feb 19, 2017
King Safety	Feb 14, 2018
KnightCap	Nov 6, 2016
Legal Move	Feb 16, 2017
M-20	Oct 9, 2013
Mate at a Glance	Sep 24, 2014
Mediocre	Feb 27, 2015
MessChess	Mar 6, 2014
Mikhail Botvinnik	Jul 15, 2017
Mobility	Jan 17, 2018
Movei	Jan 7, 2016
MVV-LVA	Oct 26, 2017
Neural Networks	Mar 12, 2018
Node Types	Oct 22, 2017
Nullmover	Jul 21, 2013
Ostrich	Dec 28, 2017
Overloading	May 5, 2017
Pandix	Feb 4, 2017
Patzer	Apr 5, 2017
Perceiver	Nov 21, 2017
Peter Fendrich	May 19, 2017
Piece-Sets	Jun 9, 2017
Pioneer	Dec 23, 2017
Population Count	Sep 3, 2017
RDChess	May 3, 2013
Rookie	Jan 7, 2016
SEE - The Swap Algorithm	Jun 5, 2017
SnailChess	Nov 26, 2014
Snitch	Apr 7, 2016
SOMA	Mar 25, 2015
Spartacus	Oct 17, 2016
Spector	Nov 11, 2016
Square Attacked By	Jan 20, 2018
Square Control	Sep 15, 2016
Static Exchange Evaluation	Dec 14, 2017
Sunsetter	Jun 1, 2017
Tao	Jan 8, 2016
Vladimir Butenko	Aug 12, 2013
Woodpusher	Dec 12, 2016
Zach Wegner	Jan 7, 2016
Zappa	Oct 24, 2017

Up one Level

Blockers and Beyond

GerdIsenberg — Fri, 21 Mar 2014 11:23:01 GMT

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 .       . . . . . . . .

External Links

Blocker from Wikipedia
Alpha blocker from Wikipedia
Beta blocker from Wikipedia
Beyond from Wikipedia
Mahavishnu Orchestra - Miles Beyond, Music Inn, Lenox, Ma - July 21, 1973, YouTube Video
John McLaughlin, Billy Cobham, Rick Laird, Jan Hammer, Jerry Goodman

References

^ Senpai 1.0 (new engine) by Fabien Letouzey, CCC, March 17, 2014
^ Senpai Chess Engine - Computer Chess Programming hosted by Steve Maughan
^ Personal communication with Fabien Letouzey, March 20, 2014
^ Re: Senpai 1.0 (new engine) by Fabien Letouzey, CCC, March 17, 2014
^ Fritz Reul (2009). New Architectures in Computer Chess. Ph.D. Thesis, Chapter 2 Non-Bitboard Architectures.
^ Re: Senpai 1.0 (new engine) by Gerd Isenberg, CCC, March 17, 2014
^ 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

What links here?

Page	Date Edited
Blockers and Beyond	Mar 21, 2014
Chess-64	Mar 21, 2014
Classical Approach	Jan 28, 2018
Draughts	Jul 12, 2017
On an empty Board	Mar 18, 2014
Senpai	Nov 10, 2017
Sliding Piece Attacks	May 27, 2016

Up one Level

Classical Approach

GerdIsenberg — Sun, 28 Jan 2018 18:03:50 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Classical Approach

The classical approach to generate sliding piece attacks was probably first used by Chess and Kaissa.

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

Ray Attacks

The classical approach works ray-wise and uses pre-calculated ray-attacks for each of the eight ray-directions and each of the 64 squares. It has to distinguish between positive and negative directions, because it has to bitscan the ray-attack intersection with the occupancy in different orders. That usually don't cares for getting line- or piece attacks, since one likely unrolls all directions needed for a particular line or piece - otherwise one may rely on a generalized bitscan.

We rely on the compass rose to enumerate ray-directions:

  noWe         nort         noEa
          +7    +8    +9
              \  |  /
  west    -1 <-  0 -> +1    east
              /  |  \
          -9    -8    -7
  soWe         sout         soEa

Positive Rays

Attacks of Positive Ray-Directions:

East (+1)           North (+8)           NorthEast (+9)      NorthWest (+7)
. . . . . . . .     . . . 1 . . . .      . . . . . . . 1     . . . . . . . .
. . . . . . . .     . . . 1 . . . .      . . . . . . 1 .     1 . . . . . . .
. . . . . . . .     . . . 1 . . . .      . . . . . 1 . .     . 1 . . . . . .
. . . . . . . .     . . . 1 . . . .      . . . . 1 . . .     . . 1 . . . . .
. . . R 1 1 1 1     . . . R . . . .      . . . B . . . .     . . . B . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .

Conditional

The first step gets the ray-attack on the otherwise empty board. Potential blockers are then determined by intersection with the occupancy, the set of all pieces. The first blocker, if any, is the least significant one-bit of the intersection. A bitscan forward determines the square of the first blocker, to reset it's ray-bits from the attack set. For instance a bishop on g2:

occupied         &  NorthWest(g2)       {a8, c6}
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 B 1     . . . . . . . .     . . . . . . . .
1 1 1 1 1 . 1 1     . . . . . . . .     . . . . . . . .
 
                    xor NorthWest(c6 = bitscanForward{a8,c6}
                    1 . . . . . . .
                    . 1 . . . . . .
                    . . . . . . . .
                    . . . . . . . .
                    . . . . . . . .
                    . . . . . . . .
                    . . . . . . . .
                    . . . . . . . .
 
                    =  final northWest Attacks
                    . . . . . . . .
                    . . . . . . . .
                    . . 1 . . . . .
                    . . . 1 . . . .
                    . . . . 1 . . .
                    . . . . . 1 . .
                    . . . . . . . .
                    . . . . . . . .

U64 rayAttacks[8][64];
 
U64 getPositiveRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {
   U64 attacks = rayAttacks[dir8][square];
   U64 blocker = attacks & occupied;
   if ( blocker ) {
      square = bitScanForward(blocker);
      attacks ^= rayAttacks[dir8][square];
   }
   return attacks;
}

Branchless

Branches are evil with todays super pipelined processors. Even if branch-prediction heuristics become smarter, branch-less solutions allow better scheduling and parallel speedup of independent instruction chains, like processing several directions.

Considering todays fast x86-64 bsf-instruction of Core 2 or K10, a branch-less solution may be worth a try. Due to the fact the occupancy of the outer squares doesn't affect the attack set, setting the most significant bit ensures to scan at least an outer square, which would address an empty ray set anyway, therefor not affecting the final result with no blocker or a most outer one.

U64 getRayAttacks(U64 occupied, enumDir dir8, unsigned long square) {
   U64 attacks    = rayAttacks[dir8][square];
   U64 blocker    =  attacks & occupied;
   _BitScanForward64 (&square, blocker | C64(0x8000000000000000));
   return attacks ^ rayAttacks[dir8][square];
}

Negative Rays

Attacks of Negative Ray-Directions:

West (-1)           South (-8)           SouthWest (-9)      SouthEast (-7)
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
1 1 1 R . . . .     . . . R . . . .      . . . B . . . .     . . . B . . . .
. . . . . . . .     . . . 1 . . . .      . . 1 . . . . .     . . . . 1 . . .
. . . . . . . .     . . . 1 . . . .      . 1 . . . . . .     . . . . . 1 . .
. . . . . . . .     . . . 1 . . . .      1 . . . . . . .     . . . . . . 1 .

Conditional

Works the same way, but needs reverse bitscan to find the first blocking piece, if any.

U64 getNegativeRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {
   U64 attacks = rayAttacks[dir8][square];
   U64 blocker = attacks & occupied;
   if ( blocker ) {
      square = bitScanReverse(blocker);
      attacks ^= rayAttacks[dir8][square];
   }
   return attacks;
}

Branchless

The branch-less solution with a fast x86-64 bsr-instruction allows better scheduling and parallel speedup of independent instruction chains, like processing several directions. Setting the least significant bit ensures to scan at least an outer square, which would address an empty ray set anyway, therefor not affecting the final result with no blocker or a most outer one.

U64 getRayAttacks(U64 occupied, enumDir dir8, unsigned long square) {
   U64 attacks    = rayAttacks[dir8][square];
   U64 blocker    =  attacks & occupied;
   _BitScanReverse64 (&square, blocker | 1);
   return attacks ^ rayAttacks[dir8][square];
}

Generalized

The idea of the generalized bitscan may be used to share the same code for all directions. The implementation of isNegative(dir8), a macro or inline-function, depends on the definition or enumeration of the directions and is likely a compare or test instruction.

Conditional

The conditional by a good predictable branch on blocker is favorable - specially for slow bitscans with some chance to skip it, e.g. in endings.

U64 getRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {
   U64 attacks = rayAttacks[dir8][square];
   U64 blocker = attacks & occupied;
   if ( blocker ) {
      square = bitScan(blocker, isNegative(dir8));
      attacks ^= rayAttacks[dir8][square];
   }
   return attacks;
}

Branchless

The branch-less routine provides a dirMask as universal set for negative rays and the empty set for positive rays, to implement the generalized bitscan. The dirBit-or ensures to scan at least outer square with empty ray sets.

U64 getRayAttacks(U64 occupied, enumDir dir8, unsigned long square) {
   U64 attacks    = rayAttacks[dir8][square];
   U64 blocker    =  attacks & occupied;
   blocker       &= -blocker | dirMask[dir8];
   blocker       |=            dirBit [dir8]
   _BitScanReverse64 (&square, blocker | dirBit[dir8]);
   return attacks ^ rayAttacks[dir8][square];
}

Zero Count

If available, Leading- or Trailing Zero Count instructions may be used instead of bitscan for another branch-less solution of the classical attack getter. Since they leave 64 for empty sets, it needs to make the ray attack arrays one greater to allow index by 64 which contains an empty set - or one needs to map 64 to 63 for positive directions.

U64 rayAttacks[8][65];
 
U64 getPositiveRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {
   U64 attacks = rayAttacks[dir8][square];
   U64 blocker = attacks & occupied;
   int firstBlockingSquare = trailingZeroCount(blocker);
   attacks ^= rayAttacks[dir8][firstBlockingSquare];
   return attacks;
}

LeadingZeroCount instead of bitscanReverse may be done similarly, considering the reversed order.

Line Attacks

As mentioned, line attacks are the union of positive and opposite negative ray-directions - since they are disjoint one may also use 'xor' or 'add':

U64 diagonalAttacks(U64 occ, enumSquare sq) {
  return getPositiveRayAttacks(occ, noEa, sq)
       | getNegativeRayAttacks(occ, soWe, sq); // ^ +
}
 
U64 antiDiagAttacks(U64 occ, enumSquare sq) {
  return getPositiveRayAttacks(occ, noWe, sq)
       | getNegativeRayAttacks(occ, soEa, sq); // ^ +
}
 
U64 fileAttacks (U64 occ, enumSquare sq) {
  return getPositiveRayAttacks(occ, nort, sq)
       | getNegativeRayAttacks(occ, sout, sq); // ^ +
}
 
U64 rankAttacks (U64 occ, enumSquare sq) {
  return getPositiveRayAttacks(occ, east, sq)
       | getNegativeRayAttacks(occ, west, sq); // ^ +
}

Piece Attacks

Union of Line Attacks

Of course piece attacks are the union of the line attacks:

U64 rookAttacks (U64 occ, enumSquare sq) {
  return fileAttacks(occ, sq)
       | rankAttacks(occ, sq); // ^ +
}
 
U64 bishopAttacks (U64 occ, enumSquare sq) {
  return diagonalAttacks(occ, sq)
       | antiDiagAttacks(occ, sq); // ^ +
}
 
U64 queenAttacks (U64 occ, enumSquare sq) {
  return rookAttacks  (occ, sq)
       | bishopAttacks(occ, sq); // ^ +
}

In one Run

As mentioned by Robert Hyatt ^[1], instead of fetching four ray-attacks on the otherwise empty board, one may already use the rook- or bishop attacks to reset outer squares from that union set.

A further improvement was suggested by Michael Sherwin ^[2], to union the occupancy with the outer bits 0 and 63. Together with appropriate bits set in separate ray-masks, this yields to an efficient branchless solution with 13 64-bit operations in total and 4.5 KByte for the lookup tables for both rooks and bishops each.

struct {
  U64 bitsN;  // bits North, including MSB (bit 63)
  U64 bitsE;  // bits East, including MSB
  U64 bitsS;  // bits South, including LSB (bit 0 == 1)
  U64 bitsW;  // bits West, including LSB 
} CACHE_ALIGN rayWstop[64]; 
 
U64 attacksEmpty[64];
U64 rayN[64];
U64 rayE[64];
U64 rayS[64];
U64 rayW[64];
 
U64 rookAttacks(U64 occ, unsigned int sq) {
   unsigned long ulN, ulE, ulS, ulW;
   occ |= C64(0x8000000000000001);
   _BitScanForward64(&ulN, occ & rayWstop[sq].bitsN);
   _BitScanForward64(&ulE, occ & rayWstop[sq].bitsE);
   _BitScanReverse64(&ulS, occ & rayWstop[sq].bitsS);
   _BitScanReverse64(&ulW, occ & rayWstop[sq].bitsW);
   return attacksEmpty[sq]^rayN[ulN]^rayE[ulE]^rayS[ulS]^rayW[ulW];
}

Publications

Stuart Cracraft (1984). Bitmap move generation in Chess. ICCA Journal, Vol. 7, No. 3, pp. 146–153
Fridel Fainshtein (2006). An Orthodox k-Move Problem-Composer for Chess Directmates. M.Sc. thesis, Bar-Ilan University, pdf, Appendix D - 64-bit Representation, pp. 105
Fridel Fainshtein, Yaakov HaCohen-Kerner (2006). A Chess Composer of Two-Move Mate Problems. ICGA Journal, Vol. 29, No. 1, pdf, Appendix E: 64-bit representation

Forum Posts

Re: Thinker output by Robert Hyatt, CCC, March 25, 2009
Re: Yet another bitboard attack generator by Robert Hyatt, CCC, October 28, 2009
Modified old 64 bit attack getter by Michael Sherwin, CCC, December 06, 2009

References

^ Re: Yet another bitboard attack generator by Robert Hyatt, CCC, October 28, 2009
^ Modified old 64 bit attack getter by Michael Sherwin, CCC, December 06, 2009

What links here?

Page	Date Edited
Andscacs	Jan 16, 2018
Bitfoot	Sep 8, 2015
BitScan	Sep 10, 2017
Blockers and Beyond	Mar 21, 2014
Classical Approach	Jan 28, 2018
DirGolem	Jun 5, 2016
Fridel Fainshtein	Oct 8, 2014
Hiding the Implementation	Feb 3, 2011
Pieces versus Directions	Oct 6, 2016
SEE - The Swap Algorithm	Jun 5, 2017
Shifted Bitboards	Jan 9, 2011
Sliding Piece Attacks	May 27, 2016
Teki	Mar 29, 2018
Tunguska	Sep 16, 2017
Yaakov HaCohen-Kerner	Aug 23, 2014

Up one Level

Congruent Modulo Bitboards

GerdIsenberg — Wed, 26 Jun 2013 18:26:44 GMT

Modulo vs. Multiplication

Modulo

Congruence relation

Casting out 255

Reciprocal Multiplication

Multiplication

Fenner's and Levene's conclusion

Home * Board Representation * Bitboards * Sliding Piece Attacks * Congruent Modulo Bitboards

Congruent Modulo Bitboards was introduced by Trevor Fenner and Mark Levene in the ICGA Journal, Vol. 31, No. 1 in 2008 ^[1]. While their Perfect Hashing approach provides great mathematical insights in Congruent Modulo arithmetic, their final conclusion in comparison with Hashing Dictionaries, Rotated Bitboards and Magic Bitboards was criticized by the obvious comparison with Kindergarten Bitboards ^[2].

Modulo vs. Multiplication

BitScan broaches the issue of Perfect Hashing with Modulo versus Multiplication as well:

So does the SWAR-Popcount, when it is about to finally add byte-wise populations:

Modulo

Congruence relation

Fenner and Levene use masked lines (not necessarily excluding the sliding piece), that is bitboards with N=8 active bits with k={7,8,9} bits apart, starting with bit zero

$A_{kN} = \{0, k, 2k, ...,(N-1)k\}$

Based on Congruence relation

$b \equiv c \pmod{m}$

or equivalently

$b \mod{m} = c \mod{m}$

they deduced two general perfect hashing functions. The case N <= k with

$h_{1}(a) = a \mod (2^k + 2)$

and the case N <= k + 1

$h_{2}(a) = a \mod (2^{k+1} + 1)$

This results in modulo 514 for diagonals, modulo 257 for anti-diagonals, and modulo 258 for files, to calculate the occupied index. Tables could made denser by storing indices, but that would require a second indirection. While Fenner and Levene used a Matlab 32-bit implementation to conclude their approach might be competitive, this is how it may be implemented in C by looking up pre-calculated attack-bitboards:

U64 arrCmodDiaAttacks [514][64];  // 257 K
U64 arrCmodAntiAttacks[257][64];
U64 arrCmodFileAttacks[258][64];
 
U64 diagonalAttacks(U64 occ, enumSquare sq) {
   const U64 aDia = C64(0x8040201008040201);
   occ = ( (occ >> diashift[sq]) & aDia) % 514;
   return arrCmodDiaAttacks[occ][sq];
}
 
U64 antiDiagAttacks(U64 occ, enumSquare sq) {
   const U64 aAntiDiaShr7 = C64(0x0002040810204081);
   occ = ( (occ >> antishift[sq]) & aAntiDiaShr7 ) % 257;
   return arrCmodAntiAttacks[occ][sq];
}
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   const U64 aFile = C64(0x0101010101010101);
   occ = ( (occ >> (sq&7)) & aFile) % 258;
   return arrCmodFileAttacks[occ][sq];
}

Casting out 255

For ranks, diagonals or anti-diagonals, where the occupancy mask excludes the sliding piece, and the rank-or byte-wise sum of disjoint bits is therefor less than 255, Casting out 256-1 works as well, without any shifts required, and with more space saving options for the lookup table, i. e. similar to Kindergarten Bitboards with shared multiples of first rank attacks and an trailing post-mask with the same line ^[3].

masked occupany  %  256-1            =  A-H    
. . . . . . . H     . . . . . . . .     . . . . . . . .
. . . . . . G .     . . . . . . . .     . . . . . . . . 
. . . . . F . .     . . . . . . . .     . . . . . . . . 
. . . . E . . .     . . . . . . . .     . . . . . . . . 
. . . . . . . .  %  . . . . . . . .  =  . . . . . . . . 
. . C . . . . .     . . . . . . . .     . . . . . . . . 
. B . . . . . .     . . . . . . . .     . . . . . . . . 
A . . . . . . .     1 1 1 1 1 1 1 1     A B C . E F G H

Reciprocal Multiplication

The 64-bit modulo by a constant can be done most efficiently by reciprocal fixed point multiplication, this is how Microsoft Visual C++ 2005 compiler implements the mod constant for x86-64 processors. One 64*64=128 bit multiplication, one shift, one further 32-bit multiplication , one subtraction. Of course using 64-bit division to get the remainder burns even more cycles.

Code:
% 514
 mov    r11d, r10 ; masked diagonal
 mov    rax, ff00ff00ff00ff01H
 mul    r10
 shr    rdx, 9
 imul   edx, 514 ; 00000202H
 sub    r11d, edx
 
% 257
 mov    r11d, r10 ; masked diagonal
 mov    rax, ff00ff00ff00ff01H
 mul    r10
 shr    rdx, 8
 imul   edx, 257 ; 00000101H
 sub    r11d, edx

Multiplication

A Kindergarten like approach might look like this (not considering inner six bits):

U64 arrDiagonalAttacks[256][64];  // 128 K
 
U64 diagonalAttacks(U64 occ, enumSquare sq) {
   occ = (diagonalMask[sq] & occ) * C64(0x0101010101010101) >> 56;
   return arrDiagonalAttacks[occ][sq];
}

and uses one 64*64=64-bit multiplication, with this x86-64 assembly for calculating an eight-bit occupied index:

 mov    rax, 0101010101010101H
 imul   rdx, rax
 shr    rdx, 56

Even Kindergarten File-Attacks are cheaper and faster, not to mention Magic Bitboards, which covers two lines of a rook or bishop in one run.

Fenner's and Levene's conclusion

Quote from their paper pp 11
3.5. Comparison with other Methods

As reported in Hyatt (2007), the rotated and magic bitboard methods are of comparable performance, and Tannous (2007) claims just a small improvement of the direct lookup method over rotated bitboards. It is easy to see that, in terms of the number of computer operations, the efficiency of our method will be similar to that of direct lookup. Thus we are justified in claiming that the computational efficiency of our method is comparable to the others.

Their conclusion was based on following statement of Robert Hyatt ^[4] ...

I had reported this earlier. Magic was no faster than rotated. I switched because of two things...

1. Magic is simpler, and simpler is better as I get older.
2. Magic gives you the opportunity to update the occupied_squares and then generate moves easily.

To do this with rotated bitboards first requires that all rotated bitboards be updated in addition to the normal occupied_squares bitboard. This is faster, if you use the feature (I don't yet, but well might at times).

... and this claim of Sam Tannous ^[5]:

The results shown indicate that directly looking up the attacking moves for sliding pieces in hash tables improves the move generation speeds from 10% to 15% depending on computer architecture. Further efficiencies can be expected in a full implementation where the overhead of maintaining rotated bitboards is eliminated. The implementation and test code is made available in an Open-Source, interactive, chess programming module called “Shatranj” (Tannous, 2006).

Publications

Zbigniew J. Czech, George Havas, Bohdan S. Majewski (1997). Perfect Hashing. Theoretical Computer Science, Vol. 182, Nos. 1-2, pp. 1-143
Trevor Fenner, Mark Levene (2008). Move Generation with Perfect Hashing Functions. ICGA Journal, Vol. 31, No. 1, pp. 3-12. pdf

Forum Posts

Nice Math - Strange Conclusions by Gerd Isenberg, CCC, April 29, 2008
Low memory usage attack bitboard generation by crystalclear, Winboard Forum, October 06, 2011

External Links

References

^ Trevor Fenner, Mark Levene (2008). Move Generation with Perfect Hashing Functions. ICGA Journal, Vol. 31, No. 1, pp. 3-12. pdf
^ Nice Math - Strange Conclusions by Gerd Isenberg, CCC, April 29, 2008
^ Low memory usage attack bitboard generation by crystalclear, Winboard Forum, October 06, 2011
^ Re: BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits by Robert Hyatt, CCC August 25, 2007
^ Sam Tannous (2007). Avoiding Rotated Bitboards with Direct Lookup. ICGA Journal, Vol. 30, No. 2, pp. 85-91, pdf

What links here?

Page	Date Edited
Congruent Modulo Bitboards	Jun 26, 2013
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
General Setwise Operations	Feb 25, 2018
Hash Table	Jan 1, 2018
ICGA Journal	Dec 21, 2017
Mark Levene	Jun 2, 2015
Sliding Piece Attacks	May 27, 2016
Trevor Fenner	Jun 2, 2015

Up one Level

CPW-Engine_attacks

GerdIsenberg — Tue, 30 Dec 2014 18:39:57 GMT

Home * Engines * CPW-Engine * Attacks

This page holds the functions responsible for detecting if a given square is attacked by a given player.

isAttacked

#include "stdafx.h"
#include "0x88_math.h"
 
int isAttacked( char byColor, S8 sq ) {
/* pawns */
if ( byColor == WHITE ) {
   if ( IS_SQ( sq + SE ) &&
        isPiece( WHITE, PAWN, sq + SE )
      )
      return 1;
   if ( IS_SQ( sq + SW ) &&
        isPiece( WHITE, PAWN, sq + SW )
      )
      return 1;
}
else {
   if ( IS_SQ( sq + NE ) &&
        isPiece( BLACK, PAWN, sq + NE )
      )
      return 1;
   if ( IS_SQ( sq + NW ) &&
        isPiece( BLACK, PAWN, sq + NW )
      )
      return 1;
}
 
/* knights */
if ( leaperAttack( byColor, sq, KNIGHT ) )
   return 1;
 
 /* kings */
if ( leaperAttack( byColor, sq, KING ) )
   return 1;
 
 /* straight line sliders */
    if ( straightAttack( byColor, sq, NORTH ) ||
         straightAttack( byColor, sq, SOUTH ) ||
         straightAttack( byColor, sq, EAST  ) ||
         straightAttack( byColor, sq, WEST  )
       )
       return 1;
 
 /* diagonal sliders */
    if ( diagAttack( byColor, sq, NE ) ||
         diagAttack( byColor, sq, SE ) ||
         diagAttack( byColor, sq, NW ) ||
         diagAttack( byColor, sq, SW )
       )
       return 1;
 
    return 0;
}

leaperAttack

int leaperAttack( char byColor, S8 sq, char byPiece ) {
    S8 nextSq;
    for ( int dir = 0; dir < 8; dir++ ) {
        nextSq = sq + vector[byPiece][dir];
        if ( IS_SQ(nextSq) &&
             isPiece( byColor, byPiece, nextSq )
           )
           return 1;
    }
    return 0;
}

straightAttack

int straightAttack(char byColor, S8 sq, int vect) {
    int nextSq = sq + vect;
 
    while ( IS_SQ(nextSq) ) {
       if (b.color[nextSq] != COLOR_EMPTY ) {
           if ( ( b.color[nextSq] == byColor ) &&
                ( b.pieces[nextSq] == ROOK || b.pieces[nextSq] == QUEEN )
              )
              return 1;
           return 0;
          }
       nextSq = nextSq + vect;
    }
     return 0;
}

diagAttack

int diagAttack(int byColor, S8 sq, int vect) {
    int nextSq = sq + vect;
 
    while ( IS_SQ( nextSq ) ) {
       if (b.color[ nextSq ] != COLOR_EMPTY ) {
           if ( ( b.color[nextSq] == byColor ) &&
                ( b.pieces[nextSq] == BISHOP || b.pieces[nextSq] == QUEEN )
              )
              return 1;
           return 0;
          }
       nextSq = nextSq + vect;
    }
    return 0;
}

Up one Level

Discovered Attack

GerdIsenberg — Mon, 08 Nov 2010 13:38:01 GMT

Home * Chess * Tactics * Discovered Attack

A Discovered Attack is a X-ray related chess tactic, revealed when one piece moves out of the way of a sliding piece ray, discovering an attack to squares, opponent pieces or the king, the latter case called a Discovered Check. Discovered attacks can be extremely powerful, as the piece moved can make a threat independently of the piece it reveals.

During move generation or move ordering, one may encourage discovering moves by considering origin squares attacked by an own sliding pieces, as well as the resulting attacking direction.

External Links

What links here?

Page	Date Edited
Battery	Jan 29, 2017
CAPS	Dec 23, 2017
Combination	Oct 25, 2016
Dartmouth CP	Jan 19, 2018
Dictionary	Aug 24, 2017
Discovered Attack	Nov 8, 2010
Discovered Check	Feb 1, 2018
Double Attack	Oct 22, 2014
Double Check	Apr 4, 2013
Move Ordering	Feb 27, 2018
Moves	Feb 19, 2018
Overloading	May 5, 2017
Sliding Pieces	Aug 3, 2017
Tactics	Jan 12, 2018
X-ray	Apr 12, 2017
X-ray Attacks (Bitboards)	Mar 31, 2015
Zwischenzug	Jan 15, 2014

Up one Level

Double Attack

GerdIsenberg — Wed, 22 Oct 2014 10:12:03 GMT

Home * Chess * Tactics * Double Attack

		A Double Attack attacks two or more pieces or important squares simultaneously with one move, either by forking with the moving piece, or at least by a single direct attack of the moving piece in conjunction with a discovered attack. The so called royal knight fork winning the queen is most important, but like other double attacks involving checks already covered by usual move selection heuristics.
Le duelliste à l'épée et au poignard ^[1]

Seeing Potential Forks

Seeing Potential Forks

Like a skewer or other tactical threats, it might be nice to determine the availability of forks in advance, to either try those moves early, to don't prune or reduce them, or even to try them at the horizon in quiescence search. As always, it depends on the board representation and the availability of appropriate data structures like Attack and Defend Maps, whether additional effort in determination of fork pattern, what kind of pieces to consider etc., makes sense and pay off.

Knight and Pawn

A common technique in bitboards to determine fork move target sets for respective pieces is to treat potential opponent targets as the kind of piece which may fork, and to pairwise intersect all their disjoint direction attacks, as demonstrated in knight forks.

Pawn fork targets have only two different and contact attacking directions. For instance, white pawn fork targets need the intersection of east and west black pawn attacks of all black pieces, excluding the guarding real black pawn attacks. If this resulting set intersects with white pawn push targets, white has likely (considering pins) one or more pawn forks.

Single pawn and knight forks are easy to determine with any board representation, since the patterns are simple. For knight forks one may rely on knight-distance of two, implying the precondition of same square color between all potential attacking targets and one own attacking knight.

Sliding Pieces

For sliding piece forks, Mailbox or 0x88 based board representations may rely on techniques as described in Intersection Squares, while it seems bitboards have an edge using attack set intersection of a pair of targets.

External Links

References

^ Jacques Callot - Le duelliste à l'épée et au poignard, 1621-1625, Source: Les Gobbi, Le duelliste à l'épée et au poignard : estampe / Jacques Callot, Bibliothèque nationale de France, Category:Jacques Callot from Wikimedia Commons

What links here?

Page	Date Edited
AI Chess	Jan 7, 2016
BigLion	Sep 28, 2016
Chenard	Sep 5, 2015
Combination	Oct 25, 2016
Dartmouth CP	Jan 19, 2018
Decoying	Jan 12, 2015
Dictionary	Aug 24, 2017
Discovered Attack	Nov 8, 2010
Double Attack	Oct 22, 2014
Double Check	Apr 4, 2013
Gibbon	Dec 23, 2014
Hanging Piece	Jan 14, 2017
Kaissa	Apr 9, 2018
Knowledge	Jul 22, 2017
Loose Piece	Jan 10, 2015
Moves	Feb 19, 2018
Paradise	Nov 19, 2014
Skewer	Oct 22, 2014
Tactics	Jan 12, 2018
Treebeard	Mar 25, 2015

Up one Level

Dumb7Fill

GerdIsenberg — Fri, 27 May 2016 08:32:45 GMT

Comparison with Kogge-Stone

Home * Board Representation * Bitboards * Sliding Piece Attacks * Dumb7Fill

Dumb7Fill - the obvious, straight forward flood-fill approach works set-wise - seven times one fill-cycle by one step only in one of eight directions. We rely on the compass rose to identify ray-directions.

  noWe         nort         noEa
          +7    +8    +9
              \  |  /
  west    -1 <-  0 -> +1    east
              /  |  \
          -9    -8    -7
  soWe         sout         soEa

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

Occluded Fill

An occluded fill includes the flood generating sliding pieces, but excludes the blocker. It is base of attack fills. One additional direction shift excludes the sliders but includes the blocker.

Seven Fill Cycles

The sliding pieces generate the flood. They were shifted one step in the desired direction and intersected with the set of empty squares, the propagator. The flood aggregates the intersection and the cycle repeats six further times to cover the maximum distance on the chessboard. A blocker, not member of propagator, stops the flood in that particular ray-direction for one sliding piece. Therefor occluded fill contains the initial generator but excludes any blocker.

U64 soutOccl(U64 gen, U64 pro) {
   for (int cycle = 0; cycle < 7; cycle++)
      gen |= pro & (gen >> 8);
   return gen;
}

Fill Loop

Alternatively one may save move-instructions by introducing an explicit flood accumulator, and to probably terminate the loop early if the flood stops:

U64 soutOccl(U64 gen, U64 pro) {
   U64 flood = 0;
   while (gen) {
      flood |= gen;
      gen = (gen >> 8) & pro;
   }
   return flood;
}

Unrolled Loop

To avoid conditional branches and to schedule several directions in parallel, the "real" dumb7fill unrolls the loop:

U64 soutOccl(U64 gen, U64 pro) {
   U64 flood = gen;
   flood |= gen = (gen >> 8) & pro;
   flood |= gen = (gen >> 8) & pro;
   flood |= gen = (gen >> 8) & pro;
   flood |= gen = (gen >> 8) & pro;
   flood |= gen = (gen >> 8) & pro;
   flood |= gen = (gen >> 8) & pro;
   flood |=       (gen >> 8) & pro;
   return flood;
}

Some south fill cycles in slow motion:

flood = gen =
brooks|bqueen       empty
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 1 . 1
1.fill
 gen = gen >> 8   &  empty           =>  flood
. . . . . . . .      . . . . . . . .     1 . . . . . . .
1 . . . . . . .      1 . . . . . . .     1 . . 1 . . . .
. . . 1 . . . .      . . . 1 . . . .     . . . 1 . . . .
. . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .      . . . . . . . .     . . . . . 1 . .
. . . . . 1 . .      . . . . . 1 . .     . . . . . 1 . .
. . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .      . . . . . . . .     . . . . . . . .
2.fill
 gen = gen >> 8   &  empty               flood  |= ...
. . . . . . . .      . . . . . . . .     1 . . . . . . .
. . . . . . . .      . . . . . . . .     1 . . 1 . . . .
1 . . . . . . .      1 . . . . . . .     1 . . 1 . . . .
. . . 1 . . . .      . . . 1 . . . .     . . . 1 . . . .
. . . . . . . .      . . . . . . . .     . . . . . 1 . .
. . . . . . . .      . . . . . . . .     . . . . . 1 . .
. . . . . 1 . .      . . . . . 0 . .     . . . . . . . .
. . . . . . . .      . . . . . . . .     . . . . . . . .
3.fill
 gen = gen >> 8   &  empty               flood |= ...
. . . . . . . .      . . . . . . . .     1 . . . . . . .
. . . . . . . .      . . . . . . . .     1 . . 1 . . . .
. . . . . . . .      . . . . . . . .     1 . . 1 . . . .
1 . . . . . . .      1 . . . . . . .     1 . . 1 . . . .
. . . 1 . . . .      . . . 0 . . . .     . . . . . 1 . .
. . . . . . . .      . . . . . . . .     . . . . . 1 . .
. . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .      . . . . . . . .     . . . . . . . .
 
...
 
6.fill
 gen = gen >> 8  &   empty               flood  |= ...
. . . . . . . .      . . . . . . . .     1 . . . . . . .
. . . . . . . .      . . . . . . . .     1 . . 1 . . . .
. . . . . . . .      . . . . . . . .     1 . . 1 . . . .
. . . . . . . .      . . . . . . . .     1 . . 1 . . . .
. . . . . . . .      . . . . . . . .     1 . . . . 1 . .
. . . . . . . .      . . . . . . . .     1 . . . . 1 . .
1 . . . . . . .      0 . . . . . . .     . . . . . . . .
. . . . . . . .      . . . . . . . .     . . . . . . . .

The flood already stopped, the final 7th fill cycles don't change anything.

Attack Fill

To get attacks, one additional direction shift of the occluded fill is necessary to exclude the rooks/queen and include the blocker:

U64 soutAttacks (U64 rooks, U64 empty) {return soutOne(soutOccl(rooks, empty));}

Comparison with Kogge-Stone

To combine the dumb7fill as attack getter, we also can take advantage of outer square occupancy doesn't affect the attack set. We need one fill cycle less, before the final shift. That takes 19 operations. In anticipation to parallel prefix, a Kogge-Stone approach takes 14 instructions, 5 less. Kogge-Stone needs more move-instructions and a temporary register to compute generator as well as propagator, while dumb7fill uses a const propagator:

dumb7fill                                  | Kogge-Stone Algorithm
                                           |
U64 soutAttacks(U64 rooks, U64 empty) {    | U64 soutAttacks(U64 rooks, U64 empty) {
   U64 flood = rooks;                      |    rooks |= empty & (rooks >>  8);
   flood |= rooks = (rooks >> 8) & empty;  |    empty  = empty & (empty >>  8);
   flood |= rooks = (rooks >> 8) & empty;  |    rooks |= empty & (rooks >> 16);
   flood |= rooks = (rooks >> 8) & empty;  |    empty  = empty & (empty >> 16);
   flood |= rooks = (rooks >> 8) & empty;  |    rooks |= empty & (rooks >> 32);
   flood |= rooks = (rooks >> 8) & empty;  |    return            rooks >>  8;
   flood |=         (rooks >> 8) & empty;  | }
   return            flood >> 8;           |
}                                          |
                                           |
in x86/64 assembly                         | in x86/64 assembly
; dumb7fill                                |  ; koggeStone
; rooks rdx                                |  ; rooks rdx
; empty rcx                                |  ; empty rcx
                                           |
  mov   rax, rdx                           |    mov   rax, rdx
                                           |    shr   rax, 8
  shr   rdx, 8                             |    and   rax, rcx
  and   rdx, rcx                           |    or    rdx, rax
  or    rax, rdx                           |
                                           |    mov   rax, rcx
  shr   rdx, 8                             |    shr   rax, 8
  and   rdx, rcx                           |    and   rcx, rax
  or    rax, rdx                           |
                                           |    mov   rax, rdx
  shr   rdx, 8                             |    shr   rax, 16
  and   rdx, rcx                           |    and   rax, rcx
  or    rax, rdx                           |    or    rdx, rax
                                           |
  shr   rdx, 8                             |    mov   rax, rcx
  and   rdx, rcx                           |    shr   rax, 16
  or    rax, rdx                           |    and   rcx, rax
                                           |
  shr   rdx, 8                             |    mov   rax, rdx
  and   rdx, rcx                           |    shr   rax, 32
  or    rax, rdx                           |    and   rax, rcx
                                           |    or    rax, rdx
  shr   rdx, 8                             |
  and   rdx, rcx                           |    shr   rax, 8
  or    rax, rdx                           |
                                           |
  shr   rax, 8                             |
                                           |
   1 move                                  |     5 moves
  19 operations                            |    14 operations
  20 instructions                          |    19 instructions

Thus, dumb7fill is not that bad, specially if processing several directions in parallel, like south and north, all east and all west attacks.

All Directions

U64 soutAttacks(U64 rooks, U64 empty) {
   U64 flood = rooks;
   flood |= rooks = (rooks >> 8) & empty;
   flood |= rooks = (rooks >> 8) & empty;
   flood |= rooks = (rooks >> 8) & empty;
   flood |= rooks = (rooks >> 8) & empty;
   flood |= rooks = (rooks >> 8) & empty;
   flood |=         (rooks >> 8) & empty;
   return            flood >> 8;
}
 
U64 nortAttacks(U64 rooks, U64 empty) {
   U64 flood = rooks;
   flood |= rooks = (rooks << 8) & empty;
   flood |= rooks = (rooks << 8) & empty;
   flood |= rooks = (rooks << 8) & empty;
   flood |= rooks = (rooks << 8) & empty;
   flood |= rooks = (rooks << 8) & empty;
   flood |=         (rooks << 8) & empty;
   return            flood << 8;
}

Horizontal fills need to consider wraps from H-file to A-file and vice versa. Fortunately this can be combined by intersection of ~A-file or ~H-file with the propagator:

U64 eastAttacks(U64 rooks, U64 empty) {
   const U64 notA = C64(0xfefefefefefefefe);
   U64 flood = rooks;
   empty &= notA;
   flood |= rooks = (rooks << 1) & empty;
   flood |= rooks = (rooks << 1) & empty;
   flood |= rooks = (rooks << 1) & empty;
   flood |= rooks = (rooks << 1) & empty;
   flood |= rooks = (rooks << 1) & empty;
   flood |=         (rooks << 1) & empty;
   return           (flood << 1) & notA ;
}
 
U64 noEaAttacks(U64 bishops, U64 empty) {
   const U64 notA = C64(0xfefefefefefefefe);
   U64 flood = bishops;
   empty &= notA;
   flood |= bishops = (bishops << 9) & empty;
   flood |= bishops = (bishops << 9) & empty;
   flood |= bishops = (bishops << 9) & empty;
   flood |= bishops = (bishops << 9) & empty;
   flood |= bishops = (bishops << 9) & empty;
   flood |=           (bishops << 9) & empty;
   return               (flood << 9) & notA ;
}
 
U64 soEaAttacks(U64 bishops, U64 empty) {
   const U64 notA = C64(0xfefefefefefefefe);
   U64 flood = bishops;
   empty &= notA;
   flood |= bishops = (bishops >> 7) & empty;
   flood |= bishops = (bishops >> 7) & empty;
   flood |= bishops = (bishops >> 7) & empty;
   flood |= bishops = (bishops >> 7) & empty;
   flood |= bishops = (bishops >> 7) & empty;
   flood |=           (bishops >> 7) & empty;
   return               (flood >> 7) & notA ;
}
 
U64 westAttacks(U64 rooks, U64 empty) {
   const U64 notH = C64(0x7f7f7f7f7f7f7f7f);
   U64 flood = rooks;
   empty &= notH;
   flood |= rooks = (rooks >> 1) & empty;
   flood |= rooks = (rooks >> 1) & empty;
   flood |= rooks = (rooks >> 1) & empty;
   flood |= rooks = (rooks >> 1) & empty;
   flood |= rooks = (rooks >> 1) & empty;
   flood |=         (rooks >> 1) & empty;
   return           (flood >> 1) & notH ;
}
 
U64 soWeAttacks(U64 bishops, U64 empty) {
   const U64 notH = C64(0x7f7f7f7f7f7f7f7f);
   U64 flood = bishops;
   empty &= notH;
   flood |= bishops = (bishops >> 9) & empty;
   flood |= bishops = (bishops >> 9) & empty;
   flood |= bishops = (bishops >> 9) & empty;
   flood |= bishops = (bishops >> 9) & empty;
   flood |= bishops = (bishops >> 9) & empty;
   flood |=           (bishops >> 9) & empty;
   return               (flood >> 9) & notH ;
}
 
U64 noWeAttacks(U64 bishops, U64 empty) {
   const U64 notH = C64(0x7f7f7f7f7f7f7f7f);
   U64 flood = bishops;
   empty &= notH;
   flood |= bishops = (bishops << 7) & empty;
   flood |= bishops = (bishops << 7) & empty;
   flood |= bishops = (bishops << 7) & empty;
   flood |= bishops = (bishops << 7) & empty;
   flood |= bishops = (bishops << 7) & empty;
   flood |=           (bishops << 7) & empty;
   return               (flood << 7) & notH ;
}

Generalized Rays

Since rotate works like a generalized shift with positive or negative shift amount - since it internally applies a modulo 64 and makes -i = 64-i. We need to clear either the lower or upper bits by intersection with a mask, which might be combined with the wrap-ands for one step. It might be applied to get attacks for both sides with a direction parameter and small lookups for shift amount and wrap-ands - instead of multiple code for eight directions. Of course generalized shift will be a bit slower due to lookups and using cl as the shift amount register.

Loop Version

This is the loop-version:

U64 occludedFill (U64 gen, U64 pro, int dir8) {
   U64 flood = 0;
   if (gen) {
      int r = shift[dir8]; // {+-1,7,8,9}
      pro  &= avoidWrap[dir8];
      do {
         flood |= gen;
         gen = rotateLeft(gen, r) & pro;
      } while (gen);
   }
   return flood;
}
 
U64 shiftOne (U64 b, int dir8) {
   int r = shift[dir8]; // {+-1,7,8,9}
   return rotateLeft(b, r) & avoidWrap[dir8];
}
 
U64 slidingAttacks (U64 sliders, U64 empty, int dir8) {
   U64 fill = occludedFill(slider, empty, dir8)
   return shiftOne(fill, dir8);
}
 
// positve left, negative right shifts
int shift[8] = {9, 1,-7,-8,-9,-1, 7, 8};
 
U64 avoidWrap[8] =
{
   0xfefefefefefefe00,
   0xfefefefefefefefe,
   0x00fefefefefefefe,
   0x00ffffffffffffff,
   0x007f7f7f7f7f7f7f,
   0x7f7f7f7f7f7f7f7f,
   0x7f7f7f7f7f7f7f00,
   0xffffffffffffff00,
};

The avoidWrap masks by some arbitrary dir8 enumeration and shift amount:

6 == noWe -> +7     7 == nort -> +8     0 == noEa -> +9
0x7F7F7F7F7F7F7F00  0xFFFFFFFFFFFFFF00  0xFEFEFEFEFEFEFE00
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
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
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
1 1 1 1 1 1 1 .     1 1 1 1 1 1 1 1     . 1 1 1 1 1 1 1
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
5 == west -> -1                         1 == east -> +1
0x7F7F7F7F7F7F7F7F                      0xFEFEFEFEFEFEFEFE
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 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 1 1 1 .                         . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .                         . 1 1 1 1 1 1 1
 
4 == soWe -> -9     3 == sout -> -8     2 == soEa -> -7
0x007F7F7F7F7F7F7F  0x00FFFFFFFFFFFFFF  0x00FEFEFEFEFEFEFE
. . . . . . . .     . . . . . . . .     . . . . . . . .
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
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
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
1 1 1 1 1 1 1 .     1 1 1 1 1 1 1 1     . 1 1 1 1 1 1 1

Unrolled Attacks

The generalized unrolled sliding attack getter:

U64 slidingAttacks (U64 sliders, U64 empty, int dir8) {
   U64 flood = sliders;
   int r = shift[dir8]; // {+-1,7,8,9}
   empty &= avoidWrap[dir8];
   flood |= sliders = rotateLeft(sliders , r) & empty;
   flood |= sliders = rotateLeft(sliders , r) & empty;
   flood |= sliders = rotateLeft(sliders , r) & empty;
   flood |= sliders = rotateLeft(sliders , r) & empty;
   flood |= sliders = rotateLeft(sliders , r) & empty;
   flood |=         = rotateLeft(sliders , r) & empty;
   return   rotateLeft(flood, r)  &   avoidWrap[dir8];
}

External Links

bitboard mobility Copyright (c) 2003, Gunnar Andersson » Othello, Mobility
Weather Report - Seventh Arrow / Umbrellas, 1971, YouTube Video
Joe Zawinul, Wayne Shorter, Miroslav Vitouš, Alphonse Mouzon, Dom Um Romão

What links here?

Page	Date Edited
More Links
AVX2	Aug 8, 2017
DirGolem	Jun 5, 2016
Dumb7Fill	May 27, 2016
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Fill Algorithms	Nov 6, 2013
Gaviota	Jan 21, 2018
General Setwise Operations	Feb 25, 2018
Gunnar Andersson	Jun 23, 2011
Influence Quantity of Pieces	Jul 21, 2017
John L. Jerz	Jul 15, 2013
Kogge-Stone Algorithm	Sep 17, 2016
Lachex	Jan 7, 2016
Little Wing	Oct 26, 2017
Mobility	Jan 17, 2018
Othello	Jan 4, 2018
Pieces versus Directions	Oct 6, 2016
Sequential Logic	May 10, 2017
Shifted Bitboards	Jan 9, 2011
SIMD and SWAR Techniques	Jun 27, 2017
Sliding Piece Attacks	May 27, 2016

Up one Level

Efficient Generation of Sliding Piece Attacks

GerdIsenberg — Sat, 05 Nov 2016 09:24:03 GMT

Home * Conferences * Workshop Chess and Mathematics * Efficient Generation of Sliding Piece Attacks

Bitboard Basics

Squares and Bitindex

Empty and Universe

Bitboard Board-Definition

Bit-Twiddling relying on the Two's Complement

LS-Bit-Isolation

LS-Bit-Reset

Converting Bitboards to Lists

BitScan

De Bruijn Multiplication

Bitscan by Modulo

Kindergarten Multiplication

Attack-Sets as Base for Bitboard Move-generation

Sliding piece Attacks on the otherwise empty board

Ray Attacks

Line Attacks

Piece attacks

Sliding Attacks by Calculation

Subtraction and Reverse Subtraction of rooks from blockers

Flood Fill Techniques with multiple sliders

Occluded Fill

Kogge-Stone Parallel Prefix Algorithm

Ray-wise Attacks in one Direction

Lookup Techniques

Rook Attacks on the first Rank - as a base of occupancy lookup

Kindergarten Bitboards

Ranks and Diagonals

Files

Congruent Modulo Bitboards

Fakultät Mathematik und Naturwissenschaften Institut für Numerische Mathematik

Workshop Chess and Mathematics ^[1]
Dresden, November 21st and 22nd, 2008

Gerd Isenberg, Hattingen

Efficient generation of Moves and Controls of Sliding Pieces

Sa., 16:00, TU Dresden, WIL C207
Attack-Sets as Base for Bitboard Move-generation: Opposed to “None-sliding” pieces, Knight, King and Pawn, whose attacks are determined by its origin square only, sliding piece attacks like Rook-, Bishop- and Queen-attacks are dependend on other pieces as well, which may block the attacking ray in one particular ray-direction. In Quiescence Search the performance of generating (winning) capture moves is crucial. Opposed to classical square-centric board-representations, which require loops over squares, bitboards permit more efficient algorithms in generating sliding attacks.

Bitboard Basics

Bitboards are 64-bit integers and represent a finite set of up to 64 elements - all the squares of a chessboard with specific boolean properties of those squares. For instance whether squares are empty or occupied, or occupied by a specific kind of piece - or which is the main topic of this talk, whether a square is controlled or attacked (defended) by a specific kind of piece, especially attacked by sliding pieces.

Squares and Bitindex

see main article Square Mapping Considerations

There is a bijective one-to-one correspondence between bits of a bitboard and the squares of a board. There are 64! different mappings, but most commonly bits are enumerated "in order" along ranks or files (orthogonal). Some programs (Rotated Bitboards) keep redundant mappings and also enumerate consecutive bits along the diagonals or anti-diagonals.

If not stated otherwise, we further rely on Little-Endian Rank-File Mapping.

with following relations:

squareIndex {0..63} = 8*rankIndex + fileIndex;
rankIndex   {0..7}  = squareIndex div 8; // squareIndex >> 3;
fileIndex   {0..7}  = squareIndex mod 8; // squareIndex & 7;

Diagonals may be enumerated in various ways determined by the difference of rankIndex and fileIndex:

DiagonalIndex {0..15} = (rankIndex - fileIndex) & 15;
\f  0  1  2  3  4  5  6  7
r_________________________
7 | 7  6  5  4  3  2  1  0
6 | 6  5  4  3  2  1  0 15
5 | 5  4  3  2  1  0 15 14
4 | 4  3  2  1  0 15 14 13
3 | 3  2  1  0 15 14 13 12
2 | 2  1  0 15 14 13 12 11
1 | 1  0 15 14 13 12 11 10
0 | 0 15 14 13 12 11 10  9

Anti-Diagonals may be enumerated in various ways determined by the sum of rankIndex and fileIndex:

AntiDiagonalIndex {0..15} = (rankIndex + fileIndex) ^ 7; // xor
\f  0  1  2  3  4  5  6  7
r_________________________
7 | 0 15 14 13 12 11 10  9
6 | 1  0 15 14 13 12 11 10
5 | 2  1  0 15 14 13 12 11
4 | 3  2  1  0 15 14 13 12
3 | 4  3  2  1  0 15 14 13
2 | 5  4  3  2  1  0 15 14
1 | 6  5  4  3  2  1  0 15
0 | 7  6  5  4  3  2  1  0

Empty and Universe

The empty set is represented by all bits zero.
The universal set contains all elements by setting all bits to binary one.

The numerical values and set-wise representations of those sets, and how the appear as a board:

empty set E = 0      universal set U   = 2^64 - 1 or ~0
 set-wise   = {}      set-wise         = {a1, b1, c1, d1, ....., e8, f8, g8, h8}
                      hexadecimal      = 0xffffffffffffffff
                      unsigned decimal = 18,446,744,073,709,551,615
. . . . . . . .      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 1 1 1 1
. . . . . . . .      1 1 1 1 1 1 1 1
. . . . . . . .      1 1 1 1 1 1 1 1

Bitboard Board-Definition

see main article Bitboard Board-Definition

To represent the board we typically need one bitboard for each piece-type and color - likely encapsulated inside a class or structure, or as an array of bitboards as part of a position object. A one-bit inside a bitboard implies the existence of a piece of this piece-type on a certain square - one to one associated by the bit-position.

               pieces
   white                  black            occupied               empty
. . . . . . . .     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 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 1 . 1 .     . . . . . 1 . 1

               pawns                                  knights
   white                  black            white                  black
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . 1 . . 1 1 1     . . . . . . . .     . . . . . . . .
. . . . . . . .     1 . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . 1 . . 1 . . .     . . . . . . . .     . . . 1 . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . 1 . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
1 1 . 1 . 1 1 1     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . 1 . . . . . .     . . . . . . . .
              bishops                                  rooks
   white                   black           white                  black
. . . . . . . .     . . 1 . . . . .     . . . . . . . .     1 . . . . 1 . .
. . . . . . . .     . . . . 1 . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. 1 . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . 1 . . . . .     . . . . . . . .     1 . . . 1 . . .     . . . . . . . .
               queens                                  kings
   white                   black           white                  black
. . . . . . . .     . . . 1 . . . .     . . . . . . . .     . . . . . . 1 .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
. . . 1 . . . .     . . . . . . . .     . . . . . . 1 .     . . . . . . . .

Setwise Operations

see main article General Setwise Operations

Boolean algebra is an algebraic structure that captures essential properties of both set operations and logic operations. Specifically, it deals with the set operations of intersection, union, complement - and the bitwise boolean operations of AND, OR, NOT. Bitwise boolean operations on 64-bit words are in fact 64 parallel operations on each bit.

Assume we have an attack set of a queen, and like to know whether the queen attacks opponent pieces it may capture, we need to 'and' the queen-attacks with the set of opponent pieces.

queen attacks    &  opponent pieces  =  attacked pieces
. . . . . . . .     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 . . . .     . . . . . . . .     . . . . . . . .

Shifts

Shift acts like a multiplication (shift left) or division (shift right) by a power of two.
With orthogonal square mapping, shift with appropriate ray directions amounts of {1,7,8,9} are used to "move" the pieces one step in that direction, or to generate their square controls set-wise.

In the 8*8 board centric world with one scalar square-coordinate 0..63, each of the max eight neighboring squares can be determined by adding an offset for each direction. For border squares one has to care about overflows and wraps from a-file to h-file or vice versa. Some conditional code is needed to avoid that. Such code is usually part of move generation for particular pieces.

The mentioned square mapping implies following eight ray-directions as a compass-rose:

  northwest    north   northeast
  noWe         nort         noEa
          +7    +8    +9
              \  |  /
  west    -1 <-  0 -> +1    east
              /  |  \
          -9    -8    -7
  soWe         sout         soEa
  southwest    south   southeast

In the set-wise world of bitboards, where a square as member of a set is determined by an appropriate one-bit 2^square, the operation to apply such movements is shifting.

One has to consider wraps, which requires one further intersection.

To be aware of their scalar 64-bit origin, we use so far a type defined unsigned integer U64 in our C or C++ source snippets, the scalar 64-bit long in Java. Feel free to define a distinct type or wrap U64 into classes for better abstraction and type-safety during compile time. The macro C64 will append a suffix to 64-bit constants as required by some compilers:

typedef unsigned __int64 U64;    // for the old microsoft compilers
typedef unsigned long long  U64; // supported by MSC 13.00+ and C99
#define C64(constantU64) constantU64##ULL

One Step Only

The advantage with bitboards is, that the shift applies to all set bits in parallel, e.g. with all pawns. Vertical shifts by +-8 don't need any under- or overflow conditions since bits simply fall out and disappear.

U64 soutOne (U64 b) {return  b >> 8;}
U64 nortOne (U64 b) {return  b << 8;}

Wraps from a-file to h-file or vice versa may be considered by only shifting subsets which may not wrap. Thus we can mask off the a- or h-file before or after a +-1,7,9 shift:

const U64 notAFile = 0xfefefefefefefefe; // ~0x0101010101010101
const U64 notHFile = 0x7f7f7f7f7f7f7f7f; // ~0x8080808080808080

Post-shift masks, ...

U64 eastOne (U64 b) {return (b << 1) & notAFile;}
U64 noEaOne (U64 b) {return (b << 9) & notAFile;}
U64 soEaOne (U64 b) {return (b >> 7) & notAFile;}
U64 westOne (U64 b) {return (b >> 1) & notHFile;}
U64 soWeOne (U64 b) {return (b >> 9) & notHFile;}
U64 noWeOne (U64 b) {return (b << 7) & notHFile;}

Pawn Attacks

see main article Pawn Attacks (Bitboards)

Pawn Attacks set-wise as application of One Step Only.

 white pawns       white pawns << 9  &       notAFile     ==      noEaOne
. . . . . . . .     . . . . . . . .      . 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      . . . . . . . .
. . . . . . . .     h . . c . . . .      . 1 1 1 1 1 1 1      . . . c . . . .
. . c . . . . .     . a b . d . f g      . 1 1 1 1 1 1 1      . a b . d . f g
a b . d . f g h     . . . . . . . .      . 1 1 1 1 1 1 1      . . . . . . . .
. . . . . . . .     / . . . . . . .      . 1 1 1 1 1 1 1      / . . . . . . .
 
 white pawns       white pawns << 7  &       notHFile     ==     noWeOne
. . . . . . . .     . . . . . . . .      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 .      . . . . . . . .
. . . . . . . .     . c . . . . . .      1 1 1 1 1 1 1 .      . c . . . . . .
. . c . . . . .     b . d . f g h .      1 1 1 1 1 1 1 .      b . d . f g h .
a b . d . f g h     . . . . . . . a      1 1 1 1 1 1 1 .      . . . . . . . .
. . . . . . . .     . . . . . . . \      1 1 1 1 1 1 1 .      . . . . . . . \
 
 white pawns                                                 Union (1 == double attacks)
. . . . . . . .                                               . . . . . . . .
. . . . . . . .                                               . . . . . . . .
. . . . . . . .                                               . . . . . . . .
. . . . . . . .                                               . . . . . . . .
. . . . . . . .                                               . c . c . . . .
. . c . . . . .                                               b a 1 . 1 g 1 g
a b . d . f g h                                               . . . . . . . .
. . . . . . . .                                               . . . . . . . .

Bit-Twiddling relying on the Two's Complement

LS-Bit-Isolation

Intersection with its Two's Complement isolates the least significant one bit:

With some arbitrary sample set:
      x          &        -x         =     LS1B_of_x
. . . . . . . .     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 . 1 1 1     . . 1 . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .

LS-Bit-Reset

Intersection with its Ones' Decrement resets the least significant one bit:

      x          &      (x-1)        =  x_with_reset_LS1B
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . 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     . . . . . . . .

... since two's complement (-x) and ones' decrement (x-1) are complement sets.

Converting Bitboards to Lists

see main article Bitboard Serialization and Traversing Subsets of a Set

At some point bitboards require serialization - for instance if we need to process move-target sets to generate moves. Thanks to the Two's Complement, isolation and reset is cheap. To determine the bit- or square-index in the 0..63 range is tad more work ...

while ( x ) {
   *list++  = log2OfPowerOfTwo (x & -x); // determine bit index, also referred as BitScan
   x &= x-1; // reset LS1B
}

or alternatively

while ( x ) {
   *list++  = bitScanForward(x); // determine bit index of least significant one bit
   x &= x-1; // reset LS1B
}

BitScan

see main article BitScan

Despite recent processors have hardware instruction for bitScan, two hashing methods are mentioned to determine the base two logarithm of a single populated Bitboard. One hash-index is based on multiplication and shift, while the second one is determined by modulo. As we will see, both techniques also appear in hashing of multiple bits of a line.

De Bruijn Multiplication

The classical De Bruijn bitscan, as described by Leiserson et al. ^[2], to determine the LS1B index by minimal perfect hashing. So called De Bruijn sequences were invented by the Dutch mathematician Nicolaas de Bruijn. A 64-bit De Bruijn sequence contains 64-overlapping unique 6-bit sequences, thus a ring of 64+5 bits. The five hidden "trailing" zeros are in fact common with the five leading zeros. There are 2^26 = 67108864 odd sequences with 6 leading binary zeros and 2^26 even sequences with 5 leading binary zeros, which may be calculated from the odd ones by shifting left one.

A multiplication with a power of two value (the isolated LS1B) acts like a left shift by it's exponent. Thus, if we multiply a 64-bit De Bruijn sequence with the isolated LS1B, we get a unique six bit sequence in the most significant bits. To obtain the bit-index we need to extract these upper six bits by shifting right the product, to lookup an array.

See also generating your "private" De Bruijn Bitscan routine.

const int index64[64] = {
   63,  0, 58,  1, 59, 47, 53,  2,
   60, 39, 48, 27, 54, 33, 42,  3,
   61, 51, 37, 40, 49, 18, 28, 20,
   55, 30, 34, 11, 43, 14, 22,  4,
   62, 57, 46, 52, 38, 26, 32, 41,
   50, 36, 17, 19, 29, 10, 13, 21,
   56, 45, 25, 31, 35, 16,  9, 12,
   44, 24, 15,  8, 23,  7,  6,  5
};
 
/**
* bitScanForward
* @author Charles E. Leiserson
*         Harald Prokop
*         Keith H. Randall
* "Using de Bruijn Sequences to Index a 1 in a Computer Word"
* @param bb bitboard to scan
* @precondition bb != 0
* @return index (0..63) of least significant one bit
*/
int bitScanForward(U64 bb) {
   const U64 debruijn64 = C64(0x07EDD5E59A4E28C2);
   return index64[((bb & -bb) * debruijn64) >> 58];
}

Bitscan by Modulo

Another idea is to apply a modulo operation of the isolated LS1B by the prime number 67 ^[3]^[4]^[5]. The remainder 0..66 can be used to perfectly hash the bit-index table. Three gaps are 0, 17, and 34, so the mod 67 can make a branchless trailing zero count.

const int lookup67[67+1] = {
   64,  0,  1, 39,  2, 15, 40, 23,
    3, 12, 16, 59, 41, 19, 24, 54,
    4, -1, 13, 10, 17, 62, 60, 28,
   42, 30, 20, 51, 25, 44, 55, 47,
    5, 32, -1, 38, 14, 22, 11, 58,
   18, 53, 63,  9, 61, 27, 29, 50,
   43, 46, 31, 37, 21, 57, 52,  8,
   26, 49, 45, 36, 56,  7, 48, 35,
    6, 34, 33, -1
};
 
/**
* trailingZeroCount
* @param bb bitboard to scan
* @return index (0..63) of least significant one bit, 64 if bb is zero
*/
int trailingZeroCount(U64 bb) {
   return lookup67[(bb & -bb) % 67];
}

Since div/mod is an expensive instruction, a modulo by constant is likely replaced by reciprocal fixed point multiplication to get the quotient and a second multiplication and difference to get the remainder. Compared with De Bruijn multiplication it is still to slow.

Kindergarten Multiplication

see main article Flipping Mirroring and Rotating

Multiplication with disjoint intermediate results was nominated as Kindergarten Multiplication.

Multiplying the masked A-file with the main-diagonal, maps the file-bits to the 8th rank, similar to a flip about the anti-diagonal A8-H1. Shifting down to the 1st rank, leaves the bits like a 90-degree anti clockwise rotation.

masked bits                             mapped to 8th rank
bits on A-file   *  main-diagonal    =  with garbage     -> 1st rank
A . . . . . . .     . . . . . . . 1     A B C D E F G H     . . . . . . . .
B . . . . . . .     . . . . . . 1 .     B C D E F G H .     . . . . . . . .
C . . . . . . .     . . . . . 1 . .     C D E F G H . .     . . . . . . . .
D . . . . . . .     . . . . 1 . . .     D E F G H . . .  >> . . . . . . . .
E . . . . . . .  *  . . . 1 . . . .  =  E F G H . . . .  56 . . . . . . . .
F . . . . . . .     . . 1 . . . . .     F G H . . . . .     . . . . . . . .
G . . . . . . .     . 1 . . . . . .     G H . . . . . .     . . . . . . . .
H . . . . . . .     1 . . . . . . .     H . . . . . . .     A B C D E F G H

That is straight forward multiplication of a masked diagonal or anti-diagonal with the A-file.
To mask the garbage off, we further shift down by 7 ranks.

masked diagonal  *  A-file              mapped
to 8th rank      ->  1st rank
. . . . . . . H     1 . . . . . . .     A B C D E F G H     . . . . . . . .
. . . . . . G .     1 . . . . . . .     A B C D E F G .     . . . . . . . .
. . . . . F . .     1 . . . . . . .     A B C D E F . .  >> . . . . . . . .
. . . . E . . .     1 . . . . . . .     A B C D E . . .  56 . . . . . . . .
. . . D . . . .  *  1 . . . . . . .  =  A B C D . . . .     . . . . . . . .
. . C . . . . .     1 . . . . . . .     A B C . . . . .     . . . . . . . .
. B . . . . . .     1 . . . . . . .     A B . . . . . .     . . . . . . . .
A . . . . . . .     1 . . . . . . .     A . . . . . . .     A B C D E F G H

Attack-Sets as Base for Bitboard Move-generation

Opposed to "None-sliding" pieces, Knight, King and Pawn, whose controls or attacks are determined by its origin square only, sliding piece attacks like Rook-, Bishop- and Queen-attacks are dependent on other pieces as well, which may block the attacking ray in one particular ray-direction.

In Quiescence Search the performance of generating (winning) capture moves is crucial. Opposed to classical square-centric board-representations, which require loops over squares, bitboards permit more efficient algorithms in generating sliding attacks.

Sliding piece Attacks on the otherwise empty board

see main article On an empty Board

Attacks of single sliding pieces on the otherwise empty board or their disjoint subsets on lines or rays are that simple than none sliding pieces. We simply use pre-calculated tables for each piece-type, line or ray, indexed by square-index.

Ray Attacks

The mentioned square mapping implies following eight ray-directions as a compass-rose:

  northwest    north   northeast
  noWe         nort         noEa
          +7    +8    +9
              \  |  /
  west    -1 <-  0 -> +1    east
              /  |  \
          -9    -8    -7
  soWe         sout         soEa
  southwest    south   southeast

Positive Rays:

East (+1)           Nort (+8)            NoEa (+9)           NoWe (+7)
. . . . . . . .     . . . 1 . . . .      . . . . . . . 1     . . . . . . . .
. . . . . . . .     . . . 1 . . . .      . . . . . . 1 .     1 . . . . . . .
. . . . . . . .     . . . 1 . . . .      . . . . . 1 . .     . 1 . . . . . .
. . . . . . . .     . . . 1 . . . .      . . . . 1 . . .     . . 1 . . . . .
. . . R 1 1 1 1     . . . R . . . .      . . . B . . . .     . . . B . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .

Negative Rays:

West (-1)           Sout (-8)            SoWe (-9)           SoEa (-7)
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .     . . . . . . . .
1 1 1 R . . . .     . . . R . . . .      . . . B . . . .     . . . B . . . .
. . . . . . . .     . . . 1 . . . .      . . 1 . . . . .     . . . . 1 . . .
. . . . . . . .     . . . 1 . . . .      . 1 . . . . . .     . . . . . 1 . .
. . . . . . . .     . . . 1 . . . .      1 . . . . . . .     . . . . . . 1 .

Line Attacks

Rank                File                 Diagonal            Anti-Diagonal
. . . . . . . .     . . . 1 . . . .      . . . . . . . 1     . . . . . . . .
. . . . . . . .     . . . 1 . . . .      . . . . . . 1 .     1 . . . . . . .
. . . . . . . .     . . . 1 . . . .      . . . . . 1 . .     . 1 . . . . . .
. . . . . . . .     . . . 1 . . . .      . . . . 1 . . .     . . 1 . . . . .
1 1 1 R 1 1 1 1     . . . R . . . .      . . . B . . . .     . . . B . . . .
. . . . . . . .     . . . 1 . . . .      . . 1 . . . . .     . . . . 1 . . .
. . . . . . . .     . . . 1 . . . .      . 1 . . . . . .     . . . . . 1 . .
. . . . . . . .     . . . 1 . . . .      1 . . . . . . .     . . . . . . 1 .

Piece attacks

Piece attacks are the union of either orthogonal or diagonal lines. Queen attacks are the union of rook- and bishop attacks.

                                   Queen
                               . . . 1 . . . 1
                               1 . . 1 . . 1 .
                               . 1 . 1 . 1 . .
               Rook            . . 1 1 1 . . .         Bishop
           . . . 1 . . . .     1 1 1 Q 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 R 1 1 1 1                         . . . B . . . .
           . . . 1 . . . .                         . . 1 . 1 . . .
           . . . 1 . . . .                         . 1 . . . 1 . .
           . . . 1 . . . .                         1 . . . . . 1 .

Sliding Attacks by Calculation

For one single sliding piece, one may consider subtraction from the set of blockers, to determine attack sets. Zeros, that are empty squares, between the nearest blocker and the sliding pieces became "ones", the nearest blocker becomes zero. In fact all flipped bits are the attacked squares in positive ray direction.

 occupied  11000101
 slider    00000100 subset of occupied
 o-s       11000001 resets the slider in occupied
 o-2s      10111101 borrows the one from nearest blocker
 occupied  11000101
 o^(o-2s)  01111000 all flipped bits are the attacks in most significant bit direction

To restrict the operations to a certain line, rank file or diagonal, a leading intersection with the line mask is necessary, same for the final result.

Subtraction and Reverse Subtraction of rooks from blockers

see main article Subtracting a rook from a blocking piece and Hyperbola Quintessence

With s (sliding piece) single element set and subset of o (occupied):

positiveRayAttacks = o  ^ (o - 2s);

The first subtraction resets the siding-piece-bit in occupied.
The second subtraction borrows a one from nearest blocker (if any), and sets all intermediate zero bits (empty squares). The exclusive or gains all flipped bits, which turnes out to be the rook attacks in "positive" attacking direction.

For negative directions one needs "reverse" arithmetic (2 + 2 == 1).

with o' = reverse (o)
and  s' = reverse (s)
negativeRayAttacks = reverse (o' ^ (o' - 2s'));

Since bit-reversal or any mirroring or flipping is distributive over xor:

reverse(a ^ b) == reverse (a) ^ reverse(b)

One can reformulate negative rays

negativeRayAttacks = o  ^  reverse (o' - 2s');

which leads to a simplification in the line-attacks, since positiveRayAttacks and negativeRayAttacks are disjoint sets for one particular sliding piece and may be combined by "xor", and o ^ o == 0.

lineAttacks = positiveRayAttacks ^ negativeRayAttacks;
lineAttacks =         o ^ (o-2s) ^ reverse( o'-2s') ^ o
lineAttacks =             (o-2s) ^ reverse( o'-2s')

Diagonal or vertical line occupancies need leading and trailing intersection with line-masks. Thanks to the little-endian versus big-endian war, recent processors have appropriate instructions to swap bytes (ranks) inside a 64-bit word for the reverse arithmetic, note that masked files or diagonals have only max one bit per rank:

U64 diagonalAttacks(U64 occ, int sqOfSlider) {
   U64 forward, reverse, slider, lineMask;
 
   lineMask = diagonalMaskEx[sqOfSlider]; // excludes square of slider
   slider   = singleBitboard[sqOfSlider]; // single bit 1 << sq, 2^sq
 
   forward  = occ & lineMask; // also performs the first subtraction by clearing the s in o
   reverse  = byteswap( forward ); // o'-s'
   forward -=         ( slider  ); // o -2s
   reverse -= byteswap( slider  ); // o'-2s'
   forward ^= byteswap( reverse );
   return forward & lineMask;      // mask the line again
}

Flood Fill Techniques with multiple sliders

Fill approaches determine attacks set-wise for multiple pieces (i.e. rooks and queen(s)) in one particular ray-direction. The flood stops on each particular ray (either 8 ranks or files, or 15 diagonals or anti-diagonals), if a square is not empty.

Occluded Fill

see main article Dumb7Fill
For sliding piece-attacks one direction step can be repeated seven times, after each shift, intersecting with empty squares accumulating all intermediate results to a union set, which results in an occluded fill set, including the sliding piece but excluding the blocker.

U64 eastOccluded (U64 rooks, U64 empty) {
   empty  = empty & notAFile; // make A-File all occupied, to consider H-A-wraps after shift
   rooks |= empty & (rooks << 1); // 1. fill
   rooks |= empty & (rooks << 1); // 2. fill
   rooks |= empty & (rooks << 1); // 3. fill
   rooks |= empty & (rooks << 1); // 4. fill
   rooks |= empty & (rooks << 1); // 5. fill
   rooks |= empty & (rooks << 1); // 6. fill
   rooks |= empty & (rooks << 1); // 7. fill // not necessary for further attack generation
   return rooks;
}

Kogge-Stone Parallel Prefix Algorithm

see main article Kogge-Stone Algorithm and Parallel Prefix Algorithms
Occluded fill might be done more efficiently parallel prefix wise by Kogge-Stone Algorithms:

U64 eastOccluded(U64 rooks, U64 empty) {
   empty  = empty & notAFile; // make A-File all occupied, to consider H-A-wraps after shift
   rooks |= empty & (rooks << 1);
   empty  = empty & (empty << 1);
   rooks |= empty & (rooks << 2);
   empty  = empty & (empty << 2);
   rooks |= empty & (rooks << 4);
   return rooks;
}

The Kogge-Stone parallel prefix algorithm for sliding piece attack generation was first introduced by Steffan Westcott in CCC ^[6]. It is a parallel prefix approach of a occluded dumb7 flood-fill, propagating sliding piece attacks in software like carries of a kogge-stone hardware adder ^[7]. We need to pass sliders as generator set and the set of empty squares as propagator set. For appropriate attacks we need to shift one step further, considering wraps.

Ray-wise Attacks in one Direction

For square attack sets, occluded fill sets need to be shifted one more step. Thus, the occluded fill needs one fill cycle less.

U64 eastAttacks (U64 rooks, U64 empty) {
   empty  = empty & notAFile; // make A-File all occupied, to consider H-A-wraps after shift
   rooks |= empty & (rooks << 1); // 1. fill
   rooks |= empty & (rooks << 1); // 2. fill
   rooks |= empty & (rooks << 1); // 3. fill
   rooks |= empty & (rooks << 1); // 4. fill
   rooks |= empty & (rooks << 1); // 5. fill
   rooks |= empty & (rooks << 1); // 6. fill
   return notAFile& (rooks << 1);
}

Because fill-approaches keep distinct ray-directions, there is still a unique source-target square relation. Fill approaches with pure calculation are Cpu-intensive, but require no memory reads. They are a domain of SIMD instruction sets like SSE2 with sixteen 128-bit registers, to process two or four distinct sets (e.g. white and black, sliders and king as queen like meta-slider) per register and several ray-directions simultaneously - e.g. three 128-bit instructions per cycle for core2duo.

Keeping distinct ray-directions has some advantages, for instance in determining pinned pieces or discovered checks. Fill-Algorithms are great to feed in line-wise attack sets of single sliders, to determine a progressive mobility on the orthogonal rays, i.e. move targets in two moves, or trajectories against important squares or areas.

 . . . . . . . .
 . . . . \ . . .
 . . . \ . 1 . .
 . . \ . 1 . \ .
 . \ . 1 . \ . .
 . . 1 . \ . . .
 . B . \ . . . .
 . . . . . . . .

Lookup Techniques

Lookup Techniques are used to hash pre-calculated attack-sets of a single pieces by square-index and occupancy of the affected lines.

Rook Attacks on the first Rank - as a base of occupancy lookup

see main article First Rank Attacks
The first rank is the ideal line to introduce occupancy lookups.

One Byte Only

Assume we (temporary) reduce the chess-board to one rank. Occupancy bitboard is one byte with up to 256 states. A rook attack-set from one of the eight squares (file) on this single rank is also only one byte. Thus we can construct an array of bytes[256][8], indexed by all 256 occupancies and 8 files, to lookup the pre-calculated rank-attack bytes.

Occupancy of the first rank = 01001010B

Rank-attacks ::= f (e-file, Occupancy) = 01110110B

BYTE arrFirstRankAttacks256x8[256][8]; // 2048 Bytes = 2KByte
 
firstRankAttack = arrFirstRankAttacks256x8[rankOccupancy][squareOnRank];

The Outer Squares

If we think about to the occupancy lookup, we may recognize that the outer squares don't matter. There are no more squares behind. The outer squares are either attacked or not - independent from their occupancy state. We can use the six inner bits only as lookup-index with two additional cheap instruction. This reduces the lookup-table by factor of four.

BYTE arrFirstRankAttacks64x8[64][8]; // 512 Bytes = 1/2KByte
 
firstRankAttack = arrFirstRankAttacks64x8[(rankOccupancy >> 1)& 63][squareOnRank];

Other ranks

It is simple to shift other ranks to the first rank, and to shift back the attack set.

Rotated Bitboards

see main article Rotated Bitboards

Rotated Bitboards are a bitboard move generation technique invented independently by Robert Hyatt ^[8] and by Ernst A. Heinz ^[9] with Peter Gillgasch from the DarkThought team. This variation uses rotated copies of the occupancy in order to place bits along a file or diagonal in adjacent bits. Because of this, these bits can be easily extracted to obtain an occupancy map for a rank, file, or diagonal. This is used, along with the square of a slider, to lookup a bitboard containing attacks in an array.

Rotated bitboards are fast to extract the occupancy index and require 32 KByte for each line direction (rank, file, diagonal and anti-diagonal) for the lookup-tables, considering the inner six bits. However, there is more work in updating four occupied bitboards while making or unmaking moves, instead of one. The fast 64-bit multiplication of recent x64 processors (~4-cycles) with a throughput of up to one cycle, makes on the fly calculations of occupied states on files and diagonals more attractive.

Kindergarten Bitboards

see main article Kindergarten Bitboards
Kindergarten Bitboards perform a fill-multiplication and uses a shared lookup table for ranks and diagonals.

Ranks and Diagonals

Ranks and diagonals - that is their appropriate line-mask by square-index - are first intersected by the occupancy of the whole board. Doesn't matter whether the slider itself is cleared or not - it is redundant anyway, considered by the pre-calculated lookup-table. Since there is only up to one bit per file, the north-fill multiplication by the A-file maps the diagonal to the 8th rank. Or - since we only need the inner six bits, we combine the required shift left one by multiplying with the B-file. Shifting right the product by 58 (64-6) leaves the six-bit occupancy-index in the 0..63 range.

For instance the diagonal-attacks of a bishop on d4. 'A'-'H' represent the masked occupied bits along this diagonal, which are either zero or one. We need 'B'-'G' as six bit number:

masked line      *  B-File           =  B-G upper six       occupancy 6 bit
. . . . . . . H     . 1 . . . . . .     . A[B C . E F G]    . . . . . . . .
. . . . . . G .     . 1 . . . . . .     . A B C . E F G     . . . . . . . .
. . . . . F . .     . 1 . . . . . .     . A B C . E F .     . . . . . . . .
. . . . E . . .     . 1 . . . . . .     . A B C . E . .  >> . . . . . . . .
. . . . . . . .  *  . 1 . . . . . .  =  . A B C . . . .  58 . . . . . . . .
. . C . . . . .     . 1 . . . . . .     . A B C . . . .     . . . . . . . .
. B . . . . . .     . 1 . . . . . .     . A B . . . . .     . . . . . . . .
A . . . . . . .     . 1 . . . . . .     . A . . . . . .    [B C . E F G]. .

The pre-calculated lookup-table contains the attacks of the first rank - but eight copies in each rank or byte. It is indexed by the six bit occupied-state ('B'-'G') and the file of the slider's square. It needs to be intersected with the same line-mask as formerly the occupancy - to map the first rank attack bits to the appropriate line - that's all. Appropriate pre-calculated attack bits are represented by 'a'-'h':

fillUpAttacks[file == 3][B C . E F G]:
 
8 copies of rank      the attack set
attacks & l-mask  ->  of this line
a b c . e f g h       . . . . . . . h
a b c . e f g h       . . . . . . g .
a b c . e f g h       . . . . . f . .
a b c . e f g h       . . . . e . . .
a b c . e f g h       . . . . . . . .
a b c . e f g h       . . c . . . . .
a b c . e f g h       . b . . . . . .
a b c . e f g h       a . . . . . . .

Code spippets.

U64 fillUpAttacks[8][64];  // 4 KByte pre-calculated Lookup table
const U64 bFile = C64(0x0202020202020202);
 
U64 diagonalAttacks(U64 occ, enumSquare sq) {
   occ = (diagonalMaskEx[sq] & occ) * bFile >> 58;
   return diagonalMaskEx[sq] & fillUpAttacks[sq&7][occ];
}
 
U64 antiDiagAttacks(U64 occ, enumSquare sq) {
   occ = (antidiagMaskEx[sq] & occ) * bFile >> 58;
   return antidiagMaskEx[sq] & fillUpAttacks[sq&7][occ];
}
 
U64 rankAttacks(U64 occ, enumSquare sq) {
   occ = (rankMaskEx[sq] & occ) * bFile >> 58;
   return rankMaskEx[sq] & fillUpAttacks[sq&7][occ];
}

Files

File attacks need tad more work:

U64 aFileAttacks [8][64];  // 4 KByte
const U64 aFile   = C64(0x0101010101010101);
const U64 diac2h7 = C64(0x0080402010080400);
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   occ = aFile  & (occ >> (sq&7));
   occ = (diac2h7 *  occ ) >> 58;
   return aFileAttacksx[sq>>3][occ] << (sq&7);
}

Congruent Modulo Bitboards

see main article Congruent Modulo Bitboards

Congruent Modulo Bitboards was introduced by Trevor Fenner and Mark Levene in the ICGA Journal Vol. 31, No. 1 in 2008 ^[10]. While their Perfect Hashing approach provides great mathematical insights in Congruent Modulo arithmetic, their final conclusion in comparison with Hashing Dictionaries, Rotated Bitboards and Magic Bitboards was criticized by the obvious comparison with Kindergarten Bitboards ^[11].

Fenner and Levene use masked line modulo 514 for the diagonals, modulo 257 for the anti-diagonals and mod 258 for files, to calculate the occupied index, but they didn't consider the inner six bits for a denser lookup. Of course, tables could made denser by storing indices, but that would require a second indirection. While Fenner and Levene used a Matlab 32-bit implementation to conclude their approach might be competitive, this is how it may be implemented in C by looking up pre-calculated attack-bitboards:

U64 arrCmodDiaAttacks [514][64];  // 257 K
U64 arrCmodAntiAttacks[257][64];
U64 arrCmodFileAttacks[258][64];
 
U64 diagonalAttacks(U64 occ, enumSquare sq) {
   occ = (diagonalMask[sq] & occ) % 514;
   return arrCmodDiaAttacks[occ][sq];
}
 
U64 antiDiagAttacks(U64 occ, enumSquare sq) {
   occ = (antiDiagMask[sq] & occ) % 257;
   return arrCmodAntiAttacks[occ][sq];
}
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   occ = (fileMask[sq] & occ) % 258;
   return arrCmodFileAttacks[occ][sq];
}

Magic Bitboards

see main article Magic Bitboards

Magic bitboards uses a multiply-right-shift perfect hashing algorithm to index a attack bitboard database - which leaves both line-attacks of a bishop or rook in one run.

The magic bitboard approach was introduced by Lasse Hansen in the Winboard programming forum. He had the idea to hash the up to twelve relevant occupied bits of both directions of a rook- or bishop movement simultaneously ^[12].

Pradu Kannan's improvements to Lasse Hansen's initial approach was to introduce a Java-like, two-dimensional array with individual size for each square and all it's relevant occupancies ^[13]. Big savings in table-size - since many squares on either orthogonals or diagonals require less bits than others, especially considering the inner six bits. While center squares are more dense for rooks, it is the opposite for bishops ^[14].

How it works

A magic move-bitboard generation technique consists of four key steps:

Mask the relevant occupancy bits to form a key. For example if you had a rook on a1, the relevant occupancy bits will be from a2-a7 and b1-g1.
Multiply the key by a "magic number" to obtain an index mapping. This magic number can be generated by brute-force trial and error quite easily although it isn't 100% certain that the magic number is the best possible (see step 3).
Right shift the index mapping by 64-n bits to create an index, where n is the number of bits in the index. A better magic number will have less bits required in the index.
Use the index to reference a preinitialized move database.

any consecutive
relevant occupancy                      combination of
bishop b1, 5 bits                       the masked bits
. . . . . . . .     . . . . . . . .     . . .[C D E F G]
. . . . . . . .     . 1 . . . . . .     . . . . . . . .
. . . . . . G .     . 1 . . . . . .     . . . . . . . .
. . . . . F . .     . 1 . . . . . .     . . . . . . . .
. . . . E . . .  *  . 1 . . . . . .  =  . .garbadge . .    >> (64- 5)
. . . D . . . .     . 1 . . . . . .     . . . . . . . .
. . C . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
any consecutive
relevant occupancy                      combination of
bishop d4, 9 bits                       the masked bits
. . . . . . . .     . . . . . . . .     2 4 5 B C E F G]
. . . . . . G .     . . .some . . .     . . . . . . .[1
. 5 . . . F . .     . . . . . . . .     . . . . . . . .
. . 4 . E . . .     . . .magic. . .     . . . . . . . .
. . . . . . . .  *  . . . . . . . .  =  . .garbadge . .    >> (64- 9)
. . C . 2 . . .     . . .bits . . .     . . . . . . . .
. B . . . 1 . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
any consecutive
relevant occupancy                      combination of
rook d4, 10 bits                        the masked bits
. . . . . . . .     . . . . . . . .     4 5 6 B C E F G]
. . . 6 . . . .     . . .some . . .     . . . . . .[1 2
. . . 5 . . . .     . . . . . . . .     . . . . . . . .
. . . 4 . . . .     . . .magic. . .     . . . . . . . .
. B C . E F G .  *  . . . . . . . .  =  . .garbadge . .    >> (64-10)
. . . 2 . . . .     . . .bits . . .     . . . . . . . .
. . . 1 . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
any consecutive
relevant occupancy                      combination of
rook a1, 12 bits                        the masked bits
. . . . . . . .     . . . . . . . .     5 6 B C D E F G]
6 . . . . . . .     . . .some . . .     . . . .[1 2 3 4
5 . . . . . . .     . . . . . . . .     . . . . . . . .
4 . . . . . . .     . . .magic. . .     . . . . . . . .
3 . . . . . . .  *  . . . . . . . .  =  . .garbadge . .    >> (64-12)
2 . . . . . . .     . . .bits . . .     . . . . . . . .
1 . . . . . . .     . . . . . . . .     . . . . . . . .
. B C D E F G .     . . . . . . . .     . . . . . . . .

The above illustration is correct for the b1 bishop, since it has only one ray and one bit per file and works kindergarten like. In general a one to one mapping of N scattered occupied bits to N consecutive bits is not always possible due to possible overflows. A perfect mapping of N scattered bits to N consecutive bits is likely not minimal for most squares. It requires one or two gaps inside the consecutive N bits, to avoid collisions, blowing up the table size.

But the purpose is to perfectly hash attack-sets rather than consecutive occupied bits.

The number of distinct attack-sets is much smaller than the relevant occupancies. Thus, with the help of constructive collisions, some initial guess how to map the bits, and/or trial and error, using exactly N bits is always possible. If we try hard enough to maximize constructive collisions - even less.

Perfect Hashing

Magic bitboards applies perfect hashing. A surjective function, to map the vector of all relevant occupancies to a range of attack-sets per square. The less bits the attack-set - the closer the blockers, the more those attack-sets are shared by occupancies with different, but redundant outer squares.

The cardinality of all relevant occupancies is determined by the number of bits to map, varying from five to twelve - thus, the cardinality is the power of two the number of bits, varying from 32 to 4096.
The cardinality of distinct attack-sets is determined by the product of the length of each of the max four direction rays greater than zero (or one). The rook on d4 has 3*4*3*4 = 144 distinct attack-sets, a bishop on a8 has only 7.

The ratio of both cardinalities, that is all relevant occupancies versus the all distinct attack-sets is illustrated below: As a quarter of a board - due to the symmetry, the other squares may deduced by flipping and mirroring. Noticeable is the huge 4096/49 ratio of 2^12 occupied states versus 7 times 7 attack-sets of the edge rooks - 12 bits instead of 6. Those "expensive" squares make constructive collisions very desirable. To become more "minimal" by saving an index bit - to halve down the table for one square or the other.

	bishop on square				rook on square
	A	B	C	D		A	B	C	D
8	64/7	32/6	32/10	32/ 12	8	4096/49	2048/42	2048/ 70	2048/ 84
7	32/6	32/6	32/10	32/ 12	7	2048/42	1024/36	1024/ 60	1024/ 72
6	32/10	32/10	128/40	128/ 48	6	2048/70	1024/60	1024/100	1024/120
5	32/12	32/12	128/48	512/108	5	2048/84	1024/72	1024/120	1024/144

	bishop on square				rook on square
	A	B	C	D		A	B	C	D
8	9.14	5.33	3.20	2.67	8	83.59	48.76	29.26	24.38
7	5.33	5.33	3.20	2.67	7	48.76	28.44	17.07	14.22
6	3.20	3.20	3.20	2.67	6	29.26	17.07	10.24	8.53
5	2.67	2.67	2.67	4.74	5	24.38	14.22	8.53	7.11

The idea to implement minimal perfect hashing by an additional 16-bit indirection turned out to be slower.

Recent table sizes were about 38 KByte for the bishop attacks, but still about 800 KByte for rook attacks. That sounds huge, considering L1 and L2 (L3) cache-sizes and number of cachelines and pages needed - we likely fetch distinct cachelines for each different square or occupancy. On the other hand caches and pages become larger in future processors. And occupancy and squares of the lookups don't change that randomly inside a search that we can still expect a lot of L1-hits. Unfortunately changes in occupancy outside the blockers and therefor not affecting the attack-set will introduce some more cache misses.

Sample Code

Anyway, register usage and code size are important issues as well - and here magic bitboards are unbeatable - specially bishopAttacks, with respect to the relative small table.

U64 attacks_table[...]; // ~840K Byte all rook and bishop attacks
 
struct SMagic {
   U64* ptr;  // pointer to the attack-table for one particular square
   U64 mask;  // to mask of both lines
   U64 magic; // magic 64-bit factor
   int shift; // shift right 
};
 
SMagic mBishopTbl[64];
SMagic mRookTbl[64];
 
U64 bishopAttacks(U64 occ, enumSquare sq) {
   U64* aptr = mBishopTbl[sq].ptr;
   occ      &= mBishopTbl[sq].mask;
   occ      *= mBishopTbl[sq].magic;
   occ     >>= mBishopTbl[sq].shift;
   return aptr[occ];
}
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   U64* aptr = mRookTbl[sq].ptr;
   occ      &= mRookTbl[sq].mask;
   occ      *= mRookTbl[sq].magic;
   occ     >>= mRookTbl[sq].shift;
   return aptr[occ];
}

Summary

The bitboard method for holding a board game appears to have been invented in the mid 1950's, by Arthur Samuel and was used in his checkers program. In computer chess bitboards were first described by Georgy Adelson-Velsky et al. in 1967 ^[15], reprinted 1970 ^[16]. Bitboards were used both in Kaissa and independently in Chess. The invention and publication of Rotated Bitboards by Robert Hyatt and Peter Gillgasch with Ernst A. Heinz in the 90s was another milestone in the history of bitboards. While rotated bitboards was the mainstream in bitboard chess programs, Magic Bitboards become more populated nowadays. Finally, Steffan Westcott's innovations, too expensive with 32-bit x86 architectures, should be revisited with x86-64 and SIMD instructions in mind.

References

^ Workshop Chess and Mathematics (pdf) agenda and abstracts
^ Charles E. Leiserson, Harald Prokop and Keith H. Randall (1998) Using de Bruijn Sequences to Index a 1 in a Computer Word (pdf)
^ bitboard 2^i mod 67 is unique post by Stefan Plenkner from rec.games.chess.computer, August 6, 1996
^ bitboard 2^i mod 67 is unique post by Joël Rivat from rec.games.chess.computer, September 2, 1996
^ bitboard 2^i mod 67 is unique post by Stefan Plenkner from rec.games.chess.computer, August 7, 1996
^ Re: flood fill attack bitboards answer by Steffan Westcott from CCC, September 15, 2002
^ Hardware algorithms for arithmetic modules from the ARITH research group, Aoki lab., Tohoku University
^ Robert Hyatt (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4, pp. 213–222.
^ Rotated Bitboards by Ernst A. Heinz
^ Trevor Fenner and Mark Levene (2008). Move Generation with Perfect Hashing Functions. ICGA Journal, Vol. 31, No. 1, pp. 3-12. ISSN 1389-6911.
^ Nice Math - Strange Conclusions post by Gerd Isenberg from CCC
^ Lasse Hansen's Initial idea from Winboard Forum, June 14, 2006
^ Magic Move-Bitboard Generation in Computer Chess (pdf) by Pradu Kannan
^ List of magics for bitboard move generation thread started by Pradu Kannan from Winboard Forum, Aug 23, 2006
^ Early Reference on Bit-Boards by Tony Warnock, October 29, 1994 rec.games.chess archive
^ Georgy Adelson-Velsky, Vladimir Arlazarov, Alexander Bitman, Alexander Zhivotovsky and Anatoly Uskov (1970). Programming a Computer to Play Chess. Russian Mathematical Surveys, Vol. 25, pp. 221-262

Up one Level

Exploding Bitboards

PsyMar — Mon, 09 Mar 2015 12:29:50 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Exploding Bitboards

The expanding or exploding bitboards were created by Harald Lüßen with some help from other people in CCC ^[1] . The idea is to generate the attacks of a sliding piece from its square outside on all its rays in parallel like the waves of a stone thrown into water. This is done in some steps with multiplications and shifts like in the kindergarten bitboards. At each step or distance from the original square the rays can be expanded or stopped by other pieces from an occupied bitboard. There are some nasty overflow problems at the border of the board that must be solved. This approach is slower than other techniques. The code below is taken from the chess engine Elephant which is known for some bitboard comparisons but not for playing strength.

In the example this big-endian file-mapping is used:

    directions and shifts
    +-----+-----+-----+
    |<<= 9|<<= 8|<<= 7|
    +-----+-----+-----+
    |<<= 1|     |>>= 1|
    +-----+-----+-----+
    |>>= 7|>>= 8|>>= 9|
    +-----+-----+-----+
 
    +-------------------------+
    | 63 62 61 60 59 58 57 56 | 8
    | 55 54 53 52 51 50 49 48 | 7
    | 47 46 45 44 43 42 41 40 | 6
    | 39 38 37 36 35 35 33 32 | 5
    | 31 30 29 28 27 26 25 24 | 4
    | 23 22 21 20 19 18 17 16 | 3
    | 15 14 13 12 11 10  9  8 | 2
    |  7  6  5  4  3  2  1  0 | 1
    +-------------------------+
       a  b  c  d  e  f  g  h

The general trick of chasing and pushing around the bits on the board is this: First shift down and sideways far enough to get a good start. Then multiply with 2 to shift one square to the side (left in this mapping) and multiply with 2^8 = 0x100 to move the bit upwards. Use any power of 2 that helps you. Build the sum of all the multiplication factors of all moves for all bits and multiply with that number. There will probably be more bits in the result than there should be because the multiplication works on all original bits. Use a mask to get rid of all the bad bits.

Bishops

For each square there is an ignition of the explosion.

/*
First expanding step (explosion) for a bishop
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . 1 . 1 . . .
 . . .sq . . . .
 . . 1 . 1 . . .
 . . . . . . . .
 . . . . . . . .
*/
Bitboard initB[64];
void makeInitB()
{
    for ( int sq = 0; sq < 64; ++sq )
    {
        Bitboard bb = C64(1) << sq;
        initB[sq]  = (bb >> 9) & C64(0x7f7f7f7f7f7f7f7f);
        initB[sq] |= (bb >> 7) & C64(0xfefefefefefefefe);
        initB[sq] |= (bb << 9) & C64(0xfefefefefefefefe);
        initB[sq] |= (bb << 7) & C64(0x7f7f7f7f7f7f7f7f);
    }
}

The explosion is only allowed along the rays.

/*
Mask for bishop attack rays
 . . . . . . . 1
 1 . . . . . 1 .
 . 1 . . . 1 . .
 . . 1 . 1 . . .
 . . .sq . . . .
 . . 1 . 1 . . .
 . 1 . . . 1 . .
 1 . . . . . 1 .
*/
Bitboard maskB[64];
void makeMaskB()
{
    int sq;
    for ( sq = 0; sq < 64; ++sq )
    {
        maskB[sq] = 0;
        int i;
        for ( i = sq - 9; i >= 0 && i % 8 != 7; i -= 9 )
            maskB[sq] |= C64(1) << i;
        for ( i = sq - 7; i >= 0 && i % 8 != 0; i -= 7 )
            maskB[sq] |= C64(1) << i;
        for ( i = sq + 9; i < 64 && i % 8 != 0; i += 9 )
            maskB[sq] |= C64(1) << i;
        for ( i = sq + 7; i < 64 && i % 8 != 7; i += 7 )
            maskB[sq] |= C64(1) << i;
    }
}

For each square there is a maximum number of steps to take.

/*
Number of expanding steps (explosions) for a bishop
*/
const int repsB[64] =
{
    6, 5, 4, 3, 3, 4, 5, 6,
    5, 5, 4, 3, 3, 4, 5, 5,
    4, 4, 4, 3, 3, 4, 4, 4,
    3, 3, 3, 3, 3, 3, 3, 3,
    3, 3, 3, 3, 3, 3, 3, 3,
    4, 4, 4, 3, 3, 4, 4, 4,
    5, 5, 4, 3, 3, 4, 5, 5,
    6, 5, 4, 3, 3, 4, 5, 6,
};

This does one step of the explosion.

/*
= init               >>= 9               *= 0x5005          &= mask            at |= bb
 . . . . . . . .     . . . . . . . .     . . . . . . . .    . . . . . . . .    . . . . . . . .
 . . . . . . . .     . . . . . . . .     . . . . . . . .    . . . . . . . .    . . . . . . . .
 . . . . . . . .     . . . . . . . .     . 1 1 . . 1 . .    . 1 . . . 1 . .    . 1 . . . 1 . .
 . . 1 . 1 . . .     . . . . . . . .     . . . . . . . .    . . . . . . . .    . . 1 . 1 . . .
 . . . s . . . .     . . . 1 . 1 . .     1 1 . . 1 . . .    . . . s . . . .    . . . s . . . .
 . . 1 . 1 . . .     . . . . . . . .     . . . . . . . .    . . . . . . . .    . . 1 . 1 . . .
 . . . . . . . .     . . . 1 . 1 . .     . 1 1 . . 1 . .    . 1 . . . 1 . .    . 1 . . . 1 . .
 . . . . . . . .     . . . . . . . .     . . . . . . . .    . . . . . . . .    . . . . . . . .
*/
Bitboard bishopAttacks( int sq, const Bitboard &free )
{
    Bitboard msk = maskB[sq];
    Bitboard bb  = initB[sq];
    Bitboard at  = bb;
    bb &= free;
    switch ( repsB[sq] )
    {
      case 6:
        bb >>= 9; bb *= 0x00050005; bb &= msk; at |= bb; bb &= free;
      case 5:
        bb >>= 9; bb *= 0x00050005; bb &= msk; at |= bb; bb &= free;
      case 4:
        bb >>= 9; bb *= 0x00050005; bb &= msk; at |= bb; bb &= free;
      case 3:
        bb >>= 9; bb *= 0x00050005; bb &= msk; at |= bb; bb &= free;
        bb >>= 9; bb *= 0x00050005; bb &= msk; at |= bb; bb &= free;
        bb >>= 9; bb *= 0x00050005; bb &= msk; at |= bb;
    }
    return at;
}

There are some possible optimisations when the repsB[] array is modified in the corners during
the game or search. Some numbers 7, 8, 9 combined with additional switch cases can work
as a shortcut for bishops in the corners behind pawns.

Rooks

For each square there is an ignition of the explosion.

/*
First expanding step (explosion) for a rook
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . 1 . . . .
 . . 1sq 1 . . .
 . . . 1 . . . .
 . . . . . . . .
 . . . . . . . .
*/
Bitboard initR[64];
void makeInitR()
{
    for ( int sq = 0; sq < 64; ++sq )
    {
        Bitboard bb = C64(1) << sq;
        initR[sq]  = (bb >> 8);
        initR[sq] |= (bb >> 1) & C64(0x7f7f7f7f7f7f7f7f);
        initR[sq] |= (bb << 1) & C64(0xfefefefefefefefe);
        initR[sq] |= (bb << 8);
        //logf << "initR[sq] " << sq << endl;
        //logf << initR[sq].txt8lines() << endl;
    }
}

The explosion is only allowed along the rays.

/*
Mask for rook attack rays
 . . . 1 . . . .
 . . . 1 . . . .
 . . . 1 . . . .
 . . . 1 . . . .
 1 1 1sq 1 1 1 1
 . . . 1 . . . .
 . . . 1 . . . .
 . . . 1 . . . .
*/
Bitboard maskR[64];
void makeMaskR()
{
    int sq;
    for ( sq = 0; sq < 64; ++sq )
    {
        maskR[sq] = 0;
        int i;
        for ( i = sq - 8; i >= 0; i -= 8 )
            maskR[sq] |= C64(1) << i;
        for ( i = sq - 1; i >= 0 && (i & 7) != 7; --i )
            maskR[sq] |= C64(1) << i;
        for ( i = sq + 1; i < 64 && (i & 7) != 0; ++i )
            maskR[sq] |= C64(1) << i;
        for ( i = sq + 8; i < 64; i += 8 )
            maskR[sq] |= C64(1) << i;
    }
}

For each square there is a maximum number of steps to take. The number 8 is just a variant of the 7th step.

/**
Number of expanding steps (explosions) for a rook
*/
const int repsR[64] =
{
    7, 6, 6, 6, 6, 6, 6, 8,
    7, 5, 5, 5, 5, 5, 5, 8,
    7, 5, 4, 4, 4, 4, 5, 8,
    7, 5, 4, 3, 3, 4, 5, 8,
    7, 5, 4, 3, 3, 4, 5, 8,
    7, 5, 4, 4, 4, 4, 5, 8,
    7, 5, 5, 5, 5, 5, 5, 8,
    7, 6, 6, 6, 6, 6, 6, 8,
};

This does one step of the explosion.
We have a lot of work to avoid overflows, wrap around the unwanted bits.

/*
= init               >>= 8               *= 0x10281         &= mask            at |= bb
 . . . . . . . .     . . . . . . . .     . . . . . . . .    . . . . . . . .    . . . . . . . .
 . . . . . . . .     . . . . . . . .     . . . . . . . .    . . . . . . . .    . . . . . . . .
 . . . . . . . .     . . . . . . . .     . . . 1 . . . .    . . . 1 . . . .    . . . 1 . . . .
 . . . 1 . . . .     . . . . . . . .     . . 1 . 1 . . .    . . . . . . . .    . . . 1 . . . .
 . . 1 s 1 . . .     . . . 1 . . . .     . 1 . 1 . 1 . .    . 1 . s . 1 . .    . 1 1 s 1 1 . .
 . . . 1 . . . .     . . 1 . 1 . . .     . . 1 . 1 . . .    . . . . . . . .    . . . 1 . . . .
 . . . . . . . .     . . . 1 . . . .     . . . 1 . . . .    . . . 1 . . . .    . . . 1 . . . .
 . . . . . . . .     . . . . . . . .     . . . . . . . .    . . . . . . . .    . . . . . . . .
                                       and nasty overflows
*/
Bitboard rookAttacks( int sq, const Bitboard &free )
{
    Bitboard msk = maskR[sq];   // The mask kills scattered bits
    Bitboard bb  = initR[sq];   // This drives the expansion/explosion. Here is the start.
    Bitboard at  = bb;          // Collecting the resulting attacks
    Bitboard cl  = at;          // Clears some intermediate overflows
    Bitboard ov;                // A nasty overflow bit when 4 directions in first step are possible.
                                // Not nessessary on left side of board for repsR[sq] = 4 or 5.
                                // Invent new numbers?
    // Perhaps it would be easier and faster to use rankR[][] on all ranks.
    // But I like the 'explosive' algorithm. And I want to show that it works.
int repsLeft = 0; // will be overwritten
    bb &= free;
    bb >>= 8;
    switch ( repsR[sq] )
    {
      case 8:
        bb *= 0x00010081;
        repsLeft = 5;
        break;
      case 7:
        bb *= 0x00010201;
        repsLeft = 5;
        break;
      case 6:
        bb *= 0x00010281;
        bb &= ~(C64(1) << (sq - 6));      // Clears for b-squares a nasty overflow from south-west-first-step to h file
        repsLeft = 5;
        break;
      case 5:
        bb *= 0x00010281;
        ov = (C64(1) << (sq + 3));
        bb |= (bb & ov) >> 1;
        bb &= ~ov;
        bb &= ~(C64(1) << (sq - 6));      // Clears for b-squares a nasty overflow from south-west-first-step to h file
        repsLeft = 4;
        break;
      case 4:
        bb *= 0x00010281;
        ov = (C64(1) << (sq + 3));
        bb |= (bb & ov) >> 1;
        bb &= ~ov;
        repsLeft = 3;
        break;
      case 3:
        bb *= 0x00010281;
        ov = (C64(1) << (sq + 3));
        bb |= (bb & ov) >> 1;
        bb &= ~ov;
        repsLeft = 2;
        break;
      }
      default:
      /* reaching here is an error */
      break;
    }
    bb &= msk; at |= bb;
    while(repsLeft-- > 0)
    {
        bb &= free; bb &= ~cl;
        cl = at;
        bb >>= 8; bb *= 0x00010281; bb &= msk; at |= bb;
    }
    if ( sq < 8 ) // or do this before the switch
    {
        int a1a8 = free ;
        at |= rankR[sq][a1a8 & 0x7e];
    }
    return at;
}

There are some possible optimisations when the repsR[] array is modified in the corners during
the game or search. Some numbers 9, 10, 11 combined with additional switch cases can work
as a shortcut for rooks in the corners behind pawns.

In the function rookAttacks() rankR is the well know simple lookup table from other bitboard algorithms.

int rankR[8][128];
void makeRankR()
{
    for ( int sq = 0; sq < 8; ++sq )
    {
        for ( int i = 0; i < 128; i += 2 )
        {
            int rr = 0;
            int j;
            for ( j = sq - 1; j >= 0; --j )
            {
                rr |= (1 << j);
                if ( !(i & (1 << j)) )  // the 1 bits are the free squares
                    break;
            }
            for ( j = sq + 1; j < 8; ++j )
            {
                rr |= (1 << j);
                if ( !(i & (1 << j)) )  // the 1 bits are the free squares
                    break;
            }
            rankR[sq][i  ] = rr;
            rankR[sq][i+1] = rr;
        }
    }
}

Results

The results can be masked or combined just like in other attack bitboards.

/*
Get a bitboard with all positions set to 1 which can be attacked
from a rook or queen on the square.
*/
Bitboard Board::orthogonal_attacks( byte square ) const
{
    Bitboard free = ~(wpieces_ | bpieces_); // from the board representation in the board class
    Bitboard result = rookAttacks( square, free );
    return result;
}
 
/*
Get a bitboard with all positions set to 1 which can be attacked
from a bishop or queen on the square.
*/
Bitboard Board::diagonal_attacks( byte square ) const
{
    Bitboard free = ~(wpieces_ | bpieces_); // from the board representation in the board class
    Bitboard result = bishopAttacks( square, free );
    return result;
}

Another usage requires masks

const Bitboard dirMaskRight[8] =
{
    // 0, line_h, line_gh, line_fh, line_eh, line_dh, line_ch, line_bh,
    0, C64(0x0101010101010101), C64(0x0303030303030303), C64(0x0707070707070707), C64(0x0f0f0f0f0f0f0f0f),
    C64(0x1f1f1f1f1f1f1f1f), C64(0x3f3f3f3f3f3f3f3f), C64(0x7f7f7f7f7f7f7f7f)
};
 
const Bitboard dirMaskLeft[8] =
{
    // line_ag, line_af, line_ae, line_ad, line_ac, line_ab, line_a, 0,
    C64(0xfefefefefefefefe), C64(0xfcfcfcfcfcfcfcfc), C64(0xf8f8f8f8f8f8f8f8), C64(0xf0f0f0f0f0f0f0f0),
    C64(0xe0e0e0e0e0e0e0e0), C64(0xc0c0c0c0c0c0c0c0), C64(0x8080808080808080), 0
};
 
const Bitboard dirMaskUp[8] =
{
    // row_28, row_38, row_48, row_58, row_68, row_78, row_8, 0,
    C64(0xffffffffffffff00), C64(0xffffffffffff0000), C64(0xffffffffff000000), C64(0xffffffff00000000),
    C64(0xffffff0000000000), C64(0xffff000000000000), C64(0xff00000000000000), 0
};
 
const Bitboard dirMaskDown[8] =
{
    // 0, row_1, row_12, row_13, row_14, row_15, row_16, row_17,
    0, C64(0x00000000000000ff), C64(0x000000000000ffff), C64(0x0000000000ffffff), C64(0x00000000ffffffff),
    C64(0x000000ffffffffff), C64(0x0000ffffffffffff), C64(0x00ffffffffffffff)
};

to generate attacks in one direction.

/*
Get a bitboard with all positions set to 1 which can be attacked
from a bishop, rook or queen on the square moving in the direction.
*/
Bitboard Board::direction_attacks( byte square, byte dir ) const
{
    Bitboard result;
    Bitboard free = ~(wpieces_ | bpieces_); // from the board representation in the board class
    // 4 3 2
    // 5 0 1
    // 6 7 8
    switch ( dir )
    {
      case 1:
        result = rookAttacks( square, free );
        result &= dirMaskRight[square & 7];
        break;
      case 5:
        result = rookAttacks( square, free );
        result &= dirMaskLeft[square & 7];
        break;
      case 7:
        result = rookAttacks( square, free );
        result &= dirMaskDown[square >> 3];
        break;
      case 3:
        result = rookAttacks( square, free );
        result &= dirMaskUp[square >> 3];
        break;
      case 8:
        result = bishopAttacks( square, free );
        result &= dirMaskRight[square & 7];
        result &= dirMaskDown[square >> 3];
        break;
      case 4:
        result = bishopAttacks( square, free );
        result &= dirMaskLeft[square & 7];
        result &= dirMaskUp[square >> 3];
        break;
      case 2:
        result = bishopAttacks( square, free );
        result &= dirMaskRight[square & 7];
        result &= dirMaskUp[square >> 3];
        break;
      case 6:
        result = bishopAttacks( square, free );
        result &= dirMaskLeft[square & 7];
        result &= dirMaskDown[square >> 3];
        break;
      default:
        result = 0;
        break;
    }
    return result;
}

References

^ Re: Compact Bitboard Attacks by Harald Lüßen, Winboard Forum, September 13, 2006

What links here?

Page	Date Edited
Elephant	Sep 19, 2016
Exploding Bitboards	Mar 9, 2015
Harald Lüßen	Mar 20, 2013
Sherwin Bitboards	Mar 20, 2013
Sliding Piece Attacks	May 27, 2016

Up one Level

First Rank Attacks

GerdIsenberg — Sat, 28 Aug 2010 21:33:55 GMT

Introduction to Occupancy Lookup

Home * Board Representation * Bitboards * Sliding Piece Attacks * First Rank Attacks

The technique of occupancy lookups is base for rotated- and kindergarten -bitboards.

Introduction to Occupancy Lookup

The first rank is the ideal line to introduce occupancy lookups.

One Byte Only

Occupancy of the first rank = 01001010B

Rank-attacks ::= f (e-file, Occupancy) = 01110110B

BYTE arrFirstRankAttacks256x8[256][8]; // 2048 Bytes = 2KByte
 
firstRankAttack = arrFirstRankAttacks256x8[rankOccupancy][squareOnRank];

Overdetermined?

In fact both indices seem somehow overdetermined, since the rook is already member of occupancy. But rather than to make the redundant rook-bit disappear to use only the remaining seven occupancy bits, with half table size - which is not that cheap and simple either - we better decide to uncouple this items to eventually pass (virtual) rook squares, not actually member of occupancy. We better rely on another property to reduce the table fourfold.

The Outer Squares

BYTE arrFirstRankAttacks64x8[64][8]; // 512 Bytes = 1/2KByte
 
firstRankAttack = arrFirstRankAttacks64x8[(rankOccupancy >> 1)& 63][squareOnRank];

Attacks on all Ranks

Since it is simple to shift ranks up and down, the general rank attack getter is already handy.

BYTE arrFirstRankAttacks64x8[64*8]; // 512 Bytes = 1/2KByte
 
U64 rankAttacks(U64 occ, enumSquare sq) {
   unsigned int file = sq &  7;
   unsigned int rkx8 = sq & 56; // rank * 8
   occ = (occ >> rkx8) & 2*63;
   U64 attacks = arrFirstRankAttacks64x8[4*occ + file];
   return attacks << rkx8;
}

The array is defined one-dimensional, and has to indexed by 8*occ + file. The reason was playing the optimization game and to safe the right shift one, but to scale by 4 instead of 8, which is done by the address calculation unit anyway.

This routine may complete the Hyperbola Quintessence.

What links here?

Page	Date Edited
Amoeba	Mar 19, 2018
Amundsen	Sep 3, 2013
Android-Chess	Jun 2, 2016
Best Magics so far	Apr 13, 2018
BMI2	Mar 6, 2018
Brainless	Jun 24, 2017
Byte	Apr 5, 2013
Chesley	Dec 25, 2012
Classical Approach	Jan 28, 2018
Congruent Modulo Bitboards	Jun 26, 2013
Dumb	Mar 10, 2018
Dumb7Fill	May 27, 2016
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
First Rank Attacks	Aug 28, 2010
Fridel Fainshtein	Oct 8, 2014
Hiding the Implementation	Feb 3, 2011
Hyperbola Quintessence	Mar 25, 2017
Kindergarten Bitboards	Aug 1, 2017
Kurt	Apr 20, 2014
Magic Bitboards	Apr 13, 2018
Occupancy of any Line	Sep 16, 2016
Prophet	Sep 30, 2017
Rabbit	Oct 5, 2014
Roberto Waldteufel	Jun 5, 2013
Rotated Bitboards	Mar 7, 2017
Sayuri	Oct 1, 2017
Sliding Piece Attacks	May 27, 2016
The switch Approach	Nov 5, 2010
Vajolet	Jan 25, 2018
Wing	Oct 26, 2017
Winglet	Apr 26, 2015
X-ray Attacks (Bitboards)	Mar 31, 2015
Yaakov HaCohen-Kerner	Aug 23, 2014

Up one Level

Hashing Dictionaries

GerdIsenberg — Sat, 01 Mar 2014 13:31:56 GMT

Avoiding Rotated Bitboards with Direct Lookup

Home * Board Representation * Bitboards * Sliding Piece Attacks * Hashing Dictionaries

This approach using associate arrays or hash tables was introduced in the ICGA Journal (June 2007) by Sam Tannous ^[1]. Like other occupancy lookup approaches it works line-wise for ranks, files, diagonals and anti-diagonals. It uses hash arrays from an interpreted, high level language, Python:

Many high level programming languages (notably Python (van Rossum, 1993)) have useful predefined data structures (e.g. associative arrays) which are dynamically resizable hash tables that resolve collisions by probing techniques. The basic lookup function used in Python is based on Algorithm D: Open Addressing with Double Hashing from Section 6.4 in Knuth ^[2].

Avoiding Rotated Bitboards with Direct Lookup

Sam Tannous compared this approach to a Rotated Bitboards implementation in Python and found direct lookup favorable for move generation. In languages like C, targeting 64-bit cpus like x86-64, or even in Java, it is likely another story if one compares Open Addressing with Double Hashing with rotated or perfect hashing techniques like Kindergarten or even Magic Bitboards.

Abstract

Quoted from Avoiding Rotated Bitboards with Direct Lookup:

This paper describes an approach for obtaining direct access to the attacked squares of sliding pieces without resorting to rotated bitboards. The technique involves creating four hash tables using the built in hash arrays from an interpreted, high level language. The rank, file, and diagonal occupancy are first isolated by masking the desired portion of the board. The attacked squares are then directly retrieved from the hash tables. Maintaining incrementally updated rotated bitboards becomes unnecessary as does all the updating, mapping and shifting required to access the attacked squares. Finally, rotated bitboard move generation speed is compared with that of the direct hash table lookup method.

External Links

Sam Tannous homepage

Class Libraries

References

^ Sam Tannous (2007). Avoiding Rotated Bitboards with Direct Lookup. ICGA Journal, Vol. 30, No. 2, pdf
^ Donald Knuth (1998). The Art of Computer Programming. Volume 3, Sorting and Searching. Addison Wesley. ISBN 0201896850

What links here?

Page	Date Edited
Congruent Modulo Bitboards	Jun 26, 2013
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Hash Table	Jan 1, 2018
Hashing Dictionaries	Mar 1, 2014
Mark Levene	Jun 2, 2015
Python	Jan 31, 2018
Sam Tannous	Mar 1, 2014
Shatranj (toolkit)	May 16, 2015
Sliding Piece Attacks	May 27, 2016
Trevor Fenner	Jun 2, 2015

Up one Level

Hiding the Implementation

GerdIsenberg — Thu, 03 Feb 2011 11:04:13 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Hiding the Implementation

None rotated approaches as mentioned in

can hide the implementation details behind a stateless interface:

U64 diagonalAttacks(U64 occ, enumSquare sq);
U64 antiDiagAttacks(U64 occ, enumSquare sq);
U64 fileAttacks    (U64 occ, enumSquare sq);
U64 rankAttacks    (U64 occ, enumSquare sq);
 
U64 rookAttacks    (U64 occ, enumSquare sq);
U64 bishopAttacks  (U64 occ, enumSquare sq);
 
U64 queenAttacks   (U64 occ, enumSquare sq);

In C / C++ one may use header files with exclusive, conditional compiled inlined routines, as combinations and variations of the mentioned approaches. Initialization should be implemented by conditional compile switches in various implementation files (c, cpp). Favorite should be bishopAttack by magic bitboards due to the relative small table less than 38KByte, while magic rookattacks takes more than 20 times the space so far.

As always with space-time tradeoff - it depends on the cache- and memory using and footprint of a individual chess program - on a particular hardware architecture - which solution is preferable and faster. Perft frameworks likely prefer larger tables but less computation. So far L1 Cache is a rare resource, Translation Lookaside Buffer als well.

External Links

Information hiding from Wikipedia

What links here?

Page	Date Edited
Fridel Fainshtein	Oct 8, 2014
Hiding the Implementation	Feb 3, 2011
Kindergarten Bitboards	Aug 1, 2017
Sliding Piece Attacks	May 27, 2016
Yaakov HaCohen-Kerner	Aug 23, 2014

Up one Level

Hyperbola Quintessence

camleon — Sat, 25 Mar 2017 14:31:28 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Hyperbola Quintessence

Hyperbola Quintessence applies the o^(o-2r)-trick also for vertical or diagonal negative Rays - by reversing the bit-order of up to one bit per rank or byte with a vertical flip aka x86-64 bswap ^[1] . It is somehow a resurrection of the reverse bitboards idea of Ryan Mack's Hyperbola Project on the fly, and was created by Gerd Isenberg. Improvements by Aleks Peshkov ^[2] made it applicable and competitive.

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

Samuel Bak - Reflexion, 1990 ^[3]

Reverse Math

Source Code

Generalized set-wise attacks

x86-64 assembly

Java

AMD's SIMD Future in 2011

Reverse Math

Assume following masked occupancy on a file, diagonal or anti-diagonal - for simplicity as a flat byte (in a real bitboard with masked files or diagonals you have 6..8 scratch-bits between the bits of this byte). Thus, vertical flip reverses the bits of this byte.

o' = reverse(o)
r' = reverse(r)
 
       normal    reversed
 o     11010101  10101011 o' occupancy including slider
 r     00010000  00001000 r' slider
 o-r   11000101  10100011 o'-r'  1. sub clears the slider
 o-2r  10110101  10011011 o'-2r' 2. sub borrows "one" from next blocker
       |......|  \....../
normal 10110101   \..../
       11011001 <--XXXX   re-reverse
single
xor    01101100 -> to get the attack set

The first subtraction of (o-2r) is done implicitly by masking off the line, removing the slider from the occupied set. The second subtraction borrows a "one" from the next nearest blocker in msb-direction, falling through all unset bits outside the line. Of course, if no blocker is available, it borrows a "one" in usual arithmetical manner from the hidden 2^N. Only the changed bits (from original o, o') are the appropriate sliding attacks, including the blocker but excluding the slider. The result finally needs to be intersected with the same line mask as previously the occupancy, to clear the wrapped borrow one bits outside the file or diagonal. The fine optimization by Aleks Peshkov covers the final union of positive and negative ray-attacks. Since opposed ray-directions are always disjoint sets, using xor instead of bitwise or safes two instructions per line-attack. That is because bit-reversal or any mirroring or flipping is own inverse and distributive over xor.

reverse(a ^ b) == reverse (a) ^ reverse(b)

thus

lineAttacks = o^(o-2r) ^ reverse((o'-2r')^o')
lineAttacks = o^(o-2r) ^ reverse( o'-2r') ^ reverse(o')
lineAttacks = o^(o-2r) ^ reverse( o'-2r') ^ o

and finally

lineAttacks =   (o-2r) ^ reverse( o'-2r')

Beside shorter code this reduces register pressure - and clearly outperforms kindergarten bitboards - ipc-wise, in code size and memory requirements.

Source Code

C

The three C-routines only differ by the line-mask applied:

U64 diagonalAttacks(U64 occ, enumSquare sq) {
   U64 forward, reverse;
   forward = occ & smsk[sq].diagonalMaskEx;
   reverse  = _byteswap_uint64(forward);
   forward -= smsk[sq].bitMask;
   reverse -= _byteswap_uint64(smsk[sq].bitMask);
   forward ^= _byteswap_uint64(reverse);
   forward &= smsk[sq].diagonalMaskEx;
   return forward;
}
 
U64 antiDiagAttacks(U64 occ, enumSquare sq) {
   U64 forward, reverse;
   forward  = occ & smsk[sq].antidiagMaskEx;
   reverse  = _byteswap_uint64(forward);
   forward -= smsk[sq].bitMask;
   reverse -= _byteswap_uint64(smsk[sq].bitMask);
   forward ^= _byteswap_uint64(reverse);
   forward &= smsk[sq].antidiagMaskEx;
   return forward;
}
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   U64 forward, reverse;
   forward  = occ & smsk[sq].fileMaskEx;
   reverse  = _byteswap_uint64(forward);
   forward -= smsk[sq].bitMask;
   reverse -= _byteswap_uint64(smsk[sq].bitMask);
   forward ^= _byteswap_uint64(reverse);
   forward &= smsk[sq].fileMaskEx;
   return forward;
}
 
U64 bishopAttacks(U64 occ, enumSquare sq) {
   return diagonalAttacks (occ, sq)
        + antiDiagAttacks (occ, sq);
}

For better locality of the line-attacks on the otherwise empty board, we may use an properly aligned array of structs.

struct
{
   U64 bitMask;         // 1 << sq for convenience
   U64 diagonalMaskEx;
   U64 antidiagMaskEx;
   U64 fileMaskEx;
} smsk[64]; // 2 KByte

Using x86-64 bswap makes it quite competitive for bishops and files, on AMD K8 or K10 it has a latency of one cycle with a throughput of 1/3, like other cheap instructions. However, Intel is tad slower - while the recent Core 2 duo processors perform 128-bit SIMD-instructions with 128-bit alus, that is bitwise logical instructions with a latency of one cycle and throughput of 1/3, the general purpose bswap-instruction takes four cycles with a throughput of one. In Intel 64 and IA32 Architectures Optimization Reference Manual ^[4] , it is therefor recommend (5.6.5. endian conversion) to use the SSSE3 pshufb instruction to swap bytes, available through intrinsic ^[5] , see SSSE3 Hyperbola Quintessence for bishop attacks.

As long there is no fast bit reversal instruction, there is no general solution for all four lines, and the rook attack-getter still needs some standard technique for the rank-attacks. Tim Cooijmans proposed to map the rank to the main diagonal before applying HQ, and to re-map the calculated attacks back to the original rank ^[6] .

Generalized set-wise attacks

Hyperbola quintessence can be generalized to work on whole sets of sliding pieces instead on individual pieces, whose ranks to be masked. The problem arising, when not masking the rank of the piece is that attacks wrap around the board during subtraction. This is shown below:

     ........       ........                            11111111
     ........       ........                            11111111
     ........       ........                            11111111
 r = ........ , o = ........ this leads to   o - 2*r =  11111111
     ........       ........                            11111111
     ........       ........                            11111111
     ....1...       ....1...                            11111...
     ........       ........                            ........
 
instead of
 
........
........
........
........
........
........
11111...
........

This is not the intended result. It can be avioded, by bitwise adding an overflow barrier on the right-hand side. Afterwards this barrier needs to be removed from the attack set:

u64 right = 0x0101010101010101ULL;
 
     ......1.      1..1..1.                              1...1111
     ....1...      1...1...                              .1111..1
     ......1.      11....1.                              1.111111
r =  .....1..  o = .11..1..   now: ((o | right) - 2*r) = .1.111.1
     ........      ........                              ........
     ......1.      ......1.                              1111111.
     .......1      .......1                              1111111.
     1.......      1.......                              1......1
 
Note, that the 4th rank was not flooded by the subtraction! Next, the blockers are removed as usual:
 
                          ...111.1
                          1111...1
                          .11111.1
o ^ ((o | right) - 2*r) = ..111..1
                          ........
                          111111..
                          11111111
                          .......1
 
The last step is to remove the barrier at the right side that became visible after the last operation.
 
                                     ...111..
                                     1111...
                                     .11111..
(o ^ ((o | right) - 2*r) & ~right =  ..111...
                                     ........
                                     111111..
                                     1111111.
                                     ........
 
This is the correct attack set for the left direction.

the complete algorithm for the left direction is therefore:

const u64 right = 0x0101010101010101ULL;
 
u64 leftAttacks = ((o ^ ((o | right) - 2*r) & ~right);

For the right-hand direction, the bits need to be reversed rank-wise.

x86-64 assembly

The VC2005 generated x86-64 assembly of bishopAttacks indicates what ipc-monster Hyperbola Quintessence is:

occ$ = 16
sq$ = 24
?bishopAttacks@@YA_K_KI@Z PROC
  00000   40 53                push    rbx
  00002   8b c2                mov    eax, edx
  00004   4c 8d 15 00 00 00 00 lea    r10, OFFSET FLAT:?smsk
  0000b   48 c1 e0 05          shl    rax, 5
  0000f   4a 8b 5c 10 08       mov    rbx, QWORD PTR [rax+r10+8]  ; diagonalMaskEx
  00014   4e 8b 4c 10 10       mov    r9,  QWORD PTR [rax+r10+16] ; antidiagMaskEx
  00019   4e 8b 14 10          mov    r10, QWORD PTR [rax+r10]    ; r := 1 << sq
  0001d   4c 8b db             mov    r11, rbx                    ; diagonalMaskEx
  00020   49 8b d1             mov    rdx, r9                     ; antidiagMaskEx
  00023   4d 8b c2             mov    r8, r10                     ; r := 1 << sq
  00026   48 23 d1             and    rdx, rcx                    ; anti & occ
  00029   4c 23 d9             and    r11, rcx                    ; dia  & occ
  0002c   49 0f c8             bswap  r8                          ; r'
  0002f   48 8b c2             mov    rax, rdx                    ; ant
  00032   49 8b cb             mov    rcx, r11                    ; dia
  00035   49 2b d2             sub    rdx, r10                    ; ant - r
  00038   48 0f c8             bswap  rax                         ; ant'
  0003b   48 0f c9             bswap  rcx                         ; dia'
  0003e   4d 2b da             sub    r11, r10                    ; dia - r
  00041   49 2b c0             sub    rax, r8                     ; ant' - r'
  00044   49 2b c8             sub    rcx, r8                     ; dia' - r'
  00047   48 0f c8             bswap  rax                         ;(ant' - r')'
  0004a   48 0f c9             bswap  rcx                         ;(dia' - r')'
  0004d   48 33 c2             xor    rax, rdx                    ; ant := (ant' - r')' ^ (ant - r)
  00050   49 33 cb             xor    rcx, r11                    ; dia := (dia' - r')' ^ (dia - r)
  00053   49 23 c1             and    rax, r9                     ; ant &= antidiagMaskEx
  00056   48 23 cb             and    rcx, rbx                    ; dia &= diagonalMaskEx
  00059   48 03 c1             add    rax, rcx                    ; attacks := dia + ant
  0005c   5b                   pop    rbx
  0005d   c3                   ret    0
?bishopAttacks@@YA_K_KI@Z ENDP

Java

Java programmer may try Long.reverseBytes:

    static private final long[] bitMask = {
        0x0000000000000001, 0x0000000000000002, 0x0000000000000004, 0x0000000000000008,
        0x0000000000000010, 0x0000000000000020, 0x0000000000000040, 0x0000000000000080,
        ...
    };
 
    static private final long[] diagonalMaskEx = {
        0x8040201008040200, 0x0080402010080400, 0x0000804020100800, 0x0000008040201000,
        0x0000000080402000, 0x0000000000804000, 0x0000000000008000, 0x0000000000000000,
        ...
    };
 
    /**
     * @param occ - occupancy
     *        sq  - from square
     * @return diagonal attacks from sq with occupancy occ
     */
    static public long diagonalAttacks(long occ, int sq)
    {
       long forward = occ & diagonalMaskEx[sq];
       long reverse = Long.reverseBytes(forward);
       forward -= bitMask[sq];
       reverse -= bitMask[sq^56];
       forward ^= Long.reverseBytes(reverse);
       forward &= diagonalMaskEx[sq];
       return forward;
    }

Long.reverse for a generalized attack getter even for ranks is too expensive, except a JVM can use a machine instruction rather than a bit-reversal routine:

    /**
     * @param occ  - occupancy
     *        line - {0..3} {rank, file, diagonal, antidiagonal}
     *        sq   - from square
     * @return attacks from sq on line with occupancy occ
     */
    static public long attacks(long occ, int line, int sq)
    {
       long forward = occ & maskEx[sq][line];
       long reverse = Long.reverse(forward);
       forward -= bitMask[sq];
       reverse -= bitMask[sq^63];
       forward ^= Long.reverse(reverse);
       forward &= maskEx[sq][line];
       return forward;
    }

AMD's SIMD Future in 2011

In 2007 AMD announced the hypothetical SSE5 instruction set ^[7] with a PPERM instruction ^[8] , which would be able to reverse vectors of two bitboards. In May 2009 AMD revised SSE5, to become more compatible with Intel's Advanced Vector Extensions, and also expanding the SIMD-register width from 128 to 256-bit, the renamed XOP instruction set ^[9] . However, the successor of the planned PPERM SSE5-instruction is now called VPPERM, but still works on 128-bit XMM registers ^[10] . VPPERM instruction requires four operands (xmm-registers):

 VPPERM dest, src1, src2, selector

For each of 16 destination bytes the corresponding selector-byte addresses one of 32 input bytes (from src1, src2) and a logical operation including bit-reversal:

char src[32];   // src2:src1
char select[16];
char dest[16];
for (int i = 0; i < 16; i++) {
   char opera = select[i] >>> 5; // unsigned shift
   char idx32 = select[i] & 31;
 
   switch ( opera ) {
      case 0: dest[i] =  src[idx32]; break;
      case 1: dest[i] = ~src[idx32]; break;
      case 2: dest[i] =  bitreverse( src[idx32]); break;
      case 3: dest[i] = ~bitreverse( src[idx32]); break;
      case 4: dest[i] = 0x00; break;
      case 5: dest[i] = 0xFF; break;
      case 6: dest[i] =  src[idx32] >> 7;  break; // signed shift
      case 7: dest[i] = ~src[idx32] >> 7;  break; // signed shift
   }
}

Since VPPERM can simultaneously reverse bits and bytes, it can for instance reverse two bitboards in one run, even from different sources, to make Hyperbola Quintessence work for all four lines.

Forum Posts

Re: BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits by Aleks Peshkov, CCC, August 25, 2007
Hyperbola Quiesscene: hardly any improvement by trojanfoe, CCC, January 13, 2009
Comparison of bitboard attack-getter variants by Sven Schüle, CCC, January 04, 2016
Re: The wrong way by Aleks Peshkov, CCC, January 05, 2016 » SSSE3 Hyperbola Quintessence

External Links

Sliding Pieces (Part 1) - Advanced Java Chess Engine Tutorial 8 by Jonathan Warkentin
Hyperbola Quintessence for rooks along ranks by Tim Cooijmans, April 6, 2014 ^[11]

Hyperbola

Quintessence

Misc

Focus - Hocus Pocus, Pinkpop Festival 1972, Geleen, YouTube Video

References

^ _byteswap_uint64 Visual C++ Developer Center - Run-Time Library Reference
^ Re: BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits by Aleks Peshkov, CCC, August 25, 2007
^ The Game of War from Samuel Bak - represented by Pucker Gallery since 1969
^ Intel 64 and IA32 Architectures Optimization Reference Manual (pdf)
^ _mm_shuffle_epi8 Visual C++ Developer Center - Run-Time Library Reference
^ Hyperbola Quintessence for rooks along ranks by Tim Cooijmans, April 6, 2014
^ 128-Bit SSE5 Instruction Set from AMD Developer Central
^ SSE5 permutations
^ XOP instruction set from Wikipedia
^ Volume 6: 128-Bit and 256-Bit XOP, FMA4 and CVT16 Instructions (pdf), see VPPERM pg. 221
^ Re: Comparison of bitboard attack-getter variants by Matthew R. Brades, CCC, January 04, 2016

What links here?

Page	Date Edited
Aleks Peshkov	Jan 13, 2016
Amoeba	Mar 19, 2018
Dumb	Mar 10, 2018
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Endianness	Jan 25, 2015
Fill Algorithms	Nov 6, 2013
First Rank Attacks	Aug 28, 2010
Flipping Mirroring and Rotating	Oct 14, 2016
General Setwise Operations	Feb 25, 2018
Hiding the Implementation	Feb 3, 2011
Hyperbola Quintessence	Mar 25, 2017
Java	Feb 25, 2018
Jonathan Warkentin	Jun 29, 2014
Karlo Bala Jr.	Feb 19, 2017
Kindergarten Bitboards	Aug 1, 2017
Kogge-Stone Algorithm	Sep 17, 2016
Parallel Prefix Algorithms	Jun 22, 2016
Reverse Bitboards	Aug 29, 2015
Ryan Mack	Jan 18, 2011
SBAMG	Dec 4, 2016
SIMD techniques	Nov 26, 2017
Sliding Piece Attacks	May 27, 2016
SSSE3	Aug 8, 2017
Subtracting a Rook from a Blocking Piece	Dec 2, 2016
Syed Fahad	Jan 1, 2017
XOP	Aug 8, 2017

Up one Level

Kindergarten Bitboards

GerdIsenberg — Tue, 01 Aug 2017 19:55:05 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Kindergarten Bitboards

		Kindergarten bitboards ^[1] was a kind of interactive forum development ^[2] with a lot of meanders ^[3] . There were two issues involved - first to calculate the occupancy of any line from the occupied bitboard ^[4] - and second, compact and dense lookup tables. As a quintessence Gerd Isenberg came up with this nomination. It relies on fast 64-bit multiplication, but is otherwise quite resource friendly and a compromise between calculation and table-size.
Paul Klee, Group of Masks, 1939 ^[5]

Ranks and Diagonals

Ranks and diagonals - that is their appropriate line-mask by square-index - are first intersected by the occupancy of the whole board. Doesn't matter whether the slider itself is cleared or not - it is redundant anyway, considered by the pre-calculated lookup-table.

Since there is only up to one bit per file, the north-fill multiplication by the A-file maps the diagonal to the 8th rank. Or - since we only need the inner six bits, we combine the required shift left one by multiplying with the B-file. Shifting right the product by 58 (64-6) leaves the six-bit occupancy-index in the 0..63 range. For instance the diagonal-attacks of a bishop on d4. 'A'-'H' represent the masked occupied bits along this diagonal, which are either zero or one.

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

We need 'B'-'G' as six bit number:

masked line      *  B-File           =  B-G upper six       occupancy 6 bit
. . . . . . . H     . 1 . . . . . .     . A[B C . E F G]    . . . . . . . .
. . . . . . G .     . 1 . . . . . .     . A B C . E F G     . . . . . . . .
. . . . . F . .     . 1 . . . . . .     . A B C . E F .     . . . . . . . .
. . . . E . . .     . 1 . . . . . .     . A B C . E . .  >> . . . . . . . .
. . . . . . . .  *  . 1 . . . . . .  =  . A B C . . . .  58 . . . . . . . .
. . C . . . . .     . 1 . . . . . .     . A B C . . . .     . . . . . . . .
. B . . . . . .     . 1 . . . . . .     . A B . . . . .     . . . . . . . .
A . . . . . . .     . 1 . . . . . .     . A . . . . . .    [B C . E F G]. .

8 copies of rank      the attack set
attacks & l-mask  ->  of this line
a b c . e f g h       . . . . . . . h
a b c . e f g h       . . . . . . g .
a b c . e f g h       . . . . . f . .
a b c . e f g h       . . . . e . . .
a b c . e f g h       . . . . . . . .
a b c . e f g h       . . c . . . . .
a b c . e f g h       . b . . . . . .
a b c . e f g h       a . . . . . . .

Since all ranks, diagonals and anti-diagonals are properly file-aligned, it works perfectly with some redundant occupied bits for shorter diagonals as well, like here the outer bit 'B':

masked line      *  B-File           =  B-G upper six       occupancy 6 bit
. . . . . . . .     . 1 . . . . . .     H .[B C . E F G]    . . . . . . . .
. . . . . . . H     . 1 . . . . . .     . . B C . E F G     . . . . . . . .
. . . . . . G .     . 1 . . . . . .     . . B C . E F G     . . . . . . . .
. . . . . F . .     . 1 . . . . . .     . . B C . E F .  >> . . . . . . . .
. . . . E . . .  *  . 1 . . . . . .  =  . . B C . E . .  58 . . . . . . . .
. . . . . . . .     . 1 . . . . . .     . . B C . . . .     . . . . . . . .
. . C . . . . .     . 1 . . . . . .     . . B C . . . .     . . . . . . . .
. B . . . . . .     . 1 . . . . . .     . . B . . . . .    [B C . E F G]. .

Appropriate pre-calculated attack bits are represented by 'b'-'h' here:

8 copies of rank      the attack set   or  the attack set
attacks & l-mask  ->  of this line     ->  of the shorter diagonal
a b c . e f g h       . . . . . . . h      . . . . . . . .
a b c . e f g h       . . . . . . g .      . . . . . . . h
a b c . e f g h       . . . . . f . .      . . . . . . g .
a b c . e f g h       . . . . e . . .      . . . . . f . .
a b c . e f g h       . . . . . . . .      . . . . e . . .
a b c . e f g h       . . c . . . . .      . . . . . . . .
a b c . e f g h       . b . . . . . .      . . c . . . . .
a b c . e f g h       a . . . . . . .      . b . . . . . .

Wasn't that simple? That is why it is called kindergarten bitboards!

The trick is to share one 4KByte table by three line-directions by re-using the mask for a final intersection. Of course one may use the calculated occupied state to index rotated bitboards like tables of 32KByte each. But dividing the table size by 3*8 on the cost of that additional 'and' (and keeping the mask inside a register) is tempting. Of course - like always with computation versus memory issues - it depends on the cache- and memory using and footprint inside a particular chess program and the hardware architecture, which solution is preferable. So far L1 Cache is a rare resource, Translation Lookaside Buffer als well.

Like other none rotated approaches, namely magic bitboards or hyperbola quintessence, the nice thing is that one can hide the implementation details behind a stateless interface. In C /C++ one may use header files with exclusive, conditional compiled inlined routines, as combinations and variations of the mentioned approaches.

The three routines only differ by the line-mask applied. As pointed out by Aleks Peshkov, it is smarter to index by file, occupancy, since fillUpAttacks[sq&7] may be shared by two (bishop) or three (queen) line-attack getters.

U64 fillUpAttacks[8][64];  // 4 KByte
 
U64 diagonalAttacks(U64 occ, enumSquare sq) {
   const U64 bFile = C64(0x0202020202020202);
   occ = (diagonalMaskEx[sq] & occ) * bFile >> 58;
   return diagonalMaskEx[sq] & fillUpAttacks[sq&7][occ];
}
 
U64 antiDiagAttacks(U64 occ, enumSquare sq) {
   const U64 bFile = C64(0x0202020202020202);
   occ = (antidiagMaskEx[sq] & occ) * bFile >> 58;
   return antidiagMaskEx[sq] & fillUpAttacks[sq&7][occ];
}
 
U64 rankAttacks(U64 occ, enumSquare sq) {
   const U64 bFile = C64(0x0202020202020202);
   occ = (rankMaskEx[sq] & occ) * bFile >> 58;
   return rankMaskEx[sq] & fillUpAttacks[sq&7][occ];
}

One may use similar structs for the line-masks than the hyperbola quintessence.

File-Attacks

Files need tad more work. Shift the board left (arithmetical right!) to the A-file to mask it. To get the inner six bits, a flip-multiplication by the c2-h7 diagonal is applied with further shift right 58. The lookup-table contains the A-file attacks, which are shifted "back" to the original file.

U64 aFileAttacks [8][64];  // 4 KByte
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   const U64 aFile   = C64(0x0101010101010101);
   const U64 diac2h7 = C64(0x0080402010080400);
   occ = aFile  & (occ >> (sq&7));
   occ = (diac2h7 *  occ ) >> 58;
   return aFileAttacks[sq>>3][occ] << (sq&7);
}

This is how it works:

masked A-file    *  c2-h7 Diagonal    =  occupancy
H . . . . . . .     . . . . . . . .     . .[G F E D C B]    . . . . . . . .
G . . . . . . .     . . . . . . . 1     . . F E D C B A     . . . . . . . .
F . . . . . . .     . . . . . . 1 .     . . E D C B A .     . . . . . . . .
E . . . . . . .     . . . . . 1 . .     . . D C B A . .  >> . . . . . . . .
D . . . . . . .  *  . . . . 1 . . .  =  . . C B A . . .  58 . . . . . . . .
C . . . . . . .     . . . 1 . . . .     . . B A . . . .     . . . . . . . .
B . . . . . . .     . . 1 . . . . .     . . A . . . . .     . . . . . . . .
A . . . . . . .     . . . . . . . .     . . . . . . . .    [G F E D C B]. .

Note that the six inner bit occupancy is reversed - considered in the pre-calculated aFileAttacks array. This reversed lookup was justified to share first rank-attacks by all directions - with a dense lookup of 512 Byte. But the 4KByte tables outperform the additional multiplications and shift of the dense version - and one may alternatively multiply with the flipped diagonal, the c7-h2 anti-diagonal:

masked A-file    *  c7-h2 AntiDiag   =  occupancy
H . . . . . . .     . . . . . . . .     . .[B C D E F G]    . . . . . . . .
G . . . . . . .     . . 1 . . . . .     . . A B C D E F     . . . . . . . .
F . . . . . . .     . . . 1 . . . .     . . . A B C D E     . . . . . . . .
E . . . . . . .     . . . . 1 . . .     . . . . A B C D  >> . . . . . . . .
D . . . . . . .  *  . . . . . 1 . .  =  . . . . . A B C  58 . . . . . . . .
C . . . . . . .     . . . . . . 1 .     . . . . . . A B     . . . . . . . .
B . . . . . . .     . . . . . . . 1     . . . . . . . A     . . . . . . . .
A . . . . . . .     . . . . . . . .     . . . . . . . .    [B C D E F G]. .

Shared Rank Lookup

As often, computation versus memory size. One may share a 512Byte Lookup of the first rank by all lines with some trailing computation. Multiplying with the A-file (fill north) for ranks and diagonals, and multiplying with the diagonal for the file. Likely the additional multiplication don't pays off.

const BYTE firstRankAttacks[8][64];
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   const U64 aFile   = C64(0x0101010101010101);
   const U64 hFile   = C64(0x8080808080808080);
   const U64 diaa1h8 = C64(0x8040201008040201);
   const U64 diac2h7 = C64(0x0080402010080400);
 
   unsigned int f = sq & 7;
   occ =   aFile   & (occ   >>  f);
   occ = ( diac2h7 *  occ ) >> 58;
   occ =   diaa1h8 * firstRankAttacks[(sq^56)>>3][occ];
   return ( hFile  &  occ ) >> (f^7);
}
 
U64 diagonalAttacks(U64 occ, enumSquare sq) {
   const U64 aFile = C64(0x0101010101010101);
   const U64 bFile = C64(0x0202020202020202);
 
   unsigned int f = sq & 7;
   occ  =  diagonalMaskEx[sq] & occ;
   occ  = (bFile * occ ) >> 58;
   occ  =  aFile *  firstRankAttacks[f][occ];
   return  diagonalMaskEx[sq] & occ;
}

32-bit Versions

One other variation of the memory versus computation theme was encouraged by 32-bit mode. 64-bit multiplication is quite expensive in 32-bit mode - a call using three imuls. Thus, it is more efficient to use shift-or plus 32-bit multiplication, which might in fact be used in 64-bit mode as well. Piotr Cichy proposed a multiplication less parallel prefix shift approach similar to Occupancy of any Line ^[6] , which is a good alternative for processors with slow multiplication.

An efficient and tricky file-approach was introduced by Zach Wegner ^[7], using a 32KByte, rotated like lookup-table:
It is quite strange, yes, but it is an out of order mapping. There are only 5 bits because each bit in the factor maps more than one bit. The trick here is the odd shift 29, so that the multiply does not overflow individual bits. I have since found that 25 and 27 will work with the same magic:

occ
. . . . . . . .
a . . . . . . .
b . . . . . . .    occ | occ >> 29    * 0x01041041 with the index bracketed
c . . . . . . .    ...\               ...\               ...\
d . . . . . . .    d . . . . . . .    1 . . . . . . .    d a[f c e b d a]
e . . . . . . .    e . . a . . . .    . . 1 . . . . .    e b . a f c e b
f . . . . . . .    f . . b . . . .    . . . . 1 . . .    f c . b . . f c
. . . . . . . .    . . . c . . . .    1 . . . . . 1 .    . . . c . . . .

The interesting thing is that this works for any masked file. In fact if it was shifted to the a-file, you could get away with the 3-bit factor 0x00041040 (but using a shift of 23).

U64 arrFileAttacks[64][64]; // [sq][occ64] 32KByte
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   occ &= fileMask[sq];
   U32 fold  = (U32)occ | (U32)(occ >> 29);
   U32 occ64 = fold * 0x01041041 >> 26;
   return arrFileAttacks[sq][occ64];
}

Ranks and diagonals are trivial, this version favors rotated like memory size for less computation and same operations than file-attacks. One may therefor generalize the routine by a line-direction parameter:

U64 arrDiagonalAttacks[64][64]; // [sq][occ64] 32KByte
 
U64 diagonalAttacks(U64 occ, enumSquare sq) {
   occ &= diagonalMaskEx[sq];
   U32 fold  = (U32)occ | (U32)(occ >> 32);
   U32 occ64 = fold * 0x02020202 >> 26;
   return arrDiagonalAttacks[sq][occ64];
}

A similar approach was proposed by Andrew Fan in 2009, been active in his own engine for a few years (2006 earliest recorded file time) ^[8].

Magic Compression

So far Kindergarten bitboards performs a perfect hashing of the up to six relevant and scattered occupied bits of any line to a six-bit index - which is a bijective mapping of 64 different occupancies per line to 64 indices for the precalculated attack sets.

If we have a closer look to the attack sets, say of a rook on the a-file, we enumerate far less disjoint sets. A rook on a1 (a8) has seven different attack-sets on that file, depending on the occupancy of a2-a7. On a2 (a7) there is even one attack set less, on a3 (a6) 2 times 5 and on a4 (a5) 3 times 4 attack-sets. Thus, there are {7, 6, 10, 12, 12, 10, 6, 7} disjoint attack-sets per square on line, or 70 in total over all eight squares.

While kindergarten bitboards apply a minimal perfect mapping of scattered bits to a six-bit index, the mapping of the attack-sets is surjective, since each of the 64 occupancies maps only up to 12 distinct sets. Of course that is because occupancies "behind" the first blocker are redundant and map the same attack.

Grant Osborne came up with the idea, derived from magic bitboards - to use different "magic" factors per square (rank), where multiplication may produce carries and enough so called constructive collisions to gain only five or even four bit indices and therefor denser tables. Since different squares may have different table sizes (16 or 32 entries), a Java-like array is used for the attacks, in C implemented as array of pointers to the arbitrary sized attack tables. The variable right shift by either 60 or 59 is encoded inside the otherwise redundant upper six bits of the magic factor, as mentioned in incorporating the shift of magic bitboards.

Grant's proposal, so far with {5,4,4,5,5,4,4,5} bit ranges for the lookups per square for vertical rook attacks, results in a 1.5 KByte array instead the 4KByte of the initial Kindergarten file attack getter ^[9] . Whether the effort of the rank-indexed magic-factor plus additional pointer indirection pays off the memory saving is another question, and should be tried inside a concrete chess program with its individual cache- and memory footprint.

U64 aFileAttacks[4*32+4*16]; // 1.5KByte
U64 aPtrFileAttacks[8]; // points to appropriate aFileAttacks
U64 fileMagic[8] = {
   0xEFFFA39DB01B23A3, // 5-bit
   0xF024691A3227FF42, // 4-bit
   0xF2808817CAD6FF0C, // 4-bit see below
   0xED6EDFBE467977D5, // 5-bit
   0xEC87CB0D961EC43A, // 5-bit
   0xF2FF594E14D8801C, // 4-bit
   0xF2FF5D69D4E3E7D6, // 4-bit
   0xEE404B349599FF88  // 5-bit
};
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   unsigned int file = sq &  7;
   unsigned int rank = sq >> 3;
 
   occ =  0x0001010101010100 & (occ >> file);
   occ = (fileMagic[rank] * occ) >> (fileMagic[rank] >> 58);  // four&five bit index
   return *(aPtrFileAttacks[rank] + occ) << file;
}

occupancy (A-File)	product	index 0..15	attack set
o - outer squares don't care x - empty or any piece . - empty b - Blocker - any piece R - Rook	occupancy * 0xF2808817CAD6FF0C	upper nibble in product	1 attacked . not attacked
o x x x b R b o	1. attack-set		. . . . 1 . 1 .
0x0000010101000100	0x3A28F9D5E2FF0C00	3	0x0000000001000100
0x0001010101000100	0x3934F9D5E2FF0C00	3	0x0000000001000100
0x0000000101000100	0x6329EDD5E2FF0C00	6	0x0000000001000100
0x0000010001000100	0x6F51FAC9E2FF0C00	6	0x0000000001000100
0x0001000101000100	0x6235EDD5E2FF0C00	6	0x0000000001000100
0x0001010001000100	0x6E5DFAC9E2FF0C00	6	0x0000000001000100
0x0000000001000100	0x9852EEC9E2FF0C00	9	0x0000000001000100
0x0001000001000100	0x975EEEC9E2FF0C00	9	0x0000000001000100
o x x x b R . o	2. attack set		. . . . 1 . 1 1
0x0000000001000000	0x17CAD6FF0C000000	1	0x0000000001000101
0x0001000001000000	0x16D6D6FF0C000000	1	0x0000000001000101
0x0000010101000000	0xB9A0E20B0C000000	11	0x0000000001000101
0x0001010101000000	0xB8ACE20B0C000000	11	0x0000000001000101
0x0000000101000000	0xE2A1D60B0C000000	14	0x0000000001000101
0x0000010001000000	0xEEC9E2FF0C000000	14	0x0000000001000101
0x0001000101000000	0xE1ADD60B0C000000	14	0x0000000001000101
0x0001010001000000	0xEDD5E2FF0C000000	14	0x0000000001000101
o x x b . R b o	3. attack set		. . . 1 1 . 1 .
0x0001010100000100	0x216A22D6D6FF0C00	2	0x0000000101000100
0x0000010100000100	0x225E22D6D6FF0C00	2	0x0000000101000100
0x0000000100000100	0x4B5F16D6D6FF0C00	4	0x0000000101000100
0x0001000100000100	0x4A6B16D6D6FF0C00	4	0x0000000101000100
o x x b . R . o	4. attack set		. . . 1 1 . 1 1
0x0000010100000000	0xA1D60B0C00000000	10	0x0000000101000101
0x0001010100000000	0xA0E20B0C00000000	10	0x0000000101000101
0x0000000100000000	0xCAD6FF0C00000000	12	0x0000000101000101
0x0001000100000000	0xC9E2FF0C00000000	12	0x0000000101000101
o x b . . R b o	5. attack set		. . 1 1 1 . 1 .
0x0000010000000100	0x578723CAD6FF0C00	5	0x0000010101000100
0x0001010000000100	0x569323CAD6FF0C00	5	0x0000010101000100
o x b . . R . o	6. attack set		. . 1 1 1 . 1 1
0x0000010000000000	0xD6FF0C0000000000	13	0x0000010101000101
0x0001010000000000	0xD60B0C0000000000	13	0x0000010101000101
o b . . . R b o	7. attack set		. 1 1 1 1 . 1 .
0x0001000000000100	0x7F9417CAD6FF0C00	7	0x0001010101000100
o b . . . R . o	8. attack set		. 1 1 1 1 . 1 1
0x0001000000000000	0xFF0C000000000000	15	0x0001010101000101
o . . . . R b o	9. attack set		1 1 1 1 1 . 1 .
0x0000000000000100	0x808817CAD6FF0C00	8	0x0101010101000100
o . . . . R . o	10. attack set, no blocker		1 1 1 1 1 . 1 1
0x0000000000000000	0x0000000000000000	0	0x0101010101000101

The table demonstrates how it works for file-attack of the a3 rook with a four bit range only five relevant occupied bits, since a3 is member of the inner six bits. The empirical determined factor is 0xF2808817CAD6FF0C, six upper bits contain the right shift for the product, for this square shift 60:
occupancy (A-File) product index 0..15 attack set o - outer squares don't care x - empty or any piece . - empty b - Blocker - any piece R - Rook occupancy * 0xF2808817CAD6FF0C upper nibble in product 1 attacked . not attacked o x x x b R b o 1. attack-set . . . . 1 . 1 . 0x0000010101000100 0x3A28F9D5E2FF0C00 3 0x0000000001000100 0x0001010101000100 0x3934F9D5E2FF0C00 3 0x0000000001000100 0x0000000101000100 0x6329EDD5E2FF0C00 6 0x0000000001000100 0x0000010001000100 0x6F51FAC9E2FF0C00 6 0x0000000001000100 0x0001000101000100 0x6235EDD5E2FF0C00 6 0x0000000001000100 0x0001010001000100 0x6E5DFAC9E2FF0C00 6 0x0000000001000100 0x0000000001000100 0x9852EEC9E2FF0C00 9 0x0000000001000100 0x0001000001000100 0x975EEEC9E2FF0C00 9 0x0000000001000100 o x x x b R . o 2. attack set . . . . 1 . 1 1 0x0000000001000000 0x17CAD6FF0C000000 1 0x0000000001000101 0x0001000001000000 0x16D6D6FF0C000000 1 0x0000000001000101 0x0000010101000000 0xB9A0E20B0C000000 11 0x0000000001000101 0x0001010101000000 0xB8ACE20B0C000000 11 0x0000000001000101 0x0000000101000000 0xE2A1D60B0C000000 14 0x0000000001000101 0x0000010001000000 0xEEC9E2FF0C000000 14 0x0000000001000101 0x0001000101000000 0xE1ADD60B0C000000 14 0x0000000001000101 0x0001010001000000 0xEDD5E2FF0C000000 14 0x0000000001000101 o x x b . R b o 3. attack set . . . 1 1 . 1 . 0x0001010100000100 0x216A22D6D6FF0C00 2 0x0000000101000100 0x0000010100000100 0x225E22D6D6FF0C00 2 0x0000000101000100 0x0000000100000100 0x4B5F16D6D6FF0C00 4 0x0000000101000100 0x0001000100000100 0x4A6B16D6D6FF0C00 4 0x0000000101000100 o x x b . R . o 4. attack set . . . 1 1 . 1 1 0x0000010100000000 0xA1D60B0C00000000 10 0x0000000101000101 0x0001010100000000 0xA0E20B0C00000000 10 0x0000000101000101 0x0000000100000000 0xCAD6FF0C00000000 12 0x0000000101000101 0x0001000100000000 0xC9E2FF0C00000000 12 0x0000000101000101 o x b . . R b o 5. attack set . . 1 1 1 . 1 . 0x0000010000000100 0x578723CAD6FF0C00 5 0x0000010101000100 0x0001010000000100 0x569323CAD6FF0C00 5 0x0000010101000100 o x b . . R . o 6. attack set . . 1 1 1 . 1 1 0x0000010000000000 0xD6FF0C0000000000 13 0x0000010101000101 0x0001010000000000 0xD60B0C0000000000 13 0x0000010101000101 o b . . . R b o 7. attack set . 1 1 1 1 . 1 . 0x0001000000000100 0x7F9417CAD6FF0C00 7 0x0001010101000100 o b . . . R . o 8. attack set . 1 1 1 1 . 1 1 0x0001000000000000 0xFF0C000000000000 15 0x0001010101000101 o . . . . R b o 9. attack set 1 1 1 1 1 . 1 . 0x0000000000000100 0x808817CAD6FF0C00 8 0x0101010101000100 o . . . . R . o 10. attack set, no blocker 1 1 1 1 1 . 1 1 0x0000000000000000 0x0000000000000000 0 0x0101010101000101

Forum Posts

Re: Rotated bitboards by Urban Koistinen, rgcc, October 31, 1997 » Collapsed files, Collapsed ranks
rotated bitboards obsolete? by Gerd Isenberg, CCC, February 26, 2006
Re: Some thoughts on Dann Corbit's rotated alternative by Steffan Westcott, CCC, March 03, 2006
Compact Bitboard Attacks by Tom Likens, Winboard Forum, March 14, 2006
Zach's tricky 32-bit approach by Zach Wegner, Winboard Forum, August 22, 2006
Magic Bitboards Explained! by Michael Sherwin, Winboard Forum, December 04, 2006
Kindergarten Bitboard Approach by Gerd Isenberg by Edsel Apostol, CCC, November 05, 2008 » OliThink
Kindergarten bitboards without multiplying by Piotr Cichy, CCC, August 07, 2009
Kindergarten Bitboard help by Gregory Strong, CCC, November 22, 2009
32-bit Magic experiments by Andrew Fan, Winboard Forum, December 03, 2009 » Magic Bitboards
Kindergarten bitboards and Xiangqi move genaration? by Han Chengye, CCC, December 30, 2009 » Chinese Chess

External Links

Kindergarten from Wikipedia
George Benson - This Masquerade, 1976, YouTube Video
Pat Metheny and friends - This Masquerade, Jazz Baltica, July 6, 2003, YouTube Video
Nils Landgren, Lars Danielsson, Wolfgang Haffner, Esbjörn Svensson, Pat Metheny, Michael Brecker

References

^ Magic Bitboards Explained! by Michael Sherwin and reply by Gerd Isenberg to call it Kindergarten Bitboards, Winboard Forum, December 4, 2006
^ Compact Bitboard Attacks by Tom Likens, Winboard Forum, March 14, 2006
^ rotated bitboards obsolete? by Gerd Isenberg, CCC, February 26, 2006
^ Re: Some thoughts on Dann Corbit's rotated alternative by Steffan Westcott, CCC, March 03, 2006
^ IMAGINE - The Israel Museum's searchable collections database
^ Kindergarten bitboards without multiplying by Piotr Cichy, CCC, August 07, 2009
^ Zach's tricky 32-bit approach by Zach Wegner, Winboard Forum, August 22, 2006
^ 32-bit Magic experiments by Andrew Fan, Winboard Forum, December 03, 2009
^ Re: How to reduce the "bits" used in a magic number by Grant Osborne, CCC, July 04, 2008

What links here?

Page	Date Edited
More Links
Andreas Guettinger	Aug 14, 2013
Andrew Fan	Jul 30, 2017
Array	Dec 1, 2016
Bitboard Serialization	Dec 24, 2014
BMI2	Mar 6, 2018
Chinese Chess	Jan 16, 2018
Chiron	Sep 24, 2017
Congruent Modulo Bitboards	Jun 26, 2013
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Exploding Bitboards	Mar 9, 2015
Firefly	Oct 23, 2017
First Rank Attacks	Aug 28, 2010
Flipping Mirroring and Rotating	Oct 14, 2016
General Setwise Operations	Feb 25, 2018
Grant Osborne	Dec 2, 2011
Gregory Strong	Apr 24, 2017
Hash Table	Jan 1, 2018
Hashing Dictionaries	Mar 1, 2014
Hiding the Implementation	Feb 3, 2011
Hyperbola Quintessence	Mar 25, 2017
Jazz	Oct 4, 2017
Kindergarten Bitboards	Aug 1, 2017
Kurt	Apr 20, 2014
Magic Bitboards	Apr 13, 2018
Mark Levene	Jun 2, 2015
Occupancy of any Line	Sep 16, 2016
OliThink	May 19, 2017
Protector	Oct 12, 2017
Rodent	Jan 11, 2018
Rotated Bitboards	Mar 7, 2017
SIMD techniques	Nov 26, 2017
Simplex	Mar 6, 2016
Sjaak (Glebbeek)	Oct 4, 2017
Sliding Piece Attacks	May 27, 2016
Space-Time Tradeoff	Jun 17, 2015
Sungorus	Apr 11, 2014
Tigran	Aug 16, 2015
Tom Likens	Mar 7, 2017
Trevor Fenner	Jun 2, 2015
Vajolet	Jan 25, 2018

Up one Level

King Pattern

GerdIsenberg — Fri, 15 Nov 2013 17:23:35 GMT

Home * Board Representation * Bitboards * King Pattern

		King pattern are about king attacks, some king safety issues and pawn endgame related stuff. There is exactly one king per side - the whole game. Not a big issue, but even if white and black kings are member of the standard bitboard definition one may avoid bitscanning whole the time. Even without explicit piece-lists , one may consider to keep the redundant king-squares incrementally updated during make/unmake.
Moore neighborhood ^[1]

Vulnerable on distant Checks

Branchless

SSE4

King and Pawns

Set-wise Rule of the Square

Flood Fill Algorithms

King Attacks

The King attacks all squares in Moore neighborhood, that is squares with a Chebyshev distance of one.

by Lookup

Likely we have a the square-index handy, to access a table of precalculated king-attacks.

U64 arrKingAttacks[64];
 
U64 kingAttacks(enumSquare sq) {return arrKingAttacks[sq];}

For instance a king on g2:

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . 1 1 1
. . . . . 1 . 1
. . . . . 1 1 1

by Calculation

To calculate all eight directions, one can actually do some simple parallel prefix stuff. Rather than to do a union of all eight direction-steps, one first applies the horizontal attacks considering file-wraps. Those up to two bits are then shifted up and down, together with the king-bitboard itself, to get all the other direction bits:

U64 kingAttacks(U64 kingSet) {
   U64 attacks = eastOne(kingSet) | westOne(kingSet);
   kingSet    |= attacks;
   attacks    |= nortOne(kingSet) | soutOne(kingSet);
   return attacks;
}

The routine is handy to initialize the kingAttacks arrays:

U64 sqBB = 1;
for (int sq = 0; sq < 64; sq++, sqBB <<= 1)
   arrKingAttacks[sq] = kingAttacks(sqBB);

It must not necessarily called with single-populated bitboards, and is base of king path fill algorithms.

King Safety

King Safety is an important evaluation topic. Some bitboard pattern are about to recognize king safety related features. To evaluate those features is a complete other story.

Pawn-Shield Pattern

During the middlegame, the king is encouraged to hide behind own pawn shields. Beside Considering open and half-open files on king's and adjacent files, one idea is to mask potential pawn shield pattern per wing of the king file - and to hash it to an appropriate index range to access tables with precalculated stuff. This mask might be used for kings on f1-h1 or f1-h2:

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . 1 1 1
. . . . . 1 1 1
. . . . . . . .

Vulnerable on distant Checks

Assuming we are aware of all taboo squares of the king. That is the union of own pieces with all opposite attacks, then we can simply calculate a move target set by relative complement of the king attacks.

moveTargets = arrKingAttacks[sq] & ~taboo;

If moveTargets is empty - the king has no move. The king might be vulnerable on distant checks from any sliding piece direction, due to lack of any escape. Otherwise, the king might be vulnerable on distant checks, if escape squares are on one line only - either rank, file, diagonal or anti-diagonal:

if ( moveTargets == 0 )
{
   dirSet = 15; // vulnerable on all lines
}
else
{
   dirSet = 0;
   pattern = moveTargets | sqBBofKing;
   if ( pattern & rankBits[sq] == pattern )
      dirSet =  1; // vulnerable on rank, e.g. base rank
   else if ( pattern & fileBits[sq] == pattern )
      dirSet =  2; // vulnerable on file
   else if ( pattern & diagBits[sq] == pattern )
      dirSet =  4; // vulnerable on diagonal
   else if ( pattern & antiBits[sq] == pattern )
      dirSet =  8; // vulnerable on antidiagonal
}

Branchless

Branchless in C - since boolean compare result is treated 0 or 1 arithmetically:

pattern = moveTargets | sqBBofKing;
dirSet  = ( pattern & rankBits[sq] == pattern ) * 1;
dirSet += ( pattern & fileBits[sq] == pattern ) * 2;
dirSet += ( pattern & diagBits[sq] == pattern ) * 4;
dirSet += ( pattern & antiBits[sq] == pattern ) * 8;

to possibly test later

if ( dirSet ) evaluate and look for possible distant mates

SSE4

Using the SSE4.1 PCMPEQQ Quadword compare for equality instruction via _mm_cmpeq_epi64 intrinsic, following otherwise SSE2 approach might be applied:

struct SKingBits {
    U64 rankBits;
    U64 fileBits;
    U64 diagBits;
    U64 antiBits;
} XMM_ALIGN kingBits[64];
 
int dirSet(U64 pattern, int sq)
{
   static const U64 XMM_ALIGN weights[4] = {
     C64(0x0000000000000001),
     C64(0x0000000000000002),
     C64(0x0000000000000004),
     C64(0x0000000000000008)
   };
   __m128i x0, x1, x2;
   const __m128i* pKB = (__m128i*)(kingBits + sq);
   const __m128i* pW  = (__m128i*) weights;
   x2 = _mm_cvtsi64x_si128 (pattern);
   x2 = _mm_unpacklo_epi64 (x2, x2);
   x0 = _mm_and_si128   (x2, pKB[0]);
   x1 = _mm_and_si128   (x2, pKB[1]);
   x0 = _mm_cmpeq_epi64 (x0, x2);
   x1 = _mm_cmpeq_epi64 (x1, x2);
   x0 = _mm_and_si128   (x0, pW[0]);
   x1 = _mm_and_si128   (x1, pW[1]);
   x0 = _mm_or_si128    (x0, x1);
   x1 = _mm_unpackhi_epi64 (x0, x0);
   x0 = _mm_or_si128    (x0, x1);
   return _mm_cvtsi128_si32(x0);
}

King and Pawns

Some pawn endgame issues. A set-wise rule of the square from king's point of view. Or does a king have a connected path along safe and empty squares to a certain square?

Set-wise Rule of the Square

Assuming a black-king on g5 - white to move. What is the set of squares, where a king can never catch a white passer? Or the inverse, where can passers might be caught, considering the rule of the square? In this inverse case, where passers may be close enough, there are other aspects to consider like two distant passers, or passer supported by own king - here it is only about races between passers and opponent king. It is about a set-wise view, where the distance to promotion is greater or equal than the distance of the king. We need to consider double pushes from the initial rank though.

black king on g5    white passers         double pawn push, need
wtm                 possibly caught       to copy 3rd to 2nd rank
. . . . . . . .      . . . . . . . .      . . . . . . . .
. . . . . . . .      . . . . . . . .      . . . . . . . .
. . . . . . . .      . . . . . . . .      . . . . . . . .
. . . . . . K .      . . . 1 1 1 K 1      . . . 1 1 1 K 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 1 1 1 1 1 1      1 1 1 1 1 1 1 1

Of course we may even mask off the base ranks since pawns can not exist there - but since we intersect with passers anyway, it don't cares.

We need to consider tempo, if black to move, the area of caught grows accordantly:

black king on g5    white passers
btm                 possibly caught
. . . . . . . .      . . . . . . . .
. . . . . . . .      . . . . . . . .
. . . . . K K K      . . . 1 1 1 1 1
. . . . . K K K      . . 1 1 1 1 K 1
. . . . . K K K      . 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

We can now pre-initialize an array of caught pawn area for each king square, for both black and white king as well as side to move:

U64 arrCaughtableArea[2][2][64];  // [color of king][side to move][square]
 
unCaughtable = whitePassers & ~arrCaughtableArea[black][white][squareOfBlackKing];

How can the array be initialized, how can we calculate it? That is already some special fill approach. For the mentioned black king, wtm case, we use the rank-distance of the black king to the 8th rank.

distance = rank(kingSquare) ^ 7; // 7 - rank
 
. . . . 3 . . .
. . . . 2 . . .
. . . . 1 . . .
. . . . K . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

One solution is first expand the king-set distance (3) times, in east and west direction along the rank:

caughtable = kingBB;
for (i = 0; i < distance; i++)
   caughtable |= westOne(caughtable) | eastOne(caughtable);
 
. . . . . . . .     . . . . . . . .      . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .
. . . . . 1 1 1     . . . . 1 1 1 1      . . . 1 1 1 1 1
. . . . . . . .     . . . . . . . .      . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .

Now it is about filling south-west and south-east rank(kingSquare) times, which finally results in the desired set of catchable passers. Special handling is required for the doubles pushes ^[2]:

for (i = 0; i < rank(kingSquare)-2; i++)
   caughtable |= soutOne(westOne(caughtable) | caughtable | eastOne(caughtable) );
caughtable |= soutOne(caughtable) | 0xff;
 
. . . . . . . .     . . . . . . . .      . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .
. . . . . . . .     . . . . . . . .      . . . . . . . .
. . . 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 1 1 1
. . . . . . . .     . . . . . . . .   |  . 1 1 1 1 1 1 1
. . . . . . . .     . . . . . . . .   v  1 1 1 1 1 1 1 1

To initialize black to move and white king arrays should not that difficult either - and is left to the ambitious reader.

Flood Fill Algorithms

Answering questions like can a king on a1 reach h8 along this path?

. . . . . . 1 T
. . 1 1 1 1 . .
. 1 . . . . . .
. . 1 1 1 1 . .
. . . . . . 1 .
. . . . . . . 1
. . . . . . 1 .
F 1 1 1 1 1 . .

The squaresAreConnected flood-fill ^[3] algorithm was introduced by Steffan Westcott ^[4].

A flood fill algorithm, like the one below, starting at the "from" square and stopping if the fill hits the to" square or the fill can't make any more progress. The fill progresses in all directions at once, so should return an answer within a few iterations. Each iteration is pretty fast too, as it just a bunch of shifting and logic operations. And no lookup tables either.

/////////////////////////////////////////////////////////////////////////
//
// Returns true if a path of set bits in 'path' exists that 8-way connect
// any set bit in sq1 to any set bit of sq2
 
bool squaresAreConnected(U64 sq1, U64 sq2, U64 path)
{
   // With bitboard sq1, do an 8-way flood fill, masking off bits not in
   // path at every step. Stop when fill reaches any set bit in sq2, or
   // fill cannot progress any further
 
   if (!(sq1 &= path) || !(sq2 &= path)) return false;
                      // Drop bits not in path
                      // Early exit if sq1 or sq2 not on any path
 
   while(!(sq1 & sq2))
   {
      U64 temp = sq1;
      sq1 |= eastOne(sq1) | westOne(sq1);    // Set all 8 neighbours
      sq1 |= soutOne(sq1) | nortOne(sq1);
      sq1 &= path;                           // Drop bits not in path
      if (sq1 == temp) return false;         // Fill has stopped
   }
   return true;                              // Found a good path
}

External Links

Checkmate pattern from Wikipedia
King's Pattern Flatware - Spoons/Teaspoon
Amon Düül II - Archangel Thunderbird (1971), YouTube Video ^[5]

References

^ Moore neighborhood from Wikipedia
^ Thanks to Thomas Herges for pointing out a bug if kings are on the eighth rank
^ Flood Fill from Wikipedia
^ Re: algorithm question answer by Steffan Westcott in CCC September 09, 2002
^ Male and Female - 1919 American silent adventure/drama film - Wikipedia

What links here?

Page	Date Edited
Algorithms	May 5, 2017
All Shortest Paths	Jan 21, 2014
Bitboards	Nov 14, 2017
Blockage Detection	Oct 19, 2017
Blockers and Beyond	Mar 21, 2014
Chunking	Jun 12, 2017
Daniel Shawul	Jan 28, 2018
Demolito	Mar 1, 2018
DirGolem	Jun 5, 2016
Evaluation Patterns	Jun 24, 2013
Fill Algorithms	Nov 6, 2013
Helmut Horacek	Oct 31, 2016
Hex	Dec 29, 2017
Iteration	May 5, 2017
King	Feb 26, 2013
King Pattern	Nov 15, 2013
King Safety	Feb 14, 2018
KPK	May 12, 2016
Mate at a Glance	Sep 24, 2014
Morph	Dec 7, 2017
Nirvanachess	Sep 30, 2017
Passed Pawn	Oct 11, 2017
Passed Pawns (Bitboards)	Aug 23, 2010
Pattern Recognition	Sep 8, 2017
Pawn Endgame	Oct 11, 2017
Pawn Race	Dec 16, 2017
PawnKing	Sep 5, 2014
Pieces versus Directions	Oct 6, 2016
Rule of the Square	Sep 6, 2014
Searcher	Sep 26, 2016
Sliding Pieces	Aug 3, 2017
Square Attacked By	Jan 20, 2018
Squares	Feb 15, 2015
SSE4	Jun 5, 2016
Steffan Westcott	Jan 21, 2014
Unstoppable Passer	Jun 21, 2016

Up one Level

Knight Pattern

GerdIsenberg — Mon, 23 Feb 2015 19:45:51 GMT

Home * Board Representation * Bitboards * Knight Pattern

		Knight Pattern with Bitboards covers knight attacks of single or multiple knights, either by indexed pre-calculated tables or direct bitboard calculation, and the set wise determination of Knight fork target squares.
M. C. Escher, Horseman ^[1]

Knight Attacks

by Lookup

by Calculation

Multiple Knight Attacks

Knight Fill

Knight Forks

See also

Selected Publications

Knight Attacks

The Knight attacks the target squares independently from other pieces around. The compass rose of all eight attacking directions associated with the to - from square differences from an 8x8 board:

        noNoWe    noNoEa
            +15  +17
             |     |
noWeWe  +6 __|     |__+10  noEaEa
              \   /
               >0<
           __ /   \ __
soWeWe -10   |     |   -6  soEaEa
             |     |
            -17  -15
        soSoWe    soSoEa

by Lookup

The knight is specified by square index, likely from a bitscan of a piece-wise bitboard serialization of a knight bitboard from a standard board-definition, to index a table of pre-calculated knight-attacks:

U64 arrKnightAttacks[64];
 
U64 knightAttacks(enumSquare sq) {return arrKnightAttacks[sq];}

For instance a knight on d4

arrKnightAttacks[d4]
 . . . . . . . .
 . . . . . . . .
 . . 1 . 1 . . .
 . 1 . . . 1 . .
 . . . . . . . .
 . 1 . . . 1 . .
 . . 1 . 1 . . .
 . . . . . . . .

by Calculation

Similar to one step only of the four orthogonal and four diagonal directions,each of the eight knight directions is calculated by left or right shift with appropriate pre- or post shift mask, to avoid A- H-file wraps or vice versa. See also AVX2 Knight Attacks.

U64 noNoEa(U64 b) {return (b << 17) & notAFile ;}
U64 noEaEa(U64 b) {return (b << 10) & notABFile;}
U64 soEaEa(U64 b) {return (b >>  6) & notABFile;}
U64 soSoEa(U64 b) {return (b >> 15) & notAFile ;}
U64 noNoWe(U64 b) {return (b << 15) & notHFile ;}
U64 noWeWe(U64 b) {return (b <<  6) & notGHFile;}
U64 soWeWe(U64 b) {return (b >> 10) & notGHFile;}
U64 soSoWe(U64 b) {return (b >> 17) & notHFile ;}
 
U64 noNoEa(U64 b) {return (b & notHFile ) << 17;}
U64 noEaEa(U64 b) {return (b & notGHFile) << 10;}
U64 soEaEa(U64 b) {return (b & notGHFile) >>  6;}
U64 soSoEa(U64 b) {return (b & notHFile ) >> 15;}
U64 noNoWe(U64 b) {return (b & notAFile ) << 15;}
U64 noWeWe(U64 b) {return (b & notABFile) <<  6;}
U64 soWeWe(U64 b) {return (b & notABFile) >> 10;}
U64 soSoWe(U64 b) {return (b & notAFile ) >> 17;}

In almost the same manner as the three pawn directions, there is a unique source-target relationship. The difference is - we have up to eight pawns, but likely not more than two knights per side. Keeping eight disjoint knight directions is consistent to direction-wise fill approaches of other pieces with unique target-source relationship - but disjoint direction-wise knight targets are sparse populated and usually contain only up to two bits.

Multiple Knight Attacks

To initialize the KnightAttacks array one may use a routine with some kind of parallel prefix calculations, rather than the union of all eight directions:

U64 knightAttacks(U64 knights) {
   U64 west, east, attacks;
   east     = eastOne (knights);
   west     = westOne (knights);
   attacks  = (east|west) << 16;
   attacks |= (east|west) >> 16;
   east     = eastOne (east);
   west     = westOne (west);
   attacks |= (east|west) <<  8;
   attacks |= (east|west) >>  8;
   return attacks;
}

or to possibly gain some more parallelism:

U64 knightAttacks(U64 knights) {
   U64 l1 = (knights >> 1) & C64(0x7f7f7f7f7f7f7f7f);
   U64 l2 = (knights >> 2) & C64(0x3f3f3f3f3f3f3f3f);
   U64 r1 = (knights << 1) & C64(0xfefefefefefefefe);
   U64 r2 = (knights << 2) & C64(0xfcfcfcfcfcfcfcfc);
   U64 h1 = l1 | r1;
   U64 h2 = l2 | r2;
   return (h1<<16) | (h1>>16) | (h2<<8) | (h2>>8);
}

If we pass multiple knights set-wise, attacks of some squares may be caused by different knights. Feeding back (safe) target sets, the routine may used to get sets of squares, knights may reach in two or more moves. For instance in late pawn-knight endings whether a knight may catch a passer.

Knight Fill

A fill cycle for a fill algorithm is the union of the attack set with the knights itself:

U64 knightFill(U64 knights) {return knightAttacks(knights) | knights;}

for instance applied six times on the otherwise empty board:

                  1. Fill            2. Fill            3. Fill
. . . . . . . .   . . . . . . . .   . . . . . . . .   . . . . . . . .
. . . . . . . .   . . . . . . . .   . . . . . . . .   . 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 1 1 1 1 . .
 
                  4. Fill            5. Fill            6. Fill
                  . 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 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 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 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 1 1 1 1

Knight Forks

A common knight pattern is the knight fork. Targets are heavy pieces - king, queen and rooks, hanging pieces, or even undefended pawns. A royal knight fork or "family" check, winning the queen is most important. Otherwise one may loop over all possible pieces, to get the knight-attacks by lookup and to intersect all combinations of attack-squares. A loop- and branch-less solution to get potential fork-attack squares is to union all intersections of all direction attacks, as explained in greater one sets:

U64 forkTargetSquare(U64 targets) {
   U64 west, east, attak, forks;
   east   = eastOne (targets);
   west   = westOne (targets);
   attak  =  east << 16;
   forks  = (west << 16) & attak;
   attak |=  west << 16;
   forks |= (east >> 16) & attak;
   attak |=  east >> 16;
   forks |= (west >> 16) & attak;
   attak |=  west >> 16;
   east   = eastOne (east);
   west   = westOne (west);
   forks |= (east <<  8) & attak;
   attak |=  east <<  8;
   forks |= (west <<  8) & attak;
   attak |=  west <<  8;
   forks |= (east >>  8) & attak;
   attak |=  east >>  8;
   forks |= (west >>  8) & attak;
   return forks;
}

The intersection of those targets with squares not occupied by own pieces or attacked by opponent pawns and knights, but attacked by own knight(s) leaves a move target set with some forced properties.

Selected Publications

Martin Gardner (1967). Problems that are Built on the Knight's Tour in Chess. Scientific American, Vol. 130
Noam D. Elkies, Richard P. Stanley (2003). The Mathematical Knight. The Mathematical Intelligencer, Vol. 25, No. 1, pdf
Ben Hill (2004). Knight’s Tours. pdf
Philip Hingston, Graham Kendall (2005). Ant Colonies Discover Knight's Tours. AI 2004, Lecture Notes in Computer Science 3339
Philip Hingston, Graham Kendall (2005). Enumerating knight's tours using an ant colony algorithm. CEC 2005

Forum Posts

Symbolic: From bitboards to ideas by Steven Edwards, CCC, March 13, 2004 » Symbolic
knight's multiple atacks by Daniel Anulliero, CCC, January 27, 2015

External Links

Knight's tour from Wikipedia
Knight's Tour Notes compiled by George Jelliss
Knight's Tour - from Wolfram MathWorld
Longest uncrossed knight's path from Wikipedia
László Lindner's knight wheel by Frederic Friedel from ChessBase Puzzle
Knight's Tour from Research Reflections by Graham Kendall, January 18, 2014
Knight's Tour - Numberphile, YouTube Video

References

^ View facsimile print from M.C. Escher - 16 Facsimile Prints

What links here?

Page	Date Edited
AVX2	Aug 8, 2017
Bitboards	Nov 14, 2017
Blockers and Beyond	Mar 21, 2014
Chunking	Jun 12, 2017
Combination	Oct 25, 2016
Decoying	Jan 12, 2015
DirGolem	Jun 5, 2016
Double Attack	Oct 22, 2014
Fill Algorithms	Nov 6, 2013
General Setwise Operations	Feb 25, 2018
Graham Kendall	May 26, 2015
Hanging Piece	Jan 14, 2017
Jonathan Warkentin	Jun 29, 2014
Killer (NL)	Dec 15, 2017
Knight Pattern	Feb 23, 2015
Knight-Distance	Oct 20, 2013
Knowledge	Jul 22, 2017
Loose Piece	Jan 10, 2015
Mathematician	Apr 9, 2018
Pattern Recognition	Sep 8, 2017
Pieces versus Directions	Oct 6, 2016
Square Attacked By	Jan 20, 2018
Symbolic	May 8, 2017
Tactics	Jan 12, 2018
Zillions of Games	May 29, 2017

Up one Level

Kogge-Stone Algorithm

GerdIsenberg — Sat, 17 Sep 2016 21:52:19 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Kogge-Stone Algorithm

		The Kogge-Stone Algorithm for set-wise sliding piece attack generation was first introduced by Steffan Westcott in CCC ^[1] . It is a parallel prefix approach of a occluded dumb7 flood-fill, propagating sliding piece attacks like carries of a Kogge-Stone hardware adder ^[2] in software. One needs to pass sliding pieces as generator set "g" and the set of empty squares as propagator set "p". For appropriate attacks we need to shift the occluded fill one step further, considering wraps.
4-bit Kogge-Stone adder ^[3]

Parallel Prefix

Direction-wise Fill

Fill on an empty Board

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

Parallel Prefix

The routine fillUpOccluded() smears the set bits of bitboard g upwards, but only along set bits of p; a reset bit in p is enough to halt a smear. Other routines have a similar effect.

U64 fillUpOccluded(U64 g, U64 p) {
   g |= p & (g <<  8);
   p &=     (p <<  8);
   g |= p & (g << 16);
   p &=     (p << 16);
   g |= p & (g << 32);
   return g;
}

The method chosen in FillUpOccluded() is based on a Kogge-Stone parallel prefix network, because it can be implemented very easily in software. The diagram below (trust me, it really _is_ supposed to look like that) is an illustration of how it works. The corresponding lines of program code are shown on the right. The inputs are fed into the network at the top, pass along the connecting lines, are combined by the # operator at various points, and the outputs appear at the bottom.

x1 x2 x3 x4 x5 x6 x7 x8         Input : g, p
|  |  |  |  |  |  |  |
V  V  V  V  V  V  V  V
|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |
|\ |\ |\ |\ |\ |\ |\ |
| \| \| \| \| \| \| \|
|  #  #  #  #  #  #  #          g |= p & (g <<  8);
|  |  |  |  |  |  |  |          p &=     (p <<  8);
|\ |\ |\ |\ |\ |\ |  |
| \: \: \: \: \: \:  |
|  \  \  \  \  \  \  |
|  :\ :\ :\ :\ :\ :\ |
|  | \| \| \| \| \| \|
|  |  #  #  #  #  #  #          g |= p & (g << 16);
|  |  |  |  |  |  |  |          p &=     (p << 16);
|\ |\ |\ |\ |  |  |  |
| \: \: \: \:  |  |  |
|  \  \  \  \  |  |  |
|  :\ :\ :\ :\ |  |  |
|  | \: \: \: \:  |  |
|  |  \  \  \  \  |  |
|  |  :\ :\ :\ :\ |  |
|  |  | \: \: \: \:  |
|  |  |  \  \  \  \  |
|  |  |  ;\ ;\ :\ :\ |
|  |  |  | \| \| \| \|
|  |  |  |  #  #  #  #          g |= p & (g << 32);
|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |
V  V  V  V  V  V  V  V
q1 q2 q3 q4 q5 q6 q7 q8         Output : g

Direction-wise Fill

We further rely on the compass rose to identify ray-directions.

  noWe         nort         noEa
          +7    +8    +9
              \  |  /
  west    -1 <-  0 -> +1    east
              /  |  \
          -9    -8    -7
  soWe         sout         soEa

Assuming little-endian file mapping. Big-endian file mapping has to swap A and H and east and west. As a reminder - shifting bitboards - the base of further stuff.

Fill on an empty Board

We already used the south- and north- parallel prefix fill-routines while calculating pawn spans. We need one additional direction step for ray-attacks on the otherwise empty board to exclude sliders. Convenient to initialize ray-attacks arrays of single sliders. We may conduct those routines from the general occluded fills by passing the universal propagator set. The vertical fills already look familiar.

U64 soutFill(U64 gen) {
   gen |= (gen >>  8);
   gen |= (gen >> 16);
   gen |= (gen >> 32);
   return gen;
}
 
U64 nortFill(U64 gen) {
   gen |= (gen <<  8);
   gen |= (gen << 16);
   gen |= (gen << 32);
   return gen;
}

Using explicit propagators as compile time constants to manage the A-, H-file-wraps.

U64 eastFill(U64 gen) {
   const U64 pr0 = notAFile;
   const U64 pr1 = pr0 & (pr0 << 1);
   const U64 pr2 = pr1 & (pr1 << 2);
   gen |= pr0 & (gen  << 1);
   gen |= pr1 & (gen  << 2);
   gen |= pr2 & (gen  << 4);
   return gen;
}
 
U64 noEaFill(U64 gen) {
   const U64 pr0 = notAFile;
   const U64 pr1 = pr0 & (pr0 <<  9);
   const U64 pr2 = pr1 & (pr1 << 18);
   gen |= pr0 & (gen <<  9);
   gen |= pr1 & (gen << 18);
   gen |= pr2 & (gen << 36);
   return gen;
}
 
U64 soEaFill(U64 gen) {
   const U64 pr0 = notAFile;
   const U64 pr1 = pr0 & (pr0 >>  7);
   const U64 pr2 = pr1 & (pr1 >> 14);
   gen |= pr0 & (gen >>  7);
   gen |= pr1 & (gen >> 14);
   gen |= pr2 & (gen >> 28);
   return gen;
}
 
U64 westFill(U64 gen) {
   const U64 pr0 = notHFile;
   const U64 pr1 = pr0 & (pr0 >> 1);
   const U64 pr2 = pr1 & (pr1 >> 2);
   gen |= pr0 & (gen >> 1);
   gen |= pr1 & (gen >> 2);
   gen |= pr2 & (gen >> 4);
   return gen;
}
 
U64 soWeFill(U64 gen) {
   const U64 pr0 = notHFile;
   const U64 pr1 = pr0 & (pr0 >>  9);
   const U64 pr2 = pr1 & (pr1 >> 18);
   gen |= pr0 & (gen >>  9);
   gen |= pr1 & (gen >> 18);
   gen |= pr2 & (gen >> 36);
   return gen;
}
 
U64 noWeFill(U64 gen) {
   const U64 pr0 = notHFile;
   const U64 pr1 = pr0 & (pr0 <<  7);
   const U64 pr2 = pr1 & (pr1 << 14);
   gen |= pr0 & (gen <<  7);
   gen |= pr1 & (gen << 14);
   gen |= pr2 & (gen << 28);
   return gen;
}

Occluded Fill

Occluded fills include sliders, but exclude blockers ^[4].

U64 soutOccl(U64 gen, U64 pro) {
   gen |= pro & (gen >>  8);
   pro &=       (pro >>  8);
   gen |= pro & (gen >> 16);
   pro &=       (pro >> 16);
   gen |= pro & (gen >> 32);
   return gen;
}
 
U64 nortOccl(U64 gen, U64 pro) {
   gen |= pro & (gen <<  8);
   pro &=       (pro <<  8);
   gen |= pro & (gen << 16);
   pro &=       (pro << 16);
   gen |= pro & (gen << 32);
   return gen;
}
 
U64 eastOccl(U64 gen, U64 pro) {
   pro &= notAFile;
   gen |= pro & (gen << 1);
   pro &=       (pro << 1);
   gen |= pro & (gen << 2);
   pro &=       (pro << 2);
   gen |= pro & (gen << 4);
   return gen;
}
 
U64 noEaOccl(U64 gen, U64 pro) {
   pro &= notAFile;
   gen |= pro & (gen <<  9);
   pro &=       (pro <<  9);
   gen |= pro & (gen << 18);
   pro &=       (pro << 18);
   gen |= pro & (gen << 36);
   return gen;
}
 
U64 soEaOccl(U64 gen, U64 pro) {
   pro &= notAFile;
   gen |= pro & (gen >>  7);
   pro &=       (pro >>  7);
   gen |= pro & (gen >> 14);
   pro &=       (pro >> 14);
   gen |= pro & (gen >> 28);
   return gen;
}
 
U64 westOccl(U64 gen, U64 pro) {
   pro &= notHFile;
   gen |= pro & (gen >> 1);
   pro &=       (pro >> 1);
   gen |= pro & (gen >> 2);
   pro &=       (pro >> 2);
   gen |= pro & (gen >> 4);
   return gen;
}
 
U64 soWeOccl(U64 gen, U64 pro) {
   pro &= notHFile;
   gen |= pro & (gen >>  9);
   pro &=       (pro >>  9);
   gen |= pro & (gen >> 18);
   pro &=       (pro >> 18);
   gen |= pro & (gen >> 36);
   return gen;
}
 
U64 noWeOccl(U64 gen, U64 pro) {
   pro &= notHFile;
   gen |= pro & (gen <<  7);
   pro &=       (pro <<  7);
   gen |= pro & (gen << 14);
   pro &=       (pro << 14);
   gen |= pro & (gen << 28);
   return gen;
}

Ray-wise Attacks

Ray-wise attacks need the occluded fills shift one further, considering wraps.

U64 soutAttacks (U64 rooks,   U64 empty) {return soutOne(soutOccl(rooks,   empty));}
U64 nortAttacks (U64 rooks,   U64 empty) {return nortOne(nortOccl(rooks,   empty));}
U64 eastAttacks (U64 rooks,   U64 empty) {return eastOne(eastOccl(rooks,   empty));}
U64 noEaAttacks (U64 bishops, U64 empty) {return noEaOne(noEaOccl(bishops, empty));}
U64 soEaAttacks (U64 bishops, U64 empty) {return soEaOne(soEaOccl(bishops, empty));}
U64 westAttacks (U64 rooks,   U64 empty) {return westOne(westOccl(rooks,   empty));}
U64 soWeAttacks (U64 bishops, U64 empty) {return soWeOne(soWeOccl(bishops, empty));}
U64 noWeAttacks (U64 bishops, U64 empty) {return noWeOne(noWeOccl(bishops, empty));}

Generalized Rays

Since rotate 64 works like a generalized shift with positive or negative shift amount, it might be applied to get pawn-attacks for both sides - or a Kogge-Stone fill with a direction parameter and small lookups for shift amount and wrap ands, instead of multiple code for eight directions. Of course generalized shift will be a bit slower due to lookups and using cl as the shift amount register.

U64 occludedFill (U64 gen, U64 pro, int dir8)
{
   int r = shift[dir8]; // {+-1,7,8,9}
   pro &= avoidWrap[dir8];
   gen |= pro & rotateLeft(gen, r);
   pro &=       rotateLeft(pro, r);
   gen |= pro & rotateLeft(gen, 2*r);
   pro &=       rotateLeft(pro, 2*r);
   gen |= pro & rotateLeft(gen, 4*r);
   return gen;
}
 
U64 shiftOne (U64 b, int dir8)
{
   int r = shift[dir8]; // {+-1,7,8,9}
   return rotateLeft(b, r) & avoidWrap[dir8];
}
 
U64 slidingAttacks (U64 sliders, U64 empty, int dir8)
{
   U64 fill = occludedFill(slider, empty, dir8)
   return shiftOne(fill, dir8);
}
 
// positve left, negative right shifts
int shift[8] = {9, 1,-7,-8,-9,-1, 7, 8};
 
U64 avoidWrap[8] =
{
   0xfefefefefefefe00,
   0xfefefefefefefefe,
   0x00fefefefefefefe,
   0x00ffffffffffffff,
   0x007f7f7f7f7f7f7f,
   0x7f7f7f7f7f7f7f7f,
   0x7f7f7f7f7f7f7f00,
   0xffffffffffffff00,
};

Publications

Peter M. Kogge, Harold S. Stone (1973). A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations. IEEE Transactions on Computers, 1973, C-22, 783-791, pdf

Forum Posts

Re: flood fill attack bitboards by Steffan Westcott, CCC, September 15, 2002
Kogge Stone Algorithm mistake on chessprogramming Wiki by Christopher Conkie, CCC, June 29, 2008
Re: Hyperbola Quiesscene: hardly any improvement by Karlo Bala Jr., CCC, January 14, 2009 » Hyperbola Quintessence
Kogge Stone, Vector Based by Srdja Matovic, CCC, January 22, 2013 » GPU ^[5] ^[6]
Fast perft on GPU (upto 20 Billion nps w/o hashing) by Ankan Banerjee, CCC, June 22, 2013 » Perft, GPU

External Links

Kogge-Stone adder from Wikipedia
Kogge-Stone algorithm from Terra Help and Information - Theories by Peter Fendrich
Gong - Shapeshifter ^[7], 1992, YouTube Video

References

^ Re: flood fill attack bitboards by Steffan Westcott, CCC, September 15, 2002
^ Hardware algorithms for arithmetic modules from the ARITH research group, Aoki lab., Tohoku University
^ Kogge-Stone adder from Wikipedia
^ Kogge Stone Algorithm mistake on chessprogramming Wiki by Christopher Conkie, CCC, June 29, 2008
^ Parallel Thread Execution from Wikipedia
^ NVIDIA Compute PTX: Parallel Thread Execution, ISA Version 1.4, March 31, 2009, pdf
^ Shapeshifting from Wikipedia

What links here?

Page	Date Edited
Algorithms	May 5, 2017
Ankan Banerjee	Aug 26, 2017
Anubis	Sep 29, 2015
Attack and Defend Maps	Nov 5, 2016
Bit-Twiddling	Nov 6, 2017
Christopher Conkie	May 17, 2016
Design Principles	Jan 17, 2018
DirGolem	Jun 5, 2016
Dumb7Fill	May 27, 2016
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Fill Algorithms	Nov 6, 2013
Fill by Subtraction	Mar 5, 2010
GPU	Dec 16, 2017
Gunnar Andersson	Jun 23, 2011
John L. Jerz	Jul 15, 2013
Karlo Bala Jr.	Feb 19, 2017
Kogge-Stone Algorithm	Sep 17, 2016
Mathematician	Apr 9, 2018
Mobility	Jan 17, 2018
On an empty Board	Mar 18, 2014
Othello	Jan 4, 2018
Paladin	Jan 29, 2017
Parallel Prefix Algorithms	Jun 22, 2016
Pawn Fills	Jul 18, 2014
Perft	Sep 26, 2017
Pieces versus Directions	Oct 6, 2016
Quad-Bitboards	Jan 30, 2017
Rodent	Jan 11, 2018
Russell Reagan	Aug 31, 2013
Shifted Bitboards	Jan 9, 2011
SIMD and SWAR Techniques	Jun 27, 2017
Sliding Piece Attacks	May 27, 2016
Srdja Matovic	Apr 14, 2018
SSE2	Feb 27, 2018
Steffan Westcott	Jan 21, 2014
Tarrasch Rule	Jun 2, 2014
X-ray Attacks (Bitboards)	Mar 31, 2015

Up one Level

Magic Bitboards

GerdIsenberg — Fri, 13 Apr 2018 13:09:31 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Magic Bitboards

		Magic bitboards, a multiply-right-shift perfect hashing algorithm to index an attack bitboard database - which leaves both line-attacks of bishop or rook in one run. Thanks to the fast 64-bit multiplication and fast and huge caches of recent processors, Magic Bitboards has become a de facto standard of modern bitboard engines, as used for instance in Crafty, Arasan, Stockfish and Houdini. While Robert Hyatt reported no immediate speed gain over Rotated Bitboards in Crafty ^[1] , Jon Dart mentioned a 20-25% speedup ^[2] in Arasan over rotated.
Samuel Bak - Auspicious Moon, 2001 ^[3]

History

The magic bitboard approach was motivated by Gerd Isenberg's multi-direction hashing technique kindergarten bitboards and probably by Gerd's and Tony van Roon-Werten's early trials to map line-wise occupancies by De Bruijn- or random number multiplication ^[4] . Lasse Hansen had the idea to hash the up to twelve relevant occupied bits of both directions of a rook- or bishop movement simultaneously ^[5] .

Pradu Kannan's improvements to Lasse Hansen's initial approach was to introduce a Java-like, two-dimensional array with individual size for each square and all it's relevant occupancies ^[6] . Big savings in table-size - since many squares on either orthogonal or diagonal lines require less bits than others, especially considering the inner six bits. While center squares are more dense for rooks, it is the opposite for bishops ^[7] .

Recently, Robert Purves coined the names Plain and Fancy Magics ^[8] , and found Hansen's initial Plain Magics with 2 MiB table for rooks and 256 KiB for bishops nearly indistinguishable from Fancy (about 800 KiB and 38 KiB) on his Intel i5 with huge L3 smart cache, see plain versus fancy source code. In the same CCC forum thread, Robert Houdart proposed a byte lookup per square for further table reductions.

How it works

A magic move-bitboard generation technique consists of four key steps:

Mask the relevant occupancy bits to form a key. For example if you had a rook on a1, the relevant occupancy bits will be from a2-a7 and b1-g1.
Multiply the key by a "magic number" to obtain an index mapping. This magic number can be generated by brute-force trial and error quite easily although it isn't 100% certain that the magic number is the best possible (see step 3).
Right shift the index mapping by 64-n bits to create an index, where n is the number of bits in the index. A better magic number will have less bits required in the index.
Use the index to reference a preinitialized move database.

The following illustration should give an impression, how magic bitboards work. All masked relevant occupied bits are perfectly hashed to the consecutive occupied state to index the pre-calculated attack-sets. Constructive collisions, where different occupancies map same attack-sets - since different bits are outer redundant bits "behind" the first blocker, are desired and even necessary to apply a perfect hashing with N bits.

                                        any consecutive
relevant occupancy                      combination of
bishop b1, 5 bits                       the masked bits
. . . . . . . .     . . . . . . . .     . . .[C D E F G]
. . . . . . . .     . 1 . . . . . .     . . . . . . . .
. . . . . . G .     . 1 . . . . . .     . . . . . . . .
. . . . . F . .     . 1 . . . . . .     . . . . . . . .
. . . . E . . .  *  . 1 . . . . . .  =  . . garbage . .    >> (64- 5)
. . . D . . . .     . 1 . . . . . .     . . . . . . . .
. . C . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
                                        any consecutive
relevant occupancy                      combination of
bishop d4, 9 bits                       the masked bits
. . . . . . . .     . . . . . . . .     2 4 5 B C E F G]
. . . . . . G .     . . .some . . .     . . . . . . .[1
. 5 . . . F . .     . . . . . . . .     . . . . . . . .
. . 4 . E . . .     . . .magic. . .     . . . . . . . .
. . . . . . . .  *  . . . . . . . .  =  . . garbage . .    >> (64- 9)
. . C . 2 . . .     . . .bits . . .     . . . . . . . .
. B . . . 1 . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
                                        any consecutive
relevant occupancy                      combination of
rook d4, 10 bits                        the masked bits
. . . . . . . .     . . . . . . . .     4 5 6 B C E F G]
. . . 6 . . . .     . . .some . . .     . . . . . .[1 2
. . . 5 . . . .     . . . . . . . .     . . . . . . . .
. . . 4 . . . .     . . .magic. . .     . . . . . . . .
. B C . E F G .  *  . . . . . . . .  =  . . garbage . .    >> (64-10)
. . . 2 . . . .     . . .bits . . .     . . . . . . . .
. . . 1 . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
                                        any consecutive
relevant occupancy                      combination of
rook a1, 12 bits                        the masked bits
. . . . . . . .     . . . . . . . .     5 6 B C D E F G]
6 . . . . . . .     . . .some . . .     . . . .[1 2 3 4
5 . . . . . . .     . . . . . . . .     . . . . . . . .
4 . . . . . . .     . . .magic. . .     . . . . . . . .
3 . . . . . . .  *  . . . . . . . .  =  . . garbage . .    >> (64-12)
2 . . . . . . .     . . .bits . . .     . . . . . . . .
1 . . . . . . .     . . . . . . . .     . . . . . . . .
. B C D E F G .     . . . . . . . .     . . . . . . . .

The above illustration is correct for the b1 bishop, since it has only one ray and one bit per file and works kindergarten like. In general a one to one mapping of N scattered occupied bits to N consecutive bits is not always possible due to overflows. A perfect mapping of N scattered bits to N consecutive bits is likely not minimal for most squares. It requires one or two gaps inside the consecutive N bits, to avoid collisions, blowing up the table size.

But the purpose is to perfectly hash attack-sets rather than consecutive occupied bits. The number of distinct attack-sets is much smaller than the relevant occupancies. Thus, with the help of constructive collisions, some initial guess how to map the bits, and/or trial and error, using exactly N bits is always possible. If one tries hard enough to maximize constructive collisions - even less. There are some N-1 ones reported at Best Magics so far, which will half the individual table size for some squares in the widespread Fancy Magic Bitboards approach.

Perfect Hashing

The cardinality of all relevant occupancies is determined by the number of bits to map, varying from five to twelve - thus, the cardinality is the power of two the number of bits, varying from 32 to 4096.
The cardinality of distinct attack-sets is determined by the product of the length of each of the max four direction rays greater than zero (or one). The rook on d4 has 3*4*3*4 = 144 distinct attack-sets, a bishop on a8 has only 7.

	bishop on square				rook on square
	A	B	C	D		A	B	C	D
8	64/7	32/6	32/10	32/ 12	8	4096/49	2048/42	2048/ 70	2048/ 84
7	32/6	32/6	32/10	32/ 12	7	2048/42	1024/36	1024/ 60	1024/ 72
6	32/10	32/10	128/40	128/ 48	6	2048/70	1024/60	1024/100	1024/120
5	32/12	32/12	128/48	512/108	5	2048/84	1024/72	1024/120	1024/144

	bishop on square				rook on square
	A	B	C	D		A	B	C	D
8	9.14	5.33	3.20	2.67	8	83.59	48.76	29.26	24.38
7	5.33	5.33	3.20	2.67	7	48.76	28.44	17.07	14.22
6	3.20	3.20	3.20	2.67	6	29.26	17.07	10.24	8.53
5	2.67	2.67	2.67	4.74	5	24.38	14.22	8.53	7.11

The idea to implement minimal perfect hashing by an additional 16-bit indirection turned out to be slower (see conditional compiles in Pradu Kannan's source ^[9] ).

Recent table sizes were about 38 KiB for the bishop attacks, but still about 800 KiB for rook attacks (Fancy). That sounds huge, considering L1 and L2 (L3) cache-sizes and number of cachelines and pages needed - we likely fetch distinct cachelines for each different square or occupancy. On the other hand caches and pages become larger in future processors. And occupancy and squares of the lookups don't change that randomly inside a search that we can still expect a lot of L1-hits. Unfortunately changes in occupancy outside the blockers and therefor not affecting the attack-set will introduce some more cache misses.

Wishing Dreams

Since there are 1428/4900 distinct attack sets for the bishop/rook attacks, we can use 11(2048 > 1428)/13(8196 > 4900) index bits for all bishop/rook attack bitboards. The table size will be 16KB for the bishop attacks and 64KB for rook attacks. To make it possible, we must find a group of magics (one per square and dependent each other). All the magics in the group must hash its all relevant occupancies into the same 11/13 bit index without any collision with others (anyhow for each square, different occupancies can hash to the same attack sets).

U64 bishopAttacks[2048]; // 16KB
U64 rookAttacks[8196]; // 64KB
 
struct GMagic {
   U64 mask;  // to mask relevant squares of both lines (no outer squares) and include sliding piece itself
   U64 magic; // magic 64-bit factor
};
 
GMagic mBishopTbl[64]; //1KB
GMagic mRookTbl[64]; //1KB
 
U64 bishopAttacks(U64 occ, enumSquare sq) {
   occ &= mBishopTbl[sq].mask;
   occ *= mBishopTbl[sq].magic;
   occ >>= 64-11;  //fixed shift
   return bishopAttacks[occ]; //no offset
}
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   occ &= mRookTbl[sq].mask;
   occ *= mRookTbl[sq].magic;
   occ >>= 64-13;
   return rookAttacks[occ];
}

But the idea seems like a wishing dream. Can we find ONE of the magic group of magics? Does it exist in theory? If not, can we use more bits to reach the condition? If yes, can we find a good magic group? A good magic group means that all the hash value <=n, so we can reduce the table size to n, until it reach to 1428/4900. Enough? If all hash values are grouped by square, can we think about using the Sharing Attacks method?

Implementations

Despite its huge table size, register usage and code size are important issues as well - and here Magic Bitboards are unbeatable. There are enough variations of space-time tradeoff and implementation details of that theme for all who like to play the optimization game. C-source code with various precompiler options is available from Pradu Kannan's site. MINIMIZE_MAGIC is about Plain versus Fancy ^[10] , while PERFECT_MAGIC_HASH enables an additional indirection via 16-bit indices. As always, with space-time tradeoffs - it depends on the individual cache- and memory footprint inside a particular chess program and the hardware architecture, which solution is preferable.

Fancy

Fancy Magic Bitboards is the main stream implementation as proposed by Pradu Kannan with individual table sizes for each square. It requires an individual shift, to leave that many index bits remaining as determined by the population of relevant occupancies. As mentioned, if one tries hard enough to maximize constructive collisions while looking for magics, one may half the size for several individual squares, see Best Magics so far.

U64 attack_table[...]; // ~840 KiB all rook and bishop attacks, less with constructive collisions optimization
 
struct SMagic {
   U64* ptr;  // pointer to attack_table for each particular square
   U64 mask;  // to mask relevant squares of both lines (no outer squares)
   U64 magic; // magic 64-bit factor
   int shift; // shift right
};
 
SMagic mBishopTbl[64];
SMagic mRookTbl[64];
 
U64 bishopAttacks(U64 occ, enumSquare sq) {
   U64* aptr = mBishopTbl[sq].ptr;
   occ      &= mBishopTbl[sq].mask;
   occ      *= mBishopTbl[sq].magic;
   occ     >>= mBishopTbl[sq].shift;
   return aptr[occ];
}
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   U64* aptr = mRookTbl[sq].ptr;
   occ      &= mRookTbl[sq].mask;
   occ      *= mRookTbl[sq].magic;
   occ     >>= mRookTbl[sq].shift;
   return aptr[occ];
}

Plain

Plain Magic Bitboards, Lasse Hansen's initial approach, takes much more memory for homogeneous two-dimensional attack arrays. 32 KiB per rook square, 4 KiB for each bishop square. It does not need a variable shift and therefor needs one processor register less to further reduce register pressure, despite shorter code. Unfortunately, so far, there are two rook corner squares (0 and 7), which prohibit dividing the rook table size by two.

U64 mBishopAttacks[64] [512]; // 256 K
U64 mRookAttacks  [64][4096]; // 2048K
 
struct SMagic {
   U64 mask;  // to mask relevant squares of both lines (no outer squares)
   U64 magic; // magic 64-bit factor
};
 
SMagic mBishopTbl[64];
SMagic mRookTbl  [64];
 
U64 bishopAttacks(U64 occ, enumSquare sq) {
   occ &= mBishopTbl[sq].mask;
   occ *= mBishopTbl[sq].magic;
   occ >>= 64-9;
   return mBishopAttacks[sq][occ];
}

Fixed shift Fancy

A fancy fixed shift variation was introduced by Onno Garms, looking for magics producing factors with appropriate reduced value ranges. That is, leave 12 bit rook indices for all squares, but with upper bit(s) clear for all possible occupancies for all the squares with less than 12 relevant bits, so that it efficiently becomes a less 12 bit index. Onno believes that it is possible to find magic factors with that property for most of those squares, to come close to the fancy table size with the advantage of a fixed shift ^[11] . Even an "overlapping" of square arrays is feasible, if they contain accordant unused slot gaps on both ends. Volker Annuss came up with a fixed shift solution of only 800 KiB and below ^[12] ^[13], and more recently even innovated with Black Magic Bitboards.

U64 attack_table[...]; // > 800 KiB  - 1.x MiB  - depending on the effort on looking for magics
 
struct SMagic {
   U64* ptr;  // pointer to attack_table for each particular square
   U64 mask;  // to mask relevant squares of both lines (no outer squares)
   U64 magic; // magic 64-bit factor
};
 
SMagic mBishopTbl[64];
SMagic mRookTbl[64];
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   U64* aptr = mRookTbl[sq].ptr;
   occ      &= mRookTbl[sq].mask;
   occ      *= mRookTbl[sq].magic;
   occ     >>= 64-12;
   return aptr[occ];
}

Black Magic Bitboards

Volker Annuss' most recent innovation and further improvement of his already dense 700 KiB fixed shift fancy reference implementation is called Black Magic Bitboards, introduced in CCC in August 2017 ^[14]. Instead of intersection with a mask to clear the not relevant occupancy bits, he used the union with the complement of mask to set all not relevant occupancy bits.

  and mask[d4]  vs.   or ~mask[d4]
. . . . . . . .     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 . 1 1 1 1
. . . 1 . . . .     1 1 1 . 1 1 1 1
. . . . . . . .     1 1 1 1 1 1 1 1

This trick, which basically adds a huge constant to the occupancy factor, enables to find Black Magics yielding in even smaller array sizes per square, determined by maximum and minimum index - the latter no longer zero for the empty occupancy! Unfortunately so far, the individual savings with denser square arrays don't completely advance to the size of the combined overlapping table, since overlapping became harder due to smaller gaps ^[15] . However, 692 KiB for the complete rook and bishop attack table is the new fixed shift reference. Black Magic Bitboards are now used in Volker's engine Arminius ^[16] ^[17]:

U64 attack_table[88507]; // 692 KiB for published black magics by Volker Annuss (new size 88316 aka 690 KiB) 
 
struct SBlackMagic {
   U64* ptr;  // pointer to attack_table for each particular square
   U64 notmask;  // to mask relevant squares of both lines (no outer squares)
   U64 blackmagic; // black magic 64-bit factor
};
 
SBlackMagic mBishopTbl[64];
SBlackMagic mRookTbl[64];
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   U64* aptr = mRookTbl[sq].ptr;
   occ      |= mRookTbl[sq].notmask;
   occ      *= mRookTbl[sq].blackmagic;
   occ     >>= 64-12;
   return aptr[occ];
}

Byte Lookup

Since there are only up to 144 different attack sets per square, Robert Houdart proposed to lookup bytes by square and hashed occupancy for a minimal perfect hashing with an additional indirection via an offset per square, which is successfully used in his engine Houdini ^[18] . Following sample code uses the Plain fixed shift method, while it may also applied for the dense Fancy one.

byte mBishopAttacks[64] [512]; // 32 K
byte mRookAttacks  [64][4096]; // 256 K
 
U64 mRookLookup[4900];  // 39 K
U64 mBishopLookup[1428];  // 11 K
 
struct SMagic {
   U64 mask;  // to mask relevant squares of both lines (no outer squares)
   U64 magic; // magic 64-bit factor
   int offset;   // offset into lookup table
};
 
SMagic mBishopTbl[64];
SMagic mRookTbl  [64];
 
U64 bishopAttacks(U64 occ, enumSquare sq) {
   occ &= mBishopTbl[sq].mask;
   occ *= mBishopTbl[sq].magic;
   occ >>= 64-9;
   return mBishopLookup[mBishopTbl[sq].offset + mBishopAttack[sq][occ]];
}

32-bit Magics

Optimizations are possible for 32-bit systems, as proposed by Grant Osborne ^[19] . Instead of letting the compiler split up a 64-bit multiply, two 32-bit multiplications can be manually implemented. Multiply the low bits of the magic with the low bits of the key and add it with the product of the high bits of the magic and the high bits of the key and use the upper bits of the sum to index the move database. For the bishops one may try only one 32-bit multiplication after xoring the masked high and low half.

struct {
  unsigned int rookMaskLo;
  unsigned int rookMaskHi;
  unsigned int rookMagicLo;
  unsigned int rookMagicHi;
  unsigned int rookShift;
  U64 *pRookAttacks;
} sm[64];
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   unsigned int lo = (int) occ;
   unsigned int hi = (int)(occ >> 32);
   lo &= sm[sq].rookMaskLo;
   hi &= sm[sq].rookMaskHi;
   lo *= sm[sq].rookMagicLo;
   hi *= sm[sq].rookMagicHi;
   lo  = (lo ^ hi) >> sm[sq].rookShift;
   return sm[sq].pRookAttacks[lo];
}

Sharing Attacks

The development has not finished. Lasse Hansen came up with another stunning idea ^[20] , to use a final intersection by attacks on an empty board, to share tables by two (rooks) or even four (bishops) squares. Bishop sharing is simple to understand, since there are light and dark colored bishops with disjoint attacks-sets, able to share the pre-calculated union of two square-attacks.

The trick is to share even equal colored bishops and rooks where both attack-sets are not disjoint - but all members of the intersection are always set, since they are direct neighbors of both sliders. This is how rooks and bishops may share union-attack-sets by two resp. four squares:

int rookSharing[64] = {
   0,  1,  2,  3,  4,  5,  6,  7,
   1,  0,  3,  2,  5,  4,  7,  6,
   8,  9, 10, 11, 12, 13, 14, 15,
   9,  8, 11, 10, 13, 12, 15, 14,
  16, 17, 18, 19, 20, 21, 22, 23,
  17, 16, 19, 18, 21, 20, 23, 22,
  24, 25, 26, 27, 28, 29, 30, 31,
  25, 24, 27, 26, 29, 28, 31, 30,
};
 
int bishopSharing[64] = {
   0,  2,  4,  4,  4,  4, 12, 14,
   0,  2,  5,  5,  5,  5, 12, 14,
   0,  2,  6,  6,  6,  6, 12, 14,
   0,  2,  7,  7,  7,  7, 12, 14,
   1,  3,  8,  8,  8,  8, 13, 15,
   1,  3,  9,  9,  9,  9, 13, 15,
   1,  3, 10, 10, 10, 10, 13, 15,
   1,  3, 11, 11, 11, 11, 13, 15,
};

On the cost of one additional and-instruction, post-masking has the potential to almost halve the rook tables - and even better for the already small bishop tables. Additionally, four union attack bitboards can be shared by eight rook- and six bishop-squares.

R 1 1 1 1 1 1 1    1 R 1 1 1 1 1 1    1 1 R 1 1 1 1 1    1 1 1 R 1 1 1 1
B R 1 1 1 1 1 1    R B 1 1 1 1 1 1    1 1 B R 1 1 1 1    1 1 R B 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 . 1 1 .    1 . 1 1 . . 1 .
1 1 . . 1 B . .    1 1 . . . 1 . .    . . 1 1 . . 1 B    . . 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 . . . .

If the additional post-mask becomes member of a structure, it exceeds 32 byte in 64-bit mode. A structure of arrays may be preferable than an array of structures.

U64 attack_table[...]; // ~400K Byte for all rook and (shared) bishop attacks
 
struct SMagic {
   U64* ptr;      // pointer to attack_table for each particular square
   U64 magic;     // magic 64-bit factor
   U64 premask;   // to mask relevant squares of both lines (no outer squares)
   U64 postmask;  // attacks on the otherwise empty board
   int shift;     // shift right
};
 
SMagic mBishopTbl[64];
SMagic mRookTbl[64];
 
U64 bishopAttacks(U64 occ, enumSquare sq) {
   U64* aptr = mBishopTbl[sq].ptr;
   occ      &= mBishopTbl[sq].premask;
   occ      *= mBishopTbl[sq].magic;
   occ     >>= mBishopTbl[sq].shift;
   return      mBishopTbl[sq].postmask & aptr[occ];
}
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   U64* aptr = mRookTbl[sq].ptr;
   occ      &= mRookTbl[sq].premask;
   occ      *= mRookTbl[sq].magic;
   occ     >>= mRookTbl[sq].shift;
   return      mRookTbl[sq].postmask & aptr[occ];
}

Incorporating the Shift

Another possible improvement was introduced by Grant Osborne ^[21] - to don't store the variable right shift inside an own array or structure element, but to use the almost redundant upper six bit of the magic factor instead - incorporating the shift into the magic number. While using a structure for pre-, postmask, magic and pointer, it's size is 4*8 = 32-byte or - if properly aligned - the half of one cache line. The additional effort for the right shift 58 to extract the variable shift is likely hidden by the latency of the independent multiplication, improving ipc.

U64 attack_table[...]; // ~400K Byte for all rook and (shared) bishop attacks
 
struct SMagic {
   U64* ptr;      // pointer to attack_table for each particular square
   U64 magic;     // magic 64-bit factor, including upper six bits as shift amount
   U64 premask;   // to mask relevant squares of both lines (no outer squares)
   U64 postmask;  // attacks on the otherwise empty board
}; // 32 Byte with 64-bit pointer!
 
SMagic mBishopTbl[64];
SMagic mRookTbl[64];
 
U64 bishopAttacks(U64 occ, enumSquare sq) {
   U64* aptr = mBishopTbl[sq].ptr;
   int shift = mBishopTbl[sq].magic >> 58;
   occ      &= mBishopTbl[sq].premask;
   occ      *= mBishopTbl[sq].magic;
   return      mBishopTbl[sq].postmask & aptr[occ >> shift];
}
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   U64* aptr = mRookTbl[sq].ptr;
   int shift = mRookTbl[sq].magic >> 58;
   occ      &= mRookTbl[sq].premask;
   occ      *= mRookTbl[sq].magic;
   return      mRookTbl[sq].postmask & aptr[occ >> shift];
}

Incorporating Offset

A similar idea as in Incorporating the Shift in the domain fixed shift magics was proposed by Eugene Kotlov concerning the indirection to the stored attack array, using the 16 lower bits of the magic factor as offset ^[22].

Initalization

Looking for Magics

The main issue is to find 64 magic factors for each rook and bishop square, to ensure they are free of collisions.

Looking for Magics

Magic Records

You may try to find your own magics - to possibly contribute to the record table for most dense fancy or plain tables. So far, there were no magics found for the expensive rook squares a1 and h1 (0, 7) with less than 12 bits, which would allow to half the plain table size. Is there any prove they don't exist - even with Black Magic?

Best Magics so far

Publications

Pradu Kannan (2007). Magic Move-Bitboard Generation in Computer Chess, as pdf
Fritz Reul (2009). New Architectures in Computer Chess, Ph.D. Thesis, Chapter 3, Magic Hash Functions for Bitboards, pdf
Maurizio Monge (2011). On perfect hashing of numbers with sparse digit representation via multiplication by a constant. Discrete Applied Mathematics, Vol. 159, No. 11

Forum Posts

2006

Fast(er) bitboard move generator by Lasse Hansen, Winboard Forum, June 14, 2006
List of magics for bitboard move generation by Pradu Kannan, Winboard Forum, August 23, 2006
Fastest Magic Move Bitboard Generator ready to use by Pradu Kannan, Winboard Forum, August 25, 2006
A Faster Magic Move Bitboard Generator? by Grant Osborne, Winboard Forum, December 15, 2006

2007

SEE with magic bitboards by Pradu Kannan, Winboard Forum, January 24, 2007 » Static Exchange Evaluation
Magic bitboards, Java by Sargon, CCC, August 19, 2007 » Java
BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits by Brian Richardson, CCC, August 24, 2007 ^[23]
Magic and precomputation by Onno Garms, Winboard Forum, September 23, 2007

2008

Magic Move Generation by Colin, CCC, February 18, 2008
How to reduce the "bits" used in a magic number by Charlie Brune, CCC, May 24, 2008
magic move - bitboard orientation by Frank Phillips, CCC, June 01, 2008
Incorporating the shift into the magic number by Grant Osborne, CCC, June 18, 2008

2009

Magics revisited by Richard Pijl, CCC, January 04, 2009
Magic with fixed shift by Onno Garms, Winboard Forum, March 18, 2009
Paradigm shifts by Gian-Carlo Pascutto, CCC, November 14, 2009
32-bit Magic experiments by Andrew Fan, Winboard Forum, December 03, 2009 » Kindergarten Bitboards

2010 ...

Plain and fancy magic on modern hardware by Robert Purves, CCC, August 22, 2010
Fixed shift magics with 800KB lookup table by Volker Annuss, Winboard Forum, September, 05, 2010
Build magics on the fly by Marco Costalba, CCC, June 07, 2011
Magic Multiplier Fundamentals by Cheney Nattress, CCC, January 03, 2013
Occupancy Variations by CDaley11, OpenChess Forum, January 25, 2013
Magic bitboards: Cache issues and state of the art? by Samuel Siltanen, CCC, March 22, 2013
Understanding Magic Bitboards by Jaco van Niekerk, Winboard Forum, April 03, 2013

2015 ...

question about magic keys generation time by Fermin Serrano, CCC, March 19, 2015 » Looking for Magics
Fancy magic bitboards question by Eric VanderHelm, CCC, September 22, 2015
M42 - A C++ library for Bitboard attack mask generation by Syed Fahad, CCC, April 30, 2016 ^[24]
understanding fixed shift fancy magic bitboard generation by Kalyankumar Ramaseshan, CCC, May 05, 2016
Re: understanding fixed shift fancy magic bitboard generation by Volker Annuss, CCC, May 06, 2016
Why should magic bitboards be sparse? by Alessandro Power, CCC, December 21, 2016
Looking for dense magics by Lucas Braesch, CCC, July 11, 2017
Black magic bitboards by Volker Annuss, CCC, August 03, 2017 » Black Magic Bitboards
Disproving the existence of some magics by Niklas Fiekas, CCC, September 16, 2017 » Looking for Magics
magic number comprising offset by Eugene Kotlov, CCC, February 07, 2018
No bishop magics with fixed shift 8 by Niklas Fiekas, CCC, April 09, 2018 » Looking for Magics

External Links

Buzz - A Winboard Chess Playing Program by Pradu Kannan - Source of Pradu Kannan's magic Move Generator
Rival Chess Engine - Magic Bitboards by Russell Newman and Chris Moreton » Rival
Chess Programming | Generating Magic Multipliers by Steve Maughan » Looking for Magics
chess - Sliding move generation using magic bitboard - Stack Overflow, June 4, 2013
M42 by Syed Fahad ^[25]
GitHub - goutham/magic-bits: Magic-bitboards for Chess by Goutham Bhat

Other Magic Stuff

Magic from Wikipedia
Magic (illusion) from Wikipedia
Magic (paranormal) from Wikipedia
Magic (cryptography) from Wikipedia
Magic number from Wikipedia
Magic constant from Wikipedia
Magic square from Wikipedia
Magic hypercube from Wikipedia
Five Senses - Magic Constant, Christmas Jazz Festival, Tallinn, December 10, 2011, YouTube Video
line-up: Nguyên Lê, Claudio Puntin, Steffen Schorn, Kristjan Randalu, Bodek Janke
Youn Sun Nah - Momento Magico (2013), YouTube Video
Youn Sun Nah, Ulf Wakenius, Lars Danielsson, Vincent Peirani

References

^ Re: BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits by Robert Hyatt, CCC, August 25, 2007
^ Arasan Blog - Aug 26, 2008 by Jon Dart
^ Major Works from Samuel Bak - represented by Pucker Gallery since 1969
^ rotated bitboards obsolete? by Gerd Isenberg, CCC, February 26, 2006
^ Fast(er) bitboard move generator by Lasse Hansen, Winboard Forum, June 14, 2006, Initial idea
^ Pradu Kannan (2007). Magic Move-Bitboard Generation in Computer Chess, as pdf
^ List of magics for bitboard move generation by Pradu Kannan, Winboard Forum, August 23, 2006
^ Plain and fancy magic on modern hardware by Robert Purves, CCC, August 22, 2010
^ Buzz - A Winboard Chess Playing Program by Pradu Kannan - Source of Pradu Kannan's magic Move Generator, PERFECT_MAGIC_HASH
^ Buzz - A Winboard Chess Playing Program by Pradu Kannan - Source of Pradu Kannan's magic Move Generator, MINIMIZE_MAGIC
^ Magic with fixed shift by Onno Garms, Winboard Forum, March 18, 2009
^ Fixed shift magics with 800KB lookup table by Volker Annuss, Winboard Forum, September, 05, 2010
^ Re: understanding fixed shift fancy magic bitboard generation by Volker Annuss, CCC, May 06, 2016
^ Black magic bitboards by Volker Annuss, CCC, August 03, 2017
^ Re: Black magic bitboards by Volker Annuss, CCC, August 04, 2017
^ Re: Black magic bitboards by Volker Annuss, CCC, August 04, 2017
^ source code according to the fixed shift fancy sample - array size from Volker's posting, also containing black magics and arrayoffsets, see Black magic bitboards by Volker Annuss, CCC, August 03, 2017
^ Re: Plain and fancy magic on modern hardware by Robert Houdart, CCC, August 26, 2010
^ A Faster Magic Move Bitboard Generator? by Grant Osborne, Winboard Forum, December 15, 2006
^ Lasse Hansen's postmask trick, Winboard Forum, May 09, 2008
^ Incorporating the shift into the magic number by Grant Osborne, CCC, June 18, 2008
^ magic number comprising offset by Eugene Kotlov, CCC, February 07, 2018
^ Movegen Re: Bitmap Type Re: Tinker 81 secs Re: Testing speed by Brian Richardson, CCC, April 24, 2000
^ M42 by Syed Fahad
^ M42 - A C++ library for Bitboard attack mask generation by Syed Fahad, CCC, April 30, 2016

What links here?

Page	Date Edited
Abbess	Jun 10, 2017
Abulafia	Oct 4, 2017
Alberto Sanjuan	Nov 3, 2014
AMD	Mar 9, 2018
Andreas Guettinger	Aug 14, 2013
Andrew Fan	Jul 30, 2017
Andscacs	Jan 16, 2018
Arasan	Apr 8, 2018
Arminius	Aug 5, 2017
Array	Dec 1, 2016
Atlas (ESP)	Jan 28, 2018
Backtracking	Dec 16, 2017
Barbarossa	Dec 20, 2016
BBChess (SI)	Jan 12, 2015
Best Magics so far	Apr 13, 2018
Bitboard Serialization	Dec 24, 2014
Bitboards	Nov 14, 2017
BMI2	Mar 6, 2018
Bobcat	Jun 27, 2017
Brutus NL	Aug 22, 2016
Buzz	Jun 22, 2016
Carballo	Oct 2, 2016
Cheese	Feb 17, 2018
Cheng	Jul 30, 2017
chess22k	Apr 23, 2018
chess4j	Jan 1, 2018
Chiron	Sep 24, 2017
Clarabit	Nov 3, 2011
Congruent Modulo Bitboards	Jun 26, 2013
Counter	Nov 13, 2017
Crafty	Jan 28, 2018
CuckooChess	Jan 17, 2017
Defenchess	Mar 18, 2018
Demolito	Mar 1, 2018
DiscoCheck	Jun 23, 2017
Djinn	Feb 8, 2016
Don Dailey	Dec 7, 2016
Donna	Aug 17, 2017
Edsel Apostol	Nov 2, 2016
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Eric Marathée	Dec 27, 2014
Ethereal	Mar 20, 2018
Exacto	Oct 3, 2015
Fire	Oct 12, 2017
Firefly	Oct 23, 2017
Fridolin	Jun 27, 2017
Galjoen	Mar 19, 2018
Garbochess	Sep 23, 2017
General Setwise Operations	Feb 25, 2018
Gerd Isenberg	Apr 4, 2016
Gibbon	Dec 23, 2014
Ginkgo	Jul 13, 2016
Giraffe	Jan 8, 2018
Glaurung	Mar 14, 2017
Godot	Apr 28, 2015
Gogobello	Jul 30, 2017
GopherCheck	Feb 3, 2017
Grant Osborne	Dec 2, 2011
Greko	Feb 27, 2018
GullChess	Jun 27, 2017
Hakkapeliitta	Apr 26, 2016
Hash Table	Jan 1, 2018
Hashing Dictionaries	Mar 1, 2014
Hedgehog	Feb 18, 2018
Hermann	Dec 7, 2017
Hiding the Implementation	Feb 3, 2011
Home	Jul 2, 2018
Houdini	Apr 14, 2018
iCE	Jan 4, 2016
Ifrit	Feb 7, 2016
Java	Feb 25, 2018
JFresh	Mar 2, 2016
Kholin	Jan 3, 2018
Kindergarten Bitboards	Aug 1, 2017
Laser	Dec 27, 2017
Lasse Hansen	Sep 1, 2015
Looking for Magics	Apr 13, 2018
Loop (Program)	Mar 14, 2017
Magic Bitboards	Apr 13, 2018
Marco Costalba	Feb 28, 2018
Mark Levene	Jun 2, 2015
Marvin	Feb 10, 2018
Maurizio Monge	Nov 27, 2015
Maverick	Jan 7, 2016
MinkoChess	Sep 5, 2013
Move Generation	Jan 29, 2018
Murka	Nov 11, 2016
Napoleon	Jun 25, 2017
Nemorino	Dec 21, 2017
NoraGrace	Nov 23, 2014
Occupancy	Sep 19, 2016
Octochess	Aug 15, 2017
Onno	Jul 19, 2013
Onno Garms	Jul 19, 2013
Orion	Oct 15, 2017
Paladin	Jan 29, 2017
Pawn Hash Table	Feb 1, 2018
Pawny	Jun 17, 2015
Pedone	Jan 16, 2018
Pradu Kannan	Aug 3, 2015
Prophet	Sep 30, 2017
Protector	Oct 12, 2017
RedQueen	Nov 13, 2017
Rhetoric	Nov 15, 2017
Rival	Jul 30, 2017
Robert Houdart	Dec 8, 2017
Robert Hyatt	Dec 25, 2017
Robert Pope	Jun 10, 2017
Robocide	May 11, 2016
Rodent	Jan 11, 2018
Rodin	Feb 7, 2016
RuyDos	Feb 17, 2018
Rybka	Mar 27, 2017
Schooner	Feb 2, 2018
Scorpio	Mar 28, 2018
Searcher	Sep 26, 2016
SEE - The Swap Algorithm	Jun 5, 2017
Senpai	Nov 10, 2017
Shield	May 17, 2017
Sliding Piece Attacks	May 27, 2016
Sloppy	Sep 17, 2016
SmarThink	Feb 2, 2018
SnailChess	Nov 26, 2014
Space-Time Tradeoff	Jun 17, 2015
Static Exchange Evaluation	Dec 14, 2017
Stockfish	Apr 7, 2018
Syed Fahad	Jan 1, 2017
Takuya Obata	Jan 7, 2017
Texel	Oct 9, 2017
Tim Kosse	May 23, 2013
Tinker	Aug 29, 2015
Titboards	Feb 20, 2013
Tornado	Dec 14, 2017
Traversing Subsets of a Set	Oct 14, 2016
Trevor Fenner	Jun 2, 2015
Trial and Error	Feb 11, 2018
Tucano	Dec 16, 2017
Tunguska	Sep 16, 2017
Vadim Demichev	Jul 26, 2013
Vajolet	Jan 25, 2018
Volker Annuss	Aug 3, 2017
Wing	Oct 26, 2017
Winglet	Apr 26, 2015
Winter	Jan 23, 2018
WyldChess	Mar 10, 2018
Xiphos	Apr 22, 2018
Zevra	Mar 12, 2018
Ziggurat	Oct 9, 2017
Zurichess	Mar 12, 2018

Up one Level

Occupancy of any Line

GerdIsenberg — Fri, 16 Sep 2016 20:25:28 GMT

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

		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.
Line Occupancy ^[1]

Avoiding Multiplication

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 ^[2] ^[3]:

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.

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?

What links here?

Page	Date Edited
Amundsen	Sep 3, 2013
Cassandre	Jul 5, 2013
Chezzz	Jan 20, 2013
Flipping Mirroring and Rotating	Oct 14, 2016
General Setwise Operations	Feb 25, 2018
Gk	Oct 9, 2017
Kindergarten Bitboards	Aug 1, 2017
Kurt	Apr 20, 2014
Occupancy	Sep 19, 2016
Occupancy of any Line	Sep 16, 2016
OliThink	May 19, 2017
Parallel Prefix Algorithms	Jun 22, 2016
Pepito	Nov 27, 2014
Population Count	Sep 3, 2017
Prophet	Sep 30, 2017
Rotated Bitboards	Mar 7, 2017
Sayuri	Oct 1, 2017
Sliding Piece Attacks	May 27, 2016
Smash	May 11, 2016
Steffan Westcott	Jan 21, 2014
Urban Koistinen	Apr 20, 2014

Up one Level

Wikispaces : chessprogramming - items matching description

Attack and Defend Maps

Table of Contents

Maintaining Attacks

Incremental Update

On the Fly

Implementations

Classical Approach

Alternatives

Piece-Sets

Ed's lookup

Direction wise

See also

Forums Posts

1995 ...

2000 ...

2005 ...

2010 ...

References

What links here?

Blockers and Beyond

Table of Contents

How it works

Sample C Source

See also

External Links

References

What links here?

Classical Approach

Table of Contents

Ray Attacks

Positive Rays

Conditional

Branchless

Negative Rays

Conditional

Branchless

Generalized

Conditional

Branchless

Zero Count

Line Attacks

Piece Attacks

Union of Line Attacks

In one Run

See also

Publications

Forum Posts

References

What links here?

Congruent Modulo Bitboards

Table of Contents

Modulo vs. Multiplication

Modulo

Congruence relation

Casting out 255

Reciprocal Multiplication

Multiplication

Fenner's and Levene's conclusion

Publications

Forum Posts

External Links

References

What links here?

CPW-Engine_attacks

Table of Contents

isAttacked

leaperAttack

straightAttack

diagAttack

Discovered Attack

See also

External Links

What links here?

Double Attack

Table of Contents

Seeing Potential Forks

Knight and Pawn

Sliding Pieces

See also