Author: Robert Hyatt
Date: 06:43:49 05/22/01
Go up one level in this thread
On May 22, 2001 at 08:03:51, Pham Minh Tri wrote: >Hi all, > >I implemented my hash table by learning from some documents and old posts. It >was a mixture of 32 and 64 bit. It worked but was not good performance. I have >revised it and found some problems, as well as some misunderstands and lack of >knowledge. Now I want to rewrite it in 64 bit. My questions are: > >1) It is necessary to have both hash key and hash signature 64 bit? Could one of >them be 32 bit? I assume you are using "hash key" to be that part of the hash signature you actually store in the table? If so, this might be pretty safe, so long as you use one end of the signature to store, and the other end to compute the table address. For small hash tables, you do take a greater chance on getting a collision of course. > >2) How to generate a 64 bit random number? (I use ran()*ran(). Is it OK?). I would use ran()<<32 + ran myself. > >3) Which set of random numbers is "bad" for chess? How to generate a "good" set >of random numbers? Is it necessary to filter (prune) some "bad" numbers? Not really. You can try to optimize the hamming distance between each pair, but that is computationally expensive at setup time and I'm not sure it is worth the trouble. Lots of duplicates will wreck things of course. > >4) To start, I usually use the command srand((unsigned)time(NULL)) - is it good >or dangerous? Should I use a "good" const? I would use the default for lots of reasons. 1. you will get a different set of random numbers each time you run. Which means you can't use the hash signatures for your opening book; 2. You don't want an even random seed, and you have a 50% chance of getting one with the above, maybe higher than that. > >5) How to map hash key into hash entries (which the number of hash entries is >not 2^N)? (I use the operation %, but wonder if there is a better way). That's about it if you don't use a power of 2. > >6) I use the operation addition for making new hash key. Certainly, it is slower >than XOR, but anything else? (I heard one time about it, but forgot). XOR is better. and easier to undo when you take back a move. If you use add, you can get overflows and when you later subtract, you can have a problem. > >7) How to measure the "collision" (I little confuse about the dividend)? And >other measurements? If you do 64 bit signatures, they will be rare enough to ignore. The only way to measure them is to store both the signature and a real compressed version of the board. When signatures match but the real board does not, you just had a collision. You don't do this except for testing, however... > >Many thanks for any help and suggestion. >Pham
This page took 0.02 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.