Magic Bitboards Explained!

[Michael Sherwin]

Gerd's Magic Bitboards explained and
Magic Bitboards explained using fileAttacks() from Gerd's 9.5 KB compromise

Code: Select all

u64 diagonalMask[64];
//  diagonal bits for each square that are a1/h8 orientated

u64 antidiagMask[64];
//  diagonal bits for each square that are h1/a8 orientated

u64 fillUpAttacks[64][8];
//  For every combination of blockers ([64]) there is
//  a bitboard of diagonal and antidiagonal attack sets for every square on a file
//  this is a data compression technique

u64 aFileAttacks[64][8];
//  For every combination of blockers ([64]) there is
//  a bitboard of file attack sets for every rank
//  this is a data compression technique

u8  firstRankAttacks[64][8];
//  For every combination of blockers ([64]) there is
//  a bitrank of rank attack sets for every file
//  this is a data compression technique


u64 rankAttacks(u64 occ, u32 sq) {
   u32 f = sq & 7;
// isolate the file

   u32 r = sq & ~7; // rank * 8
// the number of bits to shift based on the rank

   u32 o = (u32) (occ >> (r+1)) & 63;
// For the occupied set, shift the selected rank to rank one
// sence the first bit is always empty, nudge all bits down one
// and make sure that only valid bits remain (index for [64])

   return (u64)  firstRankAttacks[o][f] << r;
// retrieve and return the attackset after shifting it back to the correct rank
}


u64 fileAttacks(u64 occ, u32 sq) {
   u32 f = sq & 7;
// isolate the file

   occ   =   0x0101010101010101 & (occ   >> f); // a-file
// using an a-file mask select the file bits after haveing shifted them to the a-file
 
   u32 o = ( 0x0080402010080400 *   occ ) >> 58;
// using a 'magic number' multiply it by the a-file bits to propogate them to the a8 rank
// then shift them down to the a1 rank
// this is an easy magic to demonstrate:
// note: that rows containing all zeros have been omitted and
//       that two hex digits have been translated to binary 
//   magic                          0    0 8 0 4 0 2 0 1 0 0 8 0 4 0 0
// * blockers (occ)                 0    1 0 1 0 1 0 1 0 1 0 1 0 1 0 1    rook on a1 with all blockers
//  ____________________________________________________________
// +                             0000 0000 8 0 4 0 2 0 1 0 0 8 0 4 0 0
// +                         0 0 1000 0000 4 0 2 0 1 0 0 8 0 4 0 0
// +                     0 0 8 0 0100 0000 2 0 1 0 0 8 0 4 0 0                     
// +                 0 0 8 0 4 0 0010 0000 1 0 0 8 0 4 0 0   
// +             0 0 8 0 4 0 2 0 0001 0000 0 8 0 4 0 0
// +         0 0 8 0 4 0 2 0 1 0 0000 1000 0 4 0 0
// +     0 0 8 0 4 0 2 0 1 0 0 8 0000 0010 0 0
// + 0 0 8 0 4 0 2 0 1 0 0 8 0 4 0000 0000
// _____________________________________________________________
// = 0 0 8 0 c 0 e 0 f 0 f 8 f c 1111 1100 f c 7 c 3 c 1 c 1 c 0 4 0 0
// here are the relevant bits    _______    that are to be shifted into the low byte 
// (>> 58) here is the 58 bit           _                   
// these bits drop off and are lost     ______________________________
 
// in the set of blockers only the middle 6 bits count, so, if any of them are 0 then its bit from
// the stack of relevant bits will be missing as that row will be all zeros.

edited: this explaination works for bits on a file or a diagonal as they are widely spaced and do not invade the index area
**********************************************************************************************************
*// 'magics' work by using multipication to make parallel shifts of bits in a pattern to a mapped bit
*// in a result. therefore, you can hand create magics by deciding where in the result that you would
*// like a pattern bit to land' and then place a bit in the magic that when shifted in its turn is
*// placed into the correct slot.
*
*// example: 0100000001000000 are the possible bits of a pattern
*//         this pattern will be shifted into bits 25 && 26 then shifted back to bits 1 && 2
*//         this bit 0000000001000000 if it exist in the pattern is to be shifted to slot 25, and will be in the
*//         7th shift, therefore, moveing the bit 6 places to the right from 25 gives this partial magic 1000000000000000000
*//         this bit 0100000000000000 if it exist in the pattern is to be shifted to slot 26, and will be in the
*//          15th shift, therefore, moveing the bit 14 places from 26 to the right gives this partial magic 100000000000
*//          adding the partial magics together will form the complete magic
                                            10000001000000000000
                                                 100000001000000
                                        ________________________
                                       1000000010000000000000000
                              1000000010000000000000000000000000
                              __________________________________
                              1000000011000000010000000000000000
                                      || >> 24

I have no idea how to create an index from a pattern of closely spaced bits as they might be along a rank for rook blockers

[b]Anyone?[/b]

edit2: maybe just get the rank blockers similar to the way Gerd does it and then place them in the first 6 bits and shift the file bits magic index down to bit 7? I need to study pradu's magic for clues!
end edit2
                                             
**********************************************************************************************************
end edit

// extreme compression of data can be achived for indexs of 9 to 16 bits if they are split in half
// and each used to retrieve a possible attack set that when anded together yeilds the true attack set.
// or the indexs are used to retrieve two patial indexs that when combined point to a much smaller table.
// the idea is that half of the attack set is represented many times in the big table with the other half
// being different, so, just lookup each half seperatly in much smaller tables!                   
   
   return  ( aFileAttacks[o][sq>>3]    ) << f;
}

