Author: Ulrich Tuerke
Date: 05:35:36 12/29/99
Go up one level in this thread
On December 29, 1999 at 06:38:36, José Carlos wrote: >On December 28, 1999 at 10:02:23, Robert Hyatt wrote: > >>On December 28, 1999 at 01:38:49, William Bryant wrote: >> >>>I looked at this a year ago, but want to again ask the best way to handle >>>this situation. >>> >>>You fail high at the root, >>> increase alpha to beta -1 >>> increase beta to Mate (or Mate - 1 depending upon how these are defined) >>>Then you fail low on the same move. >>> >>>What I have been doing is accepting the fail high as correct, >>> making this the PV move, >>> and continuing the search at the next iteration with >>> a window set around alpha which is the old beta -1, + or - the aspiration >>> window size. >>> >>>Is this correct, is there a better way to handle a fail high/low. >>> >>>Thanks >>> >>>William >>>wbryant@ix.netcom.com >> >> >>I have two cases. (don't forget I use PVS). >> >>1. get a value for first root move as normal, then a later move fails high >>on the null-window search, but when I re-search with the normal PVS window, >>it now fails low. I pretend the fail high didn't happen and keep the original >>root move. >> >>2. A root move fails high, but then fails low on the re-search. I keep the >>fail-high move. You can probably eliminate the fail-low by simply searching >>with -inf,+inf, but it will be slower, and due to hash overwrites/draft problems >>this fail-high/fail-low problem will happen without this large window. And with >>the large window you might fail high on bound X, but get a score back that is >>< X... >> >>It is mainly an artifact of null-move search and hashing... > > I don't use null-move, but I use hashing, and I don't understand how is it >possible to get a fail-high and then a fail-low in the research due to the >hashing. > As I understand, when I fail-high in the pvs, I get a lower-bound for the real >value of the position (I use fail-soft), so if I research with the new alfa set >to that value, I could never fail-low. Am I wrong? Theoretically, you are 100% right. However, practical chess playing program are different. Formerly, I also very often observed the kind of search anomalies which you describe. IMHO, the main reason for this problem is a dependency of the search on alpha and beta. In pure theory, the search result must not depend on alpha and beta. In practice, we do however have these dependencies; null-move, lazy eval, extensions, ... . Consider for instance the case that your fail-high was due to some clever tactical extension, depending on alpha. Subsequently, you re-search with a shifted alpha-beta window, and - may be - you don't reproduce the pre-condition for extending (because your alpha had been shifted). Then you verification search cannot verify the evaluation of the original search. I think that reduction of some of these dependencies will already help. At least it was so in my prog. Regarding the assumption of Bob Hyatt (hashing), he is probably thinking of some "path-dependencies" of the search. Consider for instance the case that you extend the search because of re-capture. In another path the recapture may not immediately follow the capture (thus you don't extend) but the line may lead to the same final position. So, you search differentiates between these lines but hashing of course not. This can also cause some kind of anomalies. I am afraid, we have to live with these things. At least I am not willing to skip nullmove and hashing in order to get a anomaly-free search. Uli > > José C.
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.