Author: Renze Steenhuisen
Date: 05:05:15 04/08/04
Go up one level in this thread
Happy Debugging!
The problem was: I had the problem of having too many hashkey collisions. I
measured a collision as having two different positions having the same 64-bit
hashkey. The problem occured to me when counting the number of good hashtable
move-suggestions.
The chance of collision of two 64-bit hashkeys should be something like 1 in a
billion (= 10^9).
In my situation I had 0.03% of the positions a hashkey collision... and I didn't
know what it caused.
My debugging period:
- check the hashkeys:
- are they 64-bit
- count 0's and 1's distributions, both overall and per bit-position
(should both be ~50%)
- check the Hamming Distances of all keys compared to eachother
(haven't done this myself but it was said that you should get
minimum>=14 and average aproximately 31)
- check incremental hashkey generation
- make sure that all variables are initialised to 0x0000
- make sure you're using right-to-move in hashkey
- compare the incremental hashkey with the fresh-created hashkey from the
position (should be the same of course)
- make sure that you handle NULL-moves correctly
- just comment away everything accept the core algorithm, so no quiescence
or pruning or NULL-move or ETC or extensions or reductions. You can
always put it in again later on.
- if a collision occurs, print the suggested move, print the board, print
it all! And look for yourself in the data, and try to find a pattern.
My solution:
- use en-passant field in hashkey (saves some collisions)
- use castling-rights in hashkey (saves some collisions)
BUT MOST IMPORTANT!!! (the thing I missed... and costed me a day)
- use different "random" numbers for black and white pieces/pawns!!!
(that saves it all)
Hopefully this information is of any help to you, or at least you can have a
little laugh :-)
Cheers!
Renze
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.