Fixed shift magics with 800KB lookup table

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

Fixed shift magics with 800KB lookup table

Postby Volker Annuss » 05 Sep 2010, 11:05

Here is a set of magic factors that needs a 800KB lookup table only. The trick is, that the lookup tables for each square are overlapping in one big table.

The magic factors are optimized for producing either a small table or a bigger table with big unused gaps in it, that may be used for other factors.

Code: Select all
unsigned long long lookup_table[102582];

struct
{
   unsigned long long factor;
   int position;
}
bishop_magics[64] =
{   
   { 0x0000404040404040ull,   4501 },
   { 0x0000202020202000ull,  11596 },
   { 0x0000401020200000ull,  11404 },
   { 0x000080480ff80400ull,   8861 },
   { 0x0000440200000000ull,  12652 },
   { 0x000021c1007c0000ull,   5150 },
   { 0x0000104104004000ull,  10126 },
   { 0x0000020020820080ull,  35771 },
   { 0x0000004040404040ull,  11944 },
   { 0x0000002020202020ull,  10860 },
   { 0x0000004010202000ull,  11628 },
   { 0x00000080480ff804ull,  12364 },
   { 0x0000004402000000ull,   5470 },
   { 0x00000021c1007c00ull,  11852 },
   { 0x0000001041040040ull,   4565 },
   { 0x0000000820820020ull,   4567 },
   { 0x0000400080808080ull,   5438 },
   { 0x0000200040404040ull,  11436 },
   { 0x0000400080808080ull,   4373 },
   { 0x0000200200801000ull,   2372 },
   { 0x0000240080840000ull,   2234 },
   { 0x0000080080840080ull,  10572 },
   { 0x0000040010410040ull,  11340 },
   { 0x0000020008208020ull,   5533 },
   { 0x0000804000810100ull,   8828 },
   { 0x0000402000408080ull,   2500 },
   { 0x0000804000810100ull,   4245 },
   { 0x0000404004010200ull,  24345 },
   { 0x0000404004010040ull,  28407 },
   { 0x0000101000804400ull,  12108 },
   { 0x0000080800104100ull,  14156 },
   { 0x0000040400082080ull,  10828 },
   { 0x0000410040008200ull,  12938 },
   { 0x0000208020004100ull,  12412 },
   { 0x0000110080040008ull,  10316 },
   { 0x0000020080080080ull,  41195 },
   { 0x0000404040040100ull,    303 },
   { 0x0000202040008040ull,   9804 },
   { 0x0000101010002080ull,   3211 },
   { 0x0000080808001040ull,   5210 },
   { 0x0000208200400080ull,  10924 },
   { 0x0000104100200040ull,  11660 },
   { 0x0000208200400080ull,   3605 },
   { 0x0000008840200040ull,  34731 },
   { 0x0000020040100100ull,  11084 },
   { 0x0000404040400080ull,   5726 },
   { 0x0000202020200040ull,  11692 },
   { 0x0000101010100020ull,  11372 },
   { 0x0000104104004000ull,  10120 },
   { 0x0000082082002000ull,  14188 },
   { 0x0000000820806000ull,  12620 },
   { 0x0000000008403000ull,   3733 },
   { 0x0000000100202000ull,   1547 },
   { 0x0000004040802000ull,   3858 },
   { 0x0000404040404000ull,  10892 },
   { 0x0000202020202000ull,   1515 },
   { 0x0000020020820080ull,  35243 },
   { 0x0000000820820020ull,  12876 },
   { 0x0000000008208060ull,  12444 },
   { 0x0000000000084030ull,  10063 },
   { 0x0000000001002020ull,  11912 },
   { 0x0000000040408020ull,  12970 },
   { 0x0000004040404040ull,  12715 },
   { 0x0000404040404040ull,   3794 }
},

