Author: Don Dailey
Date: 21:14:33 09/22/98
Go up one level in this thread
On September 22, 1998 at 22:20:48, Dave Gomboc wrote: >On September 22, 1998 at 12:17:03, Pat King wrote: > >>Well, upon pondering the problem I made a refined estimate (but >>still only an estimate) of 2^32 or about 4.3 e+09 nodes, which >>works out to 20.2 plies instead of 19.something. Is the 2^32 >>figure for P(lookup error)=.5 for a 32 bit key a coincidence? I >>suspect not. If not, then you can easily decide on how much error >>you're willing to tolerate. Based on this analysis, 64 bits >>certainly seems like overkill to me. >> >>Pat > >We know from experimentation that 32-bit hash keys are not enough to prevent a >fatally high number of collisions in a 3-minute search. The next logical number >ot use is 64 bits, simply because it is the next higher power of two. Sure, >maybe you could try it with 48 bits or 56 bits, but why bother? It's going to >cost you more time than it is worth for the extra space that you save in the >hash table. > >Dave Gomboc There is a lot of math theory on this subject. We once studied this with empirical self testing and simple analysis. It turns out that 32 bits guarantee frequent collisions on modern processors, and yet will not weaken the program very noticably at all. The issue is not how often you get a collision, but how often it will affect the move choice at the root. That in itself is worth a few extra bits. Our calculations indicated that we were probably getting a collision every 2 or 3 seconds which seems incredibly alarming. But our test results were fine when compared with a safer version. In fact I concluded that the 64 bit version was weaker because the overhead of maintaining the key and extra state in the hash table entry slowed the program down more than the benefit. Still, I was willing to trade a little speed for peace of mind and went with the 64 bit version! A good compromise is to generate two 32 bit keys. Use one key for calculating a hash table address and use the other key for the lock or verify bits (whatever you guys are calling it these days.) In Cilkchess I am extra paranoid and generate two 64 keys since the program runs on a 64 bit machine. So effectively my key is 64 bits plus the number of bits I use to calculate the address. But 64 bits should be plenty for at least 3 or 4 more years! Of course you will get collisions no matter how many bits you use unless you represent the position exactly. - Don
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.