Zobrist alternative?

[Daniel Shawul]

It all seems a bit "calculated". When using even the simplest of LCGs the keys all look random because a different initializer is used for each execution of the LCG.

Well maybe not. It occurs to me that we can rotate the initialization key either with the sq or piece ( like a de brijun ). At least that will work for squares up to 64. The 36x36 squares we have for this game may require additional bits to be stored, or doing other mixing with the remainder (sq % 64).

Code: Select all

U64 h = U64(19282138887198); 
h = (h << sq) ^ (h >> (64 - sq));
h = h * FNV; 
h = (h << cp) ^ (h >> (14 - cp));

This seems to produce good values. If I leave out one of the rotations, there seems to be a discernible pattern in either group so both are necessary. Zobrist hashing xors so rotation should be safe.

Code: Select all

0x423c5be0316c2ba7
0x8478b7c062d8574e
0x08f16f80c5b0ae9d
0x11e2df018b615d3b
0x23c5be0316c2ba77
0x478b7c062d8574ef
0x8f16f80c5b0ae9df
0x1e2df018b615d3be
0x3c5be0316c2ba77d
0x78b7c062d8574efa
0xf16f80c5b0ae9df4
0xe2df018b615d3be8
0xc5be0316c2ba77d0
0x8b7c062d8574efa0

0x42385be0316c2ba7
0x8470b7c062d8574e
0x08e16f80c5b0ae9d
0x11c2df018b615d3b
0x2385be0316c2ba77
0x478b7c062d8574ef
0x8f16f80c5b0ae9df
0x1eadf018b615d3be
0x3d5be0316c2ba77d
0x7ab7c062d8574efa
0xf56f80c5b0ae9df4
0xeadf018b615d3be8
0xd53e0316c2ba77d0
0xaa7c062d8574efa0
0x54f80c5b0ae9df40
0xa9f018b615d3be80
0x5360316c2ba77d00
0xa64062d8574efa00
0x4c00c5b0ae9df400
0x98818b615d3be800
0x310336c23a77e660
0x62866d8474efccc1
0xc50cdb08e9df9983
0x8a99b611d3bf3306
0x15330c22277e9c6e
0x2ae67845cefd6f3d
0x55ccf08b9dfade7b
0xab99e1173bf5bcf6
0x57b3c22e77eb79ed
0xafe7e45d6fd729bc
0x5fcfc8badfae5379
0xbf9f9175bf5ca6f2
0x7f3f02ebfeb97785
0xfefe05d7fd72ef0b
0xfdfbebb07ae62078
0xfb77b76175cc1911
0xf6ef0ec36b99fcc4
0xed5e7d8757338769
0xdabcfb0eae670ed2
0xb5f9f61d5cce1da5
0x6b73cc3a399df52c
0xd6679874733bea58
0xac4f30e8e677d4b1
0x581e61d1ccefa962
0xb0bcc3a399df52c4
0x61f9a747b3be6bea
0xc3f34e8f677cd7d5
0x87669d1ecef9afaa
0x0e4d1a3d1df30535
0x1c9a147abbe6518b
0x39b408f5f7ccf9f7
0x736831eb6f99a50f
0xe65783c95f3300ff
0xcc2f0792be6601fe
0x985eef26fccc599d
0x30bdde4df998b33a
0x617bbc9bf3316674
0xc2f77937e662cce9
0x856ef26fccc599d3
0x0a5de4df998b33a6
0x143be9bfb316312d
0x2877337ce62dadbc
0x50ee06f84c5b2199
0xa15c2df018b615d3

[diep]

I don't get it. Why would not having a hash table hurt despite the branching factor? It also means there are many possibilities for repetitive positions. Go has a huge branching factor and still everyone uses hash tables...

In theory a huge branching factor in a game like this you will get more transpositions. The nps you need for that however and the search depth required is pretty big.

So if you search in a very thin manner transpositiontable is not so important. Storing the best move for this given position is

If you parallellize it in fact it's likely you don't want to store anything in hashtable last few plies

[diep]

Well, the 12x12 game (Chu Shogi) is close enough to normal Chess that a good QS will probably pay off enormously. The concern is the Lion piece, however. Two opposing Lions have even higher potential to cause a search explosion by going on a plunder raid than two Queens, and I can't see MVV/LVA ordering could put an effective stop to that. (As it does with Queens.) Because the Lions can make 'hit-and-run' captures with their double moves, with many opportunities to 'run' to a safe square after the capture, from where they can aim at the next victim of the raid. In fact they can move back to the starting square if that was a safe one, and annihilate all their neighbors from there one by one, in many different orders. So probably something special would have to be programmed to put a stop to that.

