Author: Alex Boby
Date: 11:12:57 05/08/01
Go up one level in this thread
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"?
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.