Wikispaces : chessprogramming - items matching description

Atlas

GerdIsenberg — Sun, 05 Nov 2017 10:23:37 GMT

Home * Engines * Atlas

		Atlas, an early chess program written in 1967 by Alex Bell at Atlas Computer Laboratory, Chilton. It was basically a resurrected, cleaned up Algol version of Bell's and Barricelli's old program from the early 60s to test evolutionary theories, which had an evaluation function based purely on mobility - at that time the first fully legal chess program to run in England ^[1], and likely also the base of Barricelli's WCCC 1974 entry Freedom. Atlas, running on an ICL Atlas computer ^[2], looked three plies ahead with alpha-beta, and would accept almost any captures in that depth with weighting on swaps of the more powerful pieces, i.e. it would always swap a queen for a queen. If no captures were present it prepared to castle or mini-maximised its mobility. A slight modification prevented it from moving its queen in the first 5 moves ^[3]. Atlas played a few sparring games against Lancaster ^[4], John Scott's program, then dubbed "Scott" ^[5], and largely suffered from horizon effect.
Atlas and the Hesperides ^[6]

Move Generation

A description of Atlas' move generation techniques along with a mate-in-two solver is given with Algol source code listing in Games Playing with Computers, 3.1 Chess ^[7]. Atlas uses two distinct 8x8 boards [1:65] and piece lists [O:16] for white and black man with identical piece coding, passing the boards per reference as 'mymanin' or 'opponents' dependent on side to move. Pre-calculated rook and bishop tables contain one vector of direction increments, i.e. east (+1), west (-1), north (+8), and south (-8) for rooks, and further for each square a vector of ray-direction terminal destination squares. The embedded routine 'rookorbishopmove' in scope of the outer move generation routine loops over all four directions, gets increment and terminal target square from the rook or bishop table, and iterates the destination along the ray. Inside the ray-loop it tests whether the target is occupied by an own man, to terminate the ray-loop, otherwise it stores the move, and then tests to break after a capture or even an illegal king capture with an extra exit 'cutoff'.

procedure rookorbishopmove(rookorbishop);
  integer array rookorbishop;
  begin 
    for j := 0 step 1 until 3 do
    begin 
      k := rookorbishop[j]; k is increment:
      l := rookorbishop[4 * square + j]; l is terminal square
      for i := square + k step k until l do 
      begin 
        if mymanin[i] ≠ 0 then goto newdirection;
        c := c+1;
        moves[c] := i;
        if opponents[i] ≠ 0 then 
        begin
          if opponents[i] = 6 then goto cutoff else goto newdirection
        end
      end;
newdirection:
    end
  end of rookorbishopmove;

Master

In the early 70s, Atlas evolved to Master in collaboration with Peter Kent, and later with John Birmingham and chess expert John Waldron, while Alex Bell finally left Chilton.

Namesake

Atlas by Andrés Manzanares Campillo

Publications

Alex Bell (1972). Games Playing with Computers. Allen & Unwin, index
Alex Bell (1978). The Machine Plays Chess? Pergamon Press, amazon

External Links

Chess Program

Games Playing with Computers | Chapter 3: Board Games, in Alex Bell (1972). Games Playing with Computers. Allen & Unwin
MASTER at IFIPS. Excerpt from Alex Bell (1978). The Machine Plays Chess?. Pergamon Press, hosted by Atlas Computer Laboratory from Rutherford Appleton Laboratory (RAL)

Misc

References

^ MASTER at IFIPS. Excerpt from Alex Bell (1978). The Machine Plays Chess?. Pergamon Press, hosted by Atlas Computer Laboratory from Rutherford Appleton Laboratory (RAL)
^ Atlas Computer Laboratory, hosted by Rutherford Appleton Laboratory (RAL)
^ MASTER at IFIPS. Excerpt from Alex Bell (1978). The Machine Plays Chess?. Pergamon Press, hosted by Atlas Computer Laboratory from Rutherford Appleton Laboratory (RAL)
^ John J. Scott (1969). Lancaster vs. Mac Hack. ACM SIGART Bulletin, Vol. 16
^ Chess programs: Scott from Alex Bell (1972). Games Playing with Computers. Allen & Unwin
^ Atlas and the Hesperides by John Singer Sargent, between circa 1922 and circa 1925, current location: Museum of Fine Arts, Boston, Wikimedia Commons
^ Games Playing with Computers | Chapter 3: Board Games, in Alex Bell (1972). Games Playing with Computers. Allen & Unwin

What links here?

Page	Date Edited
Alex Bell	Mar 1, 2017
AtlanChess	Sep 15, 2016
Atlas	Nov 5, 2017
Atlas (ESP)	Jan 28, 2018
Atlas Computer Laboratory	Feb 10, 2015
Engines	Mar 10, 2018
John J. Scott	Aug 30, 2016
Lancaster	Aug 30, 2016
Master	Dec 28, 2017
Move Generation	Jan 29, 2018
Peter Kent	Jan 7, 2016
Table-driven Move Generation	Feb 19, 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

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

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

Obstruction Difference

GerdIsenberg — Fri, 27 May 2016 12:50:52 GMT

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

		Obstruction Difference is another subtraction approach, proposed by Michael Hoffmann ^[1]. The idea is to get disjoint positive and negative ray masks of the occupancy, and to subtract the most significant one bit of the negative ray from the doubled least siginificat one bit (LS1B) of the positive ray. The difference is finally intersected with the linemask, excluding the sliding piece itself from the attack set.
Man Ray, Obstruction, 1947 ^[2]

Empty Sets

If there is no obstruction inside the positive ray, we simply subtract from zero, aka borrow from the hidden 2^64 bit, same if doubling results in an empty set. If there is no obstruction inside the negative ray, we need at least to subtract one. With neither blocker available, the difference is the universal set -1 (~0), and we end up with the linemask, excluding the sliding piece, which are all attacks on the otherwise empty board. Therefor, to subtract at least '1', oring '1' is required if the negative ray occupancy is empty. Since setting the least significant bit does not affect any MS1B extraction, it can be done unconditionally on the negative ray.

Isolation

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

C Code

The routine works for all lines, ranks, files, diagonals and anti-diagonals by applying appropriate line-masks, and could therefor used as a generalized routine with a line-direction parameter, or in C even passing a pointer to a structure with three (or multiples for several lines in parallel) bitboards per square and line, upper- and lower rays and the union of both.

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