Yes maybe for this big board game you could just make a huge qsearch function - should be enough to beat entire humankind.

If we already assume we already have tried the best move, then based upon that assumption we can prove of course that getting a transposition that would change the PV is unlikely as we already have searched the best path.

So just get rid of the Zobrist junk and hashtable idea.

Just is extra code you don't want to write.

[diep]

It all seems a bit "calculated". When using even the simplest of LCGs the keys all look random because a different initializer is used for each execution of the LCG.

Well maybe not. It occurs to me that we can rotate the initialization key either with the sq or piece ( like a de brijun ). At least that will work for squares up to 64. The 36x36 squares we have for this game may require additional bits to be stored, or doing other mixing with the remainder (sq % 64).

Code: Select all

U64 h = U64(19282138887198); 
h = (h << sq) ^ (h >> (64 - sq));
h = h * FNV; 
h = (h << cp) ^ (h >> (14 - cp));

This seems to produce good values. If I leave out one of the rotations, there seems to be a discernible pattern in either group so both are necessary. Zobrist hashing xors so rotation should be safe.

64 factors to 2^6
14 factors to 2*7

so the only primes you use is 7 and 2 here.

You might want to rotate prime number style. It should work for HGM's gpu approach yeah. Even then i would not use multiplication.

[diep]

Here is part of RanRot, still similar to its original code:

Code: Select all

typedef  unsigned int my_uint;

/* If your system doesn't have a rotate function for the chosen integer type
   then define it thus:                                                      */
my_uint rotl (my_uint x, my_uint r) {return(x<<r)|(x>>(sizeof(x)*8-r));}

/* define parameters (R1 and R2 must be smaller than the integer size): */
#define KK  17
#define JJ  10
#define R1   5
#define R2   3

/* global variables */
my_uint randbuffer[KK];  /* history buffer */
int r_p1, r_p2;          /* indexes into history buffer */
float scale;             /* 2^(- integer size) */


/* returns a random number between 0 and 1 */
double RanrotA(void) {
  my_uint x;
  /* generate next random number */
  x = randbuffer[r_p1] = rotl(randbuffer[r_p2],R1) + rotl(randbuffer[r_p1], R2);
  /* rotate list pointers */
  if( --r_p1 < 0)
    r_p1 = KK - 1;
  if( --r_p2 < 0 )
    r_p2 = KK - 1;
  /* conversion to float */
  return (x*scale);
}

/* get integer random number in interval from min to max */
int iRanrotA(int min, int max) {
  int i, r;
  i = max - min + 1;
  r = (int) ((double)i * RanrotA());
  if( r >= i )
    r = i;
  return(min+r);
}

If we analyze the basic core functionality it has a buffer of 17 integers.

And it's doing 2 rotations and 1 addition.

The rotations based upon 5 and 3

So should be possible to get away with the hashing function with exactly that and save out the expensive multiplication.

[diep]

A first simple attempt would be :

for given 'sq' and 'piece' :

x1 = lookupSQ[sq]; // random number
x2 = lookupPIECE[piece]; // random number

r1 = lookupR1[piece]; // list of small prime numbers
r2 = lookupR2[sq]; // list of small prime numbers

Now we want to combine this into unique number

randomresult = rotateleft(x1,r1) + rotateleft(x2,r2);

You can try get it cheaper by replacing lookupSQ or lookupPIECE to constants and just add in the 'sq' there.

I have no time to verify the result of the above. Might work.

[Daniel Shawul]

Hi Vincent
We can't use a look up table for sq and piece since we are trying to avoid that. Rotation of a magic number was a substitute for that in this case. This will probably be not a good cryptographic hash but for zobrist might work since xor changes the hash key based on adjacent bits. The problem is that there are too many squares 1200 so we need a many majic numbers. But the rotation reduces tables size by 64 times. This is mentioned somewhere in this thread to reduce tables size, but can it be used to completely avoid it? I will see what can be used from RanRot for this purpose.
Thanks

[diep]

Hi Vincent
We can't use a look up table for sq and piece since we are trying to avoid that. Rotation of a magic number was a substitute for that in this case. This will probably be not a good cryptographic hash but for zobrist might work since xor changes the hash key based on adjacent bits. The problem is that there are too many squares 1200 so we need a many majic numbers. But the rotation reduces tables size by 64 times. This is mentioned somewhere in this thread to reduce tables size, but can it be used to completely avoid it? I will see what can be used from RanRot for this purpose.
Thanks

