Author: Andrew Williams
Date: 02:11:57 08/07/99
Go up one level in this thread
On August 07, 1999 at 01:09:00, Dave Gomboc wrote: >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 For what it's worth, I use the "Mersenne Twister" random number generator. I don't know how it works; I just searched the web for "Mersenne Twister" and downloaded the source code. It was very easy to incorporate into my program and it works fine - and of course "Mersenne Twister" sounds cool. Andrew Williams
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.