Magics

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
wgarvin
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm
Location: British Columbia, Canada

Re: Magics

Post by wgarvin » Fri May 20, 2011 2:03 pm

cms271828 wrote: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).

User avatar
cms271828
Posts: 316
Joined: Wed Apr 12, 2006 8:47 pm

Re: Magics

Post by cms271828 » Fri May 20, 2011 6:06 pm

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?
Colin

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: Magics

Post by kbhearn » Fri May 20, 2011 6:37 pm

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

grant
Posts: 67
Joined: Mon Aug 06, 2007 2:42 pm
Location: London, England

Re: Magics

Post by grant » Mon May 23, 2011 11:58 am

Mdb just stands for "Magic DataBase"

Grant

Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: Magics

Post by Edmund » Tue May 24, 2011 9:35 am

grant wrote: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
Posts: 67
Joined: Mon Aug 06, 2007 2:42 pm
Location: London, England

Re: Magics

Post by grant » Tue May 24, 2011 11:06 am

Hello Edmund

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

Grant

grant
Posts: 67
Joined: Mon Aug 06, 2007 2:42 pm
Location: London, England

Re: Magics

Post by grant » Tue May 24, 2011 1:55 pm

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

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Magics

Post by Don » Tue May 24, 2011 5:33 pm

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
Posts: 20358
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Magics

Post by bob » Tue May 24, 2011 6:34 pm

Don wrote: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
Posts: 2111
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Magics

Post by Gerd Isenberg » Tue May 24, 2011 6:57 pm

grant wrote: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

Post Reply