Recognizing PV nodes

[fierz]

Dear all,

looking at some posts, and looking at some source code, it seems that doing or not doing stuff in "PV nodes" is more common than it used to be. I used to mark my PV based on the hashtable, i.e. I created a PV from the hashtable, and set an "ispv" flag on the way in the hashtable. So my search would find "ispv" only along the real pv. However, it seems that people generally use a condition like "alpha + 1 == beta". Is either way (real PV only, or alpha + 1 == beta) demonstrably more correct than the other?

cheers
Martin

[kbhearn]

alpha+1 = beta is a property of PV nodes in PVS search (a modification of alpha beta all the top engines use these days).

In essence, after finding a first candidate pv at a node, all other moves are searched with window (alpha,alpha+1) and only if these scout searches fail high is it researched with the full (alpha,beta) window. Hence 'pv nodes' in this sense are just 'not scout' nodes that may become part of the pv.

[hgm]

Correction: beta == alpha+1 is a property of non-PV nodes. And this is true only in the context of PVS; in plain alpha-beta most nodes have a non-null window, and such nodes always have the potential of becoming a PV node. But you would only know that after the fact, when the score settles between alpha and beta.

The EXACT flag of he bound type already indicates a hashed node was PV. There doesn't seem to be any need for an independent flag.

I think it is poor design anyway to have separate variables for indicating which sub-set of moves was searched / extended / reduced. This information should be implied by the depth parameter. If a 5-ply search of a PV node seaches better than a 5-ply search on a non-PV node, but worse than a 6-ply search on a non-PV node, it should be assigned depth 5.5.

[Evert]

During the search you don't actually know whether a node is a PV node or not (with the exception of the root node). However, you can know whether a node is a candidate PV node. In a PVS framework this is easy: the expected best move (which leads to a candidate PV node) is searched with an "open" (alpha, beta) window, other moves are searched with a minimal (alpha, alpha+1) window to verify that they are not better than the first move. Thus, "beta>alpha+1" is true if the current node is a PV candidate (conversely, beta==alpha+1 means the current node is not a PV candidate).

[fierz]

Dear all,

looking at some posts, and looking at some source code, it seems that doing or not doing stuff in "PV nodes" is more common than it used to be. I used to mark my PV based on the hashtable, i.e. I created a PV from the hashtable, and set an "ispv" flag on the way in the hashtable. So my search would find "ispv" only along the real pv. However, it seems that people generally use a condition like "alpha + 1 == beta". Is either way (real PV only, or alpha + 1 == beta) demonstrably more correct than the other?

cheers
Martin

I'll try to rephrase my question a bit: I realize that alpha+1==beta is the mark of a scout search in PVS - that's not what I'm interested in. The question is:
People seem to use the information that a node is in the scout search phase for doing larger reductions than other nodes. As a chessplayer, I don't understand what that means for the search. What I do understand is that I as a human chessplayer also generate a PV, and then I don't want to reduce search depth in my PV. => I am wondering whether this "ispv" condition is important for playing strength of modern engines, and I also wonder if one shouldnt look at real PV nodes only for this decision.

[Evert]

I'll try to rephrase my question a bit: I realize that alpha+1==beta is the mark of a scout search in PVS - that's not what I'm interested in. The question is:
People seem to use the information that a node is in the scout search phase for doing larger reductions than other nodes. As a chessplayer, I don't understand what that means for the search. What I do understand is that I as a human chessplayer also generate a PV, and then I don't want to reduce search depth in my PV. => I am wondering whether this "ispv" condition is important for playing strength of modern engines, and I also wonder if one shouldnt look at real PV nodes only for this decision.

I suspect it's a matter of statistics. You try to spend as little time as possible on nodes that do not affect the move selection at the root.

First, imagine that you have perfect move ordering. This means that at each candidate PV node, the best move is the first move, so you can prune all others. In fact, in this case all PV candidate moves turn out to be PV nodes. Obviously, pruning PV candidate nodes is detrimental.

If move ordering is not perfect, it is first of all safer to reduce than to prune outright. Since the number of scout nodes outnumbers the number of PV candidate nodes significantly, any random node is likely to be a a scout node. Moreover, it is probably unlikely to affect the score at the root. The closer a node is to a PV node, the more (statistically) likely it is that the node will be able to affect the PV.

Other than this statistical effect, I don't think there is an obvious reason why treating PV and scout nodes differently would be good (and several reasons for why it might be bad). There is a trade-off: you can safe a lot of time by reducing (or pruning) nodes that are unimportant, but reducing (or pruning) nodes that are important degrades the search.

How important this is in terms of Elo is, as far as I know, unknown. Perhaps Bob or someone from the Stockfish team knows this.

[mvk]

conversely, beta==alpha+1 means the current node is not a PV candidate

What to do when a PV re-search happens to return, after negation, beta-1? How to distinguish between PV and non-PV with the new alpha after?

[Evert]

conversely, beta==alpha+1 means the current node is not a PV candidate

What to do when a PV re-search happens to return, after negation, beta-1? How to distinguish between PV and non-PV with the new alpha after?

I'm not sure I understand the question.
In a PVS framework a node is a PV-candidate iff on entry beta > alpha+1. I suppose that if you use aspiration at the root, it can happen that the window bounds collapse until beta==alpha+1, in which case you should trigger a re-search with a larger window at the root.
Is there something I misunderstood here?

[mvk]

I responded to the quoted statement with a counter example.