Moderator: Andres Valverde
Pradu wrote: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.
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.Gerd Isenberg wrote:
Looks like you already resigned on the 11-bit key issue - due to snooby?
Lasse's hashkeys.c wrote: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
...
Gerd wrote: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
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
Really clever. So what you are doing isLasse Hansen wrote: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
Key = OccupancyALL & mask[sq]
Index = Key*magic[sq]>>shift[sq]
Moves = *(Ptr[sq]+Index) & postmask[sq]
The top post is from Wed Aug 23, 2006 4:06 pm so yes it was a while back.bob wrote: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...
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.Lasse Hansen wrote: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
attacks = *(aptr[sq]+index) & maskfull[sq]
attacks = RookAttacks[rookindex[sqr]+address] & maskfull[sq]
Lasse Hansen wrote: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
Pradu wrote: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 wrote:Pradu wrote: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.
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];
Pradu wrote:What I had stated in this post was wrong. Too bad I can't delete this post anymore.
Scratch that.Zach Wegner wrote:Actually, I think the theoretical max is 4 rooks
What is a conditional square?Zach Wegner wrote: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...)
Return to Programming and Technical Discussions
Users browsing this forum: No registered users and 5 guests