Magics

[cms271828]

Hi, have been away from site for some time, was wondering if there were any improvement to the magics in magic move generation.

In particular, the shifts for the bishop I have are:

58, 59, 59, 59, 59, 59, 59, 58,
59, 59, 59, 59, 59, 59, 59, 59,
60, 60, 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, 60,
59, 59, 59, 59, 59, 59, 59, 59,
58, 59, 59, 59, 59, 59, 59, 58

Of particular interest are squares 16,17,47 which have been reduced from 59(32 entries) to 60(16 entries) thanks to Richard Pijl.

So perhaps all of the '59 shift' squares can go to '60 shift'. and maybe other squares can also have their tables halved in size too.

So I was curious if any more magics have been produced to improve what I have.

I've tried to figure out how to generate them but appears to be a very difficult problem.
Any thoughts?

[Edmund]

The latest discussions on the topic I am aware of appeared on theWinboard Forum.

regards
Edmund

[Gerd Isenberg]

There are some more bishop squares with N-1 bits:
https://chessprogramming.wikispaces.com ... ics+so+far

The latest trend seems to use fixed shift magics, and magic packing.

[cms271828]

Thanks, those magics seem a good improvement on what I have.

I'm curious about Fixed Shift Magics, I can't seem to see anything that explains what they are/how they work.

Can anyone point me in the right direction...
I see this site has Fixed Shift Magics, http://www.open-aurec.com/wbforum/viewt ... =4&t=51162 but its unclear how to use them.

Thanks

[Edmund]

see https://chessprogramming.wikispaces.com ... ft%20Fancy

The only difference of fixed shift magics is to always shift the product of the magic-multiplication by the constant 52 (=64-12) for rooks and not having to look up a variable in a separate array.

This idea is not new. It just requires more memory for less computation. The novelty is the idea to have the resulting bitboard data overlap.

regards
Edmund

[cms271828]

Thanks, I don't think I get it, but this is what I think I think:

Will use pseduo java code with the ROOK case:
long is 64 bit
int is 32 bit


Consider any occupancy, and any square:
long occ = any_occupancy;
int sq = any_square

Apply mask (identical to magic move generation):
occ &= rook_mask[sq];

Multiply by magic number for that square
occ *= rook_magic[sq];

Get top 12 bits:
int index = (int)( occ >>> 52);


Then is there an array for each square of size 4096?
Moves = magicArray[sq][index];


And this is where I'm stuck, since this is just normal magic move generation but all arrays are large (4096).

Thats as much as I can understand for now

[micron]

Get top 12 bits:
int index = (int)( occ >>> 52);

Then is there an array for each square of size 4096?
Moves = magicArray[sq][index];

And this is where I'm stuck, since this is just normal magic move generation but all arrays are large (4096).

Yes, you have it right. See this thread
http://www.talkchess.com/forum/viewtopi ... at&start=0

Robert P.

[Edmund]

Then is there an array for each square of size 4096?
Moves = magicArray[sq][index];

True .. the size for each square is 4096. But the good thing is, with certain magic keys you can drive the density down. For example with square 0 (the most difficult one to get a proper compression) you can get a density of about 3/4, and the central squares have densities much lower. Now with this in mind you can start "packing" the data in the array.
Onno started off by finding magic keys that minimise the density and maximise the largest gaps between bits and then manually he fitted the tables together.

Eventually you don't have an array magicArray[sq][index] but just magicArray[index] and a second offsetArray[sq], which tells for every square where to start looking for the relevant data in the large array.

regards
Edmund

[cms271828]

Thanks, I set it up using

Code: Select all

unsigned long long lookup_table[97264];

struct
{
    unsigned long long factor;
    int position;
}
bishop_magics[64] =
{
    { 0x007bfeffbfeffbffull,  16530 },
    { 0x003effbfeffbfe08ull,   9162 },
    { 0x0000401020200000ull,   9674 },
    { 0x0000200810000000ull,  18532 },
    { 0x0000110080000000ull,  19172 },
    { 0x0000080100800000ull,  17700 },
    { 0x0007efe0bfff8000ull,   5730 },
    { 0x00000fb0203fff80ull,  19661 },
    { 0x00007dff7fdff7fdull,  17065 },
    { 0x0000011fdff7efffull,  12921 },
    { 0x0000004010202000ull,  15683 },
    { 0x0000002008100000ull,  17764 },
    { 0x0000001100800000ull,  19684 },
    { 0x0000000801008000ull,  18724 },
    { 0x000007efe0bfff80ull,   4108 },
    { 0x000000080f9fffc0ull,  12936 },
    { 0x0000400080808080ull,  15747 },
    { 0x0000200040404040ull,   4066 },
    { 0x0000400080808080ull,  14359 },
    { 0x0000200200801000ull,  36039 },
    { 0x0000240080840000ull,  20457 },
    { 0x0000080080840080ull,  43291 },
    { 0x0000040010410040ull,   5606 },
    { 0x0000020008208020ull,   9497 },
    { 0x0000804000810100ull,  15715 },
    { 0x0000402000408080ull,  13388 },
    { 0x0000804000810100ull,   5986 },
    { 0x0000404004010200ull,  11814 },
    { 0x0000404004010040ull,  92656 },
    { 0x0000101000804400ull,   9529 },
    { 0x0000080800104100ull,  18118 },
    { 0x0000040400082080ull,   5826 },
    { 0x0000410040008200ull,   4620 },
    { 0x0000208020004100ull,  12958 },
    { 0x0000110080040008ull,  55229 },
    { 0x0000020080080080ull,   9892 },
    { 0x0000404040040100ull,  33767 },
    { 0x0000202040008040ull,  20023 },
    { 0x0000101010002080ull,   6515 },
    { 0x0000080808001040ull,   6483 },
    { 0x0000208200400080ull,  19622 },
    { 0x0000104100200040ull,   6274 },
    { 0x0000208200400080ull,  18404 },
    { 0x0000008840200040ull,  14226 },
    { 0x0000020040100100ull,  17990 },
    { 0x007fff80c0280050ull,  18920 },
    { 0x0000202020200040ull,  13862 },
    { 0x0000101010100020ull,  19590 },
    { 0x0007ffdfc17f8000ull,   5884 },
    { 0x0003ffefe0bfc000ull,  12946 },
    { 0x0000000820806000ull,   5570 },
    { 0x00000003ff004000ull,  18740 },
    { 0x0000000100202000ull,   6242 },
    { 0x0000004040802000ull,  12326 },
    { 0x007ffeffbfeff820ull,   4156 },
    { 0x003fff7fdff7fc10ull,  12876 },
    { 0x0003ffdfdfc27f80ull,  17047 },
    { 0x000003ffefe0bfc0ull,  17780 },
    { 0x0000000008208060ull,   2494 },
    { 0x0000000003ff0040ull,  17716 },
    { 0x0000000001002020ull,  17067 },
    { 0x0000000040408020ull,   9465 },
    { 0x00007ffeffbfeff9ull,  16196 },
    { 0x007ffdff7fdff7fdull,   6166 }
},