Given the explanations for the rank and files I leave it to the 'student' to understand the diagonals.


correction welcomed

Mike

P.S. You gota be inorder to do this stuff! [/b]

[Gerd Isenberg]

Gerd's Magic Bitboards explained and
Magic Bitboards explained using fileAttacks() from Gerd's 9.5 KB compromise

While your explanation is fine, there is nothing magic with this approach. My proposal is to call it kindergarten-bitboards to distinguish it from the real magic approaches of Lasse or Pradu

The multiplication takes place between file- and diagonal- (or rank) pattern. Since the "Bit-distance" of two ones of the file-pattern is at least eight, and there is only up to one bit per file in the diagonal-pattern, the multiplication becomes a simply copy task without any intermediate overflows. Kindergarten-multiplication - simple take the file-pattern and put it on each "1" of the diagonal-pattern and cut it at the top (overflows to bit 64-127). Thus each one-bit of the diagonal (or rank) pattern becomes the "base" of the multiplied file-pattern. For instance the a-file pattern with bits a-h either 1 or 0 (. is 0 for better reading):

Code: Select all

h . . . . . . .   1 . . . . . . .   a b c d e f g h
g . . . . . . .   . 1 . . . . . .   . a b c d e f g
f . . . . . . .   . . 1 . . . . .   . . a b c d e f
e . . . . . . .   . . . 1 . . . .   . . . a b c d e
d . . . . . . . * . . . . 1 . . . = . . . . a b c d
c . . . . . . .   . . . . . 1 . .   . . . . . a b c
b . . . . . . .   . . . . . . 1 .   . . . . . . a b
a . . . . . . .   . . . . . . . 1   . . . . . . . a



If we use 64*64=128bit multiplication, we really have eight copies of the a-file pattern:

Code: Select all


                                    . . . . . . . .
                                    h . . . . . . .
                                    g h . . . . . .
                                    f g h . . . . .
                                    e f g h . . . .
                                    d e f g h . . .
                                    c d e f g h . .
                                    b c d e f g h .
h . . . . . . .   1 . . . . . . .   a b c d e f g h
g . . . . . . .   . 1 . . . . . .   . a b c d e f g
f . . . . . . .   . . 1 . . . . .   . . a b c d e f
e . . . . . . .   . . . 1 . . . .   . . . a b c d e
d . . . . . . . * . . . . 1 . . . = . . . . a b c d
c . . . . . . .   . . . . . 1 . .   . . . . . a b c
b . . . . . . .   . . . . . . 1 .   . . . . . . a b
a . . . . . . .   . . . . . . . 1   . . . . . . . a


Here we have the up-fill in lower 64 bit and a "below"-fill in the upper 64 bit of the product.

Gerd

[Michael Sherwin]

Gerd's Magic Bitboards explained and
Magic Bitboards explained using fileAttacks() from Gerd's 9.5 KB compromise

While your explanation is fine, there is nothing magic with this approach. My proposal is to call it kindergarten-bitboards to distinguish it from the real magic approaches of Lasse or Pradu

The multiplication takes place between file- and diagonal- (or rank) pattern. Since the "Bit-distance" of two ones of the file-pattern is at least eight, and there is only up to one bit per file in the diagonal-pattern, the multiplication becomes a simply copy task without any intermediate overflows. Kindergarten-multiplication - simple take the file-pattern and put it on each "1" of the diagonal-pattern and cut it at the top (overflows to bit 64-127). Thus each one-bit of the diagonal (or rank) pattern becomes the "base" of the multiplied file-pattern. For instance the a-file pattern with bits a-h either 1 or 0 (. is 0 for better reading):

