List of magics for bitboard move geneartion

[Pradu]

A good set of magic keys for bitboard move generation can be found here:

http://www.prism.gatech.edu/~gtg365v/Bu ... magics.txt

Sune Fischer and I are wiriting a program to produce a comparison in speed between rotated and magic move generation. I guess we shall post the source and results here to see if magic move generation outperforms rotated at modern hardware.

[Gerd Isenberg]

A good set of magic keys for bitboard move generation can be found here:

http://www.prism.gatech.edu/~gtg365v/Bu ... magics.txt

Sune Fischer and I are wiriting a program to produce a comparison in speed between rotated and magic move generation. I guess we shall post the source and results here to see if magic move generation outperforms rotated at modern hardware.

Looks like you already resigned on the 11-bit key issue - due to snooby?

Is the goal a perft-test, a test inside for instance crafty, or a complete own open source program under some public licence?
I would like to compete with my 1.5KByte approach as well - with a slightly improved 64-bit version

Best regards to Sune as well.

Cheers,
Gerd

[Pradu]

Looks like you already resigned on the 11-bit key issue - due to snooby?

Snooby is a genius algorithm I must admit! 11 bit keys exist for most squares but not for all squares. Taking a look at Lasse's keys, he dosen't have all 11 bit keys, some are 12 bit. So it isn't truly a 11 bit magic set. Usually if a key is possible it is generated very quickly by the popcount-iterative approach. I have also produced keys that are the least I could find for each square and these are probably going to be the keys being used in my move generator (including many 8-10 bit keys for rooks). These are the minimal+n hash keys in the text file (minimal bits + extra bits). The 9 bit keys and the 12 bit keys are just for the sake of completeness for move generation that require the same shift for each square in the hash function -- but I guess the minimal+n bits can also be used as 9 bit / 12 bit keys if needed.