rook_magics[64] =
{
    { 0x00a801f7fbfeffffull,  85487 },
    { 0x00180012000bffffull,  43101 },
    { 0x0040080010004004ull,      0 },
    { 0x0040040008004002ull,  49085 },
    { 0x0040020004004001ull,  93168 },
    { 0x0020008020010202ull,  78956 },
    { 0x0040004000800100ull,  60703 },
    { 0x0810020990202010ull,  64799 },
    { 0x000028020a13fffeull,  30640 },
    { 0x003fec008104ffffull,   9256 },
    { 0x00001800043fffe8ull,  28647 },
    { 0x00001800217fffe8ull,  10404 },
    { 0x0000200100020020ull,  63775 },
    { 0x0000200080010020ull,  14500 },
    { 0x0000300043ffff40ull,  52819 },
    { 0x000038010843fffdull,   2048 },
    { 0x00d00018010bfff8ull,  52037 },
    { 0x0009000c000efffcull,  16435 },
    { 0x0004000801020008ull,  29104 },
    { 0x0002002004002002ull,  83439 },
    { 0x0001002002002001ull,  86842 },
    { 0x0001001000801040ull,  27623 },
    { 0x0000004040008001ull,  26599 },
    { 0x0000802000200040ull,  89583 },
    { 0x0040200010080010ull,   7042 },
    { 0x0000080010040010ull,  84463 },
    { 0x0004010008020008ull,  82415 },
    { 0x0000020020040020ull,  95216 },
    { 0x0000010020020020ull,  35015 },
    { 0x0000008020010020ull,  10790 },
    { 0x0000008020200040ull,  53279 },
    { 0x0000200020004081ull,  70684 },
    { 0x0040001000200020ull,  38640 },
    { 0x0000080400100010ull,  32743 },
    { 0x0004010200080008ull,  68894 },
    { 0x0000200200200400ull,  62751 },
    { 0x0000200100200200ull,  41670 },
    { 0x0000200080200100ull,  25575 },
    { 0x0000008000404001ull,   3042 },
    { 0x0000802000200040ull,  36591 },
    { 0x00ffffb50c001800ull,  69918 },
    { 0x007fff98ff7fec00ull,   9092 },
    { 0x003ffff919400800ull,  17401 },
    { 0x001ffff01fc03000ull,  40688 },
    { 0x0000010002002020ull,  96240 },
    { 0x0000008001002020ull,  91632 },
    { 0x0003fff673ffa802ull,  32495 },
    { 0x0001fffe6fff9001ull,  51133 },
    { 0x00ffffd800140028ull,  78319 },
    { 0x007fffe87ff7ffecull,  12595 },
    { 0x003fffd800408028ull,   5152 },
    { 0x001ffff111018010ull,  32110 },
    { 0x000ffff810280028ull,  13894 },
    { 0x0007fffeb7ff7fd8ull,   2546 },
    { 0x0003fffc0c480048ull,  41052 },
    { 0x0001ffffa2280028ull,  77676 },
    { 0x00ffffe4ffdfa3baull,  73580 },
    { 0x007ffb7fbfdfeff6ull,  44947 },
    { 0x003fffbfdfeff7faull,  73565 },
    { 0x001fffeff7fbfc22ull,  17682 },
    { 0x000ffffbf7fc2ffeull,  56607 },
    { 0x0007fffdfa03ffffull,  56135 },
    { 0x0003ffdeff7fbdecull,  44989 },
    { 0x0001ffff99ffab2full,  21479 }
};

I have a8 = 0, h1 = 63
But I have a problem with the bishops...

Firstly, I create the index into the table with..

Code: Select all

int index = (int) ((occ * bishop_magics[sq]) >>> 52) + bishop_pos[sq];

Now for square 2 (c8), with occupancy (b7,d7,e6,f5) = 0x20100A00
I obtain index = 9794.

And for square 6 (g8), with occupancy (e6) = 0x100000
I obtain index = 9794

Clearly there's an error, since those occupancies have different attack sets.
I'm not sure what I'm doing wrong, is the bishop shift not 52?

Also data is taken from the 8th entry here http://www.open-aurec.com/wbforum/viewt ... =4&t=51162

Please help me figure this out, thanks

[cms271828]

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

Is that right?