Extreme late move reductions?

[gladius]

I'm sure other people have tried something like this out, but I'm curious what results others have seen. The "standard" LMR seems to something like "if (ply >= 3 && !isCapture && !isPV && movesMade > 4) remainingDepth--;", then the full depth research if it doesn't fail low.

I tried a few variations on this concept, with one of the more effective being, if all LMR conditions are met, and movesMade > 10, reduce remainingDepth by two, instead of just one. Clearly, move ordering is even more important here than with normal LMR, so I'm thinking of investing more effort there in higher ply nodes.

This seemed to be beneficial in a 300 game test, worth about 35 ELO, but that's pretty close to the error margins.

[Michael Sherwin]

In RomiChess the LMR reduction = 2. But, I am not sure that it is better than the previous formula, reduction = (1 + ((depth - 2) / 4)). I do know that both are better than reduction = 1 and by way more than +35 elo. RomiChess has very good move ordering in the LMR section as all remaining moves are ordered by a shallow search with an open window:

While((node = AnotherMove())) {
MakeMove(node);
node->score = -Search(-beta - 100, -alpha + 100, depth - (iDepth / 4 + 3));
TakeBack();}

[Harald Johnsen]

...
I tried a few variations on this concept, with one of the more effective being, if all LMR conditions are met, and movesMade > 10, reduce remainingDepth by two, instead of just one. Clearly, move ordering is even more important here than with normal LMR, so I'm thinking of investing more effort there in higher ply nodes.

The problem is that it's not possible to have the perfect move ordering (or else there would be no need to do any search).
So the real question is what is the rate of error on node prediction : are you reducing a cut or an all node ? If you are looking at the 10th move then there is allready a high probability that the node is an all node and you can reduce or prune it, it does not matter.
But the move ordering is not correct so the probability that a node is an all node is not proportional to the move rank. The reason we have a high cut rate on the first few moves is because of good captures that refute stupid moves of the opponent (killers are helping too). We have (for example) a 90% probability to have a cut off on the first move and a 98% probability to have a cut off in the moves 2 to 5. Once the good captures are examined there is no way to tell if the node will be a cut node or an all node.
At the end, if you reduce/prune all nodes it's a win, if you reduce/prune cut nodes you'll have random results.

HJ.

[gladius]

In RomiChess the LMR reduction = 2. But, I am not sure that it is better than the previous formula, reduction = (1 + ((depth - 2) / 4)). I do know that both are better than reduction = 1 and by way more than +35 elo. RomiChess has very good move ordering in the LMR section as all remaining moves are ordered by a shallow search with an open window:

While((node = AnotherMove())) {
MakeMove(node);
node->score = -Search(-beta - 100, -alpha + 100, depth - (iDepth / 4 + 3));
TakeBack();}

Very interesting. I found that if I started moving the depth 2 reductions earlier on, my program started playing quite a bit weaker. I just tried something similar to the open window searches, but with a constant depth - 7 on the ordering search, and it seemed to help a little bit, but I haven't finished running the tests on that yet.

I wonder if there are some other search interactions that are giving you more than 35 ELO combined with the LMR. Ah, the magic of tweaking an alpha beta search .

[gladius]

The problem is that it's not possible to have the perfect move ordering (or else there would be no need to do any search).
So the real question is what is the rate of error on node prediction : are you reducing a cut or an all node ? If you are looking at the 10th move then there is allready a high probability that the node is an all node and you can reduce or prune it, it does not matter.
But the move ordering is not correct so the probability that a node is an all node is not proportional to the move rank. The reason we have a high cut rate on the first few moves is because of good captures that refute stupid moves of the opponent (killers are helping too). We have (for example) a 90% probability to have a cut off on the first move and a 98% probability to have a cut off in the moves 2 to 5. Once the good captures are examined there is no way to tell if the node will be a cut node or an all node.
At the end, if you reduce/prune all nodes it's a win, if you reduce/prune cut nodes you'll have random results.

HJ.

Thanks Harald. I realize that perfect move ordering is not attainable, but it does seem beneficial to not aggressively prune moves which are "better", even if the better/worse is determined from a much shallower search.

It's interesting that you note that reducing in a CUT node will cause random results. Standard LMR will fall into this trap as well (given we do not have perfect move ordering), but if we are past 10 moves, it's relatively more certain that we are in an ALL node, and the node will fail low. Of course this assumes our shallower searches are a good predictor for move ordering (and the move ordering doesn't make the search more expensive), but given this, I think the idea behind more aggressively pruning the remaining moves is (sort of) sound .

[hgm]

What I would like to try is to start with LMR of 2 ply on every move, but with the window opened to about 1 pawn below the current evaluation. Moves that fail low w.r.t. this threshold then stay at this depth, moves that get above it are re-searched with an LMR of one against the original alpha.

[bob]

I'm sure other people have tried something like this out, but I'm curious what results others have seen. The "standard" LMR seems to something like "if (ply >= 3 && !isCapture && !isPV && movesMade > 4) remainingDepth--;", then the full depth research if it doesn't fail low.

I tried a few variations on this concept, with one of the more effective being, if all LMR conditions are met, and movesMade > 10, reduce remainingDepth by two, instead of just one. Clearly, move ordering is even more important here than with normal LMR, so I'm thinking of investing more effort there in higher ply nodes.

This seemed to be beneficial in a 300 game test, worth about 35 ELO, but that's pretty close to the error margins.

I personally tried R=2 a while back, but it was worse over a large number of games against a gauntlet of different opponents. I have plans on trying several variations of the idea, including something like the adaptive null move pruning I have used for years, where I vary the R value depending on how close to the frontier nodes I am... I also plan on trying different (dynamic) reduction values depending on the "quality" of the move being reduced. For example we don't reduce checks, So why not reduce truly ugly moves even more than a ply?

[jdart]

Last I checked Scorpio (open source) had variable depth LMR but not quite as you describe - there are a number of conditions on it: it is based on both eval and "lateness" (number in the move order). Personally I haven't found this a useful idea yet but it seems to be effective in this program (Scorpio is quite strong).

--Jon

[Tony]

What I would like to try is to start with LMR of 2 ply on every move, but with the window opened to about 1 pawn below the current evaluation. Moves that fail low w.r.t. this threshold then stay at this depth, moves that get above it are re-searched with an LMR of one against the original alpha.

You might want to have a look at the (multi)probCut algoritm, wich takes this even a step further.

The basic idea is that (fe) you first try to prove that the score<currentScore-4 pawns with a reduction of 6 ply.

If this fails, try to prove score<currentScore-2 pawns with a reduction of 3 ply.

The trick is to get the margins and the reductions right. Multibound hashtables are also usefull.

Tony