Author: Robert Hyatt
Date: 05:57:11 08/06/99
Go up one level in this thread
On August 05, 1999 at 22:51:41, Scott Gasch wrote: >Both Bob and Bruce mentioned a small hash table specifically for detecting >repetition. I guess this would be implemented as an array of counts indexed by >a subset of the position's hash key -- say the last n bits. What is to prevent >false draw reading, however, if two (different) positions in the same search >yield the same key subset (and artificially inflate the count). > You have to use traditional hashing methodology here... ie you use the right-most N bits of the hash signature as a probe address, but you store the _entire_ hash signature for verification. And if you index to a table entry that is used, use traditional 'collision' handling to find an unused entry, which you will _know_ is available since you are going to make the table large enough that it can't fill (it can't ever have more than 100 useful entries due to the 50 move rule). If you make it big enough, you can store _all_ the moves for the current path, plus 100 moves from the real game, and all that is left is some sort of bucket/chaining/rehashing algorithm to resolve the collision. >Related question: I am initializing my transposition hash square-piece array >with just random numbers (rand()). This is not good for many reasons: 1) if the >random numbers I get (seeded off system clock) are bad (not very random) hashing >performs badly and we have many collisions (I have not really seen this happen >but in theory I guess it could). 2) there is no way I can predict what a key >for a given position will be beforehand which is okay now but when I write an >opening book I'd like to be able to do this. So definately I need some kind of >function to generate the seeds. > >My (next) question is this -- what do you guys do for said function? I am >computing two numbers for each position - a key and a checksum. The key is just >xors of seeds for piece/square and the checksum is adding and subtracting seeds. >I had considered using prime numbers for the seeds but I don't see how that >really will help produce a uniform hash distribution. > >Scott
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.