/*
 * @author Michael Hoffmann, Gerd Isenberg
 * @param  U64 occ occupancy of the board
 * @param  SMasks* a mask structure by square and line
 * @return line attacks from that square
 */
U64 lineAttacks(U64 occ, const SMasks *pMask) {
   U64 lower, upper, mMS1B, ls1b, odiff;
   lower = pMask->lower & occ;
   upper = pMask->upper & occ;
   mMS1B = -C64(1) << bsr64(lower | 1); // ms1b of lower (at least bit zero)
   ls1b  = upper & -upper;
   odiff = 2 * ls1b + mMS1B; // x86 lea option due to add -ms1b
   return pMask->lineEx & odiff; // (pMask->lower | pMask->upper) & odiff;
}

To use it that way:

struct SMasks
{
   U64 lower;
   U64 upper;
   U64 lineEx; // lower | upper
} masks[64][4]; // 6 (4) KByte, needs initialization
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   return lineAttacks(occ, masks[sq] + 0) | lineAttacks(occ, masks[sq] + 1);
}
U64 bishopAttacks(U64 occ, enumSquare sq) {
   return lineAttacks(occ, masks[sq] + 2) | lineAttacks(occ, masks[sq] + 3);
}

Since with two's complement i << x == - (-i << x), 2*high-low is done by add for the option to use x86 lea-instruction. The routine looks competitive for CPUs with fast bsr or lzcnt but has problems on processors with slow bitScan or 32-bit processors. Register usage is moderate and should suffice all x88-64 scratch registers for two lines, even for Visual C++.

Java

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

/*
 * @author Michael Hoffmann, Gerd Isenberg
 * @param  long occ occupancy of the board
 * @param  int sq  0..63
 * @param  int line  0..3 for rank, file, dia, antidia
 * @return line attacks from that square
 */
long lineAttacks(long occ, int sq, int line) {
   long lower = longMasks[sq][line][0] & occ;
   long upper = longMasks[sq][line][1] & occ;
   long mMs1b = 0x8000000000000000 >> Long.numberOfLeadingZeros (lower | 1);
   long ls1b  = upper & -upper;
   long odiff = 2*ls1b + mMs1b;
   return longMasks[sq][line][2] & odiff;
}

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

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

How it works

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

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

References

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

What links here?

Page	Date Edited
Classical Approach	Jan 28, 2018
Hiding the Implementation	Feb 3, 2011
Hyperbola Quintessence	Mar 25, 2017
Michael Hoffmann	Aug 9, 2015
Nemo	Sep 24, 2016
Obstruction Difference	May 27, 2016
Occupancy	Sep 19, 2016
SBAMG	Dec 4, 2016
Sliding Piece Attacks	May 27, 2016
Subtracting a Rook from a Blocking Piece	Dec 2, 2016

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

On an empty Board

GerdIsenberg — Tue, 18 Mar 2014 21:05:25 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * On an empty Board

Single sliding piece attacks 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. To initialize those tables, one may use a fill approach with single populated from-sets, if availably anyway since used elsewhere. While the proposed line-routines here are quite small and cheap, incremental update during an initialization loop has some merits.

The various ray-,line- and piece sets are foundation of further attack calculation considering blocking pieces, for instance to mask the occupancy of relevant rays. Of course the piece attacks are union-sets of the disjoint line attacks, while the line attacks are unions of the disjoint ray attacks.

Ray Attacks

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

Rays by Line

Ray-Attacks may be conducted from Line-Attacks by intersection with "positive" and "negative" squares:

 positiveRay[sq] = lineAttacks[sq] & (0 - 2*singleBit[sq]);
 negativeRay[sq] = lineAttacks[sq] & (singleBit[sq] - 1);

or with shifts instead of lookups

 positiveRay[sq] = lineAttacks[sq] & (C64(-2) << sq);
 negativeRay[sq] = lineAttacks[sq] & ((C64(1) << sq) - 1);

Positive Rays

Remember Square Mapping Considerations.

By Lookup

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

Initialization

North attacks are simple to initialize inside a loop, starting from a1, shifting left:

U64 nort = C64(0x0101010101010100);
for (int sq=0; sq < 64; sq++, nort <<= 1)
   rayAttacks[sq][Nort] = nort;

Similar, but tad trickier for ranks and diagonals, due to the wraps. For instance the north-east direction:

