paulwal222 - 4 months ago 20

C 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://chessprogramming.wikispaces.com/Looking+for+Magics

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

The argument

`uint64 m`

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

It then

`pops_1st_bit`

`pops_1st_bit`

`BitTable[64]`

Answer

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.