Good Zorbist keys set

[toma]

Hi all,

I think that Thor's Hammer has big problems caused by offten conflicts in hash table. Also, the bigger problem is that with so much conflicts there is a good chance for "serious" conflict (two positions with same hash key) resulting in an incorrect cut. I tried to improve the set of Zorbist's keys (I belive they are called like this) for generation of position's hash code but with no obvius improvement. Is there a good way to generate and/or test this set.

Thanks in advance,

Toma

P.S: if I wasn't clear , I'll be happy to clarify my problem

[Reinhard Scharnagl]

I recommend to use Perft with cached sums, that is making maximum use of the transposition table for Perft. Results should equal those generated using the traditional Perft approach.

Reinhard.

[milix]

Hi Toma,
have you tried to store the full fen in the hash table and see if you really have hash table collitions (by two positions that share the same hash key)? This way you can see in real practice if you have any

[Volker Annuss]

Hi Toma,

to check, if there is a collision in the hash table, you can check, if the move you get from the hash table is legal.

A weaker but faster test is, to check, if the from-square is occupied by the correct piece.

Make sure, your keys are good enough. rand() from some standard C libs is not good. Generate them by an XOR from many files from your PC or search for mersenne twister.

Use true 64 bit keys. Two separate 32-bit-keys for black and white are not good enough. You would get many collisions in positions with only few pieces on the board.

Greetings,
Volker

[toma]

Thanks all for replays. I allready tried testing (and minimizing collisions)using perft and normal search on bunch of test positions. Problem is that it takes lots of time and there are still no guaranties that the set of keys won't fit well the test set but be bad in the real game. But it seems that I'll just have to stick with this method. Saving FEN in the hash for testing is another possibility that I think to try. Does anyone has any results of % of "hash entry" collisions that is acceptable (maybe my set is not so bad afther all)?

Toma.

[Reinhard Scharnagl]

According to my Perft using cache tests I have not had any hard collision during hours of running.

Reinhard.

[Anonymous]

Thanks all for replays. I allready tried testing (and minimizing collisions)using perft and normal search on bunch of test positions. Problem is that it takes lots of time and there are still no guaranties that the set of keys won't fit well the test set but be bad in the real game. But it seems that I'll just have to stick with this method. Saving FEN in the hash for testing is another possibility that I think to try. Does anyone has any results of % of "hash entry" collisions that is acceptable (maybe my set is not so bad afther all)?

Instead of storing FENs, it should be much more efficient (in sense of space used and processing power used) to store some other internal format. I just store two pieces in a char -> 32 bytes per position, + castling, ep and side to move. In my engine I have a perft with transposition table. In this mode, storing the whole position is even default, and it does not affect the speed very much (but of course the space used).

I have done some limited tests about how collisions (the "bad" ones, where you have identical hash keys for different positions, not the expected ones, where indices collide) affect the search. In all the tests, they practically did not affect the search. I had to store less than 16 bytes of the hash key inside the HT to get some noticable affect. At this time *many* collision happened. I forgot the details of the test and the results. I reported parts of it on CCC, where it probably can be found with the search engine-

For the test. I practically calculated the index into the HT independent from the stored part of the hashkey.

