Magics

[wgarvin]

Ok, I seem to have fixed it by shifting rooks 52, and bishops 55.

Is that right?

Yes

Rooks need 12 bits (so you shift by 64-12 = 52) and bishops need 9 bits (so you shift by 64-9 = 55).

[cms271828]

Great,

I seem to get a 21% speed up using fixed shifts over the normal magic ones.
Might be faster on 64 bit platform, not sure yet.

I tried this too by Grant Osborne:

Code: Select all

U64 Mdb[79462];

const U64 sqMagic[128] = {
//rooks
0x00A801F7FBFEFFFF, 0xFFB000810113FFFF, 0x0060001F9FF3FFFF, 0x00600C005FF9FFFF, 0xFFA003005FF9FFFF, 0x7F600280089FFFF1, 0x80B000B0029FFFFC, 0x7F50003004C5FFFF,
0xD7FFA0002FFFFFA0, 0xFF005000FDE8FFFF, 0xDAFFA0005FEBFFFF, 0xD9FF400CDF3FFF28, 0xFFFF600F600AFFFF, 0xFFFEC00FC13FFFCE, 0xFFFEC003EEBFFFF1, 0xD48150004A07FFFC,
0xD79F003000E7FFFA, 0xDA680030020BFFFF, 0x732BD20017A1BFFB, 0x01306060094FFFFF, 0x1BA98060061CFFFF, 0x01C1806003005FFF, 0x021BFD00040BFFFA, 0x02F5EE00007BFFC5,
0xF8FFF1918007C000, 0x03FFF037D000C005, 0xB18060320019BFF9, 0x0C35F03A000C1FFC, 0x3C7FFF0100100804, 0x330FFF0100080402, 0x0097FFE0C0060009, 0x0119FFE4B0050004,
0x03FFFD3000600061, 0x03FFFEB800600060, 0xFFFFFF8C00600060, 0xDBFFFE240A001830, 0x72AFFFA040600C00, 0x03CFFFA03FA00600, 0x00AFFFEC82C00C05, 0xC49FFFF8CC8000C5,
0x01FFFDFDD8005000, 0x03FFFDFE6BFFB000, 0xFFFFFFDF603F6000, 0xF41FFE5D3E660010, 0xFF7FEFF1EDF1FFF7, 0x02FFFF9FFDBFA006, 0x01FFFFEEBFFEC005, 0xD64FFFFDF3FEB001,
0xD8FFFF39FF484A00, 0xDF7FFF3FFF486300, 0xDD3FFF99FFAC2E00, 0xDE9FFF31FF2A6A00, 0xDC3FFF19FF15B600, 0xB0FFFFF5FFF28600, 0xDA8FFFE2DFFBFEE0, 0xDB3FFFF5F63C96A0,
0x00FFFF5DFF65CFB6, 0x037FFFBAFFD1C5AE, 0x033FFF71FF6CBCEA, 0x015FFFD9FFD4756E, 0xFFFFFFF5FFF338E6, 0xF7FFFFFE852AC7D5, 0x017FFFEF27EEBE74, 0x05FFFFFF23FF605E,
//bishops
0xED06EFF5367FF600, 0xF0345835BA77FF2B, 0xEC145F68A3F5DAB6, 0xEEFA1863FB56F21D, 0xEF52EB6BFE9D93CD, 0xED40A2927F3420D6, 0xF3774BCD9C7FEC97, 0xEE6034FE99F9FFFF,
0xF3D0746F8D6717F6, 0xF288BACB32E1A3F7, 0xED1AF83CAF1FFB8A, 0xECCE061867F17067, 0xEC0C238EE0CCF92E, 0xEF9760A2937F926E, 0xF28086C9AA93FF14, 0xF2180399B5E5BF87,
0xF0400F342C951FFC, 0xF0A0230579ED8FF0, 0xE40300860032FFFD, 0xE4DC00080B17FD46, 0xE4440022031C1FFB, 0xE4DFA00FD30BFF79, 0xF16C00A4BC9AFFDF, 0xF34200085E9CFFDA,
0xEF9A14560A3DBFBD, 0xEE1A18157B9EAFD1, 0xE466030086002FFE, 0xDCC006000C009010, 0xDC1A002042008040, 0xE4B1CE000470FFC0, 0xEFFD0ACE50BF3F8D, 0xEE3980648434EFD1,
0xEEDFBD7670982A0D, 0xECFFC30301D81A0F, 0xE4FFFB782F7C00C1, 0xDC0440C800008200, 0xDCFFE83400060066, 0xE4FB7DDF0FFE1EFF, 0xEC5F92F861DF4A0A, 0xEDDFD19BAD98A289,
0xF10FD6AA751E400C, 0xF07FF2A63AE9600C, 0xE40FFF6EE50E4A00, 0xE4B7FFFD2704CE04, 0xE4FFFFCCC1500300, 0xE4FFFF4AF05000A0, 0xF0FFA66283556403, 0xF2FFE31969AEC201,
0xF2FFFDFC18AC14BB, 0xF3FFFB96FB568A47, 0xEFD333EFAEEC954D, 0xEFD9A39BF8DC0383, 0xEC921FFF3A814490, 0xED61FDC595CF62A6, 0xF1FF23D3342897AC, 0xF0FFEE36EEE1565C,
0xEC2FFF3E99FCCCC7, 0xF3FFBFECFCFAC5FE, 0xEF8FFF4FF97F7453, 0xEDBFFF83E7F8DC03, 0xECBFFF77FEFA8146, 0xEC5FFF7ED3E2EF60, 0xF2FF7F47243ADCD6, 0xEDFFB65AFABFB3B5
};
U64 *sqIndecies[128] = {
//rooks
Mdb+5630, Mdb+3582, Mdb+1534, Mdb+37316, Mdb+20388, Mdb+25119, Mdb+27167, Mdb+14791,
Mdb+9726, Mdb+59500, Mdb+42975, Mdb+55878, Mdb+24095, Mdb+19364, Mdb+16431, Mdb+34164,
Mdb+12743, Mdb+58913, Mdb+56898, Mdb+54910, Mdb+60524, Mdb+42208, Mdb+43729, Mdb+69224,
Mdb+67176, Mdb+41184, Mdb+49801, Mdb+47756, Mdb+72294, Mdb+73318, Mdb+48777, Mdb+63082,
Mdb+0, Mdb+44753, Mdb+29215, Mdb+46735, Mdb+40194, Mdb+45711, Mdb+39364, Mdb+32133,
Mdb+11774, Mdb+18849, Mdb+35643, Mdb+50816, Mdb+51840, Mdb+57889, Mdb+36292, Mdb+30121,
Mdb+74342, Mdb+27867, Mdb+7085, Mdb+30239, Mdb+38466, Mdb+25931, Mdb+4282, Mdb+75366,
Mdb+65128, Mdb+76390, Mdb+77414, Mdb+61546, Mdb+71270, Mdb+22433, Mdb+78438, Mdb+52862,
//bishops
Mdb+2128, Mdb+7061, Mdb+17455, Mdb+23438, Mdb+26571, Mdb+26603, Mdb+13447, Mdb+26635,
Mdb+19347, Mdb+22766, Mdb+29679, Mdb+30126, Mdb+30158, Mdb+30190, Mdb+24126, Mdb+32569,
Mdb+33393, Mdb+33793, Mdb+1905, Mdb+3056, Mdb+2928, Mdb+2000, Mdb+35817, Mdb+36330,
Mdb+30751, Mdb+32537, Mdb+3944, Mdb+7597, Mdb+10112, Mdb+26443, Mdb+32955, Mdb+33361,
Mdb+33761, Mdb+36298, Mdb+6933, Mdb+20822, Mdb+62570, Mdb+28380, Mdb+40388, Mdb+40635,
Mdb+40667, Mdb+41319, Mdb+36161, Mdb+13319, Mdb+19219, Mdb+29597, Mdb+41576, Mdb+41704,
Mdb+41831, Mdb+42088, Mdb+40891, Mdb+41144, Mdb+41445, Mdb+41957, Mdb+43206, Mdb+45135,
Mdb+43174, Mdb+45151, Mdb+43232, Mdb+43264, Mdb+43685, Mdb+43746, Mdb+45167, Mdb+43778
};

