understanding fixed shift fancy magic bitboard generation

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

krismchess
Posts: 24
Joined: Tue Oct 13, 2015 2:52 am

Re: understanding fixed shift fancy magic bitboard generatio

Post by krismchess »

Great & Thanks for prompt response Gerd.

How do find the overlapping index as in:

Code: Select all

struct MagicInit {
    unsigned long long factor;
    int index; // this one
};
In general I have a question about reusing the generated magics by someone for e.g. the magics generated by Volker - can I use them as it is in my engine and claim that I am the author of the engine? Even doing so I'd first want to understand how those magics are generated .. copying the code isn't my intention!
--
Thanks,
Kalyan
Never Give UP!
Top
Gerd Isenberg
Posts: 2250
Joined: Wed Mar 08, 2006 8:47 pm
Location: Hattingen, Germany

Re: understanding fixed shift fancy magic bitboard generatio

Post by Gerd Isenberg »

CPW is formally Creative Commons Attribution Share-Alike 3.0 License, I consider code snippets in the public domain. For code snippets from CCC or Winboard Forum, I don't know exactly, but to mention someone's code or constants for piece attacks in a readme.txt seems fine to me, specially if it was someone's intension to publish and share (and possibly verify) the code. As Volker Annuss posts here from time to time, you may also ask him per pm for explicit permission to use his constants if they work for you.

However, using magic constants for deterministic sliding piece attack is another quality and are a less serious matter than say using other people's piece-square tables ...
Top
krismchess
Posts: 24
Joined: Tue Oct 13, 2015 2:52 am

Re: understanding fixed shift fancy magic bitboard generatio

Post by krismchess »

Thanks Gerd.

Back to the first part of my question - how to determine the index that is along with the magic factor?
--
Thanks,
Kalyan
Never Give UP!
Top
Gerd Isenberg
Posts: 2250
Joined: Wed Mar 08, 2006 8:47 pm
Location: Hattingen, Germany

Re: understanding fixed shift fancy magic bitboard generatio

Post by Gerd Isenberg »

krismchess wrote: How do find the overlapping index as in:

Code: Select all

struct MagicInit {
    unsigned long long factor;
    int index; // this one
};
Only the factor is not appropriate to find the index - you'll need the whole context. If you have a homogeneous, two dimensional array indexed by square[0..63] and occupancy[0..4095] index, the usual memory layout is

Code: Select all

sq[0] -> offset 0
sq[1] -> offset 4096
sq[i] -> offset i * 4096
But you can design you own pointer or offset array - not necessarily in square order. That requires a whole optimization framework, not only in finding magics per square, but also how to pack or interleave them.
Top
Volker Annuss
Posts: 180
Joined: Mon Sep 03, 2007 9:15 am

Re: understanding fixed shift fancy magic bitboard generatio

Post by Volker Annuss »

First I create the magic numbers as described in the wiki. For each square and each piece type I create up to three magic numbers, one that uses a small lookup table for that square and two others that have gaps (consecutive unused entries) in their tables. Larger gaps are preferred over many small ones.

Second I try to build a compact global lookup table. This is done by inserting the per square tables into the global one. They are always inserted into the first position that fits. Threshold accepting is used as optimization algorithm to get an insertion order that gives a small global table.
Starting with a random insertion sequence some modifications are done to the insertion order or another magic number is chosen for a square. These modifications are accepted if the global table becomes smaller and even if it grows by less than a threshold. The threshold is large at the beginning and is lowered step by step during the optimization until it reaches zero and only improvements are accepted.

Here is the smallest table I got so far. You may use this one or any other one in your engine.

Code: Select all

unsigned long long lookup_table[89524];

