Author: Anthony Cozzie
Date: 13:03:44 09/13/03
Go up one level in this thread
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". Brain fart ;) 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.