U64 noea = C64(0x8040201008040200);
for (int f=0; f < 8; f++, noea = eastOne(noea) {
   U64 ne = noea;
   for (int r8 = 0; r8 < 8*8; r8 += 8, ne <<= 8)
      rayAttacks[r8+f][NoEa] = ne;
}

By Calculation

Orthogonal positive rays are quite cheap to calculate on the fly. For diagonal rays split the lines as mentioned.

U64 eastMaskEx(int sq) {
   const U64 one = 1;
   return 2*( (one << (sq|7)) - (one << sq) );
}
 
U64 nortMaskEx(int sq) {
   return C64(0x0101010101010100) << sq;
}

Negative Rays

Remember Square Mapping Considerations.

By Lookup

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

Initialization

South attacks are simple to initialize inside a loop, starting from h8, shifting right:

U64 sout = C64(0x0080808080808080);
for (int sq=63; sq >= 0; sq--, sout >>= 1)
   rayAttacks[sq][Sout] = sout;

Similar, but tad trickier for ranks and diagonals, due to the wraps.

By Calculation

Orthogonal negative rays are quite cheap to calculate on the fly. For diagonal rays split the lines as mentioned.

U64 westMaskEx(int sq) {
   const U64 one = 1;
   return (one << sq) - (one << (sq&56));
}
 
U64 soutMaskEx(int sq) {
   return C64(0x0080808080808080) >> (sq ^ 63);
}

Line Attacks

 RankAttacks[sq]         = EastAttacks[sq] | WestAttacks[sq];
 FileAttacks[sq]         = NortAttacks[sq] | SoutAttacks[sq];
 DiagonalAttacks[sq]     = NoEaAttacks[sq] | SoWeAttacks[sq];
 AntiDiagonalAttacks[sq] = NoWeAttacks[sq] | SoEaAttacks[sq];

By Lookup

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 .

By Calculation

To calculate them on the fly, including...

U64 rankMask(int sq) {return  C64(0xff) << (sq & 56);}
 
U64 fileMask(int sq) {return C64(0x0101010101010101) << (sq & 7);}
 
U64 diagonalMask(int sq) {
   const U64 maindia = C64(0x8040201008040201);
   int diag =8*(sq & 7) - (sq & 56);
   int nort = -diag & ( diag >> 31);
   int sout =  diag & (-diag >> 31);
   return (maindia >> sout) << nort;
}
 
U64 antiDiagMask(int sq) {
   const U64 maindia = C64(0x0102040810204080);
   int diag =56- 8*(sq&7) - (sq&56);
   int nort = -diag & ( diag >> 31);
   int sout =  diag & (-diag >> 31);
   return (maindia >> sout) << nort;
}

... or excluding the square bit:

U64 rankMaskEx    (int sq) {return (C64(1) << sq) ^ rankMask(sq);}
U64 fileMaskEx    (int sq) {return (C64(1) << sq) ^ fileMask(sq);}
U64 diagonalMaskEx(int sq) {return (C64(1) << sq) ^ diagonalMask(sq);}
U64 antiDiagMaskEx(int sq) {return (C64(1) << sq) ^ antiDiagMask(sq);}

Piece Attacks

RookAttacks[sq]   = RankAttacks[sq]     | FileAttacks[sq];
BishopAttacks[sq] = DiagonalAttacks[sq] | AntiDiagonalAttacks[sq];
QueenAttacks[sq]  = RookAttacks[sq] | BishopAttacks[sq];

By Lookup

                                   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 .

By Calculation

U64 rookMask    (int sq) {return rankMask(sq)     | fileMask(sq);}
U64 bishopMask  (int sq) {return diagonalMask(sq) | antiDiagMask(sq);}
 
 
U64 rookMaskEx  (int sq) {return rankMask(sq)     ^ fileMask(sq);}
U64 bishopMaskEx(int sq) {return diagonalMask(sq) ^ antiDiagMask(sq);}
 
U64 queenMask   (int sq) {return rookMask(sq)     | bishopMask(sq);}
U64 queenMaskEx (int sq) {return rookMask(sq)     ^ bishopMask(sq);}

What links here?

Page	Date Edited
Aleks Peshkov	Jan 13, 2016
AVX2	Aug 8, 2017
Backtracking	Dec 16, 2017
Bitfoot	Sep 8, 2015
Blockers and Beyond	Mar 21, 2014
Classical Approach	Jan 28, 2018
Direction	Oct 6, 2016
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Gerd Isenberg	Apr 4, 2016
Hyperbola Quintessence	Mar 25, 2017
Joker IT	Sep 16, 2017
Kindergarten Bitboards	Aug 1, 2017
Kogge-Stone Algorithm	Sep 17, 2016
Magic Bitboards	Apr 13, 2018
Obstruction Difference	May 27, 2016
On an empty Board	Mar 18, 2014
Pieces versus Directions	Oct 6, 2016
Praetorian	Feb 21, 2015
Rays	Oct 20, 2016
Reverse Bitboards	Aug 29, 2015
Ryan Mack	Jan 18, 2011
SBAMG	Dec 4, 2016
Shifted Bitboards	Jan 9, 2011
Sliding Piece Attacks	May 27, 2016
Squares	Feb 15, 2015
Subtracting a Rook from a Blocking Piece	Dec 2, 2016
Thor's Hammer	Nov 23, 2013
Tinker	Aug 29, 2015

Up one Level

Reverse Bitboards

GerdIsenberg — Sat, 29 Aug 2015 20:24:16 GMT

The Hyperbola Project - New Technologies

Bitboard Design and Sliding Piece Attack Generation

Now, how do reverse bitboards help generate sliding piece attacks?

What benefit comes from having a reversed bitboard in place of rotated bitboards?

Where do the reverse bitboards come in?

How can the reverse bitboards be converted back to normal?

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

The idea of reverse bitboards was proposed by Ryan Mack in 2000 while introducing his Hyperbola Project. It was based on the x XOR (x - 2) bit-twiddling trick to generate attacks in positive ray-directions - and beside the usual occupancy bitboard, to maintain a reversed or 180 degree rotated occupied bitboard to apply the trick for negative ray-directions as well. It was intended to traverse reversed sets for move-generation, while re-reversion took place in the scalar, square centric world by xor 63 after bitscan. Alternatively, for other purposes a MMX-bitreversal routine was mentioned.

Ryan made an interesting and thought-provoking contribution. He introduced the predecessor of the o^(o-2r)-trick. With hindsight, the idea of keeping two reversed sets seemed not that successful as the author initially thought. However, Hyperbola Quintessence, where fast vertical byteswap flipping is used on the fly to reverse diagonals and files, is somehow the resurrection of Ryan's ideas, vastly improved by Aleks Peshkov's xor wizardry. Aleks' SSSE3 approach even relies on keeping reverse occupancies to further use only nine SIMD operations to generate bishop attacks.

The Hyperbola Project - New Technologies

^[1]
What follows here is merely a glimpse at the new advances in computer chess that the Hyperbola Project will include. The revolutionary design will generate enormous speed improvements, optimized specifically for the Pentium III processor's SIMD and MMX enhancements. The downside is that the initial releases of Hyperbola will require a P-III system to operate. As the core engine is being written in assembly code, it is very difficult to optimize for more than one chip at a time.

The past two years have yielded a serious look at the way computer chess programs operate today. The most significant problem with PC-oriented (non 64-bit) programs is the lack of speed associated with doing 64-bit arithmetic in a 32-bit environment.

MMX technology introduced some 64-bit operations to the Pentium family of microprocessors, which do increase performance noticeably, but not optimally. When using MMX, many operations still have to be completed in the old 32-bit system, which degrades the performance gain when the data has to be exchanged back and forth between the regular registers and the MMX registers.

The improvements shown below also address another significant bottleneck in chess programming: memory speeds. Despite the fact that Hyperbola is designed for systems with extremely fast memory (RDRAM), memory is still a bottleneck for some calculations, which require a very tight dependency chain. Since a memory read from the fastest (L1) cache has a latency of three clock cycles, the processor remains stalled in a tight dependency chain such as this, where no other calculations can be completed while the processor waits for the memory read to complete.

Bitboard Design and Sliding Piece Attack Generation

Generating the attacks for sliding pieces proved to be a significant bottleneck in the early trials. For example, before generating legal moves for a position, the program must determine whether the king is in check. To do this, the program has to find the attacks of every type of piece from the king's square and check if an appropriate enemy piece resides there. Since this cannot be done while analyzing other moves, this is a huge slowdown under the current technology, which uses four sets of bitboards (three rotated) and several memory lookups to determine the correct attacks.

Hyperbola's design is quite different in this respect from other programs. Hyperbola introduces the concept of a reversed bitboard in place of three rotated bitboards, and TOTALLY eliminates the lookup tables in favor of simple calculations, all of which can be done in the 64-bit MMX registers.

With the research still in progress on this topic, it is not clear as to exactly how much performance can be enhanced by this new technique, but it is clear that performance will be improved very significantly, especially with MMX hardware. Processors that are completely 64-bit, such as the Intel Itanium, will also be very much helped by this technique.

Now, how do reverse bitboards help generate sliding piece attacks?

First, let's cover what has to be maintained by the program. There is the normal set of bitboards, all generated in the normal direction. And there is a single reverse bitboard, which roughly takes the place of the three rotated bitboards in most programs today. The reverse bitboard contains the same information as the forward bitboard which denotes all occupied squares, but it is in reverse, that is, bit x in the forward bitboard corresponds to bit 63-x in the reverse bitboard.

What benefit comes from having a reversed bitboard in place of rotated bitboards?

Maintenance
A single reversed bitboard is easier to maintain than one rotated bitboard, let alone three. This is because a table lookup is required to convert a bit from the forward format to most rotated formats. With the reverse bitboard, simply subtract the bit number from 63. Considering that only one of these bitboards has to be maintained instead of three, this issue is important.

The Calculations
When taking account of memory latencies, calculating the piece attacks using the forward and reverse bitboards can be done significantly faster due to total independence on lookup tables and complex calculations. There are a few slight snags with the diagonal calculations, but they are minor.
The benefit of having the forward and reverse bitboards really shines in light of a very important bit manipulation trick: x XOR (x - 2) contains bits set to one, starting from the second bit, and stopping at the first bit of x that is one, but including it.
Now, if x is the bitboard of all occupied squares, and it is shifted to the right so that the square for which attacks are being calculated becomes bit zero, then XORing x with (x - 2) gives a mask of all squares attacked by the piece on the desired square, once the result is shifted back to the left. It does not include the piece that is making the attack, but it does include the first occupied square. This is exactly the result the lookup tables return!
The snags come from wraparound - that is, when the mask goes to the end of the file, rank, or diagonal... and keeps going where it shouldn't. This can be easily fixed in rank/file attacks by masking only the rank or file in question, but it is more complicated on diagonals.

Where do the reverse bitboards come in?

The regular bitboard is fine for calculating any attacks that go in the positive direction from the starting square (by masking the rank, file, or diagonal), but the bit-manipulating trick won't work in the opposite direction. The solution is simple: calculate attacks in the opposite direction using a reverse bitboard, so that on that bitboard they extend in the positive direction and can be calculated as above.

The real problem comes in trying to combine the forward and reverse bitboards - there is just no simple way to un-reverse the bitboard. The technique to do the switch is not terribly cumbersome, but it certainly cannot be used in cases where only one set of attacks is being generated... the delay far outweighs the gain.

However, in Hyperbola, this delay can be managed for an overall gain. Though it is unclear whether these types of calculations will even be used in generating legal moves, due to an incremental move generator, the two bitboards can be scanned separately, converting the returns from the bitscans from reverse to forward (by subtracting from 63) instead of converting the entire bitboard.

A more pertinent issue arises with determining whether the king is in check, which is done before generating any legal moves. Possible ways to go about this include converting the reverse bitboard, which is probably not optimal, maintaining reverse bitboards for the sliding pieces of both colors, which is possible, and testing the individual squares on the bitboards both in forward and in reverse, which is nearly out of the question. In the newer chip architectures any unpredictable branches severely degrade performance, and the technique to avoid that is also slow because it can only be used on 32-bit registers.

The most viable option is to maintain four reverse bitboards, one for the bishops/queens and rooks/queens of each color. Updating them does not degrade performance because only one of the four must be updated for any move, or none at all, in addition to the regular updates.

With the extra reverse bitboards, it is now very easy to determine if the king is in check without any memory tables. First, calculate the attacks from the king's square for both types of sliding pieces, and simply AND them with the appropriate bitboards of enemy pieces. After that, OR all the results of the comparisons together, and take a single branch.

A possible shortcut exists here still. If the king is not in check, which is almost always the case, and all of the possible sliding piece lines are closed or empty, which is usually true, then the king cannot be checked by a sliding piece. The merit of this idea is questionable, but a more concrete idea is much more helpful. If the previously used sliding piece attack bitboards are saved and it is determined that none of the squares on those bitboards have changed in the bitboard of occupied pieces, then the bitboards can be used again and the calculations skipped. If this shortcut is used, then it might be more economical to reverse the bitboard(s) after calculating them and ignoring the additional reverse bitboards. That depends on the hit rate.

How can the reverse bitboards be converted back to normal?

The fastest way to do this isn't a huge deal, but it cannot be run in parallel with other operations and does degrade performance if it is run too often. Suppose we have the lower 16 bits of a bitboard, x: FEDCBA9876543210.

Load the constant, k = 5555555555555555h
x = [(x shl 1) and k] or [(x and k) shr 1] EFCDAB8967452301
Load the constant, k = 3333333333333333h
x = [(x shl 2) and k] or [(x and k) shr 2] CDEF89AB45670123
Load the constant, k = 0F0F0F0F0F0F0F0Fh
x = [(x shl 4) and k] or [(x and k) shr 4] 89ABCDEF01234567
Now, due to the availability of a MMX shift instruction that operates on 16-bit words, the bytes can now be switched more easily
x = (x shlw 8) or (x shrw 8) 0123456789ABCDEF
And finally, the pshufw on the P-III reorganizes the words in a single instruction
x = x pshufw 00011011b

Since all of this arithmetic can be done in the MMX registers, it runs very much in parallel and can complete in a reasonable time frame on the P-III. If this algorithm were to be redesigned for P-II or PMMX architectures (without the pshufw) it would be a little slower since two more steps need to be completed. Trying to do this without 64-bit support would be extremely slow due to the extended-precision operands, despite that most of it could be done in parallel. (This algorithm is also in parallel, so it would probably take over twice as long.)

Copyright © 2000 Ryan Mack

Forum Discussions

what do think about n xor (n-2) and 'reverse bitboards'?! by Stefan, CCC, July 01, 2001
Reversed vs. Rotated Bitboards by Sune Fischer, CCC, January 28, 2002
Reverse Bitboards by Sander de Zoete, CCC, January 13, 2003

References

What links here?

Page	Date Edited
Flipping Mirroring and Rotating	Oct 14, 2016
Hyperbola Quintessence	Mar 25, 2017
Occupancy	Sep 19, 2016
Praetorian	Feb 21, 2015
Reverse Bitboards	Aug 29, 2015
Ryan Mack	Jan 18, 2011
Sander de Zoete	Nov 2, 2013
Sliding Piece Attacks	May 27, 2016
Subtracting a Rook from a Blocking Piece	Dec 2, 2016
Sune Fischer	Apr 7, 2014
Thor's Hammer	Nov 23, 2013

Up one Level

Rotated Bitboards

GerdIsenberg — Tue, 07 Mar 2017 20:56:09 GMT

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

		Rotated Bitboards, a bitboard move generation technique coined by Robert Hyatt ^[1], and later by Ernst A. Heinz ^[2] and Peter Gillgasch from the DarkThought team. This variation uses rotated copies of the occupancy in order to place bits along a file, diagonal or anti-diagonal in adjacent bits. Because of this, these bits can be easily extracted to obtain a dense occupancy map for a rank, file, diagonal, and anti-diagonal. These are used, along with the square of the sliding piece, to lookup a bitboard, containing attacks, in an array. While the attack generation per line is more or less only one memory lookup, the incremental update of the occupancy during make and unmake move becomes more expensive, since beside the usual occupied bitboard there are three more rotated bitboards to update, including additional mapping from square coordinates to the rotated indices.
M. C. Escher, Curl-up, 1951 ^[3]

An Example

Square Mapping

by Hyatt

by Gillgasch and Heinz

An Example

As example file-attacks of rook a5 with occupancy along the a-file. The 90-degree rotated bitboard has consecutive bits of that file along its 8th rank, which serves as an index to lookup the pre-calculated file-attacks:

  non-rotated           rotated             file_attacks[a5][rotated]
 ┌─┐                 ┌───────────────┐     ┌─┐
 │1│0 0 0 0 0 0 0    │1_0_0_1_R_0_1_1│════>│0│0 0 0 0 0 0 0
 │1│0 0 0 0 0 0 0     0 0 0 0 0 0 0 0      │1│0 0 0 0 0 0 0
 │0│0 0 0 0 0 0 0     0 0 0 0 0 0 0 0      │1│0 0 0 0 0 0 0
 │R│0 0 0 0 0 0 0     0 0 0 0 0 0 0 0      │0│0 0 0 0 0 0 0
 │1│0 0 0 0 0 0 0     0 0 0 0 0 0 0 0      │1│0 0 0 0 0 0 0
 │0│0 0 0 0 0 0 0     0 0 0 0 0 0 0 0      │0│0 0 0 0 0 0 0
 │0│0 0 0 0 0 0 0     0 0 0 0 0 0 0 0      │0│0 0 0 0 0 0 0
 │1│0 0 0 0 0 0 0     0 0 0 0 0 0 0 0      │0│0 0 0 0 0 0 0
 └─┘                                       └─┘

With a rook on the square marked 'R', an attack bitboard can be obtained with the array lookup file_attacks[R][10011011].

Square Mapping

Interesting is the different mapping of both approaches. Crafty seemed to use little endian square mapping but bit 0 (A1) is mentioned as MSB, while bit 63 (H8) is LSB. DarkThought uses big-endian file-mapping (H1 = 0).

by Hyatt

Crafty didn't use byte aligned diagonals, but visual rotation.

  normal chess board bitmap            occupied_squares 90 degrees
 
  A8 B8 C8 D8 E8 F8 G8 H8              H8 H7 H6 H5 H4 H3 H2 H1
  A7 B7 C7 D7 E7 F7 G7 H7              G8 G7 G6 G5 G4 G3 G2 G1
  A6 B6 C6 D6 E6 F6 G6 H6              F8 F7 F6 F5 F4 F3 F2 F1
  A5 B5 C5 D5 E5 F5 G5 H5              E8 E7 E6 E5 E4 E3 E2 E1
  A4 B4 C4 D4 E4 F4 G4 H4              D8 D7 D6 D5 D4 D3 D2 D1
  A3 B3 C3 D3 E3 F3 G3 H3              C8 C7 C6 C5 C4 C3 C2 C1
  A2 B2 C2 D2 E2 F2 G2 H2              B8 B7 B6 B5 B4 B3 B2 B1
  A1 B1 C1 D1 E1 F1 G1 H1              A8 A7 A6 A5 A4 A3 A2 A1
 
  original left 45                     original right 45
 
              H8                                 A8
            G8  H7                             A7  B8
          F8  G7  H6                         A6  B7  C8
        E8  F7  G6  H5                     A5  B6  C7  D8
      D8  E7  F6  G5  H4                 A4  B5  C6  D7  E8
    C8  D7  E6  F5  G4  H3             A3  B4  C5  D6  E7  F8
  B8  C7  D6  E5  F4  G3  H2         A2  B3  C4  D5  E6  F7  G8
A8  B7  C6  D5  E4  F3  G2  H1     A1  B2  C3  D4  E5  F6  G7  H8
  A7  B6  C5  D4  E3  F2  G1         B1  C2  D3  E4  F5  G6  H7
    A6  B5  C4  D3  E2  F1             C1  D2  E3  F4  G5  H6
      A5  B4  C3  D2  E1                 D1  E2  F3  G4  H5
        A4  B3  C2  D1                     E1  F2  G3  H4
          A3  B2  C1                         F1  G2  H3
            A2  B1                             G1  H2
              A1                                 H1
 
  original left 45                     original right 45
 
   G6 H5|F8 G7 H6|G8 H7|H8|            C7 D8|A6 B7 C8|A7 B8|A8|
   H3|D8 E7 F6 G5 H4|E8 F7             F8|A4 B5 C6 D7 E8|A5 B6
   F4 G3 H2|C8 D7 E6 F5 G4             E6 F7 G8|A3 B4 C5 D6 E7
   E4 F3 G2 H1|B8 C7 D6 E5             E5 F6 G7 H8|A2 B3 C4 D5
   D4 E3 F2 G1|A8 B7 C6 D5             E4 F5 G6 H7|A1 B2 C3 D4
   B5 C4 D3 E2 F1|A7 B6 C5             D2 E3 F4 G5 H6|B1 C2 D3
   C2 D1|A5 B4 C3 D2 E1|A6             G3 H4|D1 E2 F3 G4 H5|C1
  |A1|A2 B1|A3 B2 C1|A4 B3            |H1|G1 H2|F1 G2 H3|E1 F2

by Gillgasch and Heinz

DarkThought used a similar mapping as proposed in Pseudo Rotation by 45 degrees from Flipping Mirroring and Rotating, all diagonals are packed in file-aligned bytes.

Normal Bitboard.                       Flipped Bitboard.
#7 #6 #5 #4 #3 #2 #1 #0 Bit/Byte       #7 #6 #5 #4 #3 #2 #1 #0 Bit/Byte
a8 b8 c8 d8 e8 f8 g8 h8 #7             a8 a7 a6 a5 a4 a3 a2 a1 #7
a7 b7 c7 d7 e7 f7 g7 h7 #6             b8 b7 b6 b5 b4 b3 b2 b1 #6
a6 b6 c6 d6 e6 f6 g6 h6 #5             c8 c7 c6 c5 c4 c3 c2 c1 #5
a5 b5 c5 d5 e5 f5 g5 h5 #4             d8 d7 d6 d5 d4 d3 d2 d1 #4
a4 b4 c4 d4 e4 f4 g4 h4 #3             e8 e7 e6 e5 e4 e3 e2 e1 #3
a3 b3 c3 d3 e3 f3 g3 h3 #2             f8 f7 f6 f5 f4 f3 f2 f1 #2
a2 b2 c2 d2 e2 f2 g2 h2 #1             g8 g7 g6 g5 g4 g3 g2 g1 #1
a1 b1 c1 d1 e1 f1 g1 h1 #0             h8 h7 h6 h5 h4 h3 h2 h1 #0
 
 
A1-H8 Bitboard.                        A8-H1 Bitboard.
#7 #6 #5 #4 #3 #2 #1 #0 Bit/Byte       #7 #6 #5 #4 #3 #2 #1 #0 Bit/Byte
a8|b1 c2 d3 e4 f5 g6 h7 #7             a8 b7 c6 d5 e4 f3 g2 h1 #7
a7 b8|c1 d2 e3 f4 g5 h6 #6             a7 b6 c5 d4 e3 f2 g1|h8 #6
a6 b7 c8|d1 e2 f3 g4 h5 #5             a6 b5 c4 d3 e2 f1|g8 h7 #5
a5 b6 c7 d8|e1 f2 g3 h4 #4             a5 b4 c3 d2 e1|f8 g7 h6 #4
a4 b5 c6 d7 e8|f1 g2 h3 #3             a4 b3 c2 d1|e8 f7 g6 h5 #3
a3 b4 c5 d6 e7 f8|g1 h2 #2             a3 b2 c1|d8 e7 f6 g5 h4 #2
a2 b3 c4 d5 e6 f7 g8|h1 #1             a2 b1|c8 d7 e6 f5 g4 h3 #1
a1 b2 c3 d4 e5 f6 g7 h8|#0             a1|b8 c7 d6 e5 f4 g3 h2 #0

Quotes

From Robert Hyatt as repost to Urban Koistinen from 1997 ^[4] :

When I first thought about doing the rotated bitmap idea, I discussed it with Peter G. of the DarkThought team. He thought (as I did) that the idea was pretty neat and worth trying. I (from the first thought) had always planned on updating the rotated bitmaps by the following approach: I have a set of 64 bitmaps callet set_mask[n]. To set bit 32, I simply AND(bit-map,set_mask[32]). If I have a rotated-90 bitmap, then I also create a rotated-90 set_mask, and do this: AND(bit-map-R90,set_mask_R90[32]) and I am done. Peter didn't like this, and wanted to get rid of the extra memory load for the rotated set_mask variable. (note there are actually 4 of these loads needed, for each of the rotated bitmaps). So he thought about it a bit and found a cute mathematical transformation based on shifts, AND's and OR's (I won't give it here since it is his idea) that avoide needing the set_mask_Rxx masks (note that on some machines, even the set_mask itself is not needed. to set bit 32 you just start with "1" and shift it to the right position avoiding the memory load altogether. However, the effect of Peter's approach is to map diagonal bits on the real bitmap to adjacent bits in a "psuedo-rotated" bitmap, without needing the set_mask_R90 stuff at all. Is it better? I'm not sure. My tests on the P6 said NO. My tests on the alpha with big cache also said NO. Peter's tests on the machine he used said YES. It definitely takes more instructions to do what Peter is doing. On a machine with a huge memory latency, like the PC, my memory loading can be slow. But with a decent sized cache, the 64 words X 8 bytes per word (512 bytes) really tucks into a corner in cache and doesn't hurt at all, particularly since a cache hit on the P6 operates at CPU speed. The PII is a different case since the cache operates at 1/2 CPU speed, which might swing things in his favor. For the record, they are *close* under all cases. We are not talking 10% here...one might be 2% faster on one machine, the other 3% faster on another machine... But the "mapping" is really odd and would not let us just simply swap the L45 and R45 maps...

Table size

The initial implementations of rotated bitboards missed the outer square optimization and used the 8-bit occupied state with four lookup tables of 256*64*8 or 128-Kbyte each, thus 1/2 MByte in total. Roberto Waldteufel seemed first time mentioned the optimization trick 1998 ^[5], masking off the redundant outer occupancies for a four fold table reduction.

Of course one may use calculations similar to kindergarten bitboards to further shrink the tables. In fact, getting the occupancy state and pre-calculated information based on that are two different steps.

Publications

Ernst A. Heinz (1997). How DarkThought Plays Chess. ICCA Journal, Vol. 20, No. 3
Robert Hyatt (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4 ^[6] ^[7]
Borko Bošković, Sašo Greiner, Janez Brest, Viljem Žumer (2005). The Representation of Chess Game. Proceedings of the 27th International Conference on Information Technology Interfaces
Johannes Buchner (2005). Rotated bitboards in FUSc#. Free University of Berlin, pdf » FUSc#

Forum Posts

1995 ...

bitmaps of rotated boards by Urban Koistinen, gnu.chess, March 2, 1995
Re: Speed of Move Generator by Robert Hyatt, rgcc, August 17, 1995
Rotated bitboards - experiment and result by Robert Hyatt, rgcc, February 28, 1996
bitboard move generation question by Stuart Cracraft, rgcc, September 05, 1997
Bitboard Representation by Carl Tillotson, rgcc, September 18, 1997
Rotated bitboards by Mats Forsén, rgcc, October 29, 1997
Rotated bitboards by Peter Fendrich, CCC, April 22, 1998
Efficient Rotated Bitboard Representations by Roberto Waldteufel, CCC, October 28, 1998
Extracting information from rotated Bitboards by John Stoneham, CCC, November 02, 1998
Bitboard user's information request by Robert Hyatt, CCC, October 05, 1999

2000 ...

Nice Rotated-bitmaps Article by Hyatt in ICCA by Tom Likens, CCC, February 07, 2000 ^[8]
Rotated Bitboards? by Mauricio Castro, rgcc, October 07, 2001
Attack Bitboards by Sune Fischer, CCC, October 30, 2001
Resources about rotated bitboards by Federico Corigliano, CCC, January 02, 2004

2005 ...

Generating "through" attacks with rotated bitboard by Vlad Stamate, CCC, August 28, 2009 » X-ray Attacks (Bitboards)

2010 ...

A question on rotated bitboard by n_ven, OpenChess Forum, May 04, 2011

External Links

Rotated Bitboards by Ernst A. Heinz
Rotated bitmaps, a new twist on an old idea by Robert Hyatt, revisited version of the ICCA Journal paper ^[9]
Computer Chess Programming Theory - Bitboards by Colin Frayn
Herb Alpert - Rotation (1979), YouTube Video

References

^ 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
^ Rotated Bitboards in Ernst A. Heinz (1997). How DarkThought Plays Chess. ICCA Journal, Vol. 20, No. 3
^ Picture gallery "Back in Holland 1941 - 1954" from The Official M.C. Escher Website
^ Bitboard Representation by Carl Tillotson, rgcc, September 18, 1997, post 23 by Robert Hyatt
^ Re: Extracting information from rotated Bitboards by Roberto Waldteufel, CCC, November 02, 1998
^ Bitboard user's information request by Robert Hyatt, CCC, October 05, 1999
^ Nice Rotated-bitmaps Article by Hyatt in ICCA by Tom Likens, CCC, February 07, 2000
^ Robert Hyatt (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4
^ The ICCA Journal paper does not mention the outer square optimization with the four fold table reduction

What links here?

Page	Date Edited
More Links
Alarm	Jun 7, 2017
Alessandro Damiani	Oct 9, 2017
Alice	May 20, 2015
Amundsen	Sep 3, 2013
Android-Chess	Jun 2, 2016
Arasan	Apr 8, 2018
Aristarch	May 8, 2014
Array	Dec 1, 2016
Attack and Defend Maps	Nov 5, 2016
Beaches	Jun 10, 2017
Beowulf	May 5, 2017
Betsy	Jul 28, 2014
BigLion	Sep 28, 2016
Bison	Sep 29, 2016
Bitboards	Nov 14, 2017
BMI1	Mar 24, 2014
BMI2	Mar 6, 2018
Booot	Jan 22, 2018
Brainless	Jun 24, 2017
Bruja	Feb 3, 2015
Cassandre	Jul 5, 2013
Cheese	Feb 17, 2018
Chesley	Dec 25, 2012
ChessV	Jan 21, 2018
Chezzz	Jan 20, 2013
Cinnamon	Sep 23, 2017
Congruent Modulo Bitboards	Jun 26, 2013
Crafty	Jan 28, 2018
Cupcake	May 19, 2016
DarkThought	Jul 3, 2018
David Rasmussen	Dec 16, 2017
DiscoCheck	Jun 23, 2017
Djinn	Feb 8, 2016
Dorky	Oct 10, 2016
Edsel Apostol	Nov 2, 2016
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Ernst A. Heinz	Mar 6, 2017
Federico Andrés Corigliano	Feb 13, 2014
First Rank Attacks	Aug 28, 2010
Fischerle	Aug 21, 2017
Flipping Mirroring and Rotating	Oct 14, 2016
Fortress (Engine)	Oct 19, 2017
Freyr	Mar 6, 2014
FUSCsharp	Jun 7, 2013
Gk	Oct 9, 2017
Hagrid	Apr 12, 2016
Hashing Dictionaries	Mar 1, 2014
HeavyChess	Feb 14, 2014
IsiChess	Jan 7, 2016
Jazz	Oct 4, 2017
Johannes Buchner	May 26, 2013
Kindergarten Bitboards	Aug 1, 2017
Kiwi	Sep 2, 2016
Kurt	Apr 20, 2014
La Dame Blanche	Oct 15, 2015
LittleThought	Nov 7, 2016
Loop (Program)	Mar 14, 2017
Magic Bitboards	Apr 13, 2018
Mark Levene	Jun 2, 2015
Mathematician	Apr 9, 2018
Murka	Nov 11, 2016
Nesik	Jan 24, 2014
Occupancy	Sep 19, 2016
Occupancy of any Line	Sep 16, 2016
OliThink	May 19, 2017
Parrot	Dec 31, 2014
Pepito	Nov 27, 2014
Peter Fendrich	May 19, 2017
Peter Gillgasch	May 15, 2016
Pharaon	Sep 2, 2017
Plisk	Dec 31, 2014
Prophet	Sep 30, 2017
Protej	Jul 27, 2014
PsycoChess	Sep 17, 2016
Rabbit	Oct 5, 2014
Requiem	Feb 5, 2018
Robert Hyatt	Dec 25, 2017
Roberto Waldteufel	Jun 5, 2013
Rotated Bitboards	Mar 7, 2017
Rotated Indices	Oct 9, 2017
Rybka	Mar 27, 2017
Sayuri	Oct 1, 2017
Searcher	Sep 26, 2016
SIMD techniques	Nov 26, 2017
Simon	Mar 15, 2014
Sinobyl	Jul 3, 2014
Sliding Piece Attacks	May 27, 2016
Sloppy	Sep 17, 2016
Smash	May 11, 2016
SnailChess	Nov 26, 2014
Snitch	Apr 7, 2016
Space-Time Tradeoff	Jun 17, 2015
Sune Fischer	Apr 7, 2014
Sunsetter	Jun 1, 2017
Terra	Feb 11, 2015
Tom Likens	Mar 7, 2017
Trevor Fenner	Jun 2, 2015
Urban Koistinen	Apr 20, 2014
Vlad Stamate	Dec 31, 2014
Warrior	Feb 23, 2015

Up one Level

Rotated Indices

GerdIsenberg — Mon, 09 Oct 2017 08:04:39 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Rotated Indices

		Rotated indices, a deconcentrated version of rotated bitboards, proposed by Alessandro Damiani ^[1] as used in his engine Fortress. Instead of using rotated bitboards with packed 15 diagonals and 15 anti-diagonals each, Alessandro applies an array of 16 + 30 rotated indices for all 16 orthogonal and 30 diagonal lines on the board. Those indices are incrementally updated during make/unmake, which takes a tad more effort - but once updated, the rotated indices pay off, the more often they are used inside a node of the search. No further computation is required to look up attacks, pure indexed memory accesses. The possible disadvantage - rotated indices, similar or slightly worse than rotated bitboards, are not as versatile as techniques relying on one occupancy bitboard only - if it is about a temporary change of the occupancy on the fly for x-rays and pinned pieces etc..
Barbara Mittman, Yellow Cherries ^[2]

Forum Posts

Re: Rotated bitboards by Alessandro Damiani, rgcc, October 31, 1997
Re: Resources about rotated bitboards by Alessandro Damiani, CCC, January 16, 2004

References

^ Re: Rotated bitboards by Alessandro Damiani, rgcc, October 31, 1997
^ Still Lifes by Barbara Mittman

What links here?

Page	Date Edited
Alessandro Damiani	Oct 9, 2017
Fortress (Engine)	Oct 19, 2017
Gk	Oct 9, 2017
Rotated Bitboards	Mar 7, 2017
Rotated Indices	Oct 9, 2017
Sliding Piece Attacks	May 27, 2016

Up one Level

SBAMG

GerdIsenberg — Sun, 04 Dec 2016 09:16:26 GMT

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

SBAMG, (Subtraction based Attack Mask Generation)
a subtraction based approach proposed by Syed Fahad ^[1] which combines techniques used in Subtracting a Rook from a Blocking Piece aka o^(o-2r) and Obstruction Difference. The idea is to subtract three times the closest blocker in negative ray direction (most significant one bit of lower ray occupancy) from the line occupancy, to exclusive or that difference with the line occupancy again: o^(o-3cbn). Three times is necessary, since we need not only to subtract the next highest neigbouring square of the closest blocker for the borrow propagation, but the blocker square itself. The line occupancy excludes the sliding piece itself, and equivalently the final result is again restricted by the line-mask excluding the square of the attacker. Outer squares of the line occupancy, which don't affect resulting line attacks, are always set to avoid conditional code.

Sample

A two nibble sample calculating the rank aka byte attacks of a rook illustrates the technique:

                   binary     hex  dez
bit-index          7654 3210  
blockers and rook  .b.. r.bb
occ (without rook) 0100 0011  0x43  67
cbn                0000 0010  0x02   2 
occ-3cbn           0011 1101  0x3d  61
occ^(occ-3cbn)     0111 1110  0x7e 126
attacks (/rook)    0111 0110  0x76 118

C Code

The routine works for all lines, ranks, files, diagonals and anti-diagonals by applying appropriate line-masks, and could therefor used as a generalized routine with a line-direction parameter. Signature and BitScanReverse (bsr64) similar to Obstruction Difference.

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

/*
 * @author Syed Fahad, Gerd Isenberg
 * @param  U64 occ occupancy of the board
 * @param  SMasks* a mask structure by square and line
 * @return line attacks from that square
 */
U64 lineAttacks(U64 occ, const SMasks *pMask) {
   occ &= pMask->lineEx;
   occ |= pMask->outer;
   int bsq = bsr64(occ & pMask->lower);
   U64 cbnx3 = C64(3) << bsq; // or lookup
   occ = occ ^ (occ - cbnx3);
   return occ & pMask->lineEx;
}

To use it that way:

struct SMasks
{
   U64 lower;  // 1 for sq 0, otherwise (1 << sq) - 1
   U64 lineEx; // excluding (1 << sq)
   U64 outer;  // outer & 1 must be 1 to avoid calling bsr(0)
} masks[64][4]; // needs initialization
 
U64 rookAttacks(U64 occ, enumSquare sq) {
   return lineAttacks(occ, masks[sq] + 0) | lineAttacks(occ, masks[sq] + 1);
}
U64 bishopAttacks(U64 occ, enumSquare sq) {
   return lineAttacks(occ, masks[sq] + 2) | lineAttacks(occ, masks[sq] + 3);
}

Forum Posts

Slider attack mask generation without table lookup by Syed Fahad, CCC, May 24, 2015
SBAMG - Competing Hyperbola Quintessence by Syed Fahad, CCC, April 10, 2016 » Hyperbola Quintessence
Subtraction based Attack Mask Generation by Syed Fahad, CCC, November 16, 2016

References

^ SBAMG - Completing Hyperbola Quintessence by Syed Fahad, CCC, April 10, 2016

What links here?

Page	Date Edited
Hyperbola Quintessence	Mar 25, 2017
Obstruction Difference	May 27, 2016
SBAMG	Dec 4, 2016
Sliding Piece Attacks	May 27, 2016
Subtracting a Rook from a Blocking Piece	Dec 2, 2016
Syed Fahad	Jan 1, 2017

Up one Level

Wikispaces : chessprogramming - items matching description

Atlas

Table of Contents

Move Generation

Master

Namesake

See also

Publications

External Links

Chess Program

Misc

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?

Dumb7Fill

Table of Contents

Occluded Fill

Seven Fill Cycles

Fill Loop

Unrolled Loop

Attack Fill

Comparison with Kogge-Stone

All Directions

Generalized Rays

Loop Version

Unrolled Attacks

See also

External Links

What links here?

Efficient Generation of Sliding Piece Attacks

Table of Contents

Bitboard Basics

Squares and Bitindex

Empty and Universe

Bitboard Board-Definition

Setwise Operations

Shifts