I believe, that when you have slightly decent random numbers, everything will be almost as good, as it can get. But be aware of gross errors in the set of random numbers. Like always having lots of unset bit (which can easily happen, when you use some system provided rand() and do not paste different calls to rand() correctly together to one number. The method suggested on Bruce Moreland's page can also easily fail - whenever rand() returns a larger range than the supposed 0-2^15^-1).

Regards,
Dieter

[Reinhard Scharnagl]

I use a selfwriten 32 Bit pseudo random number generator, select a special subset of random numbers and combine those in pairs to 64 Bit.

Reinhard.

[Jaime Benito de Valle]

This page generates random numbers using atmospheric noise, rather than pseudo-random generators. You should be able to obtain enough numbers for your purposes.

http://www.random.org/

[Reinhard Scharnagl]

In my opinion the randomness is not that important as the bit distrubution is.

Reinhard.

[Sune Fischer]

[quote="toma"]Thanks all for replays. I allready tried testing (and minimizing collisions)using perft and normal search on bunch of test positions. Problem is that it takes lots of time and there are still no guaranties that the set of keys won't fit well the test set but be bad in the real game. But it seems that I'll just have to stick with this method. Saving FEN in the hash for testing is another possibility that I think to try. Does anyone has any results of % of "hash entry" collisions that is acceptable (maybe my set is not so bad afther all)?

Toma.[/quote

The PRNG I use is a Mersenne twister, but this is not so much for the randomness of it as for the portability.
I think the standard rand() function should be sufficiently random to make a good Zobrist table.
My guess is that the collisions are due to a bug and not because of "bad luck"

Have you checked that the zobrist key doesn't corrupt during search?

To debug this initially (because I had the same problem once) I did a GenZobristFromScratch() function and compared this key to the incrementally updated key.

In my experience there will initially be bugs around the castle and e.p. and promotion moves.

-S.

[Dann Corbit]

A really good test is to have two functions. The normal, incremental function builds the zobrist key from the changes only, and the second zobrist key builder analyzes the entire board (and operates only during debug compiles). If, at any time, the keys differ, throw an assertion.

[Anonymous]

I use a selfwriten 32 Bit pseudo random number generator, select a special subset of random numbers and combine those in pairs to 64 Bit.

Reinhard, do you have any results, that show, that your specially selcected random numbers do better, than just normal random numbers? We had this discussion before, and I believe, I asked a similar question before, but I cannot remember an answer.

BTW. Calling this "special subset" random numbers is not really correct. When you filter a random stream, it won't be random anymore (in general).


Regards,
Dieter

[Reinhard Scharnagl]

Hi Dieter,

randomness is not important. Signal distance is important. Nevertheless within this big subset the numbers still will remain random numbers.

I have not seen any need for further statistical tests. Until now I have not noticed any hard collision in SMIRF.

Reinhard.

[Anonymous]

Reinhard, how do you define "signal distance"?

Dieter

[Sune Fischer]

Hi Dieter,

randomness is not important. Signal distance is important. Nevertheless within this big subset the numbers still will remain random numbers.

I have not seen any need for further statistical tests. Until now I have not noticed any hard collision in SMIRF.

Reinhard.

Hi Reinhard,

Allow me to be a bit pendantic.

A single number cannot be random as such.
Randomness is a property that only a sequence of numbers can have, ie. they must posess a lot of statistical qualities. When you start selecting and changing the numbers of a random sequence it will, like Dieter said, no longer be random.

I guess you are optimizing for the minimal and maximal Hamming distance of the set?

I wonder if there is any proof that this should create better Zobrist tables, although theoreticly one could be so unlucky that a random generator produced two identical numbers.

-S

[Reinhard Scharnagl]

Sune, your assumptions and conclusions are not matching.

Dieter, Distance(a,b) := min(EqualBits(a,b), EqualBits(a,~b))

Reinhard.

[Sune Fischer]

Sune, your assumptions and conclusions are not matching.

Dieter, Distance(a,b) := min(EqualBits(a,b), EqualBits(a,~b))

Reinhard.

Hmm perhaps, though from what you write above it seems my assumption was accurate.

-S.

[Reinhard Scharnagl]

Sune,

it is not my intention to prove something to change peoples conviction, if they are not able to present a proof from it to compare. And even when proving something, people often are not willing to agree. So what?

Please think it over, why a number sequence 1, 2, 3 ... is not a good candidate for generating hash keys, and please do the same with a pseudo random number generator created sequence. It is often taken simply by the hope, to create by that a set of numbers with a SUFFICIENT signal distance. But that has nothing to do with the randomness of that sequence, even when that distance would be better than in the row first mentioned. How would you make improbable e.g. that for three selected numbers holds: a != b^c, or for some other compared xored number combinations? (more precisly demanding the signal distance to be as big as possible)

Reinhard.

[Sune Fischer]

Hi Reinhard,

To me this is not about who is doing what and who is right and wrong, I don't know which is better myself so I'm not suggesting anything.
This is just an objective technical debate, to find the truth no less! :)

With (pseudo) random keys we can pretty easily calculate the probability of a collision with n-bit keys (if we ignore the fact that an xor'ed result will not actually be random).
On the other hand the random property is just a means to an end, there may exist better distributions, like maximazing the bit-distance for example.

The question is how do we figure out which has the better properties, has anyone tested it? I guess it should be possible with e.g. 16 bit keys.

-S.