struct
{
    unsigned long long factor;
    int position;
}
bishop_magics[64] =
{
	{ 0x0000404040404040u,  33104 },
	{ 0x0000a060401007fcu,   4094 },
	{ 0x0000401020200000u,  24764 },
	{ 0x0000806004000000u,  13882 },
	{ 0x0000440200000000u,  23090 },
	{ 0x0000080100800000u,  32640 },
	{ 0x0000104104004000u,  11558 },
	{ 0x0000020020820080u,  32912 },
	{ 0x0000040100202004u,  13674 },
	{ 0x0000020080200802u,   6109 },
	{ 0x0000010040080200u,  26494 },
	{ 0x0000008060040000u,  17919 },
	{ 0x0000004402000000u,  25757 },
	{ 0x00000021c100b200u,  17338 },
	{ 0x0000000400410080u,  16983 },
	{ 0x000003f7f05fffc0u,  16659 },
	{ 0x0004228040808010u,  13610 },
	{ 0x0000200040404040u,   2224 },
	{ 0x0000400080808080u,  60405 },
	{ 0x0000200200801000u,   7983 },
	{ 0x0000240080840000u,     17 },
	{ 0x000018000c03fff8u,  34321 },
	{ 0x00000a5840208020u,  33216 },
	{ 0x0000058408404010u,  17127 },
	{ 0x0002022000408020u,   6397 },
	{ 0x0000402000408080u,  22169 },
	{ 0x0000804000810100u,  42727 },
	{ 0x000100403c0403ffu,    155 },
	{ 0x00078402a8802000u,   8601 },
	{ 0x0000101000804400u,  21101 },
	{ 0x0000080800104100u,  29885 },
	{ 0x0000400480101008u,  29340 },
	{ 0x0001010102004040u,  19785 },
	{ 0x0000808090402020u,  12258 },
	{ 0x0007fefe08810010u,  50451 },
	{ 0x0003ff0f833fc080u,   1712 },
	{ 0x007fe08019003042u,  78475 },
	{ 0x0000202040008040u,   7855 },
	{ 0x0001004008381008u,  13642 },
	{ 0x0000802003700808u,   8156 },
	{ 0x0000208200400080u,   4348 },
	{ 0x0000104100200040u,  28794 },
	{ 0x0003ffdf7f833fc0u,  22578 },
	{ 0x0000008840450020u,  50315 },
	{ 0x0000020040100100u,  85452 },
	{ 0x007fffdd80140028u,  32816 },
	{ 0x0000202020200040u,  13930 },
	{ 0x0001004010039004u,  17967 },
	{ 0x0000040041008000u,  33200 },
	{ 0x0003ffefe0c02200u,  32456 },
	{ 0x0000001010806000u,   7762 },
	{ 0x0000000008403000u,   7794 },
	{ 0x0000000100202000u,  22761 },
	{ 0x0000040100200800u,  14918 },
	{ 0x0000404040404000u,  11620 },
	{ 0x00006020601803f4u,  15925 },
	{ 0x0003ffdfdfc28048u,  32528 },
	{ 0x0000000820820020u,  12196 },
	{ 0x0000000010108060u,  32720 },
	{ 0x0000000000084030u,  26781 },
	{ 0x0000000001002020u,  19817 },
	{ 0x0000000040408020u,  24732 },
	{ 0x0000004040404040u,  25468 },
	{ 0x0000404040404040u,  10186 }
},

rook_magics[64] =
{
	{ 0x00280077ffebfffeu,  41305 },
	{ 0x2004010201097fffu,  14326 },
	{ 0x0010020010053fffu,  24477 },
	{ 0x0030002ff71ffffau,   8223 },
	{ 0x7fd00441ffffd003u,  49795 },
	{ 0x004001d9e03ffff7u,  60546 },
	{ 0x004000888847ffffu,  28543 },
	{ 0x006800fbff75fffdu,  79282 },
	{ 0x000028010113ffffu,   6457 },
	{ 0x0020040201fcffffu,   4125 },
	{ 0x007fe80042ffffe8u,  81021 },
	{ 0x00001800217fffe8u,  42341 },
	{ 0x00001800073fffe8u,  14139 },
	{ 0x007fe8009effffe8u,  19465 },
	{ 0x00001800602fffe8u,   9514 },
	{ 0x000030002fffffa0u,  71090 },
	{ 0x00300018010bffffu,  75419 },
	{ 0x0003000c0085fffbu,  33476 },
	{ 0x0004000802010008u,  27117 },
	{ 0x0002002004002002u,  85964 },
	{ 0x0002002020010002u,  54915 },
	{ 0x0001002020008001u,  36544 },
	{ 0x0000004040008001u,  71854 },
	{ 0x0000802000200040u,  37996 },
	{ 0x0040200010080010u,  30398 },
	{ 0x0000080010040010u,  55939 },
	{ 0x0004010008020008u,  53891 },
	{ 0x0000040020200200u,  56963 },
	{ 0x0000010020020020u,  77451 },
	{ 0x0000010020200080u,  12319 },
	{ 0x0000008020200040u,  88500 },
	{ 0x0000200020004081u,  51405 },
	{ 0x00fffd1800300030u,  72878 },
	{ 0x007fff7fbfd40020u,    676 },
	{ 0x003fffbd00180018u,  83122 },
	{ 0x001fffde80180018u,  22206 },
	{ 0x000fffe0bfe80018u,  75186 },
	{ 0x0001000080202001u,    681 },
	{ 0x0003fffbff980180u,  36453 },
	{ 0x0001fffdff9000e0u,  20369 },
	{ 0x00fffeebfeffd800u,   1981 },
	{ 0x007ffff7ffc01400u,  13343 },
	{ 0x0000408104200204u,  10650 },
	{ 0x001ffff01fc03000u,  57987 },
	{ 0x000fffe7f8bfe800u,  26302 },
	{ 0x0000008001002020u,  58357 },
	{ 0x0003fff85fffa804u,  40546 },
	{ 0x0001fffd75ffa802u,      0 },
	{ 0x00ffffec00280028u,  14967 },
	{ 0x007fff75ff7fbfd8u,  80361 },
	{ 0x003fff863fbf7fd8u,  40905 },
	{ 0x001fffbfdfd7ffd8u,  58347 },
	{ 0x000ffff810280028u,  20381 },
	{ 0x0007ffd7f7feffd8u,  81868 },
	{ 0x0003fffc0c480048u,  59381 },
	{ 0x0001ffffafd7ffd8u,  84404 },
	{ 0x00ffffe4ffdfa3bau,  45811 },
	{ 0x007fffef7ff3d3dau,  62898 },
	{ 0x003fffbfdfeff7fau,  45796 },
	{ 0x001fffeff7fbfc22u,  66994 },
	{ 0x0000020408001001u,  67204 },
	{ 0x0007fffeffff77fdu,  32448 },
	{ 0x0003ffffbf7dfeecu,  62946 },
	{ 0x0001ffff9dffa333u,  17005 }
};
Top
krismchess
Posts: 24
Joined: Tue Oct 13, 2015 2:52 am

