LMP in PV nodes

[bob]

First, LMP does not apply to "expected cut nodes". You only search one move at such nodes any.

No, LMP applies to expected CUT-nodes. With perfect move ordering, you expect to search only 1 move to get the expected fail-high. So if by the last moves, you haven't failed high yet, you simply prune them, faill low here, and fail high one ply upwards. If that fail high is at an expected PV-node, you research with a full window and without LMP (and at an ALL-node, the fail-high will eventually bubble up towards a PV-node, causing a research higher-up in the tree)

If your move ordering at CUT nodes is any good, you should save effort and find a better move over your current PV quicker than without LMP. On occasion, the research might discover a very late move that would have produced the initial fail-high you were looking for, hadn't you done the LMP on the previous null-window search. That's the tradeoff.

"expected" is meaningless. A node is simply PV, CUT or ALL, based on the result of the search. If you search every move, it is an ALL node, regardless of what it was expected to be. Therefore introducing the "expected" modifier to CUT/ALL doesn't really help at all.

Take a traditional search. From measurements, Crafty fails high on the first move searched at any ply about 92% of the time. Talking about any sort of pruning or reduction on a CUT node means you are only talking about 8% of the CUT nodes. And pruning/reducing there is quite dangerous. Why do we reduce later moves more than earlier moves? Because we begin to give up any hope that any of those later moves will fail high because this is likely an ALL node and everything has to be searched without a cutoff happening, so we reduce the effort to finish quicker. But at a CUT node where the best move is not searched first (or a "good enough" move is not searched first) any pruning or reducing might well cause the actual best move to either be reduced to the point the goodness can not be seen, or the move might actually be pruned and we don't get the fail high we want here.

Which takes us full-circle back to my ORIGINAL question. Why treat PV and non-PV nodes differently regarding pruning and reducing decisions? Particularly when you can't say whether a particular root move will become the new best move (and hence the successor node from that move will be a PV node) until after the move has been searched. So you make pruning/reduction decisions based on nothing more than a guess.

I became convinced a long time back that not doing null-move on PV nodes was reasonable. And there is a rational explanation why, since the null-move is not a legal move and can never be best at any node. On a PV node you must identify a best move, which means a null-move can not be backed up. If the null-search fails low, you learn nothing. If it fails high or returns a true score you still learn nothing because it is an illegal move. It only makes sense at CUT nodes where you get the fail-high at a reduced cost. And to be theoretically correct, you should not do a null-search at ALL nodes because everything is expected to fail low anyway. But in the absence of any viable way to identify an ALL node, other than by searching it and noticing that the alpha bound was not improved on (the search was actually completed with no best move) there is no way to implement this and most end up doing null-searches everywhere but at PV nodes. And some do them on PV nodes as well. The difference between doing null-searchst at PV vs not doing them is NOT very large, because there are not very many PV nodes in the tree anyway.

[bob]

The only viable exception to the PV vs non-PV node treatment is with null-move search, since doing a null-move at a PV node doesn't help, as a null-move is not legal and can not be propagated back to the root.

