How to find magic bitboards?

Question

const int BitTable[64] = {
  63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2,
  51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52,
  26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28,
  58, 20, 37, 17, 36, 8
};

int pop_1st_bit(uint64 *bb) {
  uint64 b = *bb ^ (*bb - 1);
  unsigned int fold = (unsigned) ((b & 0xffffffff) ^ (b >> 32));
  *bb &= (*bb - 1);
  return BitTable[(fold * 0x783a9b23) >> 26];
}

uint64 index_to_uint64(int index, int bits, uint64 m) {
  int i, j;
  uint64 result = 0ULL;
  for(i = 0; i < bits; i++) {
    j = pop_1st_bit(&m);
    if(index & (1 << i)) result |= (1ULL << j);
  }
  return result;
}

It's from the Chess Programming Wiki:
https://www.chessprogramming.org/Looking_for_Magics

It's part of some code for finding magic numbers.

The argument uint64 m is a bitboard representing the possible blocked squares for either a rook or bishop move. Example for a rook on the e4 square:

0 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 1 0 0 0 
0 1 1 1 0 1 1 0 
0 0 0 0 1 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 0 

The edge squares are zero because they always block, and reducing the number of bits needed is apparently helpful.

/* Bitboard, LSB to MSB, a1 through h8:
 * 56 - - - - - - 63
 *  - - - - - - - -
 *  - - - - - - - -
 *  - - - - - - - -
 *  - - - - - - - -
 *  - - - - - - - -
 *  - - - - - - - -
 *  0 - - - - - - 7
 */

So in the example above, index_to_uint64 takes an index (0 to 2^bits), and the number of bits set in the bitboard (10), and the bitboard.

It then pops_1st_bit for each number of bits, followed by another shifty bit of code. pops_1st_bit XORs the bitboard with itself minus one (why?). Then it ANDs it with a full 32-bits, and somewhere around here my brain runs out of RAM. Somehow the magical hex number 0x783a9b23 is involved (is that the number sequence from Lost?). And there is this ridiculous mystery array of randomly ordered numbers from 0-63 (BitTable[64]).

Answer 1

Alright, I have it figured out.

First, some terminology:

blocker mask: A bitboard containing all squares that can block a piece, for a given piece type and the square the piece is on. It excludes terminating edge squares because they always block.

blocker board: A bitboard containing occupied squares. It only has squares which are also in the blocker mask.

move board: A bitboard containing all squares a piece can move to, given a piece type, a square, and a blocker board. It includes terminating edge squares if the piece can move there.

Example for a rook on the e4 square, and there are some random pieces on e2, e5, e7, b4, and c4.

 The blocker mask        A blocker board         The move board
 0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0         0 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0         0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0 
 0 1 1 1 0 1 1 0         0 1 1 0 0 0 0 0         0 0 1 1 0 1 1 1 
 0 0 0 0 1 0 0 0         0 0 0 0 0 0 0 0         0 0 0 0 1 0 0 0 
 0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 

Some things to note:

• The blocker mask is always the same for a given square and piece type (either rook or bishop).
• Blocker boards include friendly & enemy pieces, and it is a subset of the blocker mask.
• The resulting move board may include moves that capture your own pieces, however these moves are easily removed afterward: moveboard &= ~friendly_pieces)

The goal of the magic numbers method is to very quickly look up a pre-calculated move board for a given blocker board. Otherwise you'd have to (slowly) calculate the move board every time. This only applies to sliding pieces, namely the rook and bishop. The queen is just a combination of the rook and bishop.

Magic numbers can be found for each square & piece type combo. To do this, you have to calculate every possible blocker board variation for each square/piece combo. This is what the code in question is doing. How it's doing it is still a bit of a mystery to me, but that also seems to be the case for the apparent original author, Matt Taylor. (Thanks to @Pradhan for the link)

So what I've done is re-implemented the code for generating all possible blocker board variations. It uses a different technique, and while it's a little slower, it's much easier to read and comprehend. The fact that it's slightly slower is not a problem, because this code isn't speed critical. The program only has to do it once at program startup, and it only takes microseconds on a dual-core i5.

/* Generate a unique blocker board, given an index (0..2^bits) and the blocker mask 
 * for the piece/square. Each index will give a unique blocker board. */
static uint64_t gen_blockerboard (int index, uint64_t blockermask) 
{
    /* Start with a blockerboard identical to the mask. */
    uint64_t blockerboard = blockermask;

    /* Loop through the blockermask to find the indices of all set bits. */
    int8_t bitindex = 0;
    for (int8_t i=0; i<64; i++) {
        /* Check if the i'th bit is set in the mask (and thus a potential blocker). */
        if ( blockermask & (1ULL<<i) ) {
            /* Clear the i'th bit in the blockerboard if it's clear in the index at bitindex. */
            if ( !(index & (1<<bitindex)) ) {
                blockerboard &= ~(1ULL<<i); //Clear the bit.
            }
            /* Increment the bit index in the 0-4096 index, so each bit in index will correspond 
             * to each set bit in blockermask. */
            bitindex++;
        }
    }
    return blockerboard;
}

To use it, do something like this:

int bits = count_bits( RookBlockermask[square] );
/* Generate all (2^bits) blocker boards. */ 
for (int i=0; i < (1<<bits); i++) {
    RookBlockerboard[square][i] = gen_blockerboard( i, RookBlockermask[square] );
}

How it works: There are 2^bits blocker boards, where bits is the number of 1's in the blocker mask, which are the only relevant bits. Also, each integer from 0 to 2^bits has a unique sequence of 1's and 0's of length bits. So this function just corresponds each bit in the given integer to a relevant bit in the blocker mask, and turns it off/on accordingly to generate a unique blocker board.

It's not as clever or fast, but it's readable.