Wikispaces : chessprogramming - items matching description

Butterfly Boards

GerdIsenberg — Tue, 27 Jan 2015 19:02:19 GMT

Home * Programming * Data * Butterfly Boards

		Butterfly Boards are two-dimensional arrays (typically of various history counters for each color), indexed by the from- and to-square coordinates of (valid and likely quiet) moves, which appear inside the search. Those counters can then be used for move ordering as mentioned in the history heuristic, or to decide about late move reductions and history leaf pruning. Another application is a kind of killer- or refutation table, to store a refutation of a specific move ^[1], also base of the countermove heuristic ^[2] ^[3].
M. C. Escher, Symmetry ^[4]

Layout

The size of the array is 4K (64 x 64 = 4096) elements for each color, but the density is poor, since most from- and to-square combinations are illegal moves by the rules of chess. Thus, most entries inside the Butterfly boards are not used. Also, as an additional drawback, from-to coordinates, specially those with distance one, are ambiguous and may be legal for several pieces. For instance e2-e3 might be a rook-, queen-, king- or white pawn-move. However, knight-, rook- and bishop moves are disjoint, queen moves are the superset from rook- and bishop-moves, king-moves the one-distance subset of queen moves, and pawn pushes are subset of rook-moves, while pawn captures and en passant (if stored at all) are subset of bishop-moves.

Therefor some programmers omit the origin from-square, but use piece-type instead for denser 12 x 64 tables with only 3/4K entries - or exclude not only captures, but also pawn pushes and/or king moves. Other programmers have abandoned hashing moves for History Heuristic and LMR, and say that given enough search depth, History counters produce just some random noise ^[5] .

This is how butterfly boards may be declared in C or C++:

counterType arrWhiteButterfly[64][64]; // from, to -> 4K
counterType arrBlackButterfly[64][64]; // from, to -> 4K

counterType arrButterfly[2][64][64]; // color, from, to -> 8K

Valid Entries

As mentioned in Influence Quantity of Pieces, there are only 1792 (7/16 of 4K) possible valid moves coordinates, 9/16 of the space in the Butterfly boards is "wasted".

Piece	covers other pieces	#	div 112 (7*16)
Rook	queen, king and pawn pushes	896	8
Bishop	queen, king and pawn captures	560	5
Knight	-	336	3
possible from-to move coordinates		1792	16

The Eponym

The name Butterfly Boards was proposed by Dap Hartmann in 1988, when he introduced the Butterfly Heuristic in the ICCA Journal ^[6], and the application of a Butterfly refutation table at the Advances in Computer Chess 6 conference in 1990 ^[7]. Plotting the illegal move coordinates as black cells # inside a 64*64 sheet, seven butterfly shaped pattern appear along the impossible move diagonal (where squares are equal).

The Butterfly

Single Shape

The thorax of the Butterfly is centered by the wraps from one rank (or dependent on the Square Mapping Considerations, one file) to the next one. With 'a1' as square null mapping, and 'd1' as square 3, 'e2' is square 12, the shape indexed by square coordinates looks as follows, covering two wrapped rank "halfs" including their center files, e.g. d1 - e2:

d e f g h a b c d e        d e f g h a b c d e
1 1 1 1 1 2 2 2 2 2        1 1 1 1 1 2 2 2 2 2
#         #           d1   # - - - - # ~ \ | /
  #       # #         e1   - # - - - # # ~ \ |
    #     # # #       f1   - - # - - # # # ~ \
      #   # # # #     g1   - - - # - # # # # ~
        # # # # # #   h1   - - - - # # # # # #
# # # # # #           a2   # # # # # # - - - -
  # # # #   #         b2   ~ # # # # - # - - -
    # # #     #       c2   \ ~ # # # - - # - -
      # #       #     d2   | \ ~ # # - - - # -
        #         #   e2   / | \ ~ # - - - - #

That is why Dap Hartmann called it Butterfly Boards.

Connected Shapes

one butterfly spans a 10 square range
n butterflies span an 8*n + 2 square range
seven butterflies span 58 square range, from 3 (d1) to 60 (e8)

d e f g h a b c d e f g h a b c d e       d e f g h a b c d e f g h a b c d e
1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3       1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3
#         #                          d1   # - - - - # ~ \ | / ~ # # # \ ~ | ~
  #       # #                        e1   - # - - - # # ~ \ | / ~ # # # \ ~ |
    #     # # #                      f1   - - # - - # # # ~ \ | / ~ # # # \ ~
      #   # # # #                    g1   - - - # - # # # # ~ \ | / # # # # \
        # # # # # #                  h1   - - - - # # # # # # ~ \ | # # # # #
# # # # # #                          a2   # # # # # # - - - - - - - | / ~ # #
  # # # #   #                        b2   ~ # # # # - # - - - - - - \ | / ~ #
    # # #     #                      c2   \ ~ # # # - - # - - - - - ~ \ | / ~
      # #       #         #          d2   | \ ~ # # - - - # - - - - # ~ \ | /
        #         #       # #        e2   / | \ ~ # - - - - # - - - # # ~ \ |
                    #     # # #      f2   ~ / | \ ~ - - - - - # - - # # # ~ \
                      #   # # # #    g2   # ~ / | \ - - - - - - # - # # # # ~
                        # # # # # #  h2   # # ~ / | - - - - - - - # # # # # #
                # # # # # #          a3   # # # # # | \ ~ # # # # # # - - - -
                  # # # #   #        b3   \ # # # # / | \ ~ # # # # - # - - -
                    # # #     #      c3   ~ \ # # # ~ / | \ ~ # # # - - # - -
                      # #       #    d3   | ~ \ # # # ~ / | \ ~ # # - - - # -
                        #         #  e3   ~ | ~ \ # # # ~ / | \ ~ # - - - - #

C-Code

Some arbitrary C-code, to produce the plot:

#include "stdafx.h"
#include <math.h>
 
void butterflyBoard(int from, int to) {
   int sq1, sq2, f1, f2, r1, r2, df, dr;
   int nr = 0, nb = 0, nn = 0;
   for (sq2 = from; sq2 <= to; sq2++)
      printf("%c", (sq2 % 10) ? ' ' : '0' + (sq2/10) );
   printf("\n");
   for (sq2 = from; sq2 <= to; sq2++)
      printf("%1d", sq2 % 10 );
   printf("\n");
   for (sq1 = from; sq1 <= to; sq1++) {
      for (sq2 = from; sq2 <= to; sq2++) {
         if ( sq1 != sq2 ) {
            r1 = sq1 >> 3;
            r2 = sq2 >> 3;
            if (r1 == r2) { // same rank
               nr++;
               printf("-");
               continue;
            }
            f1 = sq1 & 7;
            f2 = sq2 & 7;
            if ( f1 == f2 ) { // same file
               nr++;
               printf("|");
               continue;
            }
            if  (f1 - r1 == f2 - r2) { // same diagonal
               nb++;
               printf("/");
               continue;
            }
            if  (f1 + r1 == f2 + r2) { // same anti-diagonal
               nb++;
               printf("\\");
               continue;
            }
            df = abs (f2 - f1);
            dr = abs (r2 - r1);
            if ( df + dr == 3 )    { // knight distance
               nn++;
               printf("~");
               continue;
            }
         }
         printf("#"); // invalid
      }
      printf(" %2d\n", sq1);
   }
   printf("rook   moves %4d\n", nr);
   printf("bishop moves %4d\n", nb);
   printf("knight moves %4d\n", nn);
   printf("total  moves %4d\n", nr + nb + nn);
}
 