rook_magics[64] =
{
   { 0x00a801f7fbfeffffull,  14668 },
   { 0x3ff4000f9ff6fffcull,  56493 },
   { 0x0040080010004004ull,  82097 },
   { 0x0040040008004002ull,  94390 },
   { 0x0040020004004001ull,  98486 },
   { 0x4010008001001040ull,  88242 },
   { 0x0040004000800100ull,  96438 },
   { 0x0810020990202010ull,  52414 },
   { 0x0040100020080010ull,  91316 },
   { 0x003ff4000f3e7ffcull,  35409 },
   { 0x0000180004ffffe8ull,  57730 },
   { 0x0000200200040020ull,  77998 },
   { 0x0000200100020020ull,  26654 },
   { 0x0000200080010020ull,   7804 },
   { 0x007fe8007bbfffdfull,  48318 },
   { 0x000038014505fffeull,  44235 },
   { 0x0040002000100020ull,  70308 },
   { 0x0042000c000efffaull,  37932 },
   { 0x0004000801020008ull,  89266 },
   { 0x0002002004002002ull, 100534 },
   { 0x0001002002002001ull,  50863 },
   { 0x0001001000801040ull,  58235 },
   { 0x0000004040008001ull,  92340 },
   { 0x0000802000200040ull,  73899 },
   { 0x0040200010080010ull,  75948 },
   { 0x0000080010040010ull,  45287 },
   { 0x0004010008020008ull,  23321 },
   { 0x0000020020040020ull,  22297 },
   { 0x0000010020020020ull,  47287 },
   { 0x0000008020010020ull,  72868 },
   { 0x0000008020200040ull,  18764 },
   { 0x0000004010002010ull,  79022 },
   { 0x0040001000200020ull,  84145 },
   { 0x0000080400100010ull,  42639 },
   { 0x0004010200080008ull,  64685 },
   { 0x0000200200200400ull,  16023 },
   { 0x0000200100200200ull,  49839 },
   { 0x0000200080200100ull,  48815 },
   { 0x0000008000404001ull,   6780 },
   { 0x0000802000200040ull,  86193 },
   { 0x00ffffb50c001800ull,   6014 },
   { 0x007ffff1feffec00ull,  36304 },
   { 0x0004000a01000800ull,  13132 },
   { 0x0000020004002020ull,  19788 },
   { 0x0000010002002020ull,  80047 },
   { 0x0000008001002020ull, 101558 },
   { 0x0003fffe6fff9801ull,  40139 },
   { 0x0001fffe71ff9001ull,  25734 },
   { 0x00ffffd200140028ull,  21660 },
   { 0x007fffedfff6ffecull,   1918 },
   { 0x003fffe800050018ull,  69803 },
   { 0x001fffe800028018ull,  40696 },
   { 0x000ffff810280028ull,    831 },
   { 0x0007ffe800e08018ull,  20812 },
   { 0x0003fffc05900048ull,      0 },
   { 0x0001ffff02280028ull,  27770 },
   { 0x00ffffe4ffdfa3b6ull,  30473 },
   { 0x007fffddbbf77fefull,  30521 },
   { 0x0000081040042082ull,   9676 },
   { 0x001fffeff7fbfc22ull,  34521 },
   { 0x000ffff7fbfc13feull,  60052 },
   { 0x0007fffdfa03ffffull,  60589 },
   { 0x0003ffff5ffeaaabull,   1182 },
   { 0x00000034004090b2ull,  65709 }
};
Volker Annuss
 
Posts: 49
Joined: 25 Jan 2005, 11:14

Re: Fixed shift magics with 800KB lookup table

Postby Gerd Isenberg » 12 Sep 2010, 14:35

Thanks Volker. For what are the position integers?
Gerd Isenberg
 
Posts: 285
Joined: 31 Jan 2005, 20:31
Location: Hattingen, Germany

Re: Fixed shift magics with 800KB lookup table

Postby Volker Annuss » 13 Sep 2010, 17:55

Gerd Isenberg wrote:Thanks Volker. For what are the position integers?

Hi Gerd,

you are right, I should have explained it in more detail. The position is where the lookup table for one square begins inside the global lookup table.

For a rook on square 0 (which is A8 in most programs) the position is 14668. So you find the moves beginning at lookup_table[14668].
A lookup table for a rook on square 0 needs 4096 bitboards. So it is stored from lookup_table[14668] to lookup_table[18783]. Not all of these bitboards are needed for that rook, but the first and the last square are.

Now look at the rook on square 35. Its position is 16023. Let's say, for the given factor you need 1024 bitboards. (I no longer have that data ready, but I am quite sure it is 1024.) So it is stored in the global table from lookup_table[16023] to lookup_table[17046] which is completely inside some unused space of the rook on square 0.

Bishops and rooks share one big table. The rook on square 54 has position 0 and is overlapping with the bishop on square 36 with position 303.

If I did not break something, I made it below the 800000 byte boundary. The optimization is still running, and the results are not written to disk, so it may take some time, maybe only minutes, maybe some hours.
Volker Annuss
 
Posts: 49
Joined: 25 Jan 2005, 11:14

Re: Fixed shift magics with 800KB lookup table

Postby Gerd Isenberg » 13 Sep 2010, 18:44

Hi Volker,

thanks for the clarification, I had the vague idea it was something like this. If your square arrays overlap, may I ask for the algorithm? Did you first compute collission free magics square for square, to look in a second pass how their used slots fits together in a most dense manner, or is it one run for all squares?

Cheers,
Gerd
Gerd Isenberg
 
Posts: 285
Joined: 31 Jan 2005, 20:31
Location: Hattingen, Germany

