Zobrist alternative?

[Daniel Shawul]

It seems to me that my idea to mix only those operators that don't change distribution (sub,add and xor) could work and it would be cheaper than a multiply that will also skew the distribution. I belive that also causes clustering in hash tables. Maybe I missed something obvious, but I need a comment anyway...

Code: Select all

(key1[p1] + key2[sq1]) ^ (key1[p2] + key2[sq2]) ^ ....

The other variation is

Code: Select all

(key1[p1] ^ key2[sq2]) + (key1[p2] ^ key2[sq2]) + ....

What reinhard proposed also seem to be a variation of this idea only that one operator XOR is used for hashing a piece_on_square and also to get the final position.

Code: Select all

key(p, row, col) = k(p,row) ^ k(p,col)

One could do the similar things like I did

Code: Select all

(k(p1,r1) ^ k(p1,c1)) + (k(p2,r2) ^ k(p2,c2)) ...

And the other variation as well. Tables could be smaller with this one.
The keys could be 128 bits if that is needed.
Thoughts?

[hgm]

designing a hashfunction for this isn't what you need - a robot playing the moves for you is more interesting, as i bet each game takes forever

Well, the designers must have felt this could be a problem. So they added some 'range capturers' to the piece mix. These moves like sliders (Bishop, Rook or Queen), but they can jump over almost all other pieces, (only limited by the board edge, the King or a range capturer of higher rank), and then all pieces they jump over disappear (friend as well as foe). So you can potentially capture 35 pieces in a single move. That helps to speed things up!

It still seems to take about 1000 moves, though.

[smrf]

Well, I see. Also HGM explained the difficulties at pairs of same piece type using that suggested approach (when overlaying all elementary piece/coor keys also by XOR).

[Daniel Shawul]

To Daniel:
Sorry, but I messed up with the operator priorities, and what I actually meant was to use ~(rand()*rand()) for the pieceKey and squareKey arrays. The reason was that the product of two independent randoms has only 25% probability to be odd, and so its complement is odd in 75% of the cases. Multiplying two of them then has a (0.75)^2 = 9/16 probability to be odd, which is much closer to the desired 50% than when I use pure rand() values for the key factors.

I redid the test with this new formula. It has the same problems as before as long as we use multiplication. I think my solution to use (key1[p1] + key2[sq1]) ^ (key1[p2] + key2[sq2]) . The other variation could have problems with 'carry'. Every time we add two 64 bit keys, a 65th bit may be set so adding pices_on_square hash keys will have problem when then number of pieces is very high (as is the case with this game). So I prefer to add the two keys before xoring with the rest. Edit: I think it is better to use 63 bits for each key so when addition overflows a 64 bit key will take care of it. Zobrist's use of XOR do not have problems with overflow and underflow unlike add and sub.
Anyway the test result with ~(rand() * rand()) filling both tables still shows the same problems at the tails.

Code: Select all

1   0.562627 
2   0.436797 
3   0.478317 
4   0.487266 
5   0.492112 
6   0.495665 
7   0.498424 
8   0.499410 
9   0.499386 
10   0.499922 
11   0.500138 
12   0.499713 
13   0.500008 
14   0.499816 
15   0.499933 
16   0.499705 
17   0.500197 
18   0.499575 
19   0.499618 
20   0.498827 
21   0.497529 
22   0.496133 
23   0.492751 
24   0.486645 
25   0.475851 
26   0.456494 
27   0.424332 
28   0.370352 
29   0.284297 
30   0.153438 
31   0.000000 
32   0.000000 

[diep]

designing a hashfunction for this isn't what you need - a robot playing the moves for you is more interesting, as i bet each game takes forever

Well, the designers must have felt this could be a problem. So they added some 'range capturers' to the piece mix. These moves like sliders (Bishop, Rook or Queen), but they can jump over almost all other pieces, (only limited by the board edge, the King or a range capturer of higher rank), and then all pieces they jump over disappear (friend as well as foe). So you can potentially capture 35 pieces in a single move. That helps to speed things up!

It still seems to take about 1000 moves, though.

