Author: Pham Minh Tri
Date: 17:21:37 05/22/01
Go up one level in this thread
On May 22, 2001 at 09:43:49, Robert Hyatt wrote: >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. > I have used a hash key 32 bit and a hash signature 32 bit (same method for computing). I used the hash key for finding the table entry, and store the hash signature to check. Do you mean only one hash key 64 bit could replace my 2 numbers and be better? > > >> >>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 Actually, I use the random seed in hope that my program could play the little different games even they have the same openings. But I should agree with you because of other reasons. >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. > I do not really understand this point. If I subtract the same number, the variant should be recovered the old number, event last overflow of addition. Is it true? > >> >>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... > Sorry, but IMO, this is type 1 error. The definition of collision is type 2, when 2 positions map onto the same entry, but different hash keys. > >> >>Many thanks for any help and suggestion. >>Pham Thank again everybody for your helps and information.
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.