Author: Dennis Breuker
Date: 09:45:54 06/18/02
Go up one level in this thread
For an overview of hash tables replacement schemes, see my thesis: http://www.breuker.demon.nl/thesis/index.html. I quote from the summary: "In Chapter 2 three methods for improving the efficiency of a transposition table are described. The first method addresses the use of an adequate replacement scheme. When a conflict arises, a replacement scheme decides which positions to keep in the table, and which positions to discard. Experiments show that in this area improvements can still be found. A new replacement scheme, called TwoBig1, based on a two-level table and the number of nodes of the subtree investigated, outperforms all other schemes." Download chapter 2 and you can find it out for yourself! TwoBig1 basically says: do both strategies: keep the deep entries (those with a large subtree) and always store an encountered position in the table (since there are many local transpositions deep down in the search tree). Dennis >>>So you are basically using an always replace scheme. But it is inferior to the >>>other scheme (replace only when new info is of better quality = bigger depth >>>than the existing one). >>> >>>Why don't you use the better scheme? You are only one test away from it. >>> >>> >>> >>> Christophe >> >>The problem with replace only when the new information has bigger depth is that >>it is possible that there is a node with a big depth that is not used. >> >>I also think that it is possible that some nodes are used often at small depth >>with different order of moves that lead to the same position and not replacing >>only because of some deep nodes may be a mistake. >> >>It is also obvious that if I do not clear the hash tables after every move >>replace only when you have bigger depth is a mistake because you are going to be >>left with old nodes that are not important and my first implementation of hash >>tables was without clearing the hash tables. > >You could also 'age' the hashtables: Replace always when the hash entry was not >inserted/referred to during this search, use another scheme when the hashentry >was inserted during this search. This preserves results from previous iterations >for move-ordering without ending up with only old entries. > >>I remember that I did not find clear advantage for replace only when the depth >>is bigger but it may be also a result of other problems. > >A node with larger search depth costs more to reproduce. You'll need to probe an >entry with a 2 ply shallower depth about 15 times as much before it's worth >having the shallower one. > >Richard
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.