Recognizing 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
fierz
Posts: 62
Joined: Mon Mar 07, 2016 3:41 pm
Location: Zürich, Switzerland
Contact:

Recognizing PV nodes

Post by fierz » Tue Mar 29, 2016 8:02 pm

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
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: Recognizing PV nodes

Post by kbhearn » Tue Mar 29, 2016 8:13 pm

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.

User avatar
hgm
Posts: 23149
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Recognizing PV nodes

Post by hgm » Wed Mar 30, 2016 6:56 am

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.

User avatar
Evert
Posts: 2920
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Recognizing PV nodes

Post by Evert » Wed Mar 30, 2016 6:59 am

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
Posts: 62
Joined: Mon Mar 07, 2016 3:41 pm
Location: Zürich, Switzerland
Contact:

Re: Recognizing PV nodes

Post by fierz » Wed Mar 30, 2016 8:34 am

fierz wrote: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.

User avatar
Evert
Posts: 2920
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Recognizing PV nodes

Post by Evert » Wed Mar 30, 2016 2:49 pm

fierz wrote: 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
Posts: 589
Joined: Tue Jun 04, 2013 8:15 pm

Re: Recognizing PV nodes

Post by mvk » Sat Apr 02, 2016 7:28 am

Evert wrote: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?
[Account deleted]

User avatar
Evert
Posts: 2920
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Recognizing PV nodes

Post by Evert » Sat Apr 02, 2016 10:09 am

mvk wrote:
Evert wrote: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
Posts: 589
Joined: Tue Jun 04, 2013 8:15 pm

Re: Recognizing PV nodes

Post by mvk » Sat Apr 02, 2016 10:58 am

I responded to the quoted statement with a counter example.
[Account deleted]

Post Reply