int main(int argc, char* argv[])
{
   butterflyBoard(3, 20); // 0, 63
   return 0;
}

Analogy in Astronomy

Dap Hartmann found a nice analogy in astronomy. Edward Maunders was the first astronomer (1904) to plot the distribution in heliographic latitude of the centers of sunspot groups as a functions of time:

A modern version of the Mauders' sunspot "butterfly diagram" ^[8] .

Publications

Jonathan Schaeffer (1983). The History Heuristic. ICCA Journal, Vol. 6, No. 3
Dap Hartmann (1988). Butterfly Boards. ICCA Journal, Vol. 11, Nos. 2/3
Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1

External links

AVR Butterfly Board from Asuro Wiki (German)

Wikipedia

Butterflies from Wikipedia ^[9]

Butterfly insect of the order Lepidoptera
Butterfly Game a two-player abstract strategy game from Mozambique
BBN Butterfly a massively parallel computer from the 1980s
Butterfly diagram in the context of fast Fourier transform ^[10] algorithms
Butterfly or Zassenhaus lemma
Schmetterlingsgraph (German)
Butterfly knot
Butterfly theorem in elementary geometry
Butterfly curve (algebraic)
Butterfly curve (transcendental)
Butterfly catastrophe Catastrophe theory
Butterfly options a combination option trade strategy
Iron Butterfly spread
Iron Butterfly (band)
Butterfly ballot
Butterfly effect in the context of Chaos theory
The Butterfly Effect (Film)
The Butterfly Effect (band)

Musicvideo

Herbie Hancock & The Headhunters, Butterfly, 1974, YouTube Video

References

^ Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
^ Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1
^ Re: History pruning / move ordering question by Don Dailey, CCC, May 10, 2013
^ Picture gallery "Symmetry" from The Official M.C. Escher Website
^ Re: LMR: history or not? by Robert Hyatt from CCC, December 13, 2007
^ Dap Hartmann (1988). Butterfly Boards. ICCA Journal, Vol. 11, Nos. 2/3
^ Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
^ Edward Walter Maunder, Solar observations A modern version of the Mauders' sunspot "butterfly diagram". (This version from the solar group at NASA Marshall Space Flight Center.)
^ Butterfly (disambiguation) from Wikipedia
^ Fast Fourier Transform (FFT) from Reliable Software

What links here?

Page	Date Edited
Array	Dec 1, 2016
Bobby	Jan 7, 2016
Butterfly Boards	Jan 27, 2015
Butterfly Heuristic	May 6, 2016
Countermove Heuristic	Oct 1, 2017
Dap Hartmann	Jun 10, 2017
Dappet	Dec 12, 2016
Data	Nov 26, 2017
Dictionary	Aug 24, 2017
Direction	Oct 6, 2016
Encoding Moves	Mar 27, 2016
History Heuristic	Jul 19, 2017
History Leaf Pruning	Apr 15, 2013
ICGA Journal	Dec 21, 2017
Influence Quantity of Pieces	Jul 21, 2017
Last Best Reply	Jul 6, 2013
Mathematician	Apr 9, 2018
Moves	Feb 19, 2018
Neural MoveMap Heuristic	Sep 24, 2015
Relative History Heuristic	Jun 8, 2015
Squares	Feb 15, 2015
Table-driven Move Generation	Feb 19, 2017
Vector Attacks	Dec 15, 2017

Up one Level

Combinatorial Logic

GerdIsenberg — Thu, 06 Apr 2017 19:10:43 GMT

Home * Hardware * Combinatorial Logic

		A Combinatorial Logic (also Combinational Logic) is a digital circuit where one or more outputs are boolean functions of multiple inputs. The basic boolean operations conjunction, disjunction and logical negation are sufficient to derive all other boolean as well as arithmetical operations. Opposed to a sequential logic, outputs are not dependent on their history, that is a combinatorial logic does not require memory.
half adder circuit diagram

Implementation

In hardware, combinatorial logic can either realized with hardwired gates of certain logic families or programmable logic devices. If the number of inputs is reasonable small, a once programmed ROM or LUT can act as combinatorial logic. The inputs are the address, while one output is associated with a data-pin. In software this is like performing ALU-operations versus a memory lookup with pre-calculated outputs for all relevant inputs, related to the space-time tradeoff.

Basic Operations

AND

An AND gate implements a logical conjunction.
$a\wedge b$

Truth Table

- a -	- b -	a and b
0	0	0
0	1	0
1	0	0
1	1	1

Symbols and Circuits

OR

An OR gate implements a logical disjunction.
$a\vee b$

Truth Table

- a -	- b -	a or b
0	0	0
0	1	1
1	0	1
1	1	1

Symbols and Circuits

NOT

A NOT gate or Inverter implements a logical negation.
$\neg a$

Truth Table

- a -		not a
0		1
1		0

Symbols and Circuits

Derived Operations

Concrete electronic gates often combine AND and OR with trailing NOT for so called NAND and NOR gates. As application of De Morgan's laws a NAND can also be interpreted as OR of inverted inputs, and NOR as AND of inverted inputs.

NAND

A NAND gate is the inversion of AND, NOT AND.
$\neg (a\wedge b)$

Truth Table

- a -	- b -	not(a and b)
0	0	1
0	1	1
1	0	1
1	1	0

Symbols and Circuits

NOR

A NOR gate is the inversion of OR, NOT OR.
$\neg (a\vee b)$

Truth Table

- a -	- b -	not(a or b)
0	0	1
0	1	0
1	0	0
1	1	0

Symbols and Circuits

XOR

A XOR gate implements a exclusive disjunction, which might be derived from AND/OR/NOT, for instance from four NAND gates.

Truth Table

- a -	- b -	a xor b
0	0	0
0	1	1
1	0	1
1	1	0

Symbols and Circuits

DNF and CNF

Combinational logic can visualized by truth tables and the construction is generally done using disjunctive (sum of products) or conjunctive normal form (products of sums), and using boolean algebra or Karnaugh maps to simplify the expression.

ALU

Combinatorial logic is a huge part of the arithmetic logic unit (ALU) of processors, which provides accordant boolean logical instructions working on all bits of a register in parallel as mentioned in General Setwise Operations of Bitboards. Therefor each Combinatorial Logic can of course emulated in software.

Adder

A half adder performs an addition on two one-bit binary numbers. Output of an AND gate is the carry, while a XOR gate leaves the one-bit sum. A full adder with tad more gates adds three one-bit binary numbers, the third usually to feed in the carry from the previous digit, usually in carry look ahead architectures, such as Kogge-Stone adder, also mentioned as parallel prefix algorithm.