Re: understanding fixed shift fancy magic bitboard generatio

Post by krismchess »

Volker Annuss wrote:First I create the magic numbers as described in the wiki. For each square and each piece type I create up to three magic numbers, one that uses a small lookup table for that square and two others that have gaps (consecutive unused entries) in their tables. Larger gaps are preferred over many small ones.

Second I try to build a compact global lookup table. This is done by inserting the per square tables into the global one. They are always inserted into the first position that fits. Threshold accepting is used as optimization algorithm to get an insertion order that gives a small global table.
Starting with a random insertion sequence some modifications are done to the insertion order or another magic number is chosen for a square. These modifications are accepted if the global table becomes smaller and even if it grows by less than a threshold. The threshold is large at the beginning and is lowered step by step during the optimization until it reaches zero and only improvements are accepted.

Here is the smallest table I got so far. You may use this one or any other one in your engine.

Code: Select all

unsigned long long lookup_table[89524];

struct
{
    unsigned long long factor;
    int position;
}
bishop_magics[64] =
{
	{ 0x0000404040404040u,  33104 },
	{ 0x0000a060401007fcu,   4094 },
	{ 0x0000401020200000u,  24764 },
	{ 0x0000806004000000u,  13882 },
	{ 0x0000440200000000u,  23090 },
	{ 0x0000080100800000u,  32640 },
	{ 0x0000104104004000u,  11558 },
	{ 0x0000020020820080u,  32912 },
	{ 0x0000040100202004u,  13674 },
	{ 0x0000020080200802u,   6109 },
	{ 0x0000010040080200u,  26494 },
	{ 0x0000008060040000u,  17919 },
	{ 0x0000004402000000u,  25757 },
	{ 0x00000021c100b200u,  17338 },
	{ 0x0000000400410080u,  16983 },
	{ 0x000003f7f05fffc0u,  16659 },
	{ 0x0004228040808010u,  13610 },
	{ 0x0000200040404040u,   2224 },
	{ 0x0000400080808080u,  60405 },
	{ 0x0000200200801000u,   7983 },
	{ 0x0000240080840000u,     17 },
	{ 0x000018000c03fff8u,  34321 },
	{ 0x00000a5840208020u,  33216 },
	{ 0x0000058408404010u,  17127 },
	{ 0x0002022000408020u,   6397 },
	{ 0x0000402000408080u,  22169 },
	{ 0x0000804000810100u,  42727 },
	{ 0x000100403c0403ffu,    155 },
	{ 0x00078402a8802000u,   8601 },
	{ 0x0000101000804400u,  21101 },
	{ 0x0000080800104100u,  29885 },
	{ 0x0000400480101008u,  29340 },
	{ 0x0001010102004040u,  19785 },
	{ 0x0000808090402020u,  12258 },
	{ 0x0007fefe08810010u,  50451 },
	{ 0x0003ff0f833fc080u,   1712 },
	{ 0x007fe08019003042u,  78475 },
	{ 0x0000202040008040u,   7855 },
	{ 0x0001004008381008u,  13642 },
	{ 0x0000802003700808u,   8156 },
	{ 0x0000208200400080u,   4348 },
	{ 0x0000104100200040u,  28794 },
	{ 0x0003ffdf7f833fc0u,  22578 },
	{ 0x0000008840450020u,  50315 },
	{ 0x0000020040100100u,  85452 },
	{ 0x007fffdd80140028u,  32816 },
	{ 0x0000202020200040u,  13930 },
	{ 0x0001004010039004u,  17967 },
	{ 0x0000040041008000u,  33200 },
	{ 0x0003ffefe0c02200u,  32456 },
	{ 0x0000001010806000u,   7762 },
	{ 0x0000000008403000u,   7794 },
	{ 0x0000000100202000u,  22761 },
	{ 0x0000040100200800u,  14918 },
	{ 0x0000404040404000u,  11620 },
	{ 0x00006020601803f4u,  15925 },
	{ 0x0003ffdfdfc28048u,  32528 },
	{ 0x0000000820820020u,  12196 },
	{ 0x0000000010108060u,  32720 },
	{ 0x0000000000084030u,  26781 },
	{ 0x0000000001002020u,  19817 },
	{ 0x0000000040408020u,  24732 },
	{ 0x0000004040404040u,  25468 },
	{ 0x0000404040404040u,  10186 }
},

