Author: Uri Blass
Date: 11:11:25 06/16/02
Go up one level in this thread
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. I thought that this is obvious that not clearing the hash tables cannot cause Movei to be weaker but for some reason that I do not know today it seems to be wrong and the trouble that I found surprised me because it was not being slower in getting some depth(Maybe Movei is slower in getting the same depth and I did not check it but it was not the important thing that I found). The problem that I found was a different score at the same depth that caused Movei to change it's mind to a worse positional move. It is possible that it is a combination of my special pruning rules with my implementation of hash tables that caused the problem but I still do not understand the exact reason. I will have to look carefully in the tree and the evaluations to find out but Movei from version 00_71b in the last days always clear it's hash tables between moves and I am not going to change it without finding in games that changing it gives better results(I am always afraid from bugs and even a change that is in theory better is not going to be used without testing). Uri
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.