Full Adder

4-bit adder with Carry Look Ahead

Combinatorial Attacks

Assuming there are 13 times 64 digital inputs from a hardware wired chessboard. The 13 inputs per square has one exclusive "one" signal for either one of the twelve pieces or an empty signal. For each square a number of attacks/defend outputs may be defined to implement a huge Combinatorial Logic as a "zero cycle" attack table, i. e. output a8 is attacked from south by white rook as DNF (sum of products).

C Syntax

With C-like operators, that is '&' for AND and '|' for OR, the DNF would look like this:

southAttackByWhiteRook(a8) ::=
    wrook(a7)
| ( empty(a7) & wrook(a6) )
| ( empty(a7) & empty(a6) & wrook(a5) )
| ( empty(a7) & empty(a6) & empty(a5) & wrook(a4) )
| ( empty(a7) & empty(a6) & empty(a5) & empty(a4) & wrook(a3) )
| ( empty(a7) & empty(a6) & empty(a5) & empty(a4) & empty(a3) & wrook(a2) )
| ( empty(a7) & empty(a6) & empty(a5) & empty(a4) & empty(a3) & empty(a2) & wrook(a1) )

Circuit

The same sample as circuit f. i. in Diode logic with 34 diodes and 7 resistors:

 Board bus
 empty                    white rook                    
 a1 a2 a3 a4 a5 a6 a7 a8  a1 a2 a3 a4 a5 a6 a7 a8      ANDs (MIN)         OR (MAX)
 |  |  |  |  |  |  |  |   |  |  |  |  |  |  |  |           
    |  |  |  |  |  |      |  |  |  |  |  |  |               
    o--|--|--|--|--|------|--|--|--|--|--|--|----------|<|-----o---| R1 |---o +Vcc
       o--|--|--|--|------|--|--|--|--|--|--|----------|<|-----|
       |  o--|--|--|------|--|--|--|--|--|--|----------|<|-----|  D1-D7
       |  |  o--|--|------|--|--|--|--|--|--|----------|<|-----|
       |  |  |  o--|------|--|--|--|--|--|--|----------|<|-----|
       |  |  |  |  o------|--|--|--|--|--|--|----------|<|-----|
       |  |  |  |  |      o--|--|--|--|--|--|----------|<|-----o----------|>|------o  D28
       |  |  |  |  |         |  |  |  |  |  |                                      |
       o--|--|--|--|---------|--|--|--|--|--|----------|<|-----o---| R2 |---o +Vcc |
          o--|--|--|---------|--|--|--|--|--|----------|<|-----|                   |
          |  o--|--|---------|--|--|--|--|--|----------|<|-----|  D8-D13           |
          |  |  o--|---------|--|--|--|--|--|----------|<|-----|                   |
          |  |  |  o---------|--|--|--|--|--|----------|<|-----|                   |
          |  |  |  |         o--|--|--|--|--|----------|<|-----o----------|>|------o  D29
          |  |  |  |            |  |  |  |  |                                      |
          o--|--|--|------------|--|--|--|--|----------|<|-----o---| R3 |---o +Vcc |
             o--|--|------------|--|--|--|--|----------|<|-----|                   |
             |  o--|------------|--|--|--|--|----------|<|-----|  D14-18           |
             |  |  o------------|--|--|--|--|----------|<|-----|                   |
             |  |  |            o--|--|--|--|----------|<|-----o----------|>|------o  D30
             |  |  |               |  |  |  |                                      |
             o--|--|---------------|--|--|--|----------|<|-----o---| R4 |---o +Vcc |
                o--|---------------|--|--|--|----------|<|-----|  D19-D22          |
                |  o---------------|--|--|--|----------|<|-----|                   |
                |  |               o--|--|--|----------|<|-----o----------|>|------o  D31
                |  |                  |  |  |                                      |
                o--|------------------|--|--|----------|<|-----o---| R5 |---o +Vcc |
                   o------------------|--|--|----------|<|-----|  D23-D25          |
                   |                  o--|--|----------|<|-----o----------|>|------o  D32
                   |                     |  |                                      |
                   o---------------------|--|----------|<|-----o---| R6 |---o +Vcc |
                                         |  |                  |  D26-D27          |
                                         o--|----------|<|-----o----------|>|------o  D33
                                            |                                      |  D34
                                            o------------------o----------|>|------o-->--o a8 attacked  
                                                                                   |       by white rook
                                                                                   _       from south
                                                                                  | |  R7
                                                                                  |_|
                                                                                   |
                                                                                 --o--
                                                                                  ---   gnd
                                                                                   -

External Links

References

^ Edward Fredkin and Tommaso Toffoli (1982). Conservative logic. International Journal of Theoretical Physics, 21 :219–253, pdf

What links here?

Page	Date Edited
6502	Dec 25, 2017
68020	Jun 7, 2016
AVX-512	Aug 8, 2017
Belle	Jan 18, 2018
Berkeley Chess Microprocessor	May 22, 2013
Brutus	Dec 24, 2016
CHEOPS	Apr 18, 2015
ChipTest	Jun 19, 2016
Combinatorial Logic	Apr 6, 2017
Cray-1	Dec 25, 2017
Data	Nov 26, 2017
DEC Alpha	Aug 15, 2015
Deep Thought	Dec 5, 2016
Electro-Mechanical	May 2, 2016
Fairchild F8	Jul 31, 2015
FPGA	Jul 9, 2016
General Setwise Operations	Feb 25, 2018
Hardware	Jan 20, 2018
HP 2100	Jan 3, 2018
i860	Aug 21, 2015
Itanium	Aug 29, 2015
Kogge-Stone Algorithm	Sep 17, 2016
M-2	Sep 10, 2013
M-20	Oct 9, 2013
Memory	Dec 8, 2017
nCUBE	Dec 5, 2017
Neural Networks	Mar 12, 2018
Nova	Jan 20, 2016
Novag Micro Chess	Jan 16, 2013
Parallel Prefix Algorithms	Jun 22, 2016
PowerPC	Oct 6, 2017
Sequential Logic	May 10, 2017
Sliding Piece Attacks	May 27, 2016
Tempo (engine)	Dec 7, 2017
TR-4	Aug 27, 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

Evaluation of Pieces

GerdIsenberg — Mon, 08 Jan 2018 21:52:17 GMT

Home * Evaluation * of Pieces

This page serves as a quick reference for those who look for ideas about evaluating different kinds of pieces.

Pawn

Pawn Structure
Pawn Center
Blockade of Stop
penalty for "d" and "e" pawns blocked on their initial squares

Knight

Decreasing value as pawns disappear
Outposts
Knight trapped on A8/H8/A7/H7 or A1/H1/A2/H2 - see Trapped Pieces
Penalty for blocking a "c" pawn in closed openings (Crafty defines it as follows: white knight on c3, white pawns on c2 and d4, no white pawn on e4)
When calculating knight mobility, it is advisable to omit squares controlled by enemy pawns
Marginal bonus for a knight defended by a pawn
Penalty for an undefended minor piece (Stockfish)

