Author: Dan Newman
Date: 16:02:43 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). > The trick here is to also maintain a list of the hashcodes that you scan whenever the count indicates a repetition. This small (simple) hash table is there just so you can avoid a lot of scanning of the hashcode list. I haven't yet tried this yet--I just scan the list and it seems OK so far. The more complex hash table described by Bruce and Bob requires chaining to ensure that all the positions can be stored. This scheme might be as expensive as the above scheme if a lot of chaining occurs... It's also quite possible that these schemes save very little over just scanning a list of hashcodes--I guess I should do the experiment. >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 I read my random numbers in from a file that I generate with a separate program. The idea is to have exactly the same (good) set each time so that my book file will still work, and I can get the same tree seached with different compilers and machines. I play around occasionally with the program that generates the random numbers to try and get a better set--I look at Hamming distance, try to make them more random, etc. For instance, if you use a 32-bit RNG (as I do), you need two numbers for each 64-bit bitpattern. But consecutive numbers from typical RNGs are highly correlated in the lower order bits. The one I use (and all those rand()'s I've seen) alternate odd and even numbers. If you construct your 64-bit numbers from consecutive calls to such a rand() then you will effectively have at best a 63-bit random number since two of the bits are always anti-correlated. It may be much worse. The next to the last bit will typically show something like 0 1 1 0 0 1 1 0 0 ... on consecutive calls to rand(). Anyway, I use a simple dirty 32-bit RNG from Numerical Recipies that they claim is fairly good and select numbers generated on the basis of Hamming distance and/or other tests (can't remember what I did last...). It's probably best to use a RNG written in C so that you get reproducible results with different compilers and on different systems and to avoid particularly bad rand() functions (like the 16-bit RNG provided with Microsoft compilers in the past--don't know about the current MS compiler). I'm not sure what the ANSII standard requires (if anything), but I vaguely recall a 16-bit requirement. -Dan.
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.