LMP in PV nodes

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.
Post Reply
petero2
Posts: 560
Joined: Mon Apr 19, 2010 5:07 pm
Location: Sweden
Contact:

LMP in PV nodes

Post by petero2 » Sat Dec 27, 2014 8:00 pm

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 &#58; +12 elo
LMP everywhere   &#58;   0 elo
No LMP           &#58; -24 elo
What is your experience with LMP? Is it common knowledge that LMP in PV nodes is a bad idea?

gladius
Posts: 535
Joined: Tue Dec 12, 2006 9:10 am

Re: LMP in PV nodes

Post by gladius » Sat Dec 27, 2014 9:55 pm

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

User avatar
cdani
Posts: 2054
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: LMP in PV nodes

Post by cdani » Sat Dec 27, 2014 10:53 pm

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.

User avatar
lucasart
Posts: 2958
Joined: Mon May 31, 2010 11:29 am
Contact:

Re: LMP in PV nodes

Post by lucasart » Sun Dec 28, 2014 8:09 am

petero2 wrote: 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?
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Ferdy
Posts: 3620
Joined: Sun Aug 10, 2008 1:15 pm
Location: Philippines

Re: LMP in PV nodes

Post by Ferdy » Sun Dec 28, 2014 8:16 am

petero2 wrote: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 &#58; +12 elo
LMP everywhere   &#58;   0 elo
No LMP           &#58; -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
Posts: 560
Joined: Mon Apr 19, 2010 5:07 pm
Location: Sweden
Contact:

Re: LMP in PV nodes

Post by petero2 » Sun Dec 28, 2014 10:02 am

lucasart wrote:
petero2 wrote: 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
Posts: 3620
Joined: Sun Aug 10, 2008 1:15 pm
Location: Philippines

Re: LMP in PV nodes

Post by Ferdy » Sun Dec 28, 2014 12:38 pm

petero2 wrote:
lucasart wrote:
petero2 wrote: 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      &#58; RATING  ERROR   POINTS  PLAYED    (%)
   1 D1443523    &#58;    9.1    9.0    344.5     655   52.6%
   2 D1443522    &#58;   -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
Posts: 560
Joined: Mon Apr 19, 2010 5:07 pm
Location: Sweden
Contact:

Re: LMP in PV nodes

Post by petero2 » Sun Dec 28, 2014 1:07 pm

Ferdy wrote:
petero2 wrote: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
Posts: 1848
Joined: Fri Nov 26, 2010 1:00 pm
Full name: Martin Sedlak

Re: LMP in PV nodes

Post by mar » Sun Dec 28, 2014 2:55 pm

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.

User avatar
Bloodbane
Posts: 154
Joined: Thu Oct 03, 2013 2:17 pm

Re: LMP in PV nodes

Post by Bloodbane » Sun Dec 28, 2014 3:00 pm

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?
Functional programming combines the flexibility and power of abstract mathematics with the intuitive clarity of abstract mathematics.
https://github.com/mAarnos

Post Reply