How do I test the quality of the Zobrist keys?

[hgm]

Well, I also protect against bad moves in so far as they could crash the engine.

But it still would be bad if you accidentally had three keys that XOR to zero, as it means that the presence of two of those is equivalent to the presence of the third, so you would have a collision between two positions that are only a capture removed from each other. And it would not be just one pair of positions, but you would have such a collision for every combination of the other pieces on the board. And that might be more than your search can work around, if that capture happens to be possible in the root.

So if you see inexplicable search errors, you use a key that is a bit on the short side, or you use dirty tricks tho shrink the Zobrist table to 1KB, it might still be a good idea to test the keys for independence.

And finally: If the number of key collisions is so small that you never have to worry about them, it simply means that you use too long a key. Your engine would do better with the same resources if you shrunk your hash entry by carving away a few key bits, as the ncreased number of entries would benefit you more than the increased collissions would hurt you.

[hgm]

I also used this method to verify that the trick of overlapping the Zobrist randoms is not more collission prone than having completely independent keys. (I do this so I can use a table of char, rather than long long int, reducing the cache pollution associated with the Zobrist table by a factor 8 ). So the last 7 bytes of one key are the first 7 bytes of the next, etc.

char Keys[12*64+7];

// initialization
for(i=0; i<12*64+7; i++) Keys = rand()>>6;

//usage
HashKey ^= * (long long int *) (Keys + 64*PieceType + Square);

This of course leads to unaligned memory access, but this is not a crime on x86 machines. On the CPUs I tried it only has a very small penalty (it takes 3 clocks on Pentium IV and 2 on other Pentiums, in stead of 1, and on Pentium IV it was possible to do other, aligned memory accesses in parallel). The penalty for fetching something from L2 is far greater.

Testing such a set of overlapping keys of 49 bits only gave 4 collissions of order 6, in stead of the expected average of 5.

[Gerd Isenberg]

a blast from the past...

from rec.games.chess 1994

Tony Warnock

The following paper descibes a method of generating the numbers for a hash table. By using error correcting codes, we ensure that positions that are close on the board are not close in the hash space. Some experiments showed that we got an improvement in collision rate compared to using a random set of numbers.

MacWilliams and Sloane's book on error correcting codes has
the gory details about the theory and programming.

Tony Warnock & Burton Wendroff:
"Search Tables in Computer Chess"
ICCA Journal (March 1988), pp. 10-13.

Jonathan Schaeffer

... I can speak from experience here. In the early versions of my chess program Phoenix, I generated my Zobrist hash numbers using my student id number as a seed, naively thinking the radom numbers generated by this seed would be good enough. A few years later I put code in to detect when my 32-bit hash key matched the wrong position. To my surprise, there were *lots* of errors. I changed my seed to another number and the error rate dropped dramatically. With this better seed, it became very, very rare to see a hash error.

All randomly generated numbers are not the same!

[bob]

a blast from the past...

from rec.games.chess 1994

Tony Warnock

The following paper descibes a method of generating the numbers for a hash table. By using error correcting codes, we ensure that positions that are close on the board are not close in the hash space. Some experiments showed that we got an improvement in collision rate compared to using a random set of numbers.

MacWilliams and Sloane's book on error correcting codes has
the gory details about the theory and programming.

Tony Warnock & Burton Wendroff:
"Search Tables in Computer Chess"
ICCA Journal (March 1988), pp. 10-13.

Jonathan Schaeffer

... I can speak from experience here. In the early versions of my chess program Phoenix, I generated my Zobrist hash numbers using my student id number as a seed, naively thinking the radom numbers generated by this seed would be good enough. A few years later I put code in to detect when my 32-bit hash key matched the wrong position. To my surprise, there were *lots* of errors. I changed my seed to another number and the error rate dropped dramatically. With this better seed, it became very, very rare to see a hash error.

All randomly generated numbers are not the same!

I had already cited the warnock paper somewhere in this thread.

It was interesting back then, still applies today, although if you try to start a discussion on this topic, the discussion goes off into the twilight zone rather than staying on topic...

[jesper_nielsen]

a blast from the past...

from rec.games.chess 1994

Tony Warnock

The following paper descibes a method of generating the numbers for a hash table. By using error correcting codes, we ensure that positions that are close on the board are not close in the hash space. Some experiments showed that we got an improvement in collision rate compared to using a random set of numbers.

MacWilliams and Sloane's book on error correcting codes has
the gory details about the theory and programming.

Tony Warnock & Burton Wendroff:
"Search Tables in Computer Chess"
ICCA Journal (March 1988), pp. 10-13.

Jonathan Schaeffer

... I can speak from experience here. In the early versions of my chess program Phoenix, I generated my Zobrist hash numbers using my student id number as a seed, naively thinking the radom numbers generated by this seed would be good enough. A few years later I put code in to detect when my 32-bit hash key matched the wrong position. To my surprise, there were *lots* of errors. I changed my seed to another number and the error rate dropped dramatically. With this better seed, it became very, very rare to see a hash error.

All randomly generated numbers are not the same!

I had already cited the warnock paper somewhere in this thread.

It was interesting back then, still applies today, although if you try to start a discussion on this topic, the discussion goes off into the twilight zone rather than staying on topic...

Do any of you have a link for this paper, so I can read it?

Googling it did not turn up any usable hits.

Kind regards,
Jesper

[Gerd Isenberg]

Do any of you have a link for this paper, so I can read it?

Googling it did not turn up any usable hits.

Kind regards,
Jesper

Hi Jesper,

the paper seems not available in the net.
ICGA offers back issues:
http://www.cs.unimaas.nl/icga/journal/backissu.php

Cheers,
Gerd