Bishop

Bad Bishop
Bishop Pair
Bishop versus Knight
Color Weakness
Fianchetto
Returning Bishop
Bishop trapped by enemy pawns on A2/H2/A7/H7 or on A3/H3/A6/H6, see Trapped Pieces
Penalty for an undefended minor piece (Stockfish)

Rook

Increasing value as pawns disappear
Rook on open file
Rook on seventh (possibly also eigth) rank
Tarrasch Rule (Rook behind Passed Pawn)
Penalty for a Rook blocked by an uncastled King
Small bonus for a rook with enemy queen on the same file (doesn't matter if it's open or not)
Rooks defending each other (Rebel uses a piece/square table for that, making suppoeted rook on 7th rank even more valuable)

Queen

Penalty for early development ^[1]
Some programs do not evaluate queen mobility
Some versions of Fruit replace queen mobility by king tropism
If king safety evaluation relies on king tropism, queen tends to get somewhat higher bonus

King

King safety in the middlegame
King centralization in the endgame
Mate at a Glance
Penalty for standing on a wing with no pawns present in the endgame
Pins/X-ray
Castling Rights

Forum Posts

Knight Evaluation by Jonathan Rosenthal, CCC, February 24, 2015
eval pieces by Daniel Anulliero, CCC, June 15, 2015

References

^ Queen wandering, was: Crafty 14,9 by Roland Pfister, CCC, May 11, 1998

What links here?

Page	Date Edited
Bad bishop	Jun 22, 2015
Betsabe	Jul 23, 2017
BigLion	Sep 28, 2016
Bishop Pair	Sep 10, 2017
Bishop versus knight	May 17, 2016
Blockade of Stop	Oct 11, 2016
Chenard	Sep 5, 2015
Clarabit	Nov 3, 2011
Coiled	Mar 12, 2017
Color Weakness	Nov 24, 2017
Demolito	Mar 1, 2018
Evaluation	Feb 1, 2018
Evaluation of Pieces	Jan 8, 2018
Exacto	Oct 3, 2015
Faile	May 27, 2014
Genie	Feb 7, 2016
Gk	Oct 9, 2017
Ifrit	Feb 7, 2016
Influence Quantity of Pieces	Jul 21, 2017
Jabba	Sep 10, 2016
KnockOut	Sep 20, 2016
MadChess	Jul 4, 2017
Monsoon	Feb 8, 2015
Pawn Center	Feb 12, 2015
Piece-Square Tables	Mar 31, 2018
Pieces	Feb 19, 2018
Returning Bishop	Mar 16, 2013
Rival	Jul 30, 2017
Robocide	May 11, 2016
Rook on Open File	Apr 24, 2017
Rook On Seventh	May 24, 2009
Sayuri	Oct 1, 2017
Scidlet	May 31, 2014
Simplex	Mar 6, 2016
Slow Chess	May 17, 2016
Tarrasch Rule	Jun 2, 2014
Tucano	Dec 16, 2017
Tunguska	Sep 16, 2017
Y!	Sep 10, 2017

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

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];

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

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

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

Half-open file

GerdIsenberg — Tue, 11 Mar 2014 19:14:27 GMT

See also

External Links

What links here?

Home * Dictionary * Half-open file

Half-open file or semi-open file, is a file on which we do not have a pawn, but the opponent has at least one. It can be used to increase the vertical mobility of the major pieces, to attack weak pawns and to pressure enemy position or to create an outpost.

External Links

Half-open file from Wikipedia

What links here?

Page	Date Edited
Backward Pawn	May 5, 2017
Battery	Jan 29, 2017
Candidate Passed Pawn	Nov 11, 2017
Dictionary	Aug 24, 2017
Exacto	Oct 3, 2015
Files	Nov 22, 2015
Half-open file	Mar 11, 2014
Hanging pawns	Aug 5, 2015
Isolated Pawn	Nov 18, 2012
Minority Attack	Jun 6, 2012
Open file	Feb 15, 2015
Open Pawns (Bitboards)	Aug 24, 2017
Outposts	Apr 24, 2017
Pawn Fills	Jul 18, 2014
Pawns and Files (Bitboards)	Jan 16, 2013
Rook on Open File	Apr 24, 2017

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

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

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':

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

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

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

Outposts

GerdIsenberg — Mon, 24 Apr 2017 09:19:34 GMT

Home * Evaluation * Patterns * Outposts

r4rk1/ppp2ppp/3p2n1/8/4P3/2N5/PPP2PPP/2KRR3 w - -

Outposts,
a chess term most often related to knights in the center or on the opponent's half of the board, defended by an own pawn, and either no longer attackable by opponent pawns at all, or otherwise, provoking to weaken an opponent pawn on a half-open file no longer "Biting on Granite" ^[1] .

The mighty outpost Nd5! ^[2]

On a Half-open file

Occupying Holes

Factors influencing score

On a Half-open file

Nimzowitsch defined outposts as squares on a half-open file on the opponent's half of the board, defended by own pawns. The logic between such a placement was to entice the opponent to attack such a piece by a pawn, thereby weakening the pawn standing on that half-open file. In My System knight and rook outposts were mentioned - the former occurred in the center, the latter - on the wing. One game commentary mentions also "a diagonal outpost", though this subject is not expanded.

Occupying Holes

Some programmers apply a more common meaning of the word outpost, using this term in regard to a strong square in the center or opponent half of the board, defended by own pawn and no longer attackable by the opponent's pawn, occupied or about to be occupied by a knight. In this case the half-open file and provocation aspect of the outpost is lost, though the evaluation term is still useful.

Factors influencing score

To give an estimate of a typical outpost score, Toga log user manual advocates a bonus for a knight outpost on a central square as 10 centipawns, but it is possible to see bonuses as large as 16 centipawns. Furthermore, outpost value can be increased if it is defended by two pawns (thus making exchange sacrifice much less profitable) or if opponent has no minors that he can exchange for an outpost piece.

Forum Posts

knight outposts by Jan K., CCC, August 26, 2004
Toga Knight Outpost by Ben Tennison, CCC, December 10, 2012 » Toga
The eternal knight by Lyudmil Tsvetkov, CCC, January 18, 2013
A question about Outpost Knights / Bishops by Andrew Grant, CCC, May 15, 2016

External Links

References

What links here?

