Author: Christophe Theron
Date: 21:32:32 06/16/02
Go up one level in this thread
On June 16, 2002 at 16:44:23, Uri Blass wrote:
>On June 16, 2002 at 15:33:48, Christophe Theron wrote:
>
>>On June 16, 2002 at 14:11:25, Uri Blass wrote:
>>
>>>On June 16, 2002 at 12:53:19, Gian-Carlo Pascutto wrote:
>>>
>>>>Hello all,
>>>>
>>>>my program has been seriously suffering from search instabilities
>>>>since the day I started re-using my hashtables between searches
>>>>(i.e. not clearing them). I dissected the problem into a pathological
>>>>case this afternoon:
>>>>
>>>>1) We are pondering, do a deep 20 ply search and see that we have
>>>>a combination to promote a pawn or three. We start failing high
>>>>bigtime.
>>>>
>>>>2) The opponent plays a different move than expected, but because
>>>>this is an endgame, it transposes into the variation we were pondering
>>>>anyway, so we get a lot of hash hits.
>>>>
>>>>3) We start our normal search on ply 3 with a window [-50,50].
>>>>We get a hash hit one of the bottom nodes. It indicates a lowerbound
>>>>of +2000. This is enough to get a cutoff, and we fail high.
>>>>
>>>>4) We restart our normal search on ply 3 with a window [50, inf].
>>>>We get a hash hit one of the bottom nodes, but this time the bound
>>>>is _not_ enough to get a cutoff. We search this node, and (because
>>>>we're only 3 ply deep), only see an advantage of 0.01. We fail low.
>>>>
>>>>5) We see a fail high followed by a fail low in the search driver,
>>>>and need a way to resolve this. I do a full-window research in this
>>>>case [-inf,inf]. Which gets a score of +0.01 back.
>>>>
>>>>6) We start our search at ply 4 (same thing all over again)
>>>>
>>>>7) This repeats until the search starts to see the 20 pawn
>>>>advantage. We did 3 searches on each ply, two of them with an open
>>>>window.
>>>>
>>>>Thank god I don't get this worst-case-scenario often, but I
>>>>do see a lot of fail high/fail low combinations caused by this
>>>>effect.
>>>>
>>>>I'm wondering if anyone knows a solution, or what other people
>>>>that reuse hashtables do.
>>>
>>>The most simple thing to think about is clearing the hash tables after the first
>>>combination of fail high/fail low.
>>>
>>>Note that I decided to clear the hash tables in movei after every move because I
>>>found that not doing it is probably counter productive.
>>>
>>>I do not understand the reason but I found that in one case not clearing them
>>>caused a different score that leads to worse positional move at the same depth.
>>>
>>>After it I decided to test Movei with clearing the hash tables and found better
>>>results.
>>>
>>>Note that Movei does not use hash tables in an effective way.
>>>
>>>It does not use hash tables to prune the tree and it uses almost always the
>>>always replace method.
>>>
>>>The only case when I do not replace are cases when movei already remember a move
>>>at bigger remaining depth for position with the same 64 bit key(the same address
>>>in the hash tables is not enough).
>>>
>>>The reason is that in this case if the move that movei remembers is the same
>>>move it may be a waste of time and if the move is not the same move it may be
>>>counter producitve because movei may remember a different move that works only
>>>at small depth and when it gets bigger depth it may start with the wrong move.
>>
>>
>>So you are not using the "always replace" strategy. You are using the strategy
>>used by most chess programs: replace with better quality info only.
>>
>>Always replace is when you replace the hash table entry without looking at
>>what's already there.
>
>I do not think that I do what most programmer do.
>
>I believe that most programmers decide if to replace also when the entry is the
>same and the 64 bit key is different.
>
>I consider not to replace the best move only when the entry is the same and the
>64 bit key is the same.
>
>Uri
Yes you are right. I had missed this important part about the hash key being the
same.
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
This page took 0.01 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.