Author: Robert Hyatt
Date: 18:38:57 05/08/01
Go up one level in this thread
On May 08, 2001 at 14:12:57, Alex Boby wrote: >On May 08, 2001 at 13:56:10, Robert Hyatt wrote: > >>On May 08, 2001 at 13:43:50, Alex Boby wrote: >> >>>On May 08, 2001 at 09:12:29, Robert Hyatt wrote: >>> >>>>On May 08, 2001 at 01:58:00, Alex Boby wrote: >>>> >>>>> >>>>>This has probably been asked a thousand times in the past so sorry for asking >>>>>but I grep'd the archives and didn't find anything satisfying so here goes... >>>>> >>>>>How do most people deal with hash key collisions (2 positions, same key)? These >>>>>cause problems for me currently because of illegal moves. I figure that there >>>>>are 2 solutions... >>>>> >>>>>1) store the actual unique board position in the hash record for comparision. >>>>>2) check the moves stored in the hash table to see if they are valid before >>>>>using them. >>>>> >>>>>1 doesn't seem like a plausible solution (gigantic hash records) and 2 seems >>>>>like it would be slow unless I could find a trick to do it easily. >>>>> >>>>>Is there a standard solution to this problem? >>>>> >>>>>Alex >>>> >>>>1. If you are not using 64 bit hash signatures, you must. 32 bits is not >>>>enough and will cause problems. >>>> >>>>2. If your MakeMove() will corrupt the chess board when given an illegal move, >>>>then you must check it for legality as even with a 64 bit signature, there is >>>>_always_ a possibility of a collision and illegal move. >>>> >>>>3. If you are using 64 bit signatures, your random numbers are either not so >>>>random, or something is broken in your hashing. >>> >>>I am using 64 bit hash sigs but my random numbers are probably not good, I >>>haven't tested them yet. I was reading alot of posts on 'hamming distance' a >>>long while back and I think I'll look into that. But nonetheless, no matter how >>>good your numbers are you are still going to have this problem because of the >>>lossiness of the algorithm. >>> >>>It seems that I must check the moves for legality because my makemove() >>>definately corrupts the board when it gets illegal moves. >> >> >>you will have the "problem" but you should not see more than one or two >>collisions per hour or so of search. If you are seeing lots of them, then >>that suggests you have other problems... perhaps bad random numbers, or >>random numbers improperly formed... > >How can a random number be "improperly formed"? Once common way: take a random number generator that produces floating point numbers in the range 0.0 <= N < 1.0 and take two of those numbers and combine them into one 64 bit random number. Except that IEEE FP uses the leftmost 9 bits for sign and exponent which won't vary much. You are really getting 46 bit random numbers and not 64. I have seen this often.
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.