Fail low after fail high

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
jwes
Posts: 775
Joined: Sat Jul 01, 2006 5:11 am

Fail low after fail high

Post by jwes » Sat Apr 04, 2015 5:13 pm

When there is a fail high with a zero window search, and we research with an open window and it fails low, why do we assume that the first search is the one that is wrong?

User avatar
hgm
Posts: 22587
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Fail low after fail high

Post by hgm » Sat Apr 04, 2015 5:46 pm

I guess open-window searches are supposed to be more reliable. And what is the alternative? The first search did not give you a score. So if you would declare that PV, what would you compare the next branches to be searched against, to decide if they are better? (And how could you know whether the score would be a PV score, or a fail high?)

jwes
Posts: 775
Joined: Sat Jul 01, 2006 5:11 am

Re: Fail low after fail high

Post by jwes » Sat Apr 04, 2015 9:52 pm

hgm wrote:I guess open-window searches are supposed to be more reliable. And what is the alternative? The first search did not give you a score. So if you would declare that PV, what would you compare the next branches to be searched against, to decide if they are better? (And how could you know whether the score would be a PV score, or a fail high?)
One possibility would be to extend and research the node with an open window.
Another possibility would be to research the situation. Run some tests to see how often this occurs and how often the first score is better than the second score.

Sven
Posts: 3698
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Fail low after fail high

Post by Sven » Sat Apr 04, 2015 11:07 pm

jwes wrote:
hgm wrote:I guess open-window searches are supposed to be more reliable. And what is the alternative? The first search did not give you a score. So if you would declare that PV, what would you compare the next branches to be searched against, to decide if they are better? (And how could you know whether the score would be a PV score, or a fail high?)
One possibility would be to extend and research the node with an open window.
Another possibility would be to research the situation. Run some tests to see how often this occurs and how often the first score is better than the second score.
Again, you don't have a first score so there is nothing from the first search that can be compared to anything. You have a "score >= alpha+1".

If you really mean "open window" as "-INF..+INF" then there is no fail low in the research, of course. If you mean "alpha..+INF" then a fail low on that one should (might) trigger another research, otherwise you don't have a score even here.

zd3nik
Posts: 193
Joined: Wed Mar 11, 2015 2:34 am
Location: United States
Contact:

Re: Fail low after fail high

Post by zd3nik » Sat Apr 04, 2015 11:22 pm

jwes wrote:When there is a fail high with a zero window search, and we research with an open window and it fails low, why do we assume that the first search is the one that is wrong?
Many engines do slightly more aggressive forward pruning, depth reductions, etc in a null window search. in those cases an open window search is clearly more trustworthy than a null window search.

bob
Posts: 20357
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Fail low after fail high

Post by bob » Sun Apr 05, 2015 5:58 am

jwes wrote:When there is a fail high with a zero window search, and we research with an open window and it fails low, why do we assume that the first search is the one that is wrong?
Who assumes that? I don't. A fail high is always accepted for me.

bob
Posts: 20357
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Fail low after fail high

Post by bob » Sun Apr 05, 2015 6:00 am

zd3nik wrote:
jwes wrote:When there is a fail high with a zero window search, and we research with an open window and it fails low, why do we assume that the first search is the one that is wrong?
Many engines do slightly more aggressive forward pruning, depth reductions, etc in a null window search. in those cases an open window search is clearly more trustworthy than a null window search.
This isn't the main problem.

A deep draft hash entry says score > xx. You fail high. Now a normal search can't use that hash entry and has to search on its own, but it can't reach as deeply. Fail low. The fail high is STILL valid, however. You just can't resolve the actual score.

User avatar
hgm
Posts: 22587
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Fail low after fail high

Post by hgm » Sun Apr 05, 2015 10:09 am

In this scenario, it would be more accurate to take the lower bound obtained by the initial fail high, and use it as if it were an exact score. (If you don't want to do any extended re-re-search, which I expect to be prohibitively expensive, and still no certain cure, as even that could fail low.) This means you might under-estimate the score, but believing the fail low would under-estimate it even more.

Of course in general it would be hard to know whether this scenario applies, rather than the null-window search being pruned more. For this reason it would be better to address the problem when it first occurs, and where we can be aware that it occurs:

If a search of depth d is requested, and the position gets a hash hit with draft N > d, and a lower bound L with alpha < L < beta, this would not be usable. So you would do a re-search at depth d. Now suppose that this search fails low, or, even more general, returns a value < L. (Some engines would do the re-search with window {L, beta} after such a hash hit, in which case a score < L would always mean a fail low.)

You would now have to proceed based on contradictory information: one search says score < L, and a deeper search says score >= L. It makes sense to not allow the information obtained by the shallow search to overrule that of a deeper one, so in any case score >= L. The problem is that that deep search doesn't tell you how much larger, and the shallow search refuses to tell you either. The least wrong of all possible evils seems to assume that the score is exactly L: this does not violate the result of the deeper search, and it minimally violates the result of the shallower re-search. A similar policy couldbe used in the opposite case, where an over-deep hash hit gives you an upper bound that is not suitable for the current window, but the shallower search provide a lower bound that is larger.

Propagating these 'consistent' scores towards the root should ameliorate search instability in general.

mvk
Posts: 589
Joined: Tue Jun 04, 2013 8:15 pm

Re: Fail low after fail high

Post by mvk » Sun Apr 05, 2015 1:37 pm

hgm wrote:In this scenario, it would be more accurate to take the lower bound obtained by the initial fail high, and use it as if it were an exact score. (If you don't want to do any extended re-re-search, which I expect to be prohibitively expensive, and still no certain cure, as even that could fail low.) This means you might under-estimate the score, but believing the fail low would under-estimate it even more.
Sounds familiar:https://groups.google.com/d/msg/rec.gam ... kpT8qfrhQJ

I do it currently (again), but only for mates and endgame table wins. It helps solve KRK using only forward search, without evaluation, for example.
I don't think if I will reintroduce it for non-mates. It seems safer to trust the research score over the scout score, due to unequal effective search trees.
[Account deleted]

User avatar
hgm
Posts: 22587
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Fail low after fail high

Post by hgm » Sun Apr 05, 2015 2:06 pm

But would it also be safer to trust the shallow search over the deep hash hit? If the deep hash hit would also have been used in the re-search, it might not have failed low, but could have returned the same score as the scout search. And it would have had an even bigger effective tree, as the hash hits grafted a deeper sub-tree onto it as the re-search would have done.

Post Reply