Magic Move Generation

[Pradu]

You have to consider that we mask off the outer squares. Thus for a rook on h1 one bit for the six rank-bits, and three further bit-factors to somehow shift and squeeze the six file-bit to the upper 12 seems the minimum.

Code: Select all

0x008080808080807E
 . . . . . . . .
 . . . . . . . 1
 . . . . . . . 1
 . . . . . . . 1
 . . . . . . . 1
 . . . . . . . 1
 . . . . . . . 1
 . 1 1 1 1 1 1 .

Thanks, picture makes me understand why 1 bit is sufficient for horizontal rook attacks. But diagonals and verticals still unclear.

My question is not idle. Each square attack table have a set significant attack bitboards separated by unused space. Used and unused bitboards seems to have a regular pattern, so it is probably possible to find a simple way to gather all separate squares hash tables in a one big hash table with less total size. At least bishops have a simple odd/even regularity, so it may be possible to interlace light/dark correspondent squares data together.

Simply working out the magic shifted by the each bit in the key (what I did here) or doing it the other way around (key shifted by every bit in the magic...but I find this way harder to visualize because what you shift is changing) should make it clear why 5 bits are enough to shift all the relevant bits into the upper bits:

Code: Select all

key(H8) =  something & 0x008080808080807E
magic(H8) = 0x0080002040800100

indexmapping = magic*key = 
(starting from LSB to MSB)
Start with 0
If bit 1 in the key is "on", add on 0x0100004081000200
10000000
00000000
00000000
00000010
10000001
00000000
01000000
00000000

If bit 2 in the key is "on", add on 0x0200008102000400
01000000
00000000
00000000
10000001
01000000
00000000
00100000
00000000

If bit 3 in the key is "on", add on 0x0400010204000800
00100000
00000000
10000000
01000000
00100000
00000000
00010000
00000000

If bit 4 in the key is "on", add on 0x0800020408001000
00010000
00000000
01000000
00100000
00010000
00000000
00001000
00000000

If bit 5 in the key is "on", add on 0x1000040810002000
00001000
00000000
00100000
00010000
00001000
00000000
00000100
00000000

If bit 6 in the key is "on", add on 0x2000081020004000
00000100
00000000
00010000
00001000
00000100
00000000
00000010
00000000

If bit 15 in the key is "on", add on 0x0010204000800000
00000000
00001000
00000100
00000010
00000000
00000001
00000000
00000000
If bit 23 in the key is "on", add on 0x1020400080000000
00001000
00000100
00000010
00000000
00000001
00000000
00000000
00000000

If bit 31 in the key is "on", add on 0x2040008000000000
00000100
00000010
00000000
00000001
00000000
00000000
00000000
00000000

If bit 39 in the key is "on", add on 0x4000800000000000
00000010
00000000
00000001
00000000
00000000
00000000
00000000
00000000

If bit 47 in the key is "on", add on 0x0080000000000000
00000000
00000001
00000000
00000000
00000000
00000000
00000000
00000000

If bit 55 in the key is "on", add on 0x8000000000000000
00000001
00000000
00000000
00000000
00000000
00000000
00000000
00000000

The space is not unused. There are move bitboards there are in the database multiple times.

[Aleks Peshkov]

...should make it clear why 5 bits are enough to shift all the relevant bits into the upper bits:

Do you mean that a given 5 bit key for a given square is correct, or 5 bits is sufficient for any magic?

1) Is it true that exists a magic key for any square without need of arithmetic carry side effects for all significant result bits?

2) Is it true that all bits set occupancy bitboard parameter will result to all bits set magic hash value (at least for all keys we do not exploit arithmetic addition carry effects)?

If the first and the second statements are true it will be easy to find all magic keys during engine initialization.

[grant]

Hi

If you look at a bishop on the C8 square, masking off the border, there are a possible 32 different combinations of occupancy for the squares that this bishop can reach. So 5 bits you would expect to be optimal for C8. For square D5 on the other hand there are 512 different combinations of occupancy so 9 bits is optimal.
The thing about magic number generation is that if you search long and hard enough you can find keys that are better than optimal.

Grant

[wgarvin]

You might try a sparse-array-fitting approach. I.e. imagine you had a 2-dimensional array where most of the entries were zero (or something equally predictable). That sparse array could be compressed like this:...

The code of magic bitboard method is:

Code: Select all

return lookup[(occupied & mask) * magic >> shift];

The freedom only in choosing lookup and magic constants.

Exactly. The sparse array packing idea is pretty much, getting the "lookup" constant out of piece-on-square table, and overlapping them wherever that can be done without two different squares hashing some occupancy to the same slot.

