principle variation search

[nak3c]

Hi all, I am starting teach myself chess programming and had a beginner question. I fully understand alphabeta but am having difficulty seeing how principle variation search produces more cutoff's so that with good move ordering it is more efficient. in alphabeta each node essentially gets a number (alpha) that it maximizes as long as alpha does not exceed another number (beta). Most tutorials on PVS say something like "if we narrow the window get more cutoffs". I dont understand this reference to a window. branches only get cut if they are above beta, this is a threshold, not a window? most tutorials also say " if evaluation is between alpha and beta have to research with full alpha beta. " Well if the evaluation for a particular position is less than alpha then alpha simply does not change. nothing gets cut off, the PVS algorithms ive read still only cutoff if alpha is above beta, so where are these extra cutoffs?

[User923005]

Assuming you have excellent move ordering, your pv node will be right almost all the time.
You search the pv node with a normal window.
You search all other nodes with a zero width window.
That is where the time savings comes in.
As long as the pv node guess was correct, the zero window searches (for all the non-pv nodes) will complete in a blink and you will have excellent time savings.
Of course, if you have bad move ordering, then you will get fail high nodes in your non-pv nodes and you will have to expand the window and research these new pv candidates. As long as this is a rare occurrence, your search will be better. If it happens a lot, then you will have to improve your move ordering in order for pvs search to be a big win.

[nak3c]

thank you for the quick reply. Im still unclear about the "window". in normal alpha beta parent nodes pass beta values to their children and those child nodes stop searching if they get a value higher than beta (in which case the parent node will simply avoid that childs variation). Where is there a window? what does it matter what alpha is its just a number nodes try to maximize so long as they stay below beta, but if cant produce cut off's.

[lucasart]

thank you for the quick reply. Im still unclear about the "window". in normal alpha beta parent nodes pass beta values to their children and those child nodes stop searching if they get a value higher than beta (in which case the parent node will simply avoid that childs variation). Where is there a window? what does it matter what alpha is its just a number nodes try to maximize so long as they stay below beta, but if cant produce cut off's.

When we say window, we are talking about the (alpha,beta) interval. At PV nodes alpha < beta can be a relatively large window, but at non PV nodes, beta = alpha+1 is a so called null window. PVS works as follows:

1/ at PV nodes
- search the first move with full window (child node type is PV)
- try all other moves with zero window (child node type is non-PV). of course this gets aborted early if we fail high (beta cutoff).
- when you are searching the second move for example (or any move that isn't the first), you search like this

Code: Select all

play(move)
score = -search(depth-1, -(alpha+1), -alpha, nonPV)
undo(move)

- if we fail low (ie. score <= alpha), then the move doesn't beat alpha. We did a depth-1 seqarch on a zero window, which is far less costly, obviously.
- if we don't fail low, we need to research the full window. Indeed we could have score = alpha, but doing a full window search would give the correct, untruncated value that is perhaps alpha+150. full window search, raise alpha, and check for beta cutoff etc.

2/ at non PV nodes
- beta = alpha +1
- you search any node the same way

Code: Select all

play(move)
score = -search(depth-1, -beta, -alpha, nonPV)
undo(move)

- when score >= beta, you have a beta cutoff and return score (fail soft) or beta (fail hard).

[hyatt]

As an added note...

generally you search the first move at any branch with the window (alpha, beta), but the remainder are searched with the window (alpha, alpha+1) where alpha is the best score so far. Narrower window == more cutoffs. UNLESS your move ordering is bad. Because if you get a fail high on (alpha, alpha+1) you have to re-search with (alpha, beta) to see if you get a cutoff there, or else to get an actual score since a score that says ">= beta" is not so meaningful when beta is just alpha+1.

Good move ordering and PVS reduces the size of the tree. I'd guess something in the 10% range, not 1000% or anything like that. Bad move ordering and PVS can increase the size of the tree since you continually have to do two searches each time, rather than just one.

[nak3c]

ok I think I am starting to wrap my head around this PVS after reading these responses and also rereading the Moreland page. like regular alphabeta with PVS you cut when evaluations are above beta, but now you also cut if evaluations are less than a certian value. Now that I think I understand it a little better it seems risky to place so much faith in youre move ordering and the evaluation of the first leaf nodes you search beacuse if a node fails low you run the risk of missing a leaf node that is inside the window. So I suppose PVS is only an improvement if you have robust and accurate move ordering, could you perhaps even see a preformance decrease with PVS if you had poor move ordering? thanks for assistance, hopefully I am starting to sound like I know what im talking about.

[User923005]

Principal variation search is not about getting more cutoffs. It is about speeding up the non-pv node searches by reducing the search space.

The idea is this:
With a program that has good move ordering, we usually guess the best choice of a move for the pv nodes.
So, for a pv node, we perform a nice fat window to search for the true value of the node. This search will be slow. {Consider the extreme case of searching between -infinity and +infinity to help clarify the idea}.
For all the non-pv nodes, we search a window that has a width of 0. This search will be really fast, if all goes as expected. However, if it turns out that this non-pv node is actually better than the pv node, our zero window search has failed to give a speed up. Now, we will have to make a big window for the possible new pv candidate move and search it again with the big, fat window.

The savings in pvs search comes from the narrow window searches. These searches are much faster than searches with a big window. Things go wrong if the zero window searches find new pv candidates. Hence good move ordering is required.

I imagine that there are tutorials on pvs search here and there on the net.

You can think of the zero window searches as this (for each non-pv node):
"I am just doing a quick verification of this non-pv node to prove to myself that this node is not as good as the node I have selected for my principle variation"
The more often that this guess is wrong, the worse pvs search will perform because you have to start over for every goof.

[nak3c]

ahh, so we save time and effort be not having to replace alpha hundreds of thousands of times. but you should search the same number of nodes as alphabeta, potentially more if you get fail lows. Im a bit suprised you can get up to 10% speedup with this detail but I dont have intuition about how compiled c code executes. Of course Ive lookes at tutorials on the web but the four or five that ive read dont say clearly enough that this is a preformance increase to save execution time not so much a direct improvement of the algorithm. I think I have it now.

[hyatt]

ok I think I am starting to wrap my head around this PVS after reading these responses and also rereading the Moreland page. like regular alphabeta with PVS you cut when evaluations are above beta, but now you also cut if evaluations are less than a certian value. Now that I think I understand it a little better it seems risky to place so much faith in youre move ordering and the evaluation of the first leaf nodes you search beacuse if a node fails low you run the risk of missing a leaf node that is inside the window. So I suppose PVS is only an improvement if you have robust and accurate move ordering, could you perhaps even see a preformance decrease with PVS if you had poor move ordering? thanks for assistance, hopefully I am starting to sound like I know what im talking about.

PVS has only one benefit, searching a smaller tree. It should produce EXACTLY the same result as a non-PVS search, just as alpha/beta should produce EXACTLY the same result as pure minimax. But alpha/beta reduces the minimax tree significantly. almost to the square_root(minimax) in fact. And PVS just tacks on a bit more efficiency by creating additional cutoffs by avoiding searching branches that are not going to affect the PV at all.

Think about this: Which tree will be larger, a tree searched with -inf,+inf, or a tree searched with -1.0, +1.0, assuming the actual eval ends up near zero? If you use +/- infinity, if you get into a sub-tree that leads to a long mate, you have to search it. With -1,+1, you can stop searching as soon as you get a mate score, it will be outside the window...

That's how PVS helps.

[nak3c]

So you do cut off branches that fail low. I am glad I asked this question because several responses that I have gotted (and am grateful for) do not agree. User923005 says that PVS is "not about getting more cutoffs". So which is it, both seem like sensible ways to get a preformancs increase.