Computer Chess Club Archives


Search

Terms

Messages

Subject: Search instabilities when re-using hashtables

Author: Gian-Carlo Pascutto

Date: 09:53:19 06/16/02


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.

--
GCP



This page took 0.02 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.