Author: Tom Likens
Date: 12:14:54 09/13/03
Go up one level in this thread
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
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.