Magics

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
cms271828
Posts: 316
Joined: Wed Apr 12, 2006 8:47 pm

Magics

Post by cms271828 » Thu May 19, 2011 4:46 pm

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

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

Re: Magics

Post by Edmund » Thu May 19, 2011 5:05 pm

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

regards
Edmund

Gerd Isenberg
Posts: 2127
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Magics

Post by Gerd Isenberg » Thu May 19, 2011 5:53 pm

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.

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

Re: Magics

Post by cms271828 » Thu May 19, 2011 7:11 pm

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
Colin

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

Re: Magics

Post by Edmund » Thu May 19, 2011 7:25 pm

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

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

Re: Magics

Post by cms271828 » Thu May 19, 2011 7:47 pm

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
Colin

micron
Posts: 155
Joined: Mon Feb 15, 2010 8:33 am
Location: New Zealand

Re: Magics

Post by micron » Fri May 20, 2011 12:00 am

cms271828 wrote: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
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: Magics

Post by Edmund » Fri May 20, 2011 7:02 am

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

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

Re: Magics

Post by cms271828 » Fri May 20, 2011 12:18 pm

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
Colin

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

Re: Magics

Post by cms271828 » Fri May 20, 2011 1:32 pm

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

Is that right?
Colin

Post Reply