Author: Dave Gomboc
Date: 22:09:00 08/06/99
Go up one level in this thread
On August 06, 1999 at 19:02:43, Dan Newman wrote: >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. I've heard a lot of bad things about Numerical Recipies in C. I even found a page at JPL/NASA dissing it. :-) Random numbers are hopefully simple enough that they got it right, though. You could always consult Knuth... Dave
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.