const U64 HashKeyRook[64]={
0x0880008210604000, // H8 12
0x6040012001401000, // H7 11
0x0200100920820041, // H6 11
0x0200104020182e00, // H5 11
0x4b00080003001014, // H4 11
0x7100088900024400, // H3 11
0x02000c3e00010088, // H2 11
0xe600004085062204, // H1 12
0x1002800040128020, // G8 11
...

Is the goal a perft-test, a test inside for instance crafty, or a complete own open source program under some public licence?
I would like to compete with my 1.5KByte approach as well - with a slightly improved 64-bit version

Best regards to Sune as well.

Cheers,
Gerd

The initial idea was to take one of Sune's old rotated bitboard move generators, because I'm not as experienced in writing efficient rotated bitboard move generators; but then I decided to write a new one that will be easier to read/modify. I will make the program opensource.

[Pradu]

Ok here's the smallest I could get the bishops and rooks.

Bishops in 41k and rooks in 800k

Code: Select all

Bishops
=======
Shifts
58, 59, 59, 59, 59, 59, 59, 58,
59, 59, 59, 59, 59, 59, 59, 59,
59, 59, 57, 57, 57, 57, 59, 59,
59, 59, 57, 55, 55, 57, 59, 59,
59, 59, 57, 55, 55, 57, 59, 59,
59, 59, 57, 57, 57, 57, 59, 59,
59, 59, 59, 59, 59, 59, 59, 59,
58, 59, 59, 59, 59, 59, 59, 58,

Indecies
4992, 2624,  256,  896, 1280, 1664, 4800, 5120,
2560, 2656,  288,  928, 1312, 1696, 4832, 4928,
   0,  128,  320,  960, 1344, 1728, 2304, 2432,
  32,  160,  448, 2752, 3776, 1856, 2336, 2464,
  64,  192,  576, 3264, 4288, 1984, 2368, 2496,
  96,  224,  704, 1088, 1472, 2112, 2400, 2528,
2592, 2688,  832, 1216, 1600, 2240, 4864, 4960,
5056, 2720,  864, 1248, 1632, 2272, 4896, 5184,

Magics
0x0002020202020200, 0x0002020202020000, 0x0004010202000000, 0x0004040080000000, 0x0001104000000000,

0x0000821040000000, 0x0000410410400000, 0x0000104104104000,
0x0000040404040400, 0x0000020202020200, 0x0000040102020000, 0x0000040400800000, 0x0000011040000000,

0x0000008210400000, 0x0000004104104000, 0x0000002082082000,
0x0004000808080800, 0x0002000404040400, 0x0001000202020200, 0x0000800802004000, 0x0000800400A00000,

0x0000200100884000, 0x0000400082082000, 0x0000200041041000,
0x0002080010101000, 0x0001040008080800, 0x0000208004010400, 0x0000404004010200, 0x0000840000802000,

0x0000404002011000, 0x0000808001041000, 0x0000404000820800,
0x0001041000202000, 0x0000820800101000, 0x0000104400080800, 0x0000020080080080, 0x0000404040040100,

0x0000808100020100, 0x0001010100020800, 0x0000808080010400,
0x0000820820004000, 0x0000410410002000, 0x0000082088001000, 0x0000002011000800, 0x0000080100400400,

0x0001010101000200, 0x0002020202000400, 0x0001010101000200,
0x0000410410400000, 0x0000208208200000, 0x0000002084100000, 0x0000000020880000, 0x0000001002020000,

0x0000040408020000, 0x0004040404040000, 0x0002020202020000,
0x0000104104104000, 0x0000002082082000, 0x0000000020841000, 0x0000000000208800, 0x0000000010020200,

0x0000000404080200, 0x0000040404040400, 0x0002020202020200,

DB num_entries = 5248

Rooks
=====
Shifts
52, 53, 53, 53, 53, 53, 53, 52,
53, 54, 54, 54, 54, 54, 54, 53,
53, 54, 54, 54, 54, 54, 54, 53,
53, 54, 54, 54, 54, 54, 54, 53,
53, 54, 54, 54, 54, 54, 54, 53,
53, 54, 54, 54, 54, 54, 54, 53,
53, 54, 54, 54, 54, 54, 54, 53,
52, 53, 53, 53, 53, 53, 53, 52,

Indecies
86016, 73728, 36864, 43008, 47104, 51200, 77824, 94208,
69632, 32768, 38912, 10240, 14336, 53248, 57344, 81920,
24576, 33792,  6144, 11264, 15360, 18432, 58368, 61440,
26624,  4096,  7168,     0,  2048, 19456, 22528, 63488,
28672,  5120,  8192,  1024,  3072, 20480, 23552, 65536,
30720, 34816,  9216, 12288, 16384, 21504, 59392, 67584,
71680, 35840, 39936, 13312, 17408, 54272, 60416, 83968,
90112, 75776, 40960, 45056, 49152, 55296, 79872, 98304,

Magics
0x0080001020400080, 0x0040001000200040, 0x0080081000200080, 0x0080040800100080, 0x0080020400080080,

0x0080010200040080, 0x0080008001000200, 0x0080002040800100,
0x0000800020400080, 0x0000400020005000, 0x0000801000200080, 0x0000800800100080, 0x0000800400080080,

0x0000800200040080, 0x0000800100020080, 0x0000800040800100,
0x0000208000400080, 0x0000404000201000, 0x0000808010002000, 0x0000808008001000, 0x0000808004000800,

0x0000808002000400, 0x0000010100020004, 0x0000020000408104,
0x0000208080004000, 0x0000200040005000, 0x0000100080200080, 0x0000080080100080, 0x0000040080080080,

0x0000020080040080, 0x0000010080800200, 0x0000800080004100,
0x0000204000800080, 0x0000200040401000, 0x0000100080802000, 0x0000080080801000, 0x0000040080800800,

0x0000020080800400, 0x0000020001010004, 0x0000800040800100,
0x0000204000808000, 0x0000200040008080, 0x0000100020008080, 0x0000080010008080, 0x0000040008008080,

0x0000020004008080, 0x0000010002008080, 0x0000004081020004,
0x0000204000800080, 0x0000200040008080, 0x0000100020008080, 0x0000080010008080, 0x0000040008008080,

0x0000020004008080, 0x0000800100020080, 0x0000800041000080,
0x0000102040800101, 0x0000102040008101, 0x0000081020004101, 0x0000040810002101, 0x0001000204080011,

0x0001000204000801, 0x0001000082000401, 0x0000002040810402,

DB num_entries = 102400

[Lasse Hansen]

Hi!

It is possible to get even smaller tables than 41k+800k by using a post-mask in the move generation. If as indices, one uses:

U32 IdxKeyRook[64]={
8192, 34816, 36864, 38912, 40960, 43008, 45056, 12288,
34816, 8192, 38912, 36864, 43008, 40960, 12288, 45056,
32768, 30720, 0, 5120, 6144, 1024, 49152, 47104,
30720, 28672, 5120, 0, 1024, 6144, 47104, 49152,
28672, 26624, 4096, 3072, 2048, 7168, 53248, 51200,
26624, 24576, 3072, 4096, 7168, 2048, 51200, 53248,
24576, 20480, 61440, 63488, 57344, 59392, 16384, 55296,
20480, 65536, 63488, 61440, 59392, 57344, 55296, 16384,
}; // 67584 entries

U32 IdxKeyBishop[64]={
1728, 1472, 1632, 1632, 1632, 1632, 1568, 1344,
1728, 1472, 1600, 1600, 1600, 1600, 1568, 1344,
1728, 1472, 1152, 1152, 1152, 1152, 1568, 1344,
1728, 1472, 0, 0, 0, 0, 1568, 1344,
1280, 1504, 512, 512, 512, 512, 1536, 1408,
1280, 1504, 1024, 1024, 1024, 1024, 1536, 1408,
1280, 1504, 1664, 1664, 1664, 1664, 1536, 1408,
1280, 1504, 1696, 1696, 1696, 1696, 1536, 1408,
}; // 1792 entries

one is down to around 14.3k (+0.5k) + 540k (+0.5k) of lookups. The new masks must include all borders (i.e. no 64 bit trick). Works for me!

Regards, Lasse

[H.G.Muller]

Didn't Harald Lüßen already do this test comprehensively?

[Pradu]

Hi!

It is possible to get even smaller tables than 41k+800k by using a post-mask in the move generation. If as indices, one uses:

U32 IdxKeyRook[64]={
8192, 34816, 36864, 38912, 40960, 43008, 45056, 12288,
34816, 8192, 38912, 36864, 43008, 40960, 12288, 45056,
32768, 30720, 0, 5120, 6144, 1024, 49152, 47104,
30720, 28672, 5120, 0, 1024, 6144, 47104, 49152,
28672, 26624, 4096, 3072, 2048, 7168, 53248, 51200,
26624, 24576, 3072, 4096, 7168, 2048, 51200, 53248,
24576, 20480, 61440, 63488, 57344, 59392, 16384, 55296,
20480, 65536, 63488, 61440, 59392, 57344, 55296, 16384,
}; // 67584 entries

U32 IdxKeyBishop[64]={
1728, 1472, 1632, 1632, 1632, 1632, 1568, 1344,
1728, 1472, 1600, 1600, 1600, 1600, 1568, 1344,
1728, 1472, 1152, 1152, 1152, 1152, 1568, 1344,
1728, 1472, 0, 0, 0, 0, 1568, 1344,
1280, 1504, 512, 512, 512, 512, 1536, 1408,
1280, 1504, 1024, 1024, 1024, 1024, 1536, 1408,
1280, 1504, 1664, 1664, 1664, 1664, 1536, 1408,
1280, 1504, 1696, 1696, 1696, 1696, 1536, 1408,
}; // 1792 entries

one is down to around 14.3k (+0.5k) + 540k (+0.5k) of lookups. The new masks must include all borders (i.e. no 64 bit trick). Works for me!

Regards, Lasse

Really clever. So what you are doing is

Code: Select all

Key = OccupancyALL & mask[sq]
Index = Key*magic[sq]>>shift[sq]
Moves = *(Ptr[sq]+Index) & postmask[sq]


And instead in each move-bitboard in the database you will have multiple sets of moves that you will & out? You should still be able to use the 64-trick for mask[sq] right (as long as the moves are entirely on different lines)?

[Lasse Hansen]

If you have a rook at A1 and a rook at B2, they will always share the attack targets A2 and B1, but no one else. So yes, there will then be multiple attack bitmaps in the same entry. One only have to mask it out afterwards, using full mask, without the 64 bit trick. For bishops you can have 4 pieces in line, and the only common targets will always be there anyway.

So move generation is done as before, one only apply a bit wider mask to get the wanted attack board.

I havent seen anyone else do this, in http://chessprogramming.wikispaces.com/ it seems that the current minimum is 800k + 39k. Neither here or at Talkchess, unless Ive overseen it of course.

pattern = Allpieces & maskrook64[sqr]; // mask with 64 bit trick
address = (pattern*rookmagic[sq])>>rookshift(sq);
attack = RookAttacks[rookindex[sqr]+address] & maskfull[sqr];
//maskfull have to cover edges
//rookindex[sqr] is the table I gave in the earlier post

It should be easy to implement.

Regards, Lasse

[bob]

also, aren't those magic values the same ones Pradu produced last year? Those are the exact same numbers I have in Crafty and I took the last values posted by Pradu when I made the change to magic generation...

[Pradu]

also, aren't those magic values the same ones Pradu produced last year? Those are the exact same numbers I have in Crafty and I took the last values posted by Pradu when I made the change to magic generation...

The top post is from Wed Aug 23, 2006 4:06 pm so yes it was a while back.

New recent post was by Lasse in this thread.

[Pradu]

If you have a rook at A1 and a rook at B2, they will always share the attack targets A2 and B1, but no one else. So yes, there will then be multiple attack bitmaps in the same entry. One only have to mask it out afterwards, using full mask, without the 64 bit trick. For bishops you can have 4 pieces in line, and the only common targets will always be there anyway.

So move generation is done as before, one only apply a bit wider mask to get the wanted attack board.

I havent seen anyone else do this, in http://chessprogramming.wikispaces.com/ it seems that the current minimum is 800k + 39k. Neither here or at Talkchess, unless Ive overseen it of course.

I believe Grant Osborne was able to get it even smaller by trying to find magics that will hash as sequentially as possible from 0..n without any hits above n. This way you don't have to use the entire 2^numbitsindex entries.

pattern = Allpieces & maskrook64[sqr]; // mask with 64 bit trick
address = (pattern*rookmagic[sq])>>rookshift(sq);
attack = RookAttacks[rookindex[sqr]+address] & maskfull[sqr];
//maskfull have to cover edges
//rookindex[sqr] is the table I gave in the earlier post

It should be easy to implement.

Regards, Lasse

Yes, nobody has done this before. As far as I know, your approach is new. Do you have performance results of the new approach against the one? I'll try to implement it and try to get some benchmarks as well. I'm not a optimization expert; maybe Gerd can help on this but wouldn't

Code: Select all

attacks = *(aptr[sq]+index) & maskfull[sq]

be faster than

Code: Select all

attacks = RookAttacks[rookindex[sqr]+address] & maskfull[sq]

[Gerd Isenberg]

If you have a rook at A1 and a rook at B2, they will always share the attack targets A2 and B1, but no one else. So yes, there will then be multiple attack bitmaps in the same entry. One only have to mask it out afterwards, using full mask, without the 64 bit trick. For bishops you can have 4 pieces in line, and the only common targets will always be there anyway.

So move generation is done as before, one only apply a bit wider mask to get the wanted attack board.

I havent seen anyone else do this, in http://chessprogramming.wikispaces.com/ it seems that the current minimum is 800k + 39k. Neither here or at Talkchess, unless Ive overseen it of course.

pattern = Allpieces & maskrook64[sqr]; // mask with 64 bit trick
address = (pattern*rookmagic[sq])>>rookshift(sq);
attack = RookAttacks[rookindex[sqr]+address] & maskfull[sqr];
//maskfull have to cover edges
//rookindex[sqr] is the table I gave in the earlier post

It should be easy to implement.

Regards, Lasse

Great idea, Lasse!

Bishop sharing is simpler to understand, since there are light and dark colored bishops with disjoint attacks-sets, able to share the precalculated union of two square-attacks.

Your genius trick is to share even equal colored bishops and rooks where both attack-sets are obviously not always disjoint - but all members of the intersection are always set, since they are direct neighbors of both sliders.

The post-masking reminds me a bit on kindergarten bitboards, where 8 ranks and 30 diagonals share one attack-set. At least kindergarten bitboards has the "advantage" to use same mask for occupancy as well for the attack-set

Cheers,
Gerd

[Pradu]

What I had stated in this post was wrong. Too bad I can't delete this post anymore.

[Gerd Isenberg]

Yes, nobody has done this before. As far as I know, your approach is new. Do you have performance results of the new approach against the one? I'll try to implement it and try to get some benchmarks as well. I'm not a optimization expert; maybe Gerd can help on this but wouldn't

Code: Select all

attacks = *(aptr[sq]+index) & maskfull[sq]

be faster than

Code: Select all

attacks = RookAttacks[rookindex[sqr]+address] & maskfull[sq]

Yes, but it might be negligible. RookAttacks[] is a const pointer and we need to add offset or index[sq] at runtime. This addition is already done at compile time, if stored as pointers[64]. 512 instead of 256 byte (in 64-bit mode sizeof(pointer) == 8 ) to safe one add or lea looks like a good trade-off.

[Gerd Isenberg]

Yes, nobody has done this before. As far as I know, your approach is new. Do you have performance results of the new approach against the one? I'll try to implement it and try to get some benchmarks as well. I'm not a optimization expert; maybe Gerd can help on this but wouldn't

Code: Select all

attacks = *(aptr[sq]+index) & maskfull[sq]

be faster than

Code: Select all

attacks = RookAttacks[rookindex[sqr]+address] & maskfull[sq]

Yes, but it might be negligible. RookAttacks[] is a const pointer and we need to add offset or index[sq] at runtime. This addition is already done at compile time, if stored as pointers[64]. 512 instead of 256 byte (in 64-bit mode sizeof(pointer) == 8 ) to safe one add or lea looks like a good trade-off.

There is another issue with 32-byte alignment, possibly favoring offsets instead of pointer - if we keep masks/magic/pointer/shift inside a structure. In 64-bit mode it might be better to split the struct, which is not necessary with 32-bit offsets. As always - one has to try

Code: Select all

struct SMagicParm
{
    U64  preMask;
    U64  postMask;
    U64  magic;
    U64* pointer; // 4 versus 8 byte
    U32  shift;
} mp[64]; // 36 versus 32 bytes

// probably better
U64  preMask[64];
U64  postMask[64];
U64  magic[64];
U64* pointer[64];
U32  shift[64];


[Gerd Isenberg]

What I had stated in this post was wrong. Too bad I can't delete this post anymore.

HeHe - brain storming and thinking out loud
Annother idea is to overlap attack sets of different squares a bit. There are still a lot of gaps. I think <= 512KByte is possible. There are so many possibilities to recombine and overlap the attack-arrays.

[Zach Wegner]

I was thinking this at first, but I don't think it will be possible, at least easily. Theoretically you can have up to 8 rooks stored in the same bitboard, but the problem is that for each intersection of rays you need to make sure that the intersection square maps to the same bit index for each square's magic. You can ignore that in Lasse's solution because the squares are always attacked.

Actually, I think the theoretical max is 4 rooks, because you can't have a conditional square in a rook's attack set intersect with an unconditional square in another rook's. I.e. Two rooks on A1 and B4, the magic bits have to determine B1 and A4 when those are always set in one of the rook's sets. (Does that make sense? I sometimes wonder if I say exactly what I'm thinking...)

Without that, there is just one square to gain, as the IdxKeyRook table has only 2 entries that aren't duplicated.

[Zach Wegner]

Actually, I think the theoretical max is 4 rooks

Scratch that.

[diag]R7/1R6/8/3R4/4R3/8/6R1/7R w - -[/diag]

[Pradu]

Actually, I think the theoretical max is 4 rooks, because you can't have a conditional square in a rook's attack set intersect with an unconditional square in another rook's. I.e. Two rooks on A1 and B4, the magic bits have to determine B1 and A4 when those are always set in one of the rook's sets. (Does that make sense? I sometimes wonder if I say exactly what I'm thinking...)

What is a conditional square?

[Zach Wegner]

A conditional square is one that might or might not be set, depending on the bits in the index. For all the sliders, its just the squares that are more than one square away from it. The unconditional squares are the squares right next to the slider, that it will attack no matter what other pieces are on the board.

I'm pretty sure the theoretical max for rooks is six. You can have unconditional squares overlap, or conditional squares overlap, but they can't overlap each other (Well, I guess they could, but each time they do requires an extra bit in the index).