variable reductions

[bob]

I have been playing with variable reductions for several months (reducing more on higher depth remaining and as more moves are searched.) However, several times it has been mentioned that some like to reduce more in non-PV nodes than in PV nodes (nodes where alpha != beta - 1).

I've been testing this and it has consistently been a -10 Elo change. And here is what I have seen, repeatedly.

Search first most (best from last iteration) and get a score of N. Then get down into the move list where reductions are a bit higher and a new move fails high. But on the re-search it produces a significantly lower score.

I looked at the tree and finally caught it where the extra reductions hid a significant tactic and let the move fail high, but now this is a PV node and the reductions are ramped down a bit and I get a score that is worse when searched to an equivalent depth as the original best move.

Anyone else noticed such? I've always been anti-treat-em-differently (pv vs non-pv) but thought I would give it a whirl. Yet it exhibits exactly the behavior I would expect. I played several games with this last night and when I went through the log files, I saw multiple examples in every game. Not every move, but not just one time, either.

I suppose I could modify the search so that if the new move produces a lower score on the re-search, throw it away, but there are some timing conditions here. For example, failing high but not having time to resolve the real score, leading to making what could be a blunder.

Anyone else actually use different reductions for PV and non-PV? And if so, have you seen this (or have you actually looked for it vs not paying attention?)

I've tossed this for the moment, but it is easy enough to add back.

[jdart]

I do still have different reductions for PV and non-PV moves. They get the same base reduction (1 ply) but then the non-PV nodes get 50% more of any extra reduction that is applied at the PV nodes.

I have not re-visited this recently but the LMR part of the code is one area where last time I was tinkering any change made things worse. On the other hand my reduction formulas are rather different from what most others use (see https://github.com/jdart1/arasan-chess/ ... search.cpp around line 140 for details). Maybe they are still not optimal and maybe some other thing is making it behave the way it does.

--Jon

[bob]

I do still have different reductions for PV and non-PV moves. They get the same base reduction (1 ply) but then the non-PV nodes get 50% more of any extra reduction that is applied at the PV nodes.

I have not re-visited this recently but the LMR part of the code is one area where last time I was tinkering any change made things worse. On the other hand my reduction formulas are rather different from what most others use (see https://github.com/jdart1/arasan-chess/ ... search.cpp around line 140 for details). Maybe they are still not optimal and maybe some other thing is making it behave the way it does.

--Jon

Have you noticed the peculiar behavior I mentioned? IE fail high on new move at ply=N, but then score comes back worse on the re-search. Sometimes significantly worse. The one that caught my eye last night was where Crafty was at +.40 or so, failed high, and score came back as -2.7... Fortunately it had enough time to find something better, but the original choice was really the best move and it did not play that (would have needed another iteration.)

[jdart]

Are you seeing this at the root or deeper in the tree?

I do see search instability of various kinds but haven't observed this particular behavior often (doesn't mean it doesn't happen though).

--Jon

[tpetzke]

I think this behavior is expected. This is the reason you do a research of the move with original depth and don't trust the fail high with a lower depth.

The original move is considered best until the research with full depth has verified that the new move is really better. Do you already accept the new move as better before it is researched ?

The bigger problem is a move that would fail high at full depth but does not fail high with reductions. You don't spot that case. So you might miss some good moves until a few more iterations are done.

[lucasart]

Anyone else actually use different reductions for PV and non-PV? And if so, have you seen this (or have you actually looked for it vs not paying attention?)

In DiscoCheck, I've tried to reduce PV, non PV nodes differently, and it never worked. I also tried reducing Cut nodes differently, and that did not work either. Besides, there is something fundamentally wrong in doing it, so I would only commit such a patch if the gain was clear and it was proven to com from the PVness distinction indeed, not just biais correction:

To compare apples to apples you need to optimally tune the reduction formula. Suppose you don't reduce enough, and you introduce some extra reduction for non PV nodes only. It works and you conclude that treating non PV nodes differently is a good idea. This is what happens in Stockfish all the time (for everything not just PV vs non PV). I bet many engine authors make that mistake too. Yes, we look at results, but we tend to see what we want to see...

Only PV distinction I do in DiscoCheck is that null move, razoring and futility pruning are not done at PV nodes. Also I don't do TT pruning at PV nodes (only use for move ordering). The elo difference is barely measurable but it's also a stability feature: print untruncated PVs, ensure you never prune all moves at the root and return an illegal move etc.

[bob]

Are you seeing this at the root or deeper in the tree?

I do see search instability of various kinds but haven't observed this particular behavior often (doesn't mean it doesn't happen though).

--Jon

I'm talking about at the root. IE you get a score/pv with 0.40, then a fail high at the root, then a score/PV that is lower. Usually just a small bit lower but I saw that -2.4 lower in one game...

I'm becoming more and more convinced that treating PV/non-PV nodes differently regarding search heuristics is simply wrong...

[bob]

I think this behavior is expected. This is the reason you do a research of the move with original depth and don't trust the fail high with a lower depth.

The original move is considered best until the research with full depth has verified that the new move is really better. Do you already accept the new move as better before it is researched ?

The bigger problem is a move that would fail high at full depth but does not fail high with reductions. You don't spot that case. So you might miss some good moves until a few more iterations are done.

No, you are misunderstanding.

I am talking about at the root. I search move number one and get a score of +.40. I search a later move to depth-N, and it fails high. I re-search with depth=n (but still null-window search) and it fails high again. I now relax beta and search to get the score, but now this is a PV move, it gets reduced less, it sees something bad and produces a score worse than that +.40...

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...

[bob]

Anyone else actually use different reductions for PV and non-PV? And if so, have you seen this (or have you actually looked for it vs not paying attention?)

In DiscoCheck, I've tried to reduce PV, non PV nodes differently, and it never worked. I also tried reducing Cut nodes differently, and that did not work either. Besides, there is something fundamentally wrong in doing it, so I would only commit such a patch if the gain was clear and it was proven to com from the PVness distinction indeed, not just biais correction:

To compare apples to apples you need to optimally tune the reduction formula. Suppose you don't reduce enough, and you introduce some extra reduction for non PV nodes only. It works and you conclude that treating non PV nodes differently is a good idea. This is what happens in Stockfish all the time (for everything not just PV vs non PV). I bet many engine authors make that mistake too. Yes, we look at results, but we tend to see what we want to see...

Only PV distinction I do in DiscoCheck is that null move, razoring and futility pruning are not done at PV nodes. Also I don't do TT pruning at PV nodes (only use for move ordering). The elo difference is barely measurable but it's also a stability feature: print untruncated PVs, ensure you never prune all moves at the root and return an illegal move etc.

I don't do a null-move search on PV nodes because it really should not fail high. But this is purely an efficiency thing, as doing the null move search won't produce bad values, just extra work since it is destined to fail low.

I don't like the tt approach you use however. I allow everything and still don't get short PVs because of the PV hash I keep. I also prune the same at all positions, just as I reduce the same, for the same reason. Treating non-PV moves more aggressively introduces instabilities I don't like...

[mvk]

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.