LMP in PV nodes

[petero2]

In texel I have been doing LMP (late move pruning, also called move count based pruning) in both PV and non-PV nodes for a long time. Recently I was working on special endgame knowledge for KQKRP endgames, and analysis of search trees showed that sometimes the defending side could not maintain the fortress because LMP caused all moves that preserved the fortress to be pruned. Even though I only use LMP for depth <= 4, the problem spreads through the hash table to much deeper searches too.

To work around this problem I decided to test if disabling LMP in PV nodes would help. While it did help somewhat for the KQKRP endgame, the big surprise was that I measured a +12 elo increase from the combination of KQKRP evaluation and disabling of LMP in PV nodes. I don't think the KQKRP knowledge is worth much because the endgame is pretty unusual, so it seems to me that disabling LMP in PV nodes is a big win for texel.

On the other hand, disabling LMP entirely caused a 24 elo regression compared to the original version.

In summary:

Code: Select all

LMP except in PV : +12 elo
LMP everywhere   :   0 elo
No LMP           : -24 elo

What is your experience with LMP? Is it common knowledge that LMP in PV nodes is a bad idea?

[gladius]

SF disables all pruning except LMR in PV nodes. I'm not sure how recently these restrictions have been tested though.

[cdani]

In Andscacs I do two types of LMP, one for non pv only for the last level before quiescence, and one (depending on depth) regardless of the type of node (a lot more restrictive, of course).
The eval pruning I do also for pv nodes. Disabling it in pv also was a regression.

[lucasart]

What is your experience with LMP? Is it common knowledge that LMP in PV nodes is a bad idea?

I'm not sure LMP in PV nodes is a 12 elo regression by itself. Theoretically, when you don't do something at PV nodes, it should make zero elo difference, especially at high depth when PV nodes are fewer.

But it causes technical problems (eg. truncated PVs, fixed depth search can prune all moves and not return a best move etc.). That's why I would disable it. Perhaps LMP at PV nodes was causing some problem, like the best move not being updated in some cases, because you prune at Root.

Why don't you try to disable at Root only, and leave it at PV nodes, just to see if your 12 elo regression isn't just there?

[Ferdy]

In texel I have been doing LMP (late move pruning, also called move count based pruning) in both PV and non-PV nodes for a long time. Recently I was working on special endgame knowledge for KQKRP endgames, and analysis of search trees showed that sometimes the defending side could not maintain the fortress because LMP caused all moves that preserved the fortress to be pruned. Even though I only use LMP for depth <= 4, the problem spreads through the hash table to much deeper searches too.

To work around this problem I decided to test if disabling LMP in PV nodes would help. While it did help somewhat for the KQKRP endgame, the big surprise was that I measured a +12 elo increase from the combination of KQKRP evaluation and disabling of LMP in PV nodes. I don't think the KQKRP knowledge is worth much because the endgame is pretty unusual, so it seems to me that disabling LMP in PV nodes is a big win for texel.

On the other hand, disabling LMP entirely caused a 24 elo regression compared to the original version.

In summary:

Code: Select all

LMP except in PV : +12 elo
LMP everywhere   :   0 elo
No LMP           : -24 elo

What is your experience with LMP? Is it common knowledge that LMP in PV nodes is a bad idea?

In my current development version adding LMP in pv nodes showed a +10 rating points (TC 15s + 200ms inc, self test). Doing only at depth 2 or less and the side that prunes still has enough material to win (at least a rook or a minor and a pawn).

[petero2]

What is your experience with LMP? Is it common knowledge that LMP in PV nodes is a bad idea?

I'm not sure LMP in PV nodes is a 12 elo regression by itself. Theoretically, when you don't do something at PV nodes, it should make zero elo difference, especially at high depth when PV nodes are fewer.

But it causes technical problems (eg. truncated PVs, fixed depth search can prune all moves and not return a best move etc.). That's why I would disable it. Perhaps LMP at PV nodes was causing some problem, like the best move not being updated in some cases, because you prune at Root.

Why don't you try to disable at Root only, and leave it at PV nodes, just to see if your 12 elo regression isn't just there?

I should have mentioned that in texel I have a separate root search function that handles iterative deepening, aspiration windows, time management, multi pv, and other things that are only relevant in the root node. This root search function does not have any reductions/extensions except LMR, so LMP is already disabled at the root.

