Author: Andrew Williams
Date: 10:53: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 My program uses MTD(f). In the TT I have two bounds and a depth for each bound. An entry is a total of 21 bytes at the moment, although it could be compressed. It never occurred to me to put three records together in one entry. That's an interesting idea. Andrew
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.