Re: Fixed shift magics with 800KB lookup table

Postby Volker Annuss » 13 Sep 2010, 19:57

Gerd Isenberg wrote:If your square arrays overlap, may I ask for the algorithm? Did you first compute collission free magics square for square, to look in a second pass how their used slots fits together in a most dense manner, or is it one run for all squares?


Yes, I make two passes.

The first finds one magic number for each square for bishops and rooks. The estimated cost of a magic factor is length - big_gaps + 15*number_of_big_gaps. big_gaps is the length of all gaps with at least length 16.

The second pass is a threshold accepting algorithm that tries to minimize the global table. The tables for each square are inserted one by one into the global table at the first position they fit. The optimization algorithm tries to find a permutation that gives a minimal global lookup table.

There is still room for improvements. I am currently at 99521 slots in the global table. 14112 of them are unused. It may not always be optimal to insert into the first position a table fits. It would be better to have more than one factor per square for the second pass to chose from.
Volker Annuss
 
Posts: 49
Joined: 25 Jan 2005, 11:14

Re: Fixed shift magics with 800KB lookup table

Postby Gerd Isenberg » 13 Sep 2010, 21:01

That seems really an interesting puzzle challenge. Magic packing ;-)

What about using 4 Kbit sets for each rook square with a one for each used slot, to later shift these sets some bits around looking for disjoint sets resulting in "most" dense union sets?
Gerd Isenberg
 
Posts: 285
Joined: 31 Jan 2005, 20:31
Location: Hattingen, Germany

Re: Fixed shift magics with 800KB lookup table

Postby Volker Annuss » 14 Sep 2010, 06:52

Gerd Isenberg wrote:That seems really an interesting puzzle challenge. Magic packing ;-)

What about using 4 Kbit sets for each rook square with a one for each used slot, to later shift these sets some bits around looking for disjoint sets resulting in "most" dense union sets?


I already thought about that. That would give a nice speedup, although I would lose some tricks for finding the first possible insertion point based on the number of leading occupied slots. At the moment I use bool arrays.
Volker Annuss
 
Posts: 49
Joined: 25 Jan 2005, 11:14

Re: Fixed shift magics with 800KB lookup table

Postby Volker Annuss » 02 Oct 2010, 09:04

Magic factors and positions using even less memory.

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 }
};
Volker Annuss
 
Posts: 49
Joined: 25 Jan 2005, 11:14

Re: Fixed shift magics with 800KB lookup table

Postby Grant Osborne » 01 Feb 2011, 17:51

Volker

I just took a quick look at this and found that some very big gaps can be created in the global table by looking for the best magic number for some of the rooks, and these holes can easily accomodate most of the 4 & 5 bit bishops.

As for overlapping and slotting together, is it better to optimise the magic for the biggest single gap or the largest number of unused slots?

Grant
User avatar
Grant Osborne
 
Posts: 69
Joined: 16 Jun 2006, 14:05

Re: Fixed shift magics with 800KB lookup table

Postby Grant Osborne » 03 Feb 2011, 13:03

After examining only half a dozen rook keys, optimising the magic so that it produces the largest gaps, I'm already able to reduce my global table down to 714Kb. This is just by manually inserting the bishops into the holes.

When I have new magics for all the rooks, I'll take a look at sloting and overlapping. A table of less than 700Kb seems very possible.

Grant
User avatar
Grant Osborne
 
Posts: 69
Joined: 16 Jun 2006, 14:05

Re: Fixed shift magics with 800KB lookup table

Postby Grant Osborne » 08 Feb 2011, 16:49

The approach I'm now taking is to collect up to 8 magics per square (one for the biggest gap and the rest an assortment of large unused slots) and try a best fit/overlap as I go.
Square 8 (A7) gave me a gap of 512 consecutive unused slots. Wow. Table size now down to 704Kb.

Grant
User avatar
Grant Osborne
 
Posts: 69
Joined: 16 Jun 2006, 14:05

Re: Fixed shift magics with 800KB lookup table

Postby Grant Osborne » 15 Feb 2011, 12:35

Just a quick update for anyone that is interested.

I have so far found 7 squares that produce gaps of 512 consecutive slots and over when using the right magic number. This now enables me to incorporate the whole of the bishop table completely inside the rook table.

Table size is now down to 676Kb and I'll get it below 670Kb easily when I start overlapping.

Grant
User avatar
Grant Osborne
 
Posts: 69
Joined: 16 Jun 2006, 14:05

Re: Fixed shift magics with 800KB lookup table

Postby Grant Osborne » 23 Feb 2011, 17:09

I have now found 10 rook squares that have gaps greater than 511 consecutive slots namely :-