Its possible that, even with indexes that are not "optimal" (in the sense of having a minimum number of bits for the number of unique occupancies they are hashing) you might still be able to make good use of space by overlapping several of the larger index ranges. (Maybe, or maybe not---I don't have much experience with magics so I might be totally wrong)

[Aleks Peshkov]

The thing about magic number generation is that if you search long and hard enough you can find keys that are better than optimal.

IMHO better then perfect hash magics would not gain any speed. All recently used cache lines will be in level 1 cache anyway.

I want to avoid the need of large magic numbers table in source code. Redundant unused space is not important in modern PC architecture. Plus-minus 100kB of physical memory is insignificant.

[Pradu]

Hi

If you look at a bishop on the C8 square, masking off the border, there are a possible 32 different combinations of occupancy for the squares that this bishop can reach. So 5 bits you would expect to be optimal for C8. For square D5 on the other hand there are 512 different combinations of occupancy so 9 bits is optimal.
The thing about magic number generation is that if you search long and hard enough you can find keys that are better than optimal.

Grant

When I refer to optimal magic keys I mean the best possible where there arn't any better. I think what you are reffering to are magics that map n number of bits to n number of index bits.

[Pradu]

The thing about magic number generation is that if you search long and hard enough you can find keys that are better than optimal.

IMHO better then perfect hash magics would not gain any speed. All recently used cache lines will be in level 1 cache anyway.

I want to avoid the need of large magic numbers table in source code. Redundant unused space is not important in modern PC architecture. Plus-minus 100kB of physical memory is insignificant.

We haven't found them yet for rooks so we don't know the savings. It could potentially save 2x,4x if we could find magics that are just 1 or 2 bits better for each square.

[Pradu]

...should make it clear why 5 bits are enough to shift all the relevant bits into the upper bits:

Do you mean that a given 5 bit key for a given square is correct, or 5 bits is sufficient for any magic?

1) Is it true that exists a magic key for any square without need of arithmetic carry side effects for all significant result bits?

For bishop attacks it's definitely possible. For the sparse magic we used for the rook on H8 no.

2) Is it true that all bits set occupancy bitboard parameter will result to all bits set magic hash value (at least for all keys we do not exploit arithmetic addition carry effects)?

In general, no. For the cases where it's possible to generate magics with no carry side-effects like for some bishop squares, then yes.

If the first and the second statements are true it will be easy to find all magic keys during engine initialization.

I think it's more practical to use really good magics (like some of the corner square rook magics by Grant which must have taken hours if not days) precomputed and just put them in a table.

[Pradu]

...should make it clear why 5 bits are enough to shift all the relevant bits into the upper bits:

Do you mean that a given 5 bit key for a given square is correct, or 5 bits is sufficient for any magic?

Opps missed this.
I meant the former.

[Gerd Isenberg]

The thing about magic number generation is that if you search long and hard enough you can find keys that are better than optimal.

IMHO better then perfect hash magics would not gain any speed. All recently used cache lines will be in level 1 cache anyway.

I want to avoid the need of large magic numbers table in source code. Redundant unused space is not important in modern PC architecture. Plus-minus 100kB of physical memory is insignificant.

We are talking about magic, shift - 9 bytes per square and bishop/rook? The attack tables and masks are initialized at program startup of course - we need only magic/shift. There seems really no need, to initialize the magics as well - but with predefined shifts see Tord's source again. It is less than one second. Unfortunately looking for denser tables takes "super-exponential" more time, compared to the additional win of space.

Speaking for bishops, a (very fast) four bit snoob works, but produces a table size of 216KByte! Snoob 5 is tad slower, but still acceptable for online initialization and produces 59KByte bishop tables:

Code: Select all

snoobing 4 bit keys
16 squares require a shift of 59 ( 5-bit range)
 4 squares require a shift of 57 ( 7-bit range)
24 squares require a shift of 56 ( 8-bit range)
 4 squares require a shift of 55 ( 9-bit range)
14 squares require a shift of 54 (10-bit range)
 2 squares require a shift of 53 (11-bit range) !!!
  
Magic/Shift[ 0] 0x0000100008000404 53,  64 Lists, 0 Collisions
Magic/Shift[63] 0x0000100008000404 53,  64 Lists, 0 Collisions
27648 Entries -> 216KByte 

snoobing 5 bit keys 
44 squares require a shift of 59 ( 5-bit range)
12 squares require a shift of 57 ( 7-bit range)
 2 squares require a shift of 56 ( 8-bit range)
 4 squares require a shift of 55 ( 9-bit range)
 2 squares require a shift of 54 (10-bit range)
7552 Entries -> 59KByte

snoobing 6 bit keys -> takes a minute
44 squares require a shift of 59 ( 5-bit range)
 4 squares require a shift of 58 ( 6-bit range)
12 squares require a shift of 57 ( 7-bit range)
 4 squares require a shift of 55 ( 9-bit range)
5248 Entries -> 41KByte

The super-optimal mappings due to lot of carries and positive collisions, which require some more computing time, e.g.:

Code: Select all

Magic/Shift[ 1] 0x3c0962a54a77f376 60,  14 Lists,  18 collisions
Magic/Shift[ 8] 0x3c0869a54b34f7f6 60,  15 Lists,  17 Collisions
Magic/Shift[ 9] 0x3c0860a34d3673fe 60,  15 Lists,  17 Collisions
Magic/Shift[14] 0x3c0860a24b13ff77 60,  15 Lists,  17 Collisions
Magic/Shift[15] 0x3c0860a34b353f71 60,  15 Lists,  17 Collisions
Magic/Shift[22] 0x3c0c00a34b357f77 60,  16 Lists,  16 Collisions