I don't do LMP at a node unless at least one legal move has already been searched at that node, and the returned score was not a negative mate score. Also, I don't do LMP for the hash move, killers, SEE>=0 captures, promotions, passed pawn pushes and moves that give check. Additionally, if alpha or beta is a positive or negative mate score, I don't do LMP.

It is possible that there is some unknown problem in my LMP implementation and that skipping LMP in PV nodes somehow hides the problem. I don't know what that problem would be though.

It is also worth noting that in an attempt to get the most elo improvement per invested CPU cycle, I run almost all my tests at very short time control (80ms/move) and against the previous development version of texel. While this has worked well on average for texel so far, it is of course possible that for some changes it gives wrong results, so maybe this change would be far from +12 elo if measured at longer time control against different opponents.

[Ferdy]

What is your experience with LMP? Is it common knowledge that LMP in PV nodes is a bad idea?

I'm not sure LMP in PV nodes is a 12 elo regression by itself. Theoretically, when you don't do something at PV nodes, it should make zero elo difference, especially at high depth when PV nodes are fewer.

But it causes technical problems (eg. truncated PVs, fixed depth search can prune all moves and not return a best move etc.). That's why I would disable it. Perhaps LMP at PV nodes was causing some problem, like the best move not being updated in some cases, because you prune at Root.

Why don't you try to disable at Root only, and leave it at PV nodes, just to see if your 12 elo regression isn't just there?

I should have mentioned that in texel I have a separate root search function that handles iterative deepening, aspiration windows, time management, multi pv, and other things that are only relevant in the root node. This root search function does not have any reductions/extensions except LMR, so LMP is already disabled at the root.

I don't do LMP at a node unless at least one legal move has already been searched at that node, and the returned score was not a negative mate score. Also, I don't do LMP for the hash move, killers, SEE>=0 captures, promotions, passed pawn pushes and moves that give check. Additionally, if alpha or beta is a positive or negative mate score, I don't do LMP.

This "at least one legal move" seemed to be dangerous? Especially when material is low. But of course you will get more depth. I am using at least 8 legals at pv and 3 in non-pv, other conditions almost similar, I don't prune if side is in check.
Test results so far at TC 60s + 200ms inc seemed promising. D1443523 has LMP.

Code: Select all

   # PLAYER      : RATING  ERROR   POINTS  PLAYED    (%)
   1 D1443523    :    9.1    9.0    344.5     655   52.6%
   2 D1443522    :   -9.1    9.0    310.5     655   47.4%

It is possible that there is some unknown problem in my LMP implementation and that skipping LMP in PV nodes somehow hides the problem. I don't know what that problem would be though.

It is also worth noting that in an attempt to get the most elo improvement per invested CPU cycle, I run almost all my tests at very short time control (80ms/move) and against the previous development version of texel. While this has worked well on average for texel so far, it is of course possible that for some changes it gives wrong results, so maybe this change would be far from +12 elo if measured at longer time control against different opponents.

[petero2]

I don't do LMP at a node unless at least one legal move has already been searched at that node, and the returned score was not a negative mate score. Also, I don't do LMP for the hash move, killers, SEE>=0 captures, promotions, passed pawn pushes and moves that give check. Additionally, if alpha or beta is a positive or negative mate score, I don't do LMP.

This "at least one legal move" seemed to be dangerous? Especially when material is low. But of course you will get more depth. I am using at least 8 legals at pv and 3 in non-pv, other conditions almost similar, I don't prune if side is in check.

The conditions I listed are necessary but not sufficient to cause LMP to kick in. The main LMP condition is that the loop index in the move loop (which corresponds to the number of pseudo-legal moves examined) must be large enough. Large enough depends on the remaining depth, like this:

Code: Select all

Depth   lmpLimit
1       3
2       6
3       12
4       24
>4      inf

So at depth 1, LMP can only happen after at least 3 pseudo-legal moves have been examined.

I also have a condition that disables LMP if the side to move has no pawns or no pieces.

[mar]

The way I do LMP is simply an extension to futility pruning, i.e. I simply shift the marging down by n*movecount.
So naturally I don't do that in PV nodes.
It's nothing sophisticated but IIRC it gave me over 20 elo in self-play.

[Bloodbane]

This might be a stupid question, but how could LMP even be theoretically correct at PV-nodes? The point of LMP is to reduce the time spent at ALL-nodes, and PV-nodes are not ALL-nodes so I do not see how there would be any sense in applying it there. Or is it the fact that a PV-node can turn into an ALL-node in some cases?