Sq Gap
A8 1124
B8 583
D8 512
E8 512
F8 718
G8 635
H8 693
A7 512
A3 738
H3 658

It would seem logical to insert all the 9-bit keys for rooks and bishops into these holes but incredibly, in some cases the positioning of the gaps exactly line up e.g rook E7 fits inside rook H8, and A8 will accomodate any 10 bit key. There are in fact so many gaps that I am not worrying about the bishops at all, it's just a question of how the rooks best slot together, like a giant jigsaw puzzle.

The final table will be about 650Kb.

Grant
User avatar
Grant Osborne
 
Posts: 69
Joined: 16 Jun 2006, 14:05

Re: Fixed shift magics with 800KB lookup table

Postby Grant Osborne » 04 Mar 2011, 11:10

So for my first attempt the global table (rooks and bishops combined) is just over 621Kb which is better than I estimated.

U64 lookup_table[79548];

An algorithm that tries to minimize the table would certainly help right now, but as I don't have one it's a case of manually selecting the next square that seems to fit in the best. I'm going to have one more try at this and see if I can get below 620Kb before I move on to something else.

Grant
User avatar
Grant Osborne
 
Posts: 69
Joined: 16 Jun 2006, 14:05

Re: Fixed shift magics with 800KB lookup table

Postby Gerd Isenberg » 04 Mar 2011, 20:12

Grant Osborne wrote:So for my first attempt the global table (rooks and bishops combined) is just over 621Kb which is better than I estimated.

U64 lookup_table[79548];

An algorithm that tries to minimize the table would certainly help right now, but as I don't have one it's a case of manually selecting the next square that seems to fit in the best. I'm going to have one more try at this and see if I can get below 620Kb before I move on to something else.

Grant


Wow, Congratulations Grant! Fixed shift magics on a DOS-Box with 640K! ;-)
Do you have noticed a speed gain reducing memory at some point with your chess program?

Cheers,
Gerd
Gerd Isenberg
 
Posts: 285
Joined: 31 Jan 2005, 20:31
Location: Hattingen, Germany

Re: Fixed shift magics with 800KB lookup table

Postby Grant Osborne » 05 Mar 2011, 16:54

Hi Gerd

I have not tested this for any increase in speed.
I have been concentrating on getting the table as compact as I can without breaking it.

It is possible that the table can be made smaller still by looking for magics that produce gaps in specific places, but this is much more involved and may not be worth the effort.

Grant
User avatar
Grant Osborne
 
Posts: 69
Joined: 16 Jun 2006, 14:05

Re: Fixed shift magics with 800KB lookup table

Postby Grant Osborne » 18 Mar 2011, 17:39

I managed to shrink the table down to 620Kb which is just about the smallest I can get it.
Here's how it all fits together.

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
};

Grant
User avatar
Grant Osborne
 
Posts: 69
Joined: 16 Jun 2006, 14:05

Re: Fixed shift magics with 800KB lookup table

Postby Teemu Pudas » 22 Mar 2011, 20:26

Grant Osborne wrote:
Code: Select all
const U64 sqMagic[128] = {
   //rooks
   0x00A801F7FBFEFFFF, 0xFFB000810113FFFF, /*snip */
U64 *sqIndecies[128] = {
   //rooks
   Mdb+5630,  Mdb+3582, /*snip*/


Isn't sqIndecies[0] + (0x000001000100001Aull * sqMagic[0] >> 52) == sqIndecies[1] + (0x0000020000000200ull * sqMagic[1] >> 52)?
Teemu Pudas
 
Posts: 124
Joined: 16 Apr 2007, 14:03

Re: Fixed shift magics with 800KB lookup table

Postby Gerd Isenberg » 22 Mar 2011, 23:18

Teemu Pudas wrote:Isn't sqIndecies[0] + (0x000001000100001Aull * sqMagic[0] >> 52) == sqIndecies[1] + (0x0000020000000200ull * sqMagic[1] >> 52)?

Why not. Index ranges of different squares are not disjoint.
Gerd Isenberg
 
Posts: 285
Joined: 31 Jan 2005, 20:31
Location: Hattingen, Germany

Re: Fixed shift magics with 800KB lookup table

Postby Gerd Isenberg » 22 Mar 2011, 23:22

Gerd Isenberg wrote:
Teemu Pudas wrote:Isn't sqIndecies[0] + (0x000001000100001Aull * sqMagic[0] >> 52) == sqIndecies[1] + (0x0000020000000200ull * sqMagic[1] >> 52)?

Why not. Relative index ranges of different squares are not disjoint.
Gerd Isenberg
 
Posts: 285
Joined: 31 Jan 2005, 20:31
Location: Hattingen, Germany

Next

Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 1 guest