That was my initial thinking as well, but I'm not convinced anymore that it makes sense: suppose you do include a null-move search in the PV. If the null-move fails high, then you take the cut-off, which (eventually) triggers a re-search with a larger window to keep the null-move in window. If it doesn't fail high, you just search the remaining moves as normal. At no point do you get a null-move in the PV at the end of an iteration (you might get it for an intermediate result, but that's not necessarily a problem although it might look a bit odd if you display that to the user). Am I missing something?

What would not surprise me is if a null move is simply a waste of time in a PV node, but I haven't tested this in any way. Of course, one could do something with the information from the null-move search (change move-ordering, or threat extensions) and those may help. Again, not something I've tried at (expected) PV nodes.

You would have to special-case it. But I ran millions of test positions and in general, null-move everywhere increased the overall tree-size measurably. These were fixed-depth searches so that nodes could be compared. This is not a significant issue in terms of Elo, but it has a measurable effect.

Ok, so if I understand you correctly, then allowing a NULL move in an (expected) PV node is not so much incorrect (because a NULL move should never be part of the PV) but is rather a waste of time?

Yes, with one exception. If you reach a zugzwang position, you have a problem because then the null-move will actually be the best move, and it can't be played. If you explicitly disallow this, then all you have done is added the overhead for searching that null-move tree which is often pretty minimal thanks to hashing and an adaptive R value.

[Henk]

If there are not many PV nodes then there may also not be much profit when you apply LMR/LMP at PV nodes. Or am I wrong. And if that is the case the question is not interesting for the safest way is not to apply LMR/LMP in PV nodes.

[Rein Halbersma]

"expected" is meaningless. A node is simply PV, CUT or ALL, based on the result of the search. If you search every move, it is an ALL node, regardless of what it was expected to be. Therefore introducing the "expected" modifier to CUT/ALL doesn't really help at all.

"expected" means precisely what you expect (pun intended): it means that given the search so far, the "expected" node type is precisely the parity of the distance to the lowest "provisional" PV node so far. It can and on occasion will change during the search, in the same way that the PV presumptive gets updated during the search as well. It only is crowned KV when the search is completed.

Which takes us full-circle back to my ORIGINAL question. Why treat PV and non-PV nodes differently regarding pruning and reducing decisions? Particularly when you can't say whether a particular root move will become the new best move (and hence the successor node from that move will be a PV node) until after the move has been searched. So you make pruning/reduction decisions based on nothing more than a guess.

In PVS, the non-PV (well you don't know for sure, but say you expect them to be non-PV) are different because you can research after a fail-high. This makes doing speculative stuff at expected fail-high nodes possible.

[bob]

If there are not many PV nodes then there may also not be much profit when you apply LMR/LMP at PV nodes. Or am I wrong. And if that is the case the question is not interesting for the safest way is not to apply LMR/LMP in PV nodes.

The question is not about the potential benefit, but about the potential consistency. The current approach of treating them differently introduces some interesting hashing inconsistencies. In hashing, all we use to identify a position is the Zobrist signature and then the depth to see if the results are usable at the current node. If you take position P and search it in a non-PV context and reduce it more aggressively, how do you stop from using that hash hit in the PV where you will reduce less aggressively. The hash entry is wrong in that context. The same happens in the other direction as well. One "could" address this by storing the node type for the current node, but that doesn't fix the problem since there are nodes BELOW this node in the tree that would/could be searched differently as well. Searches are already pretty unstable, this would seen to exacerbate the issue.

[bob]

"expected" is meaningless. A node is simply PV, CUT or ALL, based on the result of the search. If you search every move, it is an ALL node, regardless of what it was expected to be. Therefore introducing the "expected" modifier to CUT/ALL doesn't really help at all.

"expected" means precisely what you expect (pun intended): it means that given the search so far, the "expected" node type is precisely the parity of the distance to the lowest "provisional" PV node so far. It can and on occasion will change during the search, in the same way that the PV presumptive gets updated during the search as well. It only is crowned KV when the search is completed.

Which takes us full-circle back to my ORIGINAL question. Why treat PV and non-PV nodes differently regarding pruning and reducing decisions? Particularly when you can't say whether a particular root move will become the new best move (and hence the successor node from that move will be a PV node) until after the move has been searched. So you make pruning/reduction decisions based on nothing more than a guess.

In PVS, the non-PV (well you don't know for sure, but say you expect them to be non-PV) are different because you can research after a fail-high. This makes doing speculative stuff at expected fail-high nodes possible.

You only address 1/2 of the problem. What about that node where you SHOULD fail high, but you don't because you reduced or pruned too aggressively? In one place you see the true result, in the other you don't. Yet the two positions are IDENTICAL in every way except that one was a PV node and one was not, something that is not recorded in a hash entry for obvious reasons...

[kinderchocolate]

Bob, what about the possibility that a non-PV node would be promoted to a PV node is relatively small and therefore can be reduced to some certain threshold while improving the engine performance? This is an engineering decision but it might work as long as the threshold is not absolutely crazy. How do you explain this?

[kinderchocolate]

Bob, another question. If you tried to distinguish between a PV and non-PV node in Crafty and your new algorithm gives you a sound +50 Elo. What would you do? Would you dismiss it because it sounds not theoretical to you? Would you try to analyze the reasons and apply the understanding to your old approach? What would you do?

[bob]

Bob, what about the possibility that a non-PV node would be promoted to a PV node is relatively small and therefore can be reduced to some certain threshold while improving the engine performance? This is an engineering decision but it might work as long as the threshold is not absolutely crazy. How do you explain this?

I haven't tried to explain anything, I have simply asked the question "why treat PV and non-PV nodes differently?".

Yes, there are very few PV nodes. But they are critical nodes because the optimal pathway goes through them. If someone had responded "OK, I have tested this and I agree that for each new iteration we do, about one of every five times we do one, we change our mind. Which means that 80% of the time we do not. The gain by reducing the effort for that 80% of the positions offsets the loss where we miss a new best move because we reduce/prune it too aggressively and it never fails high at all."

And then there is the hash table inconsistency issue which is a further complication of this approach. I've not said it is bad or good or even break-even. I've simply asked "why" in light of some obvious issues it introduces.

[bob]

Bob, another question. If you tried to distinguish between a PV and non-PV node in Crafty and your new algorithm gives you a sound +50 Elo. What would you do? Would you dismiss it because it sounds not theoretical to you? Would you try to analyze the reasons and apply the understanding to your old approach? What would you do?

My take here has always been "if something works, where common sense says it should not, then figure out why it works." So far, I have not found a case where that could not be done. Occasionally an actual bug will improve results in either a test position, a class of test positions, etc... But you KNOW that a subscript violation can't be a good thing. You investigate and discover that index+1 just happens to return a value that is good in this kind of position. You fix the array, and the indexing error is gone, you know why the indexing error helped, and all is well.

I developed the approach at least 10-15 years ago that NOTHING gets overlooked. If I make a speed change and the node count changes by just one node, I dig until I explain this. Chances are it is not something that is significant, but it is something that should not happen. I have spent days tracking that single node down in the past.

I seem to fall into that last category you gave, based on the above.