Sherwin Index II, The Sequal

[H.G.Muller]

The keys we need seem to be rather sparse, just a few scattered one bits. So perhaps it would work if you gererate them as

rand() & rand() & rand()

Then only 1 out of each 8 bits will be set on the average. Also be aware to use a random that is sufficiently uncorrelated in the low-order bits. For safety when I use the random from the standard C library I always use

(rand()<<2 ^ rand()>>16)

rather than a single call.

[Gerd Isenberg]

The keys we need seem to be rather sparse, just a few scattered one bits. So perhaps it would work if you gererate them as

rand() & rand() & rand()

Then only 1 out of each 8 bits will be set on the average. Also be aware to use a random that is sufficiently uncorrelated in the low-order bits. For safety when I use the random from the standard C library I always use

(rand()<<2 ^ rand()>>16)

rather than a single call.

What about a 32-bit gosper algorithm (next higher number with same number of 1-bits) for that purpose and to start with sparse sets 3, 7, 15?
http://golovchenko.org/hackersdelight/notes.htm

Pradu found his keys very fast with a 64-bit version where shift right with a log2 (bitscan) is much faster than the original div or while-loop.
http://wbforum.vpittlik.org/viewtopic.p ... 876&t=5436

Code: Select all

#define deBruijn32 0x077cb531;
int index32[32];

u32 snoob (u32 x) {
    u32 smallest, ripple, ones;
    smallest = x & -(int)x;
    ripple   = x + smallest;
    ones     = x ^ ripple;
    ones     = (ones >> 2) >> index32[(smallest*deBruijn32) >> 27];
    return ripple | ones;
}


for 32-bit DeBruijn see
http://supertech.csail.mit.edu/papers/debruijn.pdf

[H.G.Muller]

