Author: Tord Romstad
Date: 12:28:07 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(). Welcome to the club! Since version 0.3.0 (released one week ago), Gothmog also uses MTD(f). Even if your first results are not very good, don't give it up too soon. It took me a couple of weeks before my MTD(f) version performed as well as the non-MTD(f) version. If your PVS is more optimised and less buggy than my old aspiration alpha-beta search (which is almost certainly the case), you may need to invest even more work before MTD(f) pays off. >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. I use 24 bytes (8 bytes for the hash key, 4 bytes for the best move, 2 bytes for the upper bound, 2 bytes for the lower bound, 2 bytes for the search depth associated to the upper bound, 2 bytes for the search depth associated to the lower bound, 2 bytes for generation counters, and 2 bytes for various flags). I am definitely not a low-level programmer. What does "cache-line-aligned only 75% of the time" mean, and is it something I should worry about? Tord
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.