rook_magics[64] =
{
	{ 0x00280077ffebfffeu,  41305 },
	{ 0x2004010201097fffu,  14326 },
	{ 0x0010020010053fffu,  24477 },
	{ 0x0030002ff71ffffau,   8223 },
	{ 0x7fd00441ffffd003u,  49795 },
	{ 0x004001d9e03ffff7u,  60546 },
	{ 0x004000888847ffffu,  28543 },
	{ 0x006800fbff75fffdu,  79282 },
	{ 0x000028010113ffffu,   6457 },
	{ 0x0020040201fcffffu,   4125 },
	{ 0x007fe80042ffffe8u,  81021 },
	{ 0x00001800217fffe8u,  42341 },
	{ 0x00001800073fffe8u,  14139 },
	{ 0x007fe8009effffe8u,  19465 },
	{ 0x00001800602fffe8u,   9514 },
	{ 0x000030002fffffa0u,  71090 },
	{ 0x00300018010bffffu,  75419 },
	{ 0x0003000c0085fffbu,  33476 },
	{ 0x0004000802010008u,  27117 },
	{ 0x0002002004002002u,  85964 },
	{ 0x0002002020010002u,  54915 },
	{ 0x0001002020008001u,  36544 },
	{ 0x0000004040008001u,  71854 },
	{ 0x0000802000200040u,  37996 },
	{ 0x0040200010080010u,  30398 },
	{ 0x0000080010040010u,  55939 },
	{ 0x0004010008020008u,  53891 },
	{ 0x0000040020200200u,  56963 },
	{ 0x0000010020020020u,  77451 },
	{ 0x0000010020200080u,  12319 },
	{ 0x0000008020200040u,  88500 },
	{ 0x0000200020004081u,  51405 },
	{ 0x00fffd1800300030u,  72878 },
	{ 0x007fff7fbfd40020u,    676 },
	{ 0x003fffbd00180018u,  83122 },
	{ 0x001fffde80180018u,  22206 },
	{ 0x000fffe0bfe80018u,  75186 },
	{ 0x0001000080202001u,    681 },
	{ 0x0003fffbff980180u,  36453 },
	{ 0x0001fffdff9000e0u,  20369 },
	{ 0x00fffeebfeffd800u,   1981 },
	{ 0x007ffff7ffc01400u,  13343 },
	{ 0x0000408104200204u,  10650 },
	{ 0x001ffff01fc03000u,  57987 },
	{ 0x000fffe7f8bfe800u,  26302 },
	{ 0x0000008001002020u,  58357 },
	{ 0x0003fff85fffa804u,  40546 },
	{ 0x0001fffd75ffa802u,      0 },
	{ 0x00ffffec00280028u,  14967 },
	{ 0x007fff75ff7fbfd8u,  80361 },
	{ 0x003fff863fbf7fd8u,  40905 },
	{ 0x001fffbfdfd7ffd8u,  58347 },
	{ 0x000ffff810280028u,  20381 },
	{ 0x0007ffd7f7feffd8u,  81868 },
	{ 0x0003fffc0c480048u,  59381 },
	{ 0x0001ffffafd7ffd8u,  84404 },
	{ 0x00ffffe4ffdfa3bau,  45811 },
	{ 0x007fffef7ff3d3dau,  62898 },
	{ 0x003fffbfdfeff7fau,  45796 },
	{ 0x001fffeff7fbfc22u,  66994 },
	{ 0x0000020408001001u,  67204 },
	{ 0x0007fffeffff77fdu,  32448 },
	{ 0x0003ffffbf7dfeecu,  62946 },
	{ 0x0001ffff9dffa333u,  17005 }
};
Thanks Volker. Can you please share the code that is used to generate the lookup table i.e. the one you've generated above?
--
Thanks,
Kalyan
Never Give UP!
Top

Return to “Computer Chess Club: Programming and Technical Discussions”