I suppose you could do lots of things. Fact remains that generating them by hand is totally trivial (as long as you don't want subminimal). So it really must be simple to program for the computer to be competative...

[Michael Sherwin]

With help from Gerd, a lot of head banging (my own) and very little sleep
this is what I have arrived at. So, Gerd if you are still here, please
take one more look at this before I start testing. Thanks! No big hurry,
I will be sleeping for a couple of days.

I am very interested in magic, especially for the rooks, however I want
to get this pure shifting method up and running first before I try something
that I do not understand very well yet.

Note: Because, the queen uses both calls, occ is only the blockers
when these routines are called.

Code: Select all

u64 Bishop32Attacks(u64 *occ, square *sq) {
  sq-> index  = occ-> lo | (occ-> hi >> 1);
  sq-> index |= (sq-> index >> sq-> bishop-> shifts);
  sq-> LoMPI = bishopLoMinimalPerfectIndex[ sq -> index       &  0xff];
  sq-> HiMPI = bishopHiMinimalPerfectIndex[(sq -> index >> 8) &  0xff];
  return       bishopAttacks[sq-> bOff + (sq->LoMPI | sq-> HiMPI)];
}

u64 Bishop64Attacks(u64 *occ, square *sq) {
  sq-> index  = occ-> lo | (occ-> hi >> 1);
  sq-> index |= (sq-> index >> sq-> bishop-> shifts);
  return        loBishopAttacks[sq-> loBAOff +  sq-> index       & 0xff];
              & hiBishopAttacks[sq-> hiBAOff + (sq-> index >> 8) & 0xff];
}

u64 Rook32Attacks(u64 *occ, square *sq) {
  sq-> index  = rankIndexs[(u32)(*occ & sq-> rank) >> sq-> rook-> raShift]
             |  ((occ-> lo & sq-> rook-> loMask1)  >> sq-> rook-> loShift)
             |  ((occ-> hi & sq-> rook-> hiMask1)  >> sq-> rook-> hiShift);
  sq-> index |= ((index    & sq-> rook-> loMask2)  >> sq-> rook-> shift34);
  sq-> LoMPI  = rookLoMinimalPerfectIndex[ sq -> index         & 0xff];
  sq-> HiMPI  = rookHiMinimalPerfectIndex[(sq -> index   >> 8) & 0xff];
  return        rookAttacks[sq-> rOff + (sq-> LoMPI | sq-> HiMPI)];
}

u64 Rook64Attacks(u64 *occ, square *sq) {
  sq-> index  = rankIndexs[(u32)(*occ & sq-> rank) >> sq-> rook-> raShift]
             |  ((occ-> lo & sq-> rook-> loMask1)  >> sq-> rook-> loShift)
             |  ((occ-> hi & sq-> rook-> hiMask1)  >> sq-> rook-> hiShift);
  sq-> index |= ((index    & sq-> rook-> loMask2)  >> sq-> rook-> shift34);
  return        loRookAttacks[sq-> loRAOff +  sq-> index       & 0xff]
              & hiRookAttacks[sq-> hiRAOff + (sq ->index >> 8) & 0xff];
}

Edit:
Note: The below mappings are not 100%. The idea is that the rank
bits can be placed into the first 16 bits exactly how they are needed
so that the other bits can be packed in to form two split minimal indexs.
End edit

The new idea for the rooks is to retrieve a rank index that looks like this:

For an a-file or h-file square:

x x x . . . . .
x x x . . . . .

or

x x . . . . . .
x x x x . . . .

or

x x x x . . . .
x x . . . . . .

depending on the other shift patterns.

For any other square:

x x . . . . . .
x x x . . . . .

or

x x x . . . . .
x x . . . . . .

depending on the other shift patterns.

This allows perfectly compressed split indexs for the rooks

Mike

[H.G.Muller]

I adapted my magic key generator for Rooks to the mapping with two 32-bit multiplies,

Code: Select all

    k = ( (int)magic[Sqr] * (int)Occupied ^
             (int)(magic[Sqr]>>32) * (int)(Occupied>>32) ) >> shift[Sqr];


and got the following:

Code: Select all

 0. mask =    101010101017e  magic = 4801040010020011, key length = 12
 1. mask =    202020202027c  magic = 1081011005002040, key length = 11
 2. mask =    404040404047a  magic = 200210a002040010, key length = 11
 3. mask =    8080808080876  magic =   10000e14808008, key length = 11
 4. mask =   1010101010106e  magic =  880080008810004, key length = 11
 5. mask =   2020202020205e  magic =  1320d0001000144, key length = 11
 6. mask =   4040404040403e  magic =     820001008c01, key length = 11
 7. mask =   8080808080807e  magic =     208044802041, key length = 12
10. mask =    1010101017e00  magic = 4040828000004020, key length = 11
11. mask =    2020202027c00  magic = 1000300060806008, key length = 10
12. mask =    4040404047a00  magic =  84040a000404014, key length = 10
13. mask =    8080808087600  magic = 5180085140808014, key length = 10
14. mask =   10101010106e00  magic =   4601200442040c, key length = 10
15. mask =   20202020205e00  magic =  4c0208070002102, key length = 10
16. mask =   40404040403e00  magic = 1108020003220801, key length = 10
17. mask =   80808080807e00  magic =   20408000208001, key length = 11
20. mask =    10101017e0100  magic = 4080c20010082080, key length = 11
21. mask =    20202027c0200  magic = 1820040011520010, key length = 10
22. mask =    40404047a0400  magic = 191044000000a020, key length = 10
23. mask =    8080808760800  magic =  800710000022101, key length = 10
24. mask =   101010106e1000  magic = 8080084000102408, key length = 10
25. mask =   202020205e2000  magic =   71022024000404, key length = 10
26. mask =   404040403e4000  magic = 1300180408100202, key length = 10
27. mask =   808080807e8000  magic = 220240802000d101, key length = 11
30. mask =    101017e010100  magic = 1541018000406202, key length = 11
31. mask =    202027c020200  magic =  900409000024022, key length = 10
32. mask =    404047a040400  magic =  210420000106282, key length = 10
33. mask =    8080876080800  magic =   49122008d00039, key length = 10
34. mask =   1010106e101000  magic = 1081000540421831, key length = 10
35. mask =   2020205e202000  magic = 8108441000101202, key length = 10
36. mask =   4040403e404000  magic = 4901120200201a44, key length = 10
37. mask =   8080807e808000  magic =  1004401018442c6, key length = 11
40. mask =    1017e01010100  magic =   80008010432058, key length = 11
41. mask =    2027c02020200  magic = 8840004008008024, key length = 10
42. mask =    4047a04040400  magic = 4080300082408292, key length = 10
43. mask =    8087608080800  magic = 4101001001042048, key length = 10
44. mask =   10106e10101000  magic = 1408814380040008, key length = 10
45. mask =   20205e20202000  magic =  c0110a020100804, key length = 10
46. mask =   40403e40404000  magic = 8104020000050491, key length = 10
47. mask =   80807e80808000  magic =   40008002501051, key length = 11
50. mask =    17e0101010100  magic =   41002014208801, key length = 11
51. mask =    27c0202020200  magic = 6404100084810028, key length = 10
52. mask =    47a0404040400  magic =   24200208500044, key length = 10
53. mask =    8760808080800  magic =  a10100000082011, key length = 10
54. mask =   106e1010101000  magic =  22600041000900a, key length = 10
55. mask =   205e2020202000  magic = 721a000410100842, key length = 10
56. mask =   403e4040404000  magic = 4080810040010122, key length = 10
57. mask =   807e8080808000  magic = 3402808080034011, key length = 11
60. mask =   7e010101010100  magic = e000600840320418, key length = 11
61. mask =   7c020202020200  magic =  280288040400060, key length = 10
62. mask =   7a040404040400  magic =  214400810080401, key length = 10
63. mask =   76080808080800  magic =   92008000048009, key length = 10
64. mask =   6e101010101000  magic = 800880800010e184, key length = 10
65. mask =   5e202020202000  magic =    2004000004413, key length = 10
66. mask =   3e404040404000  magic = 8002008040848009, key length = 10
67. mask =   7e808080808000  magic =  260448000448003, key length = 11
70. mask = 7e01010101010100  magic =  110504112002280, key length = 12
71. mask = 7c02020202020200  magic = 8020149100234003, key length = 11
72. mask = 7a04040404040400  magic =   11052d01020860, key length = 11
73. mask = 7608080808080800  magic =  4142029c1010090, key length = 11
74. mask = 6e10101010101000  magic =    41022c8280902, key length = 11
75. mask = 5e20202020202000  magic =   b6040140106821, key length = 11
76. mask = 3e40404040404000  magic =  100008180200c42, key length = 11
77. mask = 7e80808080808000  magic = 190a8249004400a3, key length = 12
 0. square =                1
 1. square =                2
 2. square =                4
 3. square =                8
 4. square =               10
 5. square =               20
 6. square =               40
 7. square =               80
10. square =              100
11. square =              200
12. square =              400
13. square =              800
14. square =             1000
15. square =             2000
16. square =             4000
17. square =             8000
20. square =            10000
21. square =            20000
22. square =            40000
23. square =            80000
24. square =           100000
25. square =           200000
26. square =           400000
27. square =           800000
30. square =          1000000
31. square =          2000000
32. square =          4000000
33. square =          8000000
34. square =         10000000
35. square =         20000000
36. square =         40000000
37. square =         80000000
40. square =        100000000
41. square =        200000000
42. square =        400000000
43. square =        800000000
44. square =       1000000000
45. square =       2000000000
46. square =       4000000000
47. square =       8000000000
50. square =      10000000000
51. square =      20000000000
52. square =      40000000000
53. square =      80000000000
54. square =     100000000000
55. square =     200000000000
56. square =     400000000000
57. square =     800000000000
60. square =    1000000000000
61. square =    2000000000000
62. square =    4000000000000
63. square =    8000000000000
64. square =   10000000000000
65. square =   20000000000000
66. square =   40000000000000
67. square =   80000000000000
70. square =  100000000000000
71. square =  200000000000000
72. square =  400000000000000
73. square =  800000000000000
74. square = 1000000000000000
75. square = 2000000000000000
76. square = 4000000000000000
77. square = 8000000000000000


I did not test the results. The program was:

Code: Select all

#include <stdio.h>

#define HBITS 12
#define HSIZE (1<<HBITS)

int hash[HSIZE];

typedef unsigned long long int BB;

BB sq[64];

BB RMask[64];

int targets[4096];
BB occup[4096];

void pbrd(BB b)
{
    int i, j;

    for(i=0; i<8; i++)
    {
        for(j=0; j<8; j++)
        {   printf(" %lld", b&1); b>>=1; }
        printf("\n");
    }
}

main()
{
    int i, j, k, x, shift, mask, cnt;
    BB h, a, b, c, s, magic;
    FILE *f;

    /* initialize 64 different square masks */
    for(i=0; i<64; i++) sq[i] = 1LL<<i;

    /* shuffle them

    for(i=0; i<63; i++)
    {
        k = rand()>>16 & 1023;
        k *= 64-i;
        k>>=10;
        k += i;
        printf("%d\n", k);
        h = sq[i];
        sq[i] = sq[k];
        sq[k] = h;
    }

    /* make rook sets */
    for(i=0; i<64; i++)
    {
        h = 0;
        x = i&7; /* file nr */
        for(j=010; j<070; j+=010) /* scan file */
            if(j != (i&070)) h |= sq[j+x];
        x = i&070; /* rank nr */
        for(j=1; j<7; j++) /* scan rank */
            if(j != (i&7))   h |= sq[j+x];
        RMask[i] = h;

    }

    f = fopen("keys.dat", "w");
    for(i=0; i<64; i++)
    {
        h = RMask[i]; pbrd(h);

        a = 0;
        /* assign a unique number to the attack set for each occupation */
        for(j=0; j<4096; j++)
        {
            /* determine how far we can go in each direction */
            k = 0;
            x = i;
            while(sq[x+=1]   & h) if(sq[x]&a) break; else k++;
            x = i; k *= (x&7) + ((x&7) == 0);
            while(sq[x-=1]   & h) if(sq[x]&a) break; else k++;
            x = i; k *= 7 - (x>>3) + ((x&070)==070);
            while(sq[x+=010] & h) if(sq[x]&a) break; else k++;
            x = i; k *= (x>>3) + ((x&070)==0);
            while(sq[x-=010] & h) if(sq[x]&a) break; else k++;
            occup[j] = a;
            targets[j] = k+1;
            /*printf("%4d. %d\n", j, k);*/

            a = (a|~h)+1&h;
        }

        /* now try to find a magic that does the mapping */

        shift = 10;
again:
        mask = 1<<shift;
        printf("%d bits\n", shift);
        x = 1e6; /* try a million times */
        while(--x)
        {   
            /* new magic */
            magic = rand()>>15 & rand()>>15 & rand()>>15;
            magic = magic << 16 ^ rand()>>15 & rand()>>15 & rand()>>15;
            magic = magic << 16 ^ rand()>>15 & rand()>>15 & rand()>>15;
            magic = magic << 16 ^ rand()>>15 & rand()>>15 & rand()>>15;

            /* erase hash table */
            for(j=0; j<HSIZE; j++) hash[j] = 0;

            for(j=0; j<4096; j++)
            {
/*                k = magic * (occup[j]+1) >> (64-HBITS) & (HSIZE-1);*/
                k = ( (int)magic * (int)occup[j] ^
                      (int)(magic>>32) * (int)(occup[j]>>32) ) >> (32-shift)
                       & (mask-1);
                if(hash[k] && hash[k] != targets[j]) goto bad;
                hash[k] = targets[j];
            }
            printf("magic found after %d tries: %llx\n", 1000000-x, magic); break;
            bad:;
            if((x&0xFFFF)==0) printf("try %16llx, %4d OK\n", magic, j);

        }
        if(x==0 && ++shift<=HBITS) goto again;
       
        pbrd(RMask[i]);
        fprintf(f, "%2o. mask = %16llx  magic = %16llx, key length = %2d\n", i, RMask[i], magic, shift);
        fflush(f);
    }

    for(i=0; i<64; i++)
        fprintf(f, "%2o. square = %16llx\n", i, sq[i]);
    fclose(f);
}


[H.G.Muller]

By the way: it would probably need an additional cast to unsigned before shifting, in order to make sure that the compiler uses the correct shift instruction (logical rather than arithmetic):

Code: Select all

    k = (unsigned int) ( (int)magic[Sqr] * (int)Occupied ^
             (int)(magic[Sqr]>>32) * (int)(Occupied>>32) ) >> shift[Sqr];


In the generator I enforce this by an extra and instruction, which is wasteful when speed is an issue.

I casted all 32-bit quantities to signed int, rather than unsigned, in an attempt to force the compiler to use IMUL rather than MUL. For some reason IMUL seems to be faster (according to the tables I had). Both MUL and IMUL take two n-bit operands and produce a 2n-bit result. If the operands are signed or unsigned does not affect the low-order n bits, which are the only ones used here. (This is easily seen if you realize that the difference between the signed and unsigned interpretation of an n-bit pattern is either 0 or 2^n, depending on the sign bit.)

Perhaps the compiler is smart enough to use IMUL always in cases were you are using the low-order 32-bits of a product only, even when you multiply unsigneds. I was not sure of that, and to be safe I casted to (int). But then you have to cast back to (unsigned int) before shifting.

[Grant Osborne]

Thanks H.G.

I neglected to cast to unsigned int in my key generator. Now I'm getting much better keys. Maybe I can find some sub-minimal magics.

Grant

[H.G.Muller]

Yes, I initially forgot about that too.

But nosing through my old key generator the AND with the n-bit mask reminded me that you would have to be careful.

This nicely explains why you always needed one bit extra key length: you needed an extra most-significant bit that would always be zero.

By the way, I have a suggestion (related to what I said in the other thread):

Effectively, what you were doing is to find a key that used only a limited range of the available key space (namely the lower half). You could very easy generalize this: don't stop after you find a key, but for each key record what the largest value attained by this key was, and then continue searching for keys that remain even lower. A 12-bit key that only goes up to 2200 is nearly as good as an 11-bit key, and might be a lot easier to find...

[Michael Sherwin]

Hi H.G.,

Thank you for this! I will be able to test both shifting and magic against each other. I just need to figure out if the results are a perfectly compressed index. However, for split index approach it would be best to have the index compressed in two parts, i.e. end up with the index compressed into the right most bits of ranks 1 & 2 as evenly as possible. This would help to save huge amounts of memory.

Mike

[Grant Osborne]

Yes, I initially forgot about that too.

But nosing through my old key generator the AND with the n-bit mask reminded me that you would have to be careful.

This nicely explains why you always needed one bit extra key length: you needed an extra most-significant bit that would always be zero.

By the way, I have a suggestion (related to what I said in the other thread):

Effectively, what you were doing is to find a key that used only a limited range of the available key space (namely the lower half). You could very easy generalize this: don't stop after you find a key, but for each key record what the largest value attained by this key was, and then continue searching for keys that remain even lower. A 12-bit key that only goes up to 2200 is nearly as good as an 11-bit key, and might be a lot easier to find...

OK understand!
Working on it now.

Grant

[H.G.Muller]

..., i.e. end up with the index compressed into the right most bits of ranks 1 & 2 as evenly as possible.

I am not sure how you count. Ranks 1 and 2, are that the low-order bits? After multiply the collected bits always end up in the high-order bits, since, although a multiply does multiple shifts and adds simultaneously, the shifts are always to the left. So you need a righ-shift afterwards.

I am not sure if there is anything against making the splitting of the key completely square dependent, i.e.

Code: Select all

LoIndex = (Whatever >> LoShift[Sqr]) & LoMask[Sqr];
HiIndex =  Whatever >> HiShift[Sqr];


This would just require 3 tables of 64 bytes, and the loads could be done well in advance (using the square number that is in a register anyway as an index), in parallel with the calculation of the Whatever.

In that case it is not so clear what the optimal distribution of the key is, it might depend on if the number of bits in it is even or odd. Odd would force an unequal split, and the best way to save space would then be to put all possible reduction in the largest of the two (for which you would of course pick HiIndex, by properly tuning the shifts). The LoIndex could then always use the full range going with its number of bits.

For an even-length key I seriously doubt if you would save much from trying to spread the range reduction evenly over the low and high index, (even if that were possible, by creating a range with many holes in it), compared to just making the range as compact as possible and put all the savings in the high index.)