Author: Robert Hyatt
Date: 18:11:34 11/08/98
Go up one level in this thread
On November 08, 1998 at 18:38:07, Inmann Werner wrote: >Hello all! > >I work with hash tables since a year. And I often changed the algorithm, when to >replace a hash entry. > >Hash tables have two reasons. >1) To store the value of a position, and if you get a hit, you reduce your >further tree search to 0. >2) for move ordering in the move generator, to get good moves at first. > >Because of evaluation function and other problems, i clean the hash table after >each real move. (Do all do that?) I don't... I only do this if something changes the piece/square tables at the root, which would change all the scores and make hashed scores invalid. I also don't "zero" the table to keep the good moves for move ordering, so I just have 4 types... EXACT, LOWER, UPPER, USELESS... >But I do not clean it really, I only set a flag cleaned, which means, that the >entry is dead for 1) (hash hit for value), but not for move ordering. > >Now, with iterative deepening, the same move often comes, and there are requests >to put it into the hash table. >And here my problem begins. >for move ordering, it is best to have the deepest searched move in the table, >ignoring the value. >for cutoof hits, you need also deep searched values, but not the "cleaned" one >from previous searches. > >How should the entrys be replaced? >What do other programmers do here? >Maybe have two hash tables? > >Greetings > >Werner the easiest approach is what I would call the "Ken Thompson" algorithm... you use two hash tables... one is depth-preferred where you always keep the entry with the deepest "draft"... the other is "always" store. In my case, I check depth preferred and if I should replace, I move the depth-preferred entry to "always store" and then overwrite depth-preferred. Otherwise I stuff in always-store... I also have an "age" field that is a 3 bit value... each new search (not iteration) increments an "age counter"... if the age field in the hash entry doesn't match the current age counter, I overwrite, period...
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.