They had invented the machine gun already in the 16th century?
Very impressive!

[hgm]

Well, it is more like an elephant stampede...

In Ko Shogi (19x19 board) there is actually a piece called 'Gatling Gun'. IIRC it can capture the first two pieces along an orthogonal or diagonal without moving. (Ko Shogi has several such 'shooting' pieces). But it is of much later date, of course!

[diep]

designing a hashfunction for this isn't what you need - a robot playing the moves for you is more interesting, as i bet each game takes forever

Well, the designers must have felt this could be a problem. So they added some 'range capturers' to the piece mix. These moves like sliders (Bishop, Rook or Queen), but they can jump over almost all other pieces, (only limited by the board edge, the King or a range capturer of higher rank), and then all pieces they jump over disappear (friend as well as foe). So you can potentially capture 35 pieces in a single move. That helps to speed things up!

It still seems to take about 1000 moves, though.

At such a huge board making a move already takes more time. Even if you would play it rapid. Say 20 seconds a move, that's already impossible basically.

Say 30 seconds a move that's 30k seconds in total that's 10 hours. Times 2 that's 24 hours for a game if you play pretty quick.

More something to put in a museum

[wgarvin]

I have bad experience with shifting keys by only 1 bit. I tried it in a simulator, and it drove up the number of key collisions enormously. When rotating keys by [????] bits I could not detect any difference in collision statistics with truly random keys.

I have no explanation for this; it was just an observation.

Hi hgm,

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

Could you please reply with the missing number, to sate my curiosity?

Thanks in advance!

[Daniel Shawul]

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.

I found a good page that discusses about different string hashing techniques, among which additive hashing is mentioned..yeah! Eternally confused.

Additive hashing:
--------------------
The authors mentioned it is a very poor hashing because permutations are hashed to the same key. But this is not relevant for us, because that is what we want unlike in strings where order matters. Other than that it should work fine. I was afraid of overflow effect but I think that is not much of an issue.

XOR hashing:
----------------
They said this is poor for string hashing because it doesn't have the "avalanche" property. Well zobrist uses xor so I guess this is a non issue. The only problem here is that XOR to get both the piece_on_square key and make the final key introduces clear collisions that are easily demonstrated.

Rotate hashing
-----------------
I am not sure how to use this to hash piece and square, but it is very similar to XORing so it faces the same problems. A rotate by 4 bits would be ((p << 4) ^ (p >> 28) ^ sq) so if zobrist hashing is still used (xoring) then it would face the same problems.

Bernestein hash
------------------
No theory behind this method and I am not sure it will work for us, since a magic multiplier other than 33 will probably be required. Anyway multiply and add (MAD) is another option. Still expensive though. But it should work with zobrist xoring.

Shift and xoring
-------------------
Similar to rotate hashing but this one works with zobrist as it has an add.

The rest seem to be either too expensive or something else... Anyway you can review them yourself.
Finally there is a suggestion on how to design hash functions that I quote here verbatim

Designing a hash function is more trial and error with a touch of theory than any well defined procedure. For example, beyond making the connection between random numbers and the desirable random distribution of hash values, the better part of the design for my JSW hash involved playing around with constants to see what would work best.

I would also be lying if I said that the choice of operations was not almost completely random trial and error by pulling from a pool of combinations of XOR, OR, AND, addition, subtraction, and multiplication. The biggest design element of JSW hash is using the table of random numbers keyed on each byte of the input to act as a mixing step. Then it was simply a matter of choosing a less complicated hash algorithm to paste that addition onto, and finally the fiddling and testing to get the algorithm performing well.

I will not claim that hash function design is always like that, but the evidence certainly suggests it. If you design hash functions in a deterministic way, I would love to hear from you.

So the distribution of hash keys is important as I tried to maintain a uniform distribution. That is important to reduce clustering. Also I think they mentioned that multiplication changes the distribution as I observed.

They have also a test code for hash collision test so I will try them out if I have time and the interest to pursue it, but to me adding the keys is the best so far

Daniel

[hgm]

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.