Zobrist alternative?

[hgm]

The silence is deafening Anyway now I am more or less convinced that adding the keys works as good as ,if not better ,than any other method. To summarize:

Code: Select all

    key(piece,square) = key1[piece] + key2[square]

And then xor to get final keys.

Code: Select all

    final_key = key(p1,sq1) ^ key(p2,sq2) ^ key(p3,sq3) ^ ... etc

Advantages:
a) addition is much faster than multiplication
b) requires very small talbles at least for this game. 209 + 36 x 36 = 1505 keys are required which a reduction of about 465X times!
c) keeps the uniform distribution while others like multiplication skew it somehow.

Indeed, the space savings on 'factorizing' the key are huge. This is why I liked it. You could be right in that multiplication might be unnecessary, and (faster) addition could do. I would have to try how it affects collisions, as I am not completely at easy with it: addition is a lot like XOR, and for 'sparse' numbers (few 1 bits) they are often the same. Of course random numbers will hardly ever be sparse, but they will always always contain some sparses zones, and it is conceivable this would decrease their effective length.

[Edmund]

The silence is deafening Anyway now I am more or less convinced that adding the keys works as good as ,if not better ,than any other method. To summarize:

Code: Select all

    key(piece,square) = key1[piece] + key2[square]

And then xor to get final keys.

Code: Select all

    final_key = key(p1,sq1) ^ key(p2,sq2) ^ key(p3,sq3) ^ ... etc

Advantages:
a) addition is much faster than multiplication
b) requires very small talbles at least for this game. 209 + 36 x 36 = 1505 keys are required which a reduction of about 465X times!
c) keeps the uniform distribution while others like multiplication skew it somehow.

So even if addition turns out to be poor for some reason, the advantages are too much tempting not to use it.
...
Daniel

Do key1 and key2 have to be two distinct sets of random numbers?

[smrf]

One alternative seems to be not to use caching at all. I am not sure how big the branching factor of this game would be, but I estimate it to be that huge, that occurrences of duplicate positions will have a very small rate. Thus it easily could be, that avoiding any caching and Zobrist keys could speed up the whole thing.

[hgm]

I am not sure. Exactly because the board is so large, there could be several independent tactical skermishes going on simultaneously, and their captures could be interleaved in any possible order. So transpositions in QS could be important.

[Edmund]

Do key1 and key2 have to be two distinct sets of random numbers?

Forget my last post. Obviously it wouldn't work.

[Karlo Bala]

Such a wonderful game simply deserves 5 ​​MB of Zobrist keys.

[Daniel Shawul]

Indeed, the space savings on 'factorizing' the key are huge. This is why I liked it. You could be right in that multiplication might be unnecessary, and (faster) addition could do. I would have to try how it affects collisions, as I am not completely at easy with it: addition is a lot like XOR, and for 'sparse' numbers (few 1 bits) they are often the same. Of course random numbers will hardly ever be sparse, but they will always always contain some sparses zones, and it is conceivable this would decrease their effective length.

My complaint was to the absence of comments despite my repeated plea,and the fact that it looks like something to give a shot at. I had doubts also with XOR and ADD operations being similar but by the same reasoning so are MUL and ADD. Multiplication clearly produces sparse zones at the tails according to the tests I did (skewing the distribution). Infact it could be more damaging than ADD since multiplication can be reformulated as a series of additions. According to the page I posted above,multiplicative hash seems to be as bad as addition.
Also I seem to remeber you used add instead of zobrist for holdings in the past. So mixing two different operations ADD and XOR should be better. Anyway a direct test for collisions is what is needed.

[Daniel Shawul]

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...

[bob]

Your post says "rotating by 1 bit is bad, but rotating by N bits is good" but the number N is missing.

Oops! I meant to say 8. What I do in most of my engines is something like:

char Zobrist[PIECES*SQUARES];

hashKey ^= *(int*) (Zobrist[SQUARES*piece + square);

So the key for a neighbor square starts at the next byte, and overlaps all other bytes with the next key. (This is not really the same as rotating the bits.)

For Polyglot book access in WinBoard I truly rotate keys from the given table to generate keys for unorthox piece types and squares of bigger boards.

Any measurement on the potential harm caused by almost 1/8th of the entries lying across two cache lines? 7 out of 64 to be exact...

[hgm]

I measured the penalty for such a cache-line-straddling access, and it was very low. (On Intel Celeron M; I would not know about AMD.) Within the cache line there was no penalty whatsoever.

But with a 0x88 board, the key table can be positioned in such a way that the cache line is never exceeded. (By starting the board at a cache line, the 4th rank of the board would be at address 48-55, and even the access for h4 would span 55-62. a5 would map to the start of the next cache line.

Of course on other architectures (ARM?) such tricks are likely to cause exceptions ('bus error'). i386 is really exceptional in allowing non-aligned access.