Reduction Research Question

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.
D Sceviour
Posts: 442
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Reduction Research Question

Post by D Sceviour » Fri Sep 25, 2015 3:01 pm

If the depth was reduced, and the Search() returns a value >= beta, accepting the move score is risky (the move was reduced as it was predicted bad and expected to fail low). Supposedly, the search is repeated using the original (non-reduced) depth to see if the fail-high happens again. There are a number of problems with this:

(1) The first problem is that research can introduce errors as well as solve them. The horizon ply cannot refute threats in quiescence, only swap material. At deep depths, it probably adds noise. Is it worth the extra test?

(2) The second problem is how to organize this from competing against a PVS research. A depth reduction research and a PVS research demand could occur independently or at the same time. Which one should be done first? Could they be combined into a single test?

(3) Should the research be when score > alpha rather than score > beta?

(4) The discovery of the need for a full depth search is not on the fail-high return but on the fail-low return. Consider the position:

[d]rnb2rk1/pp1nppbp/2p3p1/P2pP3/1q1P4/2N1BN1P/1PP1BPP1/R2QK2R w KQ - 1 2

In this position of the classic poisoned pawn, Bd2 will eventually win the Queen but the move Bd2 happens to pop up as move #33 in the move list. By move #33, the algorithm is already suggesting a reduction of two-ply and the correct answer is pushed over the horizon. A four-ply search would return a fail-low and cannot see that a search is necessary to at least a depth of six.

1. Bd2 e6 2. Nxd5 Qxb2 ... then stand pat @ Quiescence

One obvious answer is to improve the move ordering for e3d2, but how? Search Bishop x-ray attacks on the Queen first?

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

Re: Reduction Research Question

Post by hgm » Fri Sep 25, 2015 3:34 pm

You should never accept a score between alpha and beta from a reduced search, as this would now be the new PV. If you would even start reducing the PV, you would be really lying about the depth.

As to how to handle the interaction between PVS and LMR: this depends a bit on how stable your search is. Verifying if a score is above beta through a research is normally not needed for PVS. Especially if you need to do an unreduced source when the fail high holds, and it would almost always hold, you might as well go directly to the unreduced open-window search. There are engines that do all 4 combinations of open/closed window and reduced/unreduced search. Of course opening the window can only happen in PV nodes, which is about 0% of all nodes.

One supposes that the move ordering is based on some quality measure, e.g. history. Otherwise increasing reduction with move number would not be justified at all. And yest, the disadvantage of reduction is that you might overlook things, when moves are unpredictably good.

D Sceviour
Posts: 442
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: Reduction Research Question

Post by D Sceviour » Fri Sep 25, 2015 4:02 pm

hgm wrote:You should never accept a score between alpha and beta from a reduced search, as this would now be the new PV. If you would even start reducing the PV, you would be really lying about the depth.
So the answer to question #3 is yes?
hgm wrote:As to how to handle the interaction between PVS and LMR: this depends a bit on how stable your search is. Verifying if a score is above beta through a research is normally not needed for PVS. Especially if you need to do an unreduced source when the fail high holds, and it would almost always hold, you might as well go directly to the unreduced open-window search. There are engines that do all 4 combinations of open/closed window and reduced/unreduced search. Of course opening the window can only happen in PV nodes, which is about 0% of all nodes.
I currently research PVS if score > alpha and score < beta, with no serious problems. This would be expected to conflict very quickly if the reduction research condition were changed from score >=beta to score > alpha.

D Sceviour
Posts: 442
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: Reduction Research Question

Post by D Sceviour » Sat Sep 26, 2015 1:23 pm

I am disappointed in the response to the posted questions. I can only imagine the technical discussion was posted unclearly or incompletely. The relationship between PVS, reduction search windows and move ordering is very important. There has to be more than black magic guesses, or mega game testing to find the best results. The principles should be laid out in an orderly fashion, and with definite numbers.

Henk
Posts: 5718
Joined: Mon May 27, 2013 8:31 am

Re: Reduction Research Question

Post by Henk » Sat Sep 26, 2015 1:44 pm

Each search "can introduce errors as well as solve them". So try minimize errors as much as possible but there is lack of time and memory. Perhaps search horizon is cause of biggest errors. Otherwise errors are caused by skipping relatively important nodes (moves).

Volker Annuss
Posts: 173
Joined: Mon Sep 03, 2007 7:15 am

Re: Reduction Research Question

Post by Volker Annuss » Sat Sep 26, 2015 2:31 pm

So the answer to question #3 is yes?
The answer to question #3 is neither yes nor no. You should research when score >= beta.

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

Re: Reduction Research Question

Post by hgm » Sat Sep 26, 2015 2:40 pm

D Sceviour wrote:So the answer to question #3 is yes?
Indeed.

But the current paradigm for engine development is indeed close to black magic. You just try the various options, and test what works best. The 'official' meaning of LMR is that you research unreduced when the move beats alpha, i.e. only moves that fail low should be reduced. PVS is just a technique to increase alpha-beta efficiency through 'internal aspiration', i.e. narrowing the window compared to what it should logically be as a gamble, which pays off when the score is not in the range that you artifically excluded, and requires a re-serarch otherwise. It is not supposed to cause any cutoffs or reductions that could not have been made by normal alpha-beta and favorable move ordering.

D Sceviour
Posts: 442
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: Reduction Research Question

Post by D Sceviour » Sat Sep 26, 2015 2:43 pm

Henk wrote:Each search "can introduce errors as well as solve them". So try minimize errors as much as possible but there is lack of time and memory. Perhaps search horizon is cause of biggest errors. Otherwise errors are caused by skipping relatively important nodes (moves).
Thank you Henk. This is a good start. I agree a search can produce errors, but it is possible a reduction research is more likely to produce an error. That is, a search returns a tentative score. If a reduction research returns a different score then it is just as likely the research has produced an error as not (on average). The point is a reduction research may be a waste of time. My own results indicate reduction research is a waste of time, but then again perhaps I am missing something.

On the other hand, a PVS research (without consideration of reduction) is very important.

What do you mean by “search horizon is cause of biggest errors"?

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

Re: Reduction Research Question

Post by hgm » Sat Sep 26, 2015 2:51 pm

Volker Annuss wrote:
So the answer to question #3 is yes?
The answer to question #3 is neither yes nor no. You should research when score >= beta.
I don't think that is correct. If you don't research when alpha < score < beta the you would accept reduction of the PV. You would not want the moves you are actually going to play to have been investigated with a shallow search only.

For PVS null-window fail highs you only need to research if alpha < score < beta. When score >= beta you can accept the fail high, unless you have a very much expectancy-dependent search, which would make a fail-high result of a score that was expected to fail low very unreliable. But is seems to me that in that case there is something fundamentally wrong with your search; normally the situation would correct itself, because to get an oppositie fail the daughters should have had one too, and should already have taken action.

D Sceviour
Posts: 442
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: Reduction Research Question

Post by D Sceviour » Sat Sep 26, 2015 3:05 pm

Volker Annuss wrote: The answer to question #3 is neither yes nor no. You should research when score >= beta.
Hello Volker. If a reduction research should be done when score >= beta, then the answer to question #3 would be no. At least, that seems to be the best reasoning at the moment. A reduction is being performed under the assumption the move list will fail low, and not under the assumption that a research will produce a new PV.

However, here lies another question. What we are trying to find is a better move, not just spin through the move list as fast as possible. What should be done if a reduction research returns a score > alpha and score < beta? What I assume you are saying is to ignore it.

Post Reply