LMP in PV nodes

[mjlef]

Suppose the best move is a sacrifice, and you take the reasonable move ordering approach of trying losing captures last.

Then, with LMP in the root node (we are talking about pruning here, not reductions), you will never play the sacrifice, no matter what depth you achieve. It will keep getting pruned, every time.

--Jon

OK, suppose the 15th move in the root list is a capture that loses. Do you reduce it or not? What about the 15th move at ply=2 positions?

This STILL makes absolutely no sense to me. If it is OK to reduce moves that you HOPE will become a new best move, then it should be just as OK to reduce moves that are already part of a best move.

The discussion is about LMP (Late Move PruningO, not Reductions. Pruned moves are not searched, so pruning at the root would just never search those moves at all.

[xmas79]

Suppose the best move is a sacrifice, and you take the reasonable move ordering approach of trying losing captures last.

Then, with LMP in the root node (we are talking about pruning here, not reductions), you will never play the sacrifice, no matter what depth you achieve. It will keep getting pruned, every time.

--Jon

OK, suppose the 15th move in the root list is a capture that loses. Do you reduce it or not? What about the 15th move at ply=2 positions?

This STILL makes absolutely no sense to me. If it is OK to reduce moves that you HOPE will become a new best move, then it should be just as OK to reduce moves that are already part of a best move.

The discussion is about LMP (Late Move PruningO, not Reductions. Pruned moves are not searched, so pruning at the root would just never search those moves at all.

Of course they will not be searched, if and only if you prune blindly. Usually you have some conditions around, something like "remainingDepth < X", so at increasing depths pruning at root will not be done and the move will start to be searched. I also see "pruning" as a (much) more aggressive "reduction", so LMR and LMP seems to me the "same" thing...

[bob]

Suppose the best move is a sacrifice, and you take the reasonable move ordering approach of trying losing captures last.

Then, with LMP in the root node (we are talking about pruning here, not reductions), you will never play the sacrifice, no matter what depth you achieve. It will keep getting pruned, every time.

--Jon

OK, suppose the 15th move in the root list is a capture that loses. Do you reduce it or not? What about the 15th move at ply=2 positions?

This STILL makes absolutely no sense to me. If it is OK to reduce moves that you HOPE will become a new best move, then it should be just as OK to reduce moves that are already part of a best move.

The discussion is about LMP (Late Move PruningO, not Reductions. Pruned moves are not searched, so pruning at the root would just never search those moves at all.

LMP/LMR do exactly the same thing, they hide parts of the tree. They just do it in different ways. Back to the question, what theoretical basis is there for treating a PV node differently from a non-PV node, since the reason we are searching those non-PV nodes is to find a BETTER PV in the first place?

[Bloodbane]

since the reason we are searching those non-PV nodes is to find a BETTER PV in the first place?

This seems incorrect to me. Consider PVS: when we have a move which raised alpha in a PV-node we assume we are going to stick with this move, and so we search the rest of the moves with a null window. If we assume that there is a better move out there is a contradiction with the previous assumption, and that seems like a bit of a problem to me. I myself consider searching the non-PV nodes a case of "trust, but verify", not effort expended to find something which might not even be there.

[bob]

since the reason we are searching those non-PV nodes is to find a BETTER PV in the first place?

This seems incorrect to me. Consider PVS: when we have a move which raised alpha in a PV-node we assume we are going to stick with this move, and so we search the rest of the moves with a null window. If we assume that there is a better move out there is a contradiction with the previous assumption, and that seems like a bit of a problem to me. I myself consider searching the non-PV nodes a case of "trust, but verify", not effort expended to find something which might not even be there.

PVS doesn't assume there is no better move. It just searches more efficiently when there is no better move. If you don't change your mind, why do the search in the first place? The simple question is "why do you bother searching all of the moves at any ply if you assume the first one is best?" The answer is "because you are not CERTAIN that the first move is best." A program changes its mind on iteration N+1 about one of every 5 searches. If you treat PV moves differently, you make this harder to do, which means you will certainly overlook on the non-PV moves, and most likely search unnecessary stuff on the actual PV moves since they get treated less aggressively.

As I have repeatedly said, I simply see absolutely no theoretical justification for this "different treatment." And to date, no one has offered anything concrete at all.

BTW with your "trust but verify" how do you verify ANYTHING if you treat the rest of the moves more aggressively, which makes them more likely to have technical errors in their sub-trees.

[lucasart]

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?

LMP is theoretically incorrect, whether you do it at PV, Cut, All, or random nodes. It's not about theory, but about practice and elo trade-off. You're fooling yourself to think that not doing at PV nodes is safer, because it affects PV nodes by back propagation the same way.

[Michel]

Not pruning in PV nodes allows the PVS mechanism to correct certain mistakes in the search.

I once worked this out for LMR at CUT nodes. See here

http://www.talkchess.com/forum/viewtopic.php?t=48356

In general for PVS to yield the correct tree value a lower bound returned by a CUT node should be sane and similarly an upper bound returned by an ALL node should be sane.

Of course PVS researches take time so it is a tradeoff.

PS. CUT/ALL is defined by the parity of the distance to the lowest PV ancestor.

[Michel]

I guess what I wanted to say is this.

In PVS PV nodes really _are_ special for the following reason: if a scout search fails high then the child node is researched as a PV node. If the the fail high was erroneous the research may catch it.

However this "error correction" does not work if the same pruning is done in PV nodes as in non-PV nodes.

[jdart]

A lot of things in computer chess are heuristics that have problematic conceptual foundations but happen to work, most of the time. And methods that fail at some part of the tree can still produce good results overall.

Still, I think Mark has a point. Empirically, with current move ordering techniques, including especially the presence of hash moves that have succeeded before, the first move is often the best. So you do, in general, have a priori (although probabalistic) knowledge about that move. You can rely on that knowledge, or not - only experiment will really tell if it is desirable to do so.

--Jon

[bob]

A lot of things in computer chess are heuristics that have problematic conceptual foundations but happen to work, most of the time. And methods that fail at some part of the tree can still produce good results overall.

Still, I think Mark has a point. Empirically, with current move ordering techniques, including especially the presence of hash moves that have succeeded before, the first move is often the best. So you do, in general, have a priori (although probabalistic) knowledge about that move. You can rely on that knowledge, or not - only experiment will really tell if it is desirable to do so.

--Jon

Doesn't LMR/LMP do EXACTLY that? IE leave the first move alone, and get more aggressive in pruning/reductions as you advance through the move list? But if you agree that the first move is often best and the others inferior, why would you STILL search those "other moves" more carefully at a PV node than at an ALL node? That is the issue and it is not being touched on at all.