Fail low after fail high

[jwes]

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?

[hgm]

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]

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]

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]

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]

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]

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.

[hgm]

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]

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.

[hgm]

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.