Evert wrote:Correct me if I'm wrong, but I didn't see any claim that LMR/LMP is a large win in expected CUT nodes or whether it is more appropriate there than in ALL nodes, just that it is theoretically safe to do it there in that particular circumstance.
Exactly, whether it helps is an entirely different issue.
Since it is theoretically safe, it can't make the tree smaller than the minimal tree. However, we're not working with perfectly ordered trees (or PVS would not be needed) and I can see how LMP in cut nodes may be of benefit if the "best move" is almost always within the first couple of moves searched.
syzygy wrote:No, I am talking about PVS. An expected cut node is a node at an odd number of ply from the last PV node visited. Applying LMP to such a node means skipping the last few moves if the earlier moves do not cut.
Theoretically sound. Has been explained too many times already. The re-search fixes things.
Just a side question: what do you do with your node classification? Do you have PV/CUT/ALL and do different things at those 3 node types, or do you do PV/NonPV? In particular, do you treat CUT/ALL nodes differently wrt LMR? If so, how?
At the moment I only do PV/NonPV. But I think it makes sense to treat CUT and ALL nodes differently. Doing LMP in CUT nodes versus doing LMP in ALL nodes illustrates very nicely that such nodes are completely different things.
It also shows that distance to the PV node is the only thing that is relevant regarding node classification. An ALL node that cuts remains an ALL node for the purpose of the null-window verification search. If the verification search fails, the ALL node does not by definition turn into a CUT node but typically disappears from the search tree (and might possibly reappear later, again as an ALL node).
The hash table should probably distinguish between PV/CUT/ALL nodes as well when deciding on taking a hash cut. This should not be a serious limitation, as I don't think many nodes switch node type during a search.
syzygy wrote:No, I am talking about PVS. An expected cut node is a node at an odd number of ply from the last PV node visited. Applying LMP to such a node means skipping the last few moves if the earlier moves do not cut.
Theoretically sound. Has been explained too many times already. The re-search fixes things.
Just a side question: what do you do with your node classification? Do you have PV/CUT/ALL and do different things at those 3 node types, or do you do PV/NonPV? In particular, do you treat CUT/ALL nodes differently wrt LMR? If so, how?
At the moment I only do PV/NonPV. But I think it makes sense to treat CUT and ALL nodes differently. Doing LMP in CUT nodes versus doing LMP in ALL nodes illustrates very nicely that such nodes are completely different things.
They are also completely different in their correctness: LMP is correct for any given level of iterative deepening, but LMR is only "dynamically correct" in the sense that every move will eventually be searched (as long as the reductions grow sublinear in depth and move number).
syzygy wrote:No, I am talking about PVS. An expected cut node is a node at an odd number of ply from the last PV node visited. Applying LMP to such a node means skipping the last few moves if the earlier moves do not cut.
Theoretically sound. Has been explained too many times already. The re-search fixes things.
Just a side question: what do you do with your node classification? Do you have PV/CUT/ALL and do different things at those 3 node types, or do you do PV/NonPV? In particular, do you treat CUT/ALL nodes differently wrt LMR? If so, how?
At the moment I only do PV/NonPV. But I think it makes sense to treat CUT and ALL nodes differently. Doing LMP in CUT nodes versus doing LMP in ALL nodes illustrates very nicely that such nodes are completely different things.
They are also completely different in their correctness: LMP is correct for any given level of iterative deepening, but LMR is only "dynamically correct" in the sense that every move will eventually be searched (as long as the reductions grow sublinear in depth and move number).
I don't understand what you mean. I also don't understand what you mean with grow sublinear in depth. You mean reduce more and more if near the root.
I think LMP is the bad friend of LMR. LMR may have a bad first move and with LMP that first move may even be worse because of bad pruning.
Henk wrote:
I don't understand what you mean. I also don't understand what you mean with grow sublinear in depth. You mean reduce more and more if near the root.
I think LMP is the bad friend of LMR. LMR may have a bad first move and with LMP that first move may even be worse because of bad pruning.
With depth, I mean "remaining depth". Suppose you reduce with log(depth) * log(move #). Then the actual remaining search depth will still be increasing in the parameter "depth". This means that all moves will get a chance to be searched eventually.
syzygy wrote:No, I am talking about PVS. An expected cut node is a node at an odd number of ply from the last PV node visited. Applying LMP to such a node means skipping the last few moves if the earlier moves do not cut.
Theoretically sound. Has been explained too many times already. The re-search fixes things.
Just a side question: what do you do with your node classification? Do you have PV/CUT/ALL and do different things at those 3 node types, or do you do PV/NonPV? In particular, do you treat CUT/ALL nodes differently wrt LMR? If so, how?
At the moment I only do PV/NonPV. But I think it makes sense to treat CUT and ALL nodes differently. Doing LMP in CUT nodes versus doing LMP in ALL nodes illustrates very nicely that such nodes are completely different things.
They are also completely different in their correctness: LMP is correct for any given level of iterative deepening, but LMR is only "dynamically correct" in the sense that every move will eventually be searched (as long as the reductions grow sublinear in depth and move number).
LMR in cut nodes is theoretically correct as well.
If the PV node has white to move, then performing either LMR or LMP in a cut node of a verification tree, i.e. a node with black to move, essentially errs in favour of white. LMR applied to a move by black searches the move to a reduced depth, unless the move looks good for black. If it does look good for black, it is searched at full depth. So the result for black is never better than when not applying LMR. This also holds true for LMP as discussed earlier in this thread.
If the PV node has white to move, then erring in favour of white in a null-window verification search is theoretically safe since at worst it triggers a re-search which would not have been necessary otherwise.
syzygy wrote:No, I am talking about PVS. An expected cut node is a node at an odd number of ply from the last PV node visited. Applying LMP to such a node means skipping the last few moves if the earlier moves do not cut.
Theoretically sound. Has been explained too many times already. The re-search fixes things.
Just a side question: what do you do with your node classification? Do you have PV/CUT/ALL and do different things at those 3 node types, or do you do PV/NonPV? In particular, do you treat CUT/ALL nodes differently wrt LMR? If so, how?
At the moment I only do PV/NonPV. But I think it makes sense to treat CUT and ALL nodes differently. Doing LMP in CUT nodes versus doing LMP in ALL nodes illustrates very nicely that such nodes are completely different things.
They are also completely different in their correctness: LMP is correct for any given level of iterative deepening, but LMR is only "dynamically correct" in the sense that every move will eventually be searched (as long as the reductions grow sublinear in depth and move number).
LMR in cut nodes is theoretically correct as well.
In CUT-nodes, I agree. But LMR at ALL-nodes is not safe for a single level in iterative deepening. It might miss resources that are searched too shallow.
Rein Halbersma wrote:In CUT-nodes, I agree. But LMR at ALL-nodes is not safe for a single level in iterative deepening. It might miss resources that are searched too shallow.
Of course, but the same applies to LMP in ALL-nodes.
bob wrote:Sorry, but this is not "theoretically correct".
Yes it is.
LMP in "expected cut nodes" is theoretically safe. It will give the same score at the same iteration. The explanation has already been given.
(I am ignoring hashing effects.)
First, LMP does not apply to "expected cut nodes". You only search one move at such nodes any. It is something that applies at ALL nodes, hence the "late" in LMP. It sounds like you are talking about pure alpha/beta pruning, which is theoretically sound, and which is also NOT related to a move's order in which it is searched. It is based only on proving that the previous move leads to a score that is worse than an earlier move.
No, I am talking about PVS. An expected cut node is a node at an odd number of ply from the last PV node visited. Applying LMP to such a node means skipping the last few moves if the earlier moves do not cut.
Theoretically sound. Has been explained too many times already. The re-search fixes things.
1. At a cut node there is no pruning, because alpha/beta terminates the search there by refuting the move at the previous ply. I have no idea what you are talking about when you mention "LMP" when there are NO "late moves" to deal with. Over 90% of the time a CUT node searches exactly one move.
2. The re-search does NOT "fix things" because the original search might not even fail high due to the extra pruning and reducing that is done on non-PV nodes. If you don't fail high, you don't get a chance to "correct" anything, you just overlook the move and blindly stick to the previous best move.
Evert wrote:Correct me if I'm wrong, but I didn't see any claim that LMR/LMP is a large win in expected CUT nodes or whether it is more appropriate there than in ALL nodes, just that it is theoretically safe to do it there in that particular circumstance.
Exactly, whether it helps is an entirely different issue.
Since it is theoretically safe, it can't make the tree smaller than the minimal tree. However, we're not working with perfectly ordered trees (or PVS would not be needed) and I can see how LMP in cut nodes may be of benefit if the "best move" is almost always within the first couple of moves searched.
Why has this been hijacked? The original question was dealing with PV vs ALL nodes. Absolutely nothing to do with CUT nodes. Talking about LMP or LMR in a CUT node makes zero sense, since most of the time only one move is searched in a CUT node anyway.