bob wrote:The reason is that searching move N with bigger reductions hides something near the end and it fails high. But when the beta bound is relaxed, this move now becomes a PV move and it is searched deeper (reduced reductions) and it sees that "stinger" but we have already failed high and consider this move better...
That is not different from "symmetrical" LMR? For a move to enter the PV, it must also prove itself twice, at different depths, lowest first. So the search eventually focusses more on confirming the PV than on refuting it. Asymetrical reductions don't change the basics, but just shift a few nodes between scout and research.
So the question is really why you don't see that effect already.
That's not the "effect" I am concerned about. I am concerned with a later move failing high at the root (on the reduced search). Then failing high again on the non-reduced search. Then coming back with a LOWER score on the final re-search where beta has been relaxed.
I don't mind the move failing high on the reduced search then failing low on the non-reduced search where it is then simply ignored. I mind it failing high twice on the reduced and non-reduced (non-reduced at the root only, of course, and since this is STILL a non-PV move it gets reduced more down through the tree than after the second fail-high where beta is changed, turning this into a PV move that is reduced less than the just-completed re-search.
Seems like a broken concept. Apparently others have noticed this as well. I simply thought I would test while I was working on a more aggressive LMR approach, but it looks to be a dangerous idea to treat PV/non-PV nodes differently in how they are searched.
bob wrote:That's not the "effect" I am concerned about. I am concerned with a later move failing high at the root (on the reduced search). Then failing high again on the non-reduced search. Then coming back with a LOWER score on the final re-search where beta has been relaxed.
Ah, your scheme is different from mine. I don't have the middle search.
bob wrote:That's not the "effect" I am concerned about. I am concerned with a later move failing high at the root (on the reduced search). Then failing high again on the non-reduced search. Then coming back with a LOWER score on the final re-search where beta has been relaxed.
Ah, your scheme is different from mine. I don't have the middle search.
Not sure I follow. The basic premise behind LMR has always been
(1) search a move to reduced depth.
(2) if it fails high, re-search it to the normal depth.
Only then do you trust the fail-high. And since this was a real fail-high at the root, I need to re-search with a new beta bound to get the true score. Do you not do it like that??
I think he means the interaction between PVS and LMR:
(1) Search at reduced depth with null window
(2) If (1) fails high, re-search with open window at reduced depth
(3) If (2) fails high, re-search with null window at full depth
(4) if (3) fails high, re-search with open window at full depth
When PV prunes or reduces more, upgrading to PV (by opening the window) is not fundamentally different from cancelling any other reduction, in particular the reduction due to LMR. The only difference is that upgrading to PV more selectively undoes reductions in part of the tree, while LMR does it over the full width of the tree.
But both offer an opportunity for search instability.
From this it can also be seen that LMR and extra non-PV reductions do similar things, so that doing them both might overdo things. (In fact, reducing EVERY move in a non-PV node seems equivalent to doing LMR in the parent, where PVS would take care of the re-search. Except that it is more difficult to exempt captures and such.) The optimal LMR reduction might thus be lower when you also do extra non-PV reductions.
I don't do LMR at the root. I just do a scout search for the moves beyond the first. If it fails high, I research with an open window and only if it still increases alpha, it is a new best move.
hgm wrote:I think he means the interaction between PVS and LMR:
(1) Search at reduced depth with null window
(2) If (1) fails high, re-search with open window at reduced depth
(3) If (2) fails high, re-search with null window at full depth
(4) if (3) fails high, re-search with open window at full depth
In Myrddin I skip (3) above, and I couldn't begin to say if it's better or worse because honestly I never considered adding it. Am I missing something important leaving it out?
tpetzke wrote:I don't do LMR at the root. I just do a scout search for the moves beyond the first. If it fails high, I research with an open window and only if it still increases alpha, it is a new best move.
Thomas...
There's nothing wrong with it. Since you already do a scout search, making the scout search even faster can only ever be good.
bob wrote:
That's not the "effect" I am concerned about. I am concerned with a later move failing high at the root (on the reduced search). Then failing high again on the non-reduced search. Then coming back with a LOWER score on the final re-search where beta has been relaxed.
I don't do this. If the reduced search fails high, it is re-searched with both reduction removed and with an upper bound of beta.
Every time I have tested a two-stage re-search strategy it has scored worse, even though it seems like a plausible idea.
hgm wrote:I think he means the interaction between PVS and LMR:
(1) Search at reduced depth with null window
(2) If (1) fails high, re-search with open window at reduced depth
(3) If (2) fails high, re-search with null window at full depth
(4) if (3) fails high, re-search with open window at full depth
I don't do things in that order (in fact (2) seems wrong to me).
I search at reduced depth with null window; if that fails high
I search at normal depth with null-window to see if it will really fail high on the correct depth; if that fails high
I search at normal depth with an expanded window to get a real score at the root.
When PV prunes or reduces more, upgrading to PV (by opening the window) is not fundamentally different from cancelling any other reduction, in particular the reduction due to LMR. The only difference is that upgrading to PV more selectively undoes reductions in part of the tree, while LMR does it over the full width of the tree.
But both offer an opportunity for search instability.
From this it can also be seen that LMR and extra non-PV reductions do similar things, so that doing them both might overdo things. (In fact, reducing EVERY move in a non-PV node seems equivalent to doing LMR in the parent, where PVS would take care of the re-search. Except that it is more difficult to exempt captures and such.) The optimal LMR reduction might thus be lower when you also do extra non-PV reductions.
