Author: Tord Romstad
Date: 05:34:04 09/14/03
Go up one level in this thread
On September 13, 2003 at 16:03:44, Anthony Cozzie wrote: >On September 13, 2003 at 15:28:07, Tord Romstad 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(). >> >>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 > >I really didn't explain this right. I meant to say "in a single cache line only >75% of the time". Which I also don't understand a word of. :-) But as my latest gprof output shows that my program spends less than 1% of its processor time on hash table stuff, I suppose there is no reason for me to worry about this. 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.