Hi, just try it.

I'm rotating the sq random number by a small prime lookuped for piece and vice versa. Maybe you missed this detail.

And then we add up this after 2 rotations.

So effectively we're having a bitresult of a multiplication in a field.

HGM wanted to avoid 5MB lookup to generate his Zobrist key and this definitely does with such tiny lookup tables of just a few kilobyte

HGM wanted to avoid lookup of a double array, not single array.

double array is [piece][sq]
this is however single lookups of just [piece] and [sq]
We CAN use looking up piece and sq in a table,
we just can't afford a table sized sq * piece, that's all

Bottomline is that what i posted here is factors faster than the multiplication you proposed.

As the lookups probably can get prefetched what i posted is under 2 clocks and will keep just 3 execution units busy for 1 cycle

So throughput latency is 1 cycle, not counting the prefetch of the L1.

What you posted is maybe 5 cycles throughput or so?

[Don]

Hi Vincent
We can't use a look up table for sq and piece since we are trying to avoid that. Rotation of a magic number was a substitute for that in this case. This will probably be not a good cryptographic hash but for zobrist might work since xor changes the hash key based on adjacent bits. The problem is that there are too many squares 1200 so we need a many majic numbers. But the rotation reduces tables size by 64 times. This is mentioned somewhere in this thread to reduce tables size, but can it be used to completely avoid it? I will see what can be used from RanRot for this purpose.
Thanks

Hi, just try it.

You missed the point. We have already discussed using two small tables and have concluded that adding them together might work just fine. Then it was suggested that might find a way to completely avoid any table lookups and wondered if there was a fast way to do that. Not because we don't think we should, but because we wondered if we could.

I'm rotating the sq random number by a small prime lookuped for piece and vice versa. Maybe you missed this detail.

And then we add up this after 2 rotations.

So effectively we're having a bitresult of a multiplication in a field.

HGM wanted to avoid 5MB lookup to generate his Zobrist key and this definitely does with such tiny lookup tables of just a few kilobyte

HGM wanted to avoid lookup of a double array, not single array.

double array is [piece][sq]
this is however single lookups of just [piece] and [sq]
We CAN use looking up piece and sq in a table,
we just can't afford a table sized sq * piece, that's all

Bottomline is that what i posted here is factors faster than the multiplication you proposed.

As the lookups probably can get prefetched what i posted is under 2 clocks and will keep just 3 execution units busy for 1 cycle

So throughput latency is 1 cycle, not counting the prefetch of the L1.

What you posted is maybe 5 cycles throughput or so?

[Daniel Shawul]

Hmm you seem to be missing a whole lot of the discussion that was going on.

Hi, just try it.

I'm rotating the sq random number by a small prime lookuped for piece and vice versa. Maybe you missed this detail.

And then we add up this after 2 rotations.

So effectively we're having a bitresult of a multiplication in a field.

HGM wanted to avoid 5MB lookup to generate his Zobrist key and this definitely does with such tiny lookup tables of just a few kilobyte

HGM wanted to avoid lookup of a double array, not single array.

double array is [piece][sq]
this is however single lookups of just [piece] and [sq]
We CAN use looking up piece and sq in a table,
we just can't afford a table sized sq * piece, that's all

Bottomline is that what i posted here is factors faster than the multiplication you proposed.

I didn't. HGM did use separate tables for piece and sq saving significantly on table size and used multiplication as well. But I suggested addition, try and beat that As Don explained, we are now trying to avoid table look ups all in all, as the matter is settled anyway if you have hahskeys for [piece] and [sq]. The RanRot code you gave keeps two previously generated keys to generate the next random number unlike rand() which only keeps one. Bear in mind that this is not _sequential_ random number generation. I am sure the FNV method will work fine if executed sequentially. But the point is to generate a random looking hash key for a given piece_on_square without previous knowlege. So the seed for each square should be different which I tried to vary rotating a single 64 bit hash key. When the number of squares is high (36x36) it might require additional keys to be stored unless other mixing operations are done on the same key to avoid a need for that ...

As the lookups probably can get prefetched what i posted is under 2 clocks and will keep just 3 execution units busy for 1 cycle

So throughput latency is 1 cycle, not counting the prefetch of the L1.

What you posted is maybe 5 cycles throughput or so?