understanding fixed shift fancy magic bitboard generation

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.
Post Reply
Volker Annuss
Posts: 163
Joined: Mon Sep 03, 2007 7:15 am

Re: understanding fixed shift fancy magic bitboard generatio

Post by Volker Annuss » Fri May 06, 2016 7:33 pm

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 12:52 am

Re: understanding fixed shift fancy magic bitboard generatio

Post by krismchess » Sun May 08, 2016 2:07 pm

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
Post Reply

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