Author: Anthony Cozzie
Date: 12:59:19 09/13/03
Go up one level in this thread
On September 13, 2003 at 15:14:54, Tom Likens wrote: >On September 13, 2003 at 13:39:22, Anthony Cozzie wrote: > >>I have decided that I want to try out MTD(f) in Zappa. It sounds like a cute >>algorithm with a number of advantages over PVS(). >> >>My hash table right now is a crafty-style limit hash: 2 bits type (upperbound, >>exact, etc) and 16 bits score (zappa uses -10,000 -> +10,000 which requires 16 >>bits). It seems like MTD(f) requires a dual-bound hash: 16 bits upper limit and >>16 bits lower limit. I would imagine that a single bound hash would be very >>inefficient. >> >>Unfortunately, I can't get this to fit in 64 bits. >>UL: 16 bits, LL: 16 bits, Move: 24 bits, Depth: 7 bits, 1Rep: 1 bit, Mate >>Threat: 1 bit, Search ID (for depth-first): 3 bits = 68 bits. >> >>So, it seems to me that there are 4 possibilities: >> >>1. Steal 4 bits from the hash key. Collisions are now 16x more likely (don't >>really like that) >> >>2. Extend trans_ent to 32 bytes (wasting 45% of the total memory) >> >>3. Extend trans_ent to 24 bytes (cache-line-aligned only 75% of the time) >> >>4. Extend trans_ent to 21 bytes, have 3 probes and 1 pad byte. (somewhat ugly, >>more memory traffic) >> >>Option 4 looks the most appealing to me right now, but I'm open to suggestions. >> >>anthony > >Hello Anthony, > >I'm guessing you use a 64-bit hash key and steal the lower (or upper) N bits >for the address into your hash table. If the previous assumption is true >then you have N redundant bits that you could steal from the *storage* of >the hash key without any loss of accuracy. For example, if you use the >lower 16-bits then when you save the hash key into your table only save the >upper 48 bits. And when you compare only compare the upper 48 bits. Of >course your main hash key is still 64-bits. This should free up the >bits you need. > >--tom Sigh . . I guess its been too long since I took 18-347. Can't believe I forgot the fundamentals of such things. Thanks for the help. anthony
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.