Code: Select all

h . . . . . . .   1 . . . . . . .   a b c d e f g h
g . . . . . . .   . 1 . . . . . .   . a b c d e f g
f . . . . . . .   . . 1 . . . . .   . . a b c d e f
e . . . . . . .   . . . 1 . . . .   . . . a b c d e
d . . . . . . . * . . . . 1 . . . = . . . . a b c d
c . . . . . . .   . . . . . 1 . .   . . . . . a b c
b . . . . . . .   . . . . . . 1 .   . . . . . . a b
a . . . . . . .   . . . . . . . 1   . . . . . . . a



If we use 64*64=128bit multiplication, we really have eight copies of the a-file pattern:

Code: Select all


                                    . . . . . . . .
                                    h . . . . . . .
                                    g h . . . . . .
                                    f g h . . . . .
                                    e f g h . . . .
                                    d e f g h . . .
                                    c d e f g h . .
                                    b c d e f g h .
h . . . . . . .   1 . . . . . . .   a b c d e f g h
g . . . . . . .   . 1 . . . . . .   . a b c d e f g
f . . . . . . .   . . 1 . . . . .   . . a b c d e f
e . . . . . . .   . . . 1 . . . .   . . . a b c d e
d . . . . . . . * . . . . 1 . . . = . . . . a b c d
c . . . . . . .   . . . . . 1 . .   . . . . . a b c
b . . . . . . .   . . . . . . 1 .   . . . . . . a b
a . . . . . . .   . . . . . . . 1   . . . . . . . a


Here we have the up-fill in lower 64 bit and a "below"-fill in the upper 64 bit of the product.

Gerd

Hi Gerd,

Your way is IMO a kindergarten-magic algorithm for figuring by hand magics for patterns with widely seperated bits.

I butcherd the magic explaination. I did not consider the invasion of closly placed bits into the index area. Once I figure the correction, I will edit my original post.

Mike

[Gerd Isenberg]

Hi Gerd,

Your way is IMO a kindergarten-magic algorithm for figuring by hand magics for patterns with widely seperated bits.

I butcherd the magic explaination. I did not consider the invasion of closly placed bits into the index area. Once I figure the correction, I will edit my original post.

Mike

Of course the point is to get the occupancy a-h (b-g) on a file or diagonal to consecutive bits along a rank or byte.

Code: Select all

h . . . . . . .   1 . . . . . . .   a b c d e f g h
g . . . . . . .   . 1 . . . . . .   . a b c d e f g
f . . . . . . .   . . 1 . . . . .   . . a b c d e f
e . . . . . . .   . . . 1 . . . .   . . . a b c d e
d . . . . . . . * . . . . 1 . . . = . . . . a b c d
c . . . . . . .   . . . . . 1 . .   . . . . . a b c
b . . . . . . .   . . . . . . 1 .   . . . . . . a b
a . . . . . . .   . . . . . . . 1   . . . . . . . a

1 . . . . . . .   a . . . . . . .   a b c d e f g h
1 . . . . . . .   . b . . . . . .   . b c d e f g h
1 . . . . . . .   . . c . . . . .   . . c d e f g h
1 . . . . . . .   . . . d . . . .   . . . d e f g h
1 . . . . . . . * . . . . e . . . = . . . . e f g h
1 . . . . . . .   . . . . . f . .   . . . . . f g h
1 . . . . . . .   . . . . . . g .   . . . . . . g h
1 . . . . . . .   . . . . . . . h   . . . . . . . h


This up-fill is also possible with parallel-prefix shifts, aka Kogge-Stone:

Instead of

Code: Select all

x *= 0x0101010101010101;


one may use

Code: Select all

x = x + (x<<8) + (x<<16) + ... + (x<<56);


or

Code: Select all

x += x <<  8;
x += x << 16;
x += x << 32;


or instead of

Code: Select all

x *= 0x0101010101010101;
x >>= (64-8); // get the high byte


one may use

Code: Select all

x += x >>  8;
x += x >> 16;
x += x >> 32;
x &= 0xff;


We can replace the "add" by "or" since we don't get overflows.
But the "or" even works if we have multiple bits per file, so we can use it for instance to get front- and back-span sets of white or black pawns - even with double and triple-pawns.

Gerd