But I don't get what Mdb is, any thoughts?

[kbhearn]

Mdb is the one dimensional lookup table in which you put the attack sets for each index.

[grant]

Mdb just stands for "Magic DataBase"

Grant

[Edmund]

Mdb just stands for "Magic DataBase"

Grant

Hello Grant

May I ask you to comment on the issue brought up by Teemu Pudas in the other board that the magics might not be correct.

Thank you very much in advance.

Edmund

[grant]

Hello Edmund

I think I'll need a translator because I didn't understand a word of what he wrote.

Grant

[grant]

Edmund

I read the initial post in the other forum by Volker Annuss some time ago, and I decided to try for myself to reduce the table size as much as I could. This was my only goal. The post is headed "Fixed shift magics with 800KB lookup table". However, I found that a smaller table could be achieved with variable shift magics which of course requires a lookup table to get the shift. I obviously did not make this clear in my posts.
Anyway, I think that 620Kb is pretty good going though I still maintain that the table can be still further reduced, but the effort required will not be worth the result.
As to the issue of the magics not working... they work for me.

Grant

[Don]

While we are on the subject of magics, I have a question for the developers on this forum.

Is it better to populate a data structure with the move lists for the pieces or just create them from a bitmap stored in the magics destination array? There are some tradeoffs for each method and I have never payed much attention to my move generator (it's the same as it was 3 years ago.)

Any thoughts on this? I'm looking to tweak Komodo's speed and I'm cleaning up some things now.

[bob]

While we are on the subject of magics, I have a question for the developers on this forum.

Is it better to populate a data structure with the move lists for the pieces or just create them from a bitmap stored in the magics destination array? There are some tradeoffs for each method and I have never payed much attention to my move generator (it's the same as it was 3 years ago.)

Any thoughts on this? I'm looking to tweak Komodo's speed and I'm cleaning up some things now.

I think the direct computation is the simplest and fastest. A second level of indirection (move lists for each piece) just adds complexity and only replaces a memory look-up. I tried the piece-list idea years ago (with rotated, not magic) and did not find any improvement at all. It was very slightly slower, and added to the code size as well...

Of course, YMMV, so testing is the only way to answer it for _your_ program. There are way too many unknown interactions within a chess engine already, sometimes adding something makes it faster rather than slower, sometimes deleting code makes it slower, not faster. Etc.

[Gerd Isenberg]

Edmund

I read the initial post in the other forum by Volker Annuss some time ago, and I decided to try for myself to reduce the table size as much as I could. This was my only goal. The post is headed "Fixed shift magics with 800KB lookup table". However, I found that a smaller table could be achieved with variable shift magics which of course requires a lookup table to get the shift. I obviously did not make this clear in my posts.
Anyway, I think that 620Kb is pretty good going though I still maintain that the table can be still further reduced, but the effort required will not be worth the result.
As to the issue of the magics not working... they work for me.

Grant

Teemu's point was - like me assuming fixed rook shifts of (64-12) - that squares 0 and 1 with some possible occupancy collide with the same Mdb index. Better post the shifts next time to make it more clear

Gerd