Page	Date Edited
AI Chess	Jan 7, 2016
Alarm	Jun 7, 2017
Amundsen	Sep 3, 2013
Amyan	Dec 10, 2013
Andrew Grant	Jan 13, 2018
Bismark	Apr 22, 2015
Cheese	Feb 17, 2018
chess22k	Apr 23, 2018
Chunking	Jun 12, 2017
Coiled	Mar 12, 2017
Dartmouth CP	Jan 19, 2018
Design Principles	Jan 17, 2018
Dragon FR	Sep 9, 2016
Ethereal	Mar 20, 2018
Evaluation of Pieces	Jan 8, 2018
Evaluation Patterns	Jun 24, 2013
Gaviota	Jan 21, 2018
Gibbon	Dec 23, 2014
Gogobello	Jul 30, 2017
Half-open file	Mar 11, 2014
Holes	Oct 16, 2017
Kaissa	Apr 9, 2018
Lyudmil Tsvetkov	Mar 28, 2018
Outposts	Apr 24, 2017
Pattern Recognition	Sep 8, 2017
Pawn Structure	Oct 2, 2017
RuyDos	Feb 17, 2018
Scorpio	Mar 28, 2018
Shield	May 17, 2017
Sloppy	Sep 17, 2016
Snitch	Apr 7, 2016
Spike	Jan 7, 2016
Stockfish	Apr 7, 2018
Strategic Test Suite	Dec 19, 2016
Toga	Dec 28, 2017
TRACE	Feb 14, 2013
Wasp	Nov 24, 2017
WyldChess	Mar 10, 2018
Xpdnt	Sep 13, 2015

Up one Level

Rook

GerdIsenberg — Fri, 05 Nov 2010 17:08:07 GMT

Home * Chess * Pieces * Rook

CPW Pages with the tag "rook"

What links here?

Page	Date Edited
More Links
Algebraic Chess Notation	Sep 25, 2017
Alice	May 20, 2015
Arimaa	Jan 4, 2017
Backward Pawn	May 5, 2017
Battery	Jan 29, 2017
Blockade of Stop	Oct 11, 2016
Castling	May 5, 2017
Denis Onneweer	Oct 3, 2012
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Elephant	Sep 19, 2016
Fill Algorithms	Nov 6, 2013
First Rank Attacks	Aug 28, 2010
Gambit Fruit	Mar 29, 2013
General Setwise Operations	Feb 25, 2018
Halfmove Clock	Aug 9, 2017
Hash Table	Jan 1, 2018
Influence Quantity of Pieces	Jul 21, 2017
Initial Position	Apr 14, 2018
Irreversible Moves	Jan 25, 2014
Joanna	Dec 9, 2014
King	Feb 26, 2013
KRK	Nov 26, 2016
Legal Move	Feb 16, 2017
MicroChess	Jul 14, 2015
Mobility	Jan 17, 2018
Mop-up Evaluation	Nov 26, 2016
MVV-LVA	Oct 26, 2017
Najib Nakad	Oct 22, 2014
Outposts	Apr 24, 2017
Pawn Spans	Jul 22, 2010
Pawns and Files (Bitboards)	Jan 16, 2013
Pieces	Feb 19, 2018
Pin	Mar 7, 2017
Point Value	Mar 31, 2018
Promotions	Jun 6, 2017
Reversible Moves	Mar 13, 2010
Rook	Nov 5, 2010
Rook (Program)	Jan 8, 2016
Rook Endgame	Sep 18, 2017
Scidlet	May 31, 2014

Up one Level

Rook on Open File

GerdIsenberg — Mon, 24 Apr 2017 09:20:48 GMT

Home * Evaluation * of Pieces * Rooks on (semi) open files

An open file is usually defined as a file with no pawns on it; a semi-open file as containing only the enemy pawns. In both cases a rook occupying such a file gets greater vertical mobility as well as a chance to penetrate the enemy camp, positioning itself on the 7th rank.

Early versions of Fruit omitted this evaluation term altogether. Some programs, like Rebel, have an additional bonus for doubling rooks on an open file. Some increase the bonus if the file has a bearing against the enemy king , some make the bonus dependent on the number of own pawns. It is worth noting that Nimzowitsch in My System used the term "(semi) open file" even for the rooks standing in front of the pawn chain. The same has been said about Rybka. Bonuses applied to a rook on an open file vary from 8 to 20 centipawns ^[1]. Typical bonus for a semi-open file is half of that for a fully open file.

Forum Posts

So same, so different by Lyudmil Tsvetkov, CCC, February 12, 2015

References

^ 20 cp comes from Toga log user manual, after adding actual bonus and penalty for a rook on a closed file

What links here?

Page	Date Edited
More Links
Amundsen	Sep 3, 2013
Amyan	Dec 10, 2013
Battery	Jan 29, 2017
BigLion	Sep 28, 2016
Bismark	Apr 22, 2015
Cheese	Feb 17, 2018
chess22k	Apr 23, 2018
ChessBrainVB	Jun 24, 2017
Coiled	Mar 12, 2017
Defenchess	Mar 18, 2018
Diablo	May 17, 2016
Dorpsgek	Apr 2, 2018
Ethereal	Mar 20, 2018
Evaluation of Pieces	Jan 8, 2018
Exacto	Oct 3, 2015
Garbochess	Sep 23, 2017
HeavyChess	Feb 14, 2014
ISA	Apr 2, 2018
Kaissa	Apr 9, 2018
Kholin	Jan 3, 2018
Lyudmil Tsvetkov	Mar 28, 2018
Marvin	Feb 10, 2018
Minority Attack	Jun 6, 2012
Murka	Nov 11, 2016
Nebula	Feb 7, 2015
Open file	Feb 15, 2015
Pawn Structure	Oct 2, 2017
Planning	Feb 12, 2018
PolarChess	May 15, 2017
RattateChess	Dec 2, 2014
Robocide	May 11, 2016
Rook on Open File	Apr 24, 2017
Sayuri	Oct 1, 2017
Scorpio	Mar 28, 2018
SCP	Jun 16, 2016
Shield	May 17, 2017
Sloppy	Sep 17, 2016
Spike	Jan 7, 2016
Stockfish	Apr 7, 2018
Strategic Test Suite	Dec 19, 2016

Up one Level

Rook On Seventh

GerdIsenberg — Sun, 24 May 2009 11:36:56 GMT

Home * Evaluation * of Pieces * Rook on Seventh

This is a common evaluation term. In chess, having a rook on the seventh rank is quite powerful, since it can both attack opponent pawns on their baseline and trap a king on the 8th (1st) rank. Especially the situation termed the absolute control of the seventh rank - having two unopposed major pieces on it with the king trapped on the 8th rank - can have a devastating effect.

More elaborate programs only give a bonus for rook on the seventh rank if there are opponent pawns on the 7th rank, or the opponent's king is on the eighth rank. Simple engines, on the other hand, might incorporate this bonus in the piece-square tables.

Whereas this evaluation term is generally acclaimed as useful, there is a debate whether to assign a smaller bonus for placing a rook on the eighth (first) rank.

What links here?

Page	Date Edited
Alarm	Jun 7, 2017
Amundsen	Sep 3, 2013
Amyan	Dec 10, 2013
Battery	Jan 29, 2017
BigLion	Sep 28, 2016
Cheese	Feb 17, 2018
Chess 0.5	Nov 20, 2016
Coiled	Mar 12, 2017
Dartmouth CP	Jan 19, 2018
Diablo	May 17, 2016
Djinn	Feb 8, 2016
Ethereal	Mar 20, 2018
Evaluation of Pieces	Jan 8, 2018
Evaluation Overlap	Jul 19, 2016
Exacto	Oct 3, 2015
HeavyChess	Feb 14, 2014
ISA	Apr 2, 2018
Kaissa	Apr 9, 2018
Marvin	Feb 10, 2018
Nebula	Feb 7, 2015
Planning	Feb 12, 2018
Quantifying Evaluation features	Jun 6, 2012
RattateChess	Dec 2, 2014
Robocide	May 11, 2016
Rook on Open File	Apr 24, 2017
Rook On Seventh	May 24, 2009
Scorpio	Mar 28, 2018
Shield	May 17, 2017
Sloppy	Sep 17, 2016
Spike	Jan 7, 2016
Strategic Test Suite	Dec 19, 2016
SuperChess	Dec 7, 2016
Teki	Mar 29, 2018
Wasp	Nov 24, 2017
WyldChess	Mar 10, 2018

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

Sequential Logic

GerdIsenberg — Wed, 10 May 2017 09:02:48 GMT

Home * Hardware * Sequential Logic

		A Sequential Logic is a digital circuit where one or more outputs are boolean functions of multiple inputs and the history of the outputs. In contrast to combinatorial logic, a sequential logic requires memory to somehow feed the history of the outputs back to the inputs. Usually, for deterministic and reliable behavior considering internal latencies and propagation delays, a sequential logic is synchronous, that is the memory only change their content on the edge of a clock signal.
Sequential circuit ^[1]

Applications

Sequential Rook Attack

Applications

Sequential logic, that is combinatorial logic combined with memory, is the base of Finite-state machines, Turing machines as well as digital computers.

Sequential Rook Attack

As an further example, a sequential logic may perform the same task as mentioned in Combinatorial Attack and Defend Map, but with less gates in up to seven cycles - similar to the bitboard techniques like Dumb7Fill:

                                             +-------+
                                +------+     |       |
 o--/64/-- empty(square) -/64/--| 64:1 |---->|       |-----o result reliable / otherwise processing after reset
                                +------+     | Comb. |-----o A8 is attacked by white rook from south
                                   ^         | Logic |
                                +------+     |       |
 o--/64/-- wrook(square) -/64/--| 64:1 |---->|       |-->--+
                                +-----.+     |       |     |
                                   ^      o->|       |     |
                                 /6|      |  +-------+     |
                                   |      |                v
                                +--------------+           |
                                |              |           |
                                |    Latch     |<----------+
                     reset o----|              |
                                +---^----------+
                                    |
                                   clk

Publications

Alan H. Bond (1987). Broadcasting Arrays - A Highly Parallel Computer Architecture Suitable For Easy Fabrication. pdf
Alan Clements (2005). Sequential Logic. pdf

External Links

References

^ Sequential Logic

What links here?

Page	Date Edited
BCP	Dec 30, 2015
Belle	Jan 18, 2018
CHEOPS	Apr 18, 2015
ChipTest	Jun 19, 2016
Combinatorial Logic	Apr 6, 2017
Data	Nov 26, 2017
Electro-Mechanical	May 2, 2016
FPGA	Jul 9, 2016
Hardware	Jan 20, 2018
Memory	Dec 8, 2017
Process	Jul 31, 2017
Pseudorandom number generator	May 11, 2017
Queue	Apr 4, 2017
Sequential Logic	May 10, 2017
Sliding Piece Attacks	May 27, 2016
Space-Time Tradeoff	Jun 17, 2015

Up one Level

Sherwin Bitboards

GerdIsenberg — Wed, 20 Mar 2013 12:47:36 GMT

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

The Sherwin bitboards were created by Michael Sherwin with some help from other people in CCC ^[1]. The idea is to generate the attacks of a sliding piece by collecting all occupied squares on its rays for each row. Then use a first lookup table to get an index into a second table that contains the attack bitboards. Most of the hard work is done in the initialization of the tables. Care must be taken with the right order and enumeration of the table indizes. The code below is taken from the chess engine Elephant and it uses the same big-endian file-mapping as the exploding bitboards.

Bishops

These are the relevant squares for a bishop on d4. We don't have to look at pieces at the border of the board to decide whether their squares can be attacked or defended.

 . . . . . . . -
 - . . . . . 1 .  giving 1 bit  or 2 different values from row 7
 . 1 . . . 1 . .  giving 2 bits or 4 different values from row 6
 . . 1 . 1 . . .  giving 2 bits or 4 different values from row 5
 . . . B . . . .  giving 0 bits or 0 different values from row 4
 . . 1 . 1 . . .  giving 2 bits or 4 different values from row 3
 . 1 . . . 1 . .  giving 2 bits or 4 different values from row 2
 - . . . . . - .

We need an helper array and an initializing function for the rays. This mask covers the inner 6x6 board only.

Bitboard bishopBits[64];
void initBishopBits()
{
    int sq;
    for ( sq = 0; sq < 64; ++sq )
    {
        bishopBits[sq] = 0;
        int i;
        for ( i = sq - 9; i >= 0 && i % 8 != 7; i -= 9 )
            bishopBits[sq] |= C64(1) << i;
        for ( i = sq - 7; i >= 0 && i % 8 != 0; i -= 7 )
            bishopBits[sq] |= C64(1) << i;
        for ( i = sq + 9; i < 64 && i % 8 != 0; i += 9 )
            bishopBits[sq] |= C64(1) << i;
        for ( i = sq + 7; i < 64 && i % 8 != 7; i += 7 )
            bishopBits[sq] |= C64(1) << i;
        bishopBits[sq] &= C64(0x007e7e7e7e7e7e00);
    }
}

With the help of a first table we condense the scattered bits to a compact index number. For bits named a to i the value for Bd4 will be:

 . . . . . . . -
 - . . . . . i .  giving 1 bit  or 2 different values from row 7
 . g . . . h . .  giving 2 bits or 4 different values from row 6
 . . e . f . . .  giving 2 bits or 4 different values from row 5
 . . . B . . . .  giving 0 bits or 0 different values from row 4
 . . c . d . . .  giving 2 bits or 4 different values from row 3
 . a . . . b . .  giving 2 bits or 4 different values from row 2
 - . . . . . - .
 
-> 0x0000000ihgfedcba as index. With 2^9 = 512 index values.

There are 4 squares with 9 bits like Bd4. Other squares need another amount of bits.

const byte squareBitsB[64] =
{
  6, 5, 5, 5, 5, 5, 5, 6,
  5, 5, 5, 5, 5, 5, 5, 5,
  5, 5, 7, 7, 7, 7, 5, 5,
  5, 5, 7, 9, 9, 7, 5, 5,
  5, 5, 7, 9, 9, 7, 5, 5,
  5, 5, 7, 7, 7, 7, 5, 5,
  5, 5, 5, 5, 5, 5, 5, 5,
  6, 5, 5, 5, 5, 5, 5, 6,
};

Here is how much values of the first table we need. That is also the size of the second table.

 4 squares with 9 bits for 512 indices are 2048 indices.
12 squares with 7 bits for 128 indices are 1536 indices.
44 squares with 5 bits for  32 indices are 1408 indices.
 4 squares with 6 bits for  64 indices are  256 indices.
                                     Total 5248 indices.

This is the layout of the first big table with index-bits for each square and all rows. The indices are in this order:

0000999999999 4 times 9 bit
0001999999999
0010999999999
0011999999999
0100007777777 12 times 7 bit
01....7777777
0110117777777
0111000666666 4 times 6 bit
0111001666666
0111010666666
0111011666666
0111100055555 44 times 5 bit
........55555
1010001155555

And here is the initializing function.

short int bishopRows[64][6][64];
void initBishopRows()
{
    int baseIndex = 0;
    for ( int bits = 9; bits >= 5; --bits )
    {
        for ( int sq = 0; sq < 64; ++sq )
        {
            if ( squareBitsB[sq] != bits )
                continue;
            Bitboard bb = bishopBits[sq];
            bb >>= 9;
            int shift = 0;
            for ( int row = 0; row < 6; ++row )
            {
                int p = (bb >> (row * 8)) & 0x3f;
                for ( int pattern = 0; pattern < 64; ++pattern )
                {
                    int index = 0;
                    int s = shift;
                    for ( int i = 0; i < 6; ++i )
                    {
                        if ( p & (1 << i) )
                        {
                            index |= ( (pattern & (1 << i)) ? (1 << s) : 0 );
                            s++;
                            if ( pattern == 63 )
                                shift++;
                        }
                    }
                    bishopRows[sq][row][pattern] = baseIndex + index;
                }
            }
            baseIndex += (1 << bits);
        }
    }
}

A second table with 5248 entries can hold all bishop attack bitboards. This table must also be initialized.

Bitboard bishopAttackTable[5248];
void initBishopAttacks()
{
    int baseIndex = 0;
    for ( int bits = 9; bits >= 5; --bits )
    {
        for ( int sq = 0; sq < 64; ++sq )
        {
            if ( squareBitsB[sq] != bits )
                continue;
            Bitboard bb = bishopBits[sq];
            for ( int index = 0; index < (1 << bits); ++ index )
            {
                Bitboard occ = 0;
                int i = index;
                for ( int rsq = 0; rsq < 64; ++rsq )
                {
                    if ( bb.test_bit( rsq ) )
                    {
                        if ( i & 1 )
                            occ.set_bit( rsq );
                        i >>= 1;
                    }
                }
                Bitboard att = 0;
                int j;
                for ( j = sq + 9; j < 64 && (j & 7) != 0; j += 9 )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                for ( j = sq + 7; j < 64 && (j & 7) != 7; j += 7 )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                for ( j = sq - 9; j >= 0 && (j & 7) != 7; j -= 9 )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                for ( j = sq - 7; j >= 0 && (j & 7) != 0; j -= 7 )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                bishopAttackTable[baseIndex + index] = att;
            }
            baseIndex += (1 << bits);
        }
    }
}

Ok, here comes the function to get the bishop attack bitboard for a square and occupied bitboard.

Bitboard bishopAttacks( int sq, Bitboard occ )
{
    // The remaining blocking pieces in the X-rays
    occ  &= bishopBits[sq];
    occ >>= 9;
    // Since every square has its set of row values the six row lookups
    // simply map any blockers to specific bits that when ored together
    // gives an offset in the bishop attack table.
    short int *bRows = &bishopRows[sq][0][0];
    int index = (bRows +   0)[(occ >>  0) & 0x3f]  // row 2
              | (bRows +  64)[(occ >>  8) & 0x3f]  // row 3
              | (bRows + 128)[(occ >> 16) & 0x3f]  // row 4
              | (bRows + 192)[(occ >> 24) & 0x3f]  // row 5
              | (bRows + 256)[(occ >> 32) & 0x3f]  // row 6
              | (bRows + 320)[(occ >> 40) & 0x3f]; // row 7
    return bishopAttackTable[index];
}

Perhaps you should look at this function first to understand the algorithm.

After the creation of the lookup tables which is only done once the often used bishopAttacks() function is rather easy and performant. And it is branchless.

There is a possible modification of this function that uses unions rather than >> and &. Some people believe that is faster. But it depends on big and little endianess.

#if BIG_ENDIAN() && !LITTLE_ENDIAN()
// Big end first means row 8 is first byte with my square encoding.
struct BBBytes
{
    unsigned char row8;
    unsigned char row7;
    unsigned char row6;
    unsigned char row5;
    unsigned char row4;
    unsigned char row3;
    unsigned char row2;
    unsigned char row1;
};
#elif LITTLE_ENDIAN() && !BIG_ENDIAN()
// Little end first means row 1 is first byte with my square encoding.
struct BBBytes
{
    unsigned char row1;
    unsigned char row2;
    unsigned char row3;
    unsigned char row4;
    unsigned char row5;
    unsigned char row6;
    unsigned char row7;
    unsigned char row8;
};
#else
    #error big little endian
#endif
 
union BBUnion
{
    Bits64   bb;    // typedef uint64 Bits64;
    BBBytes  bbb;
};
 
Bitboard bishopAttacks( int sq, Bitboard occ )
{
    // The remaining blocking pieces in the X-rays
    occ  &= bishopBits[sq];
    occ >>= 1;
    BBUnion occu;
    occu.bb = occ;
    // Since every square has its set of row values the six row lookups
    // simply map any blockers to specific bits that when ored together
    // gives an offset in the bishop attack table.
    short int *bRows = &bishopRows[sq][0][0];
    int index = (bRows +   0)[occu.bbb.row2]  // row 2
              | (bRows +  64)[occu.bbb.row3]  // row 3
              | (bRows + 128)[occu.bbb.row4]  // row 4
              | (bRows + 192)[occu.bbb.row5]  // row 5
              | (bRows + 256)[occu.bbb.row6]  // row 6
              | (bRows + 320)[occu.bbb.row7]; // row 7
    return bishopAttackTable[index];
}

Rooks

Rooks are mostly treated like the bishops. It starts with their rays.

Bitboard rookBits[64];
void initRookBits()
{
    int sq;
    for ( sq = 0; sq < 64; ++sq )
    {
        rookBits[sq] = 0;
        int i;
        for ( i = sq - 1; i >= 0 && i % 8 != 7; --i )
            rookBits[sq] |= C64(1) << i;
        for ( i = sq - 8; i >= 0; i -= 8 )
            rookBits[sq] |= C64(1) << i;
        for ( i = sq + 1; i < 64 && i % 8 != 0; ++i )
            rookBits[sq] |= C64(1) << i;
        for ( i = sq + 8; i < 64; i += 8 )
            rookBits[sq] |= C64(1) << i;
        if ( (sq & 7) != 7 )
            rookBits[sq] &= C64(0x7f7f7f7f7f7f7f7f);
        if ( (sq & 7) != 0 )
            rookBits[sq] &= C64(0xfefefefefefefefe);
        if ( (sq / 8) != 7 )
            rookBits[sq] &= C64(0x00ffffffffffffff);
        if ( (sq / 8) != 0 )
            rookBits[sq] &= C64(0xffffffffffffff00);
    }
}

There are 36 squares with 10 bits like Rd4. Other squares need another amount of bits.

const byte squareBitsR[64] =
{
  12, 11, 11, 11, 11, 11, 11, 12,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  12, 11, 11, 11, 11, 11, 11, 12,
};

This is the layout of the first big table with index-bits for each square and all rows. The indices are in this order:

00000cccccccccccc 4 times 12 bit
00001cccccccccccc
00010cccccccccccc
00011cccccccccccc
001000bbbbbbbbbbb 24 times 11 bit
0.....bbbbbbbbbbb
100111bbbbbbbbbbb
1010000aaaaaaaaaa 36 times 10 bit
.......aaaaaaaaaa
1110011aaaaaaaaaa

For rooks we need a bigger second table. It has 102400 entries. This makes even the first table bigger because it can not use 2 byte short integer values. And the last dimension of the first table has to cover all 8 bits of a row. This is because rooks on file a or h have rays along the outside files.

Here is the initializing function.

int rookRows[64][8][256];
void initRookRows()
{
    int baseIndex = 0;
    for ( int bits = 12; bits >= 10; --bits )
    {
        for ( int sq = 0; sq < 64; ++sq )
        {
            if ( squareBitsR[sq] != bits )
                continue;
            Bitboard bb = rookBits[sq];
            int shift = 0;
            for ( int row = 0; row < 8; ++row )
            {
                int p = (bb >> (row * 8)) & 0xff;
                for ( int pattern = 0; pattern < 256; ++pattern )
                {
                    int index = 0;
                    int s = shift;
                    for ( int i = 0; i < 8; ++i )
                    {
                        if ( p & (1 << i) )
                        {
                            index |= ( (pattern & (1 << i)) ? (1 << s) : 0 );
                            s++;
                            if ( pattern == 255 )
                                shift++;
                        }
                    }
                    rookRows[sq][row][pattern] = baseIndex + index;
                    //logf << "rookRows " << sq << " " << row << " " << pattern << " : ";
                    //logf << rookRows[sq][row][pattern] << endl;
                }
            }
            baseIndex += (1 << bits);
        }
    }
}

A second table with 102400 entries can hold all rook attack bitboards. This table must also be initialized.

Bitboard rookAttackTable[102400];
void initRookAttacks()
{
    int baseIndex = 0;
    for ( int bits = 12; bits >= 10; --bits )
    {
        for ( int sq = 0; sq < 64; ++sq )
        {
            if ( squareBitsR[sq] != bits )
                continue;
            Bitboard bb = rookBits[sq];
            for ( int index = 0; index < (1 << bits); ++ index )
            {
                Bitboard occ = 0;
                int i = index;
                for ( int rsq = 0; rsq < 64; ++rsq )
                {
                    if ( bb.test_bit( rsq ) )
                    {
                        if ( i & 1 )
                            occ.set_bit( rsq );
                        i >>= 1;
                    }
                }
                Bitboard att = 0;
                int j;
                for ( j = sq + 1; j < 64 && (j & 7) != 0; ++j )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                for ( j = sq + 8; j < 64; j += 8 )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                for ( j = sq - 1; j >= 0 && (j & 7) != 7; --j )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                for ( j = sq - 8; j >= 0; j -= 8 )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                rookAttackTable[baseIndex + index] = att;
            }
            baseIndex += (1 << bits);
        }
    }
}

Ok, here comes the function to get the bishop attack bitboard for a square and occupied bitboard.

Bitboard rookAttacks( int sq, Bitboard occ )
{
    // The remaining blocking pieces in the +-rays
    occ &= rookBits[sq];
    // Since every square has its set of row values the six row lookups
    // simply map any blockers to specific bits that when ored together
    // gives an offset in the bishop attack table.
    int *rRows = &rookRows[sq][0][0];
    int index = (rRows +    0)[(occ >>  0) & 0xff]  // row 1
              | (rRows +  256)[(occ >>  8) & 0xff]  // row 2
              | (rRows +  512)[(occ >> 16) & 0xff]  // row 3
              | (rRows +  768)[(occ >> 24) & 0xff]  // row 4
              | (rRows + 1024)[(occ >> 32) & 0xff]  // row 5
              | (rRows + 1280)[(occ >> 40) & 0xff]  // row 6
              | (rRows + 1536)[(occ >> 48) & 0xff]  // row 7
              | (rRows + 1792)[(occ >> 56) & 0xff]; // row 8
    return rookAttackTable[index];
}

Bitboard rookAttacks( int sq, Bitboard occ )
{
    // The remaining blocking pieces in the +-rays
    occ &= rookBits[sq];
    BBUnion occu;
    occu.bb = occ;
    // Since every square has its set of row values the six row lookups
    // simply map any blockers to specific bits that when ored together
    // gives an offset in the bishop attack table.
    int *rRows = &rookRows[sq][0][0];
    int index = (rRows +    0)[occu.bbb.row1]  // row 1
              | (rRows +  256)[occu.bbb.row2]  // row 2
              | (rRows +  512)[occu.bbb.row3]  // row 3
              | (rRows +  768)[occu.bbb.row4]  // row 4
              | (rRows + 1024)[occu.bbb.row5]  // row 5
              | (rRows + 1280)[occu.bbb.row6]  // row 6
              | (rRows + 1536)[occu.bbb.row7]  // row 7
              | (rRows + 1792)[occu.bbb.row8]; // row 8
    return rookAttackTable[index];
}

Results

The results of the functions bishopAttacks() and rookAttacks() can be used in the same way as described in exploding bitboards.

References

^ New bitboard move generator by Michael Sherwin, Winboard Forum, September 14, 2006

What links here?

Page	Date Edited
Elephant	Sep 19, 2016
Harald Lüßen	Mar 20, 2013
Michael Sherwin	Dec 18, 2017
RomiChess	Jan 2, 2018
Sherwin Bitboards	Mar 20, 2013
Sliding Piece Attacks	May 27, 2016

Up one Level

Wikispaces : chessprogramming - items matching description

Butterfly Boards

Table of Contents

Layout

Valid Entries

The Eponym

The Butterfly

Single Shape

Connected Shapes

C-Code

Analogy in Astronomy

See also

Publications

External links

Wikipedia

Musicvideo

References

What links here?

Combinatorial Logic

Table of Contents

Implementation

Basic Operations

AND

Truth Table

Symbols and Circuits

OR

Truth Table

Symbols and Circuits

NOT

Truth Table

Symbols and Circuits

Derived Operations

NAND

Truth Table

Symbols and Circuits

NOR

Truth Table

Symbols and Circuits

XOR

Truth Table

Symbols and Circuits

DNF and CNF

ALU

Adder

Combinatorial Attacks

C Syntax

Circuit

See also

External Links

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?

Evaluation of Pieces

Table of Contents

Pawn

Knight

Bishop

Rook

Queen

King

See also

Forum Posts

References

What links here?

Exploding Bitboards

Table of Contents

Bishops