Author: Roberto Waldteufel
Date: 02:52:43 09/22/98
Go up one level in this thread
On September 22, 1998 at 04:19:45, Dan Newman wrote: >On September 21, 1998 at 21:50:52, Dan Newman wrote: > >>I once read a paper on this subject that found the two level table to >>be the best amonst various other schemes--at least I think I read such >>a paper... I've looked around and can't find it though. I'll look >>some more later... > >I found the paper: D.M. Breuker, J.W.H.M. Uiterwijk and >H.J. van den Herik, "Replacement Schemes for Transposition >Tables," ICCAJ (1994), v17n4, p183-193. You can download >a postscript version of it via Breuker's page at >http://www.cs.rulimburg.nl/~breuker/. (My copy of the >postscript paper seems to be missing the figures though...) > >They compare 7 different replacement schemes including two >versions of the two level scheme. They found that two level >schemes are better than one level. They found the worst >scheme was one they call "New" in which the entry is always >overwritten. The best was one they call "TwoBig1" in which >one level is "always replace", and the other is "replace if >the number of nodes searched below the position is greater". >(Depth takes far fewer bits to store than node counts, and >for that reason it may be preferable to use the other two >level scheme they describe, called "TwoDeep"--that's the one >that I use.) > >Anyway, for large tables (>512 K entries) they found only >a 3% spread in nodecounts between the worst and best schemes. >For an 8K table they got 23%. (This makes sense since a >larger table has fewer collisions to start out with and then >later, once it's filled, its entries tend to hang around >longer.) > >Carl Ebling in "All the Right Moves" (1986) describes a >two level hash table scheme. (I got a copy last year via >Amazon.com. It's a dissertation on Hitech's hardware.) >I'll excerpt a small section that explains the reasoning >behind the two level scheme, p.96: > "At the greater search depths, the main table becomes > static as it is filled with positions near the top of > the tree [I assume he means near the root], and the > FIFO table [this is analogous to the "always replace" > table] becomes a cache for nodes in the current subtree." > >He goes on to describe a scheme which uses only one table >but which has much of the benefit of the two table scheme. >Nodes near to the root are subject to the depth replacement >scheme and are marked as "privileged". Those that are >further from the root are "always replace"--except they >aren't allowed to replace privileged nodes. > >-Dan. Thanks for the info and references. I think I will give this a try if I can find some time to work on it (been quite busy recently due to illness in the family). It occurs to me that my depth replacement single level system may be seriously flawed because sometimes positions with large depths can stay far too long in the table long after the game has moved on. Maybe there should also be an "age" entry in the tables based on the move-number at the root of the search when the move was stored (or maybe last used)? Best wishes, Roberto
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.