The strengths and weaknesses of PVS

[Edmund]

Yesterday I stumbled upon a post by hgm in the thread from 2008: fail soft vs fail hard

yes, but PVS is a significant win, compared to fail-soft, which is essentially no change once you use PVS.

Well, PVS only starts to become a win when your move ordering is good enough (but not too good). For micro-Max it was a loss.

At first thought I doubted the assertion "but not too good" as I imagined that the better the move ordering the more effective the PVS-search. Anyway I then tried to assess the advantages and disadvantages of PVS.

First of all, in a perfectly ordered tree, there is no difference between PVS and normal alpha beta in its natural tree size.

Now an imperfect tree; there one has to distinguish between the depth at which the move-ordering mistake occurred. Ie. was it at the PV node or closer to the Leaves:

If a move-ordering mistake happened at the PV node, in PVS the whole tree has to be researched resulting in extra work. No extra work is needed in a normal Alpha Beta search.

A mistake happening on a CUT node will be quicker resolved in PVS than in Alpha Beta. However in Alpha Beta the further right the CUT node was in the tree the faster will the mistake be resolved.

These were the differences regarding the number of cut-offs based on wrong move ordering decisions. Next there is the issue that Zero width nodes (as the majority of nodes in the PVS framework) have far less information about their location in the tree and the characteristics of the position than they would in the alpha beta framework. The size of the window of a node in the alpha beta framework has a very large impact on the relevance of the node.


Having mentioned all the major differences I could think of, I now want to add some additional thoughts:

First of all, some of the disadvantage of alpha beta over PVS regarding the wider windows could be solved by explicitly ordering moves in ALL nodes not from best to worst, but from least aggressive to most aggressive. This way less traps are set for the succeeding CUT nodes, in the process creating some more tight bounds, so that the most potential moves are then quicker dealt with. So rather try a solid but quiet move than a move attacking an unprotected opponents piece or similar.

Next, PVS is only strong when the PV-node at which it is applied features a singular move. It might be well worth disabling PVS on moves which have proven to have potential. This holds especially true if the principal move fails low and we know that the second move in the list was able to produce cut-offs in the past (as far as I know some programs already only start PVS if at least one move has scored > alpha).

Applying the above point results in having open window CUT and ALL nodes. It might now be considered adding a PVS search on ALL nodes if the at the PV assumed potential for the line doesn't hold (e.g. the TT move fails low).

Finally, PVS is most effective if the actual score is lower than the current alpha, but still very close. In other words assuming good move ordering in PV nodes (or any nodes where PVS is applied) the late moves which have an expected score way lower than alpha don't gain much and are easily refuted even without the artificially lowered beta bound. For those it might be well worth doing a full window search and take advantage of the additional information the score bounds bring. Those might then be used for example to back up some advanced pruning decisions.

[hgm]

Note that the 'text-book' pseudo-code for PVS (and the very similar LMR) is actually quite stupid, as you immediately re-enter a node that you just returned from, in case of a re-search. As a consequence, you have to redo all the things that had already been done, and were abandoned when you returned from the node. Such as generating moves, scoring them, sorting them. A valid hash move for the node might have been erased in the process.

My recent engines do use PVS, and implement it through self-deepening. I pass a flag to Search() to indicade if the move is a PV move (to be searched with open window), an early move, or a late move. For non-PV moves alpha is upped to beta-1 before the search starts. If the search fails low compared to beta-1 with an upper bound above the original alpha, the search is redone with the original alpha, using the already existing move list.

And for the reply to a late move, initially the search depth is reduced, and a low-failing search is then followed by a search at the full depth, just like it is an other iteration of IID.

I have not measured if this gives much of a speedup. (This would obviously depend on how often you do a re-search.) But apart from a speed advantage (that must obviously exist, even if it can be negligibly small), I like this method because it allows you more flexibility in combining re-searches with IID: you can decide for each IID iteration separately to first re-search with open window before starting the next iteration.

[Edmund]

My recent engines do use PVS, and implement it through self-deepening. ...

This indeed sounds like a nice structural refinement. But I would rather do it for the increased flexibility and nicer code structure than for the speedup. I don't know about your recent engines, but in Glass researches are only done on nodes with a certain minimum depth or PV nodes, so I don't see much speed to be gained here from saved move generations. However the additional informations available can very well be used for reduction/pruning decisions. (eg. knowing that a certain move failed low in the previous iteration of IID and it is late/non tactical could be a pruning/reduction criterion).

I would also be interested on some comments regarding your statement from 2 years ago. In what way can good move ordering make PVS worse than plain Alpha Beta? Were you thinking in similar lines as my initial post or are there additional aspects I missed?

[bob]

My recent engines do use PVS, and implement it through self-deepening. ...

This indeed sounds like a nice structural refinement. But I would rather do it for the increased flexibility and nicer code structure than for the speedup. I don't know about your recent engines, but in Glass researches are only done on nodes with a certain minimum depth or PV nodes, so I don't see much speed to be gained here from saved move generations. However the additional informations available can very well be used for reduction/pruning decisions. (eg. knowing that a certain move failed low in the previous iteration of IID and it is late/non tactical could be a pruning/reduction criterion).

I would also be interested on some comments regarding your statement from 2 years ago. In what way can good move ordering make PVS worse than plain Alpha Beta? Were you thinking in similar lines as my initial post or are there additional aspects I missed?

I personally believe, from lots of testing and changes over the past 30 years (PVS was originally defined in 1978) is that if you have decent move ordering (trees where the best move is ordered first 90% of the time or better are called "strongly ordered game trees"), use the normal PVS which comes from Knuth/Moore's ALL, CUT and PV node definitions, and use an aspiration window at the root, then it is going to be _very_ difficult to find something that works better. I have tried most every idea that has been proposed, all the way through mtd(f) and simply have never found something that is an improvement over PVS, over a wide variety of tests. Yes, there are things that look better in tactical positions, things that look better in non-tactical positions, but overall, PVS appears to be as good as one can do. Note that PVS has zero to do with null-move, LMR, extensions, reductions, forward pruning, and such. It is, quite simply, an algorithm that evaluates the first move and tries to prove all the rest are worse, by searching a really optimal tree (zero-width has to fail high or low).

Everything else goes in on top of PVS, but those ideas also would go in on top of non-aspiration-window PVS, or on top of mtd(f), etc so they are independent issues.

IID is simply _another_ move ordering strategy that helps in certain cases, hurts in others, whether it is good overall or not is hard to say. I removed it from Crafty and saw a very slight Elo improvement as a result. It is really easy to choose positions where IID is a big win. For example, one of those ugly cases where you search and get a fail high, but then can't resolve a true score because of the hash table. So you start iteration N+1 with no idea about how to order the tree, and IID will shine there. But in other positions it wastes time when a good capture will cause a cutoff and the IID search expends way too much effort to find a capture that your move generator spits out cheaply. Overall there is a small cost when you test in games.

[hgm]

I would also be interested on some comments regarding your statement from 2 years ago. In what way can good move ordering make PVS worse than plain Alpha Beta? Were you thinking in similar lines as my initial post or are there additional aspects I missed?

I just meant that for perfect move ordering there would be no advantage. I don't expect PVS can actually get worse than alpha-beta, for near-perfect ordering.

The main effect of PVS is that it re-orders the hunt for alternative moves to refute a certain line after the original refutation (from the previous iteration) failed so that deviations closer to the root are tried earlier. In alpha beta you would walk the tree strictly depth first. So if the original high-failing line runs into resistance at the tip, alpha-beta spends a lot of nodes very close to the leaves, to figure out exactly how much the score will drop for them. In PVS you only establish that the moves did not meet the original target, and you will try to look first if this is because a fatal mistake was already made closer to the root, by first looking if there are alternatives there that can still meet the original target. If you can, no time was wasted on finding out how poor the final moves in the now discarded branch are.; you leave that for the re-search.

[micron]

Note that the 'text-book' pseudo-code for PVS (and the very similar LMR) is actually quite stupid, as you immediately re-enter a node that you just returned from, in case of a re-search. As a consequence, you have to redo all the things that had already been done, and were abandoned when you returned from the node. Such as generating moves, scoring them, sorting them. A valid hash move for the node might have been erased in the process.

How would you improve this textbook pseudocode?

Code: Select all

thisScore = -Search( depth - 1, -b, -alpha, ply + 1 ); 
if ( thisScore > alpha && thisScore < beta ) 
	thisScore = -Search&#40; depth - 1, -beta, -alpha, ply + 1 );

Robert P.

[hgm]

Code: Select all

 
thisScore = -Search( depth - 1, -beta, -alpha, ply + 1, pvMove );
pvMove = FALSE;

[bob]

Code: Select all

 
thisScore = -Search( depth - 1, -beta, -alpha, ply + 1, pvMove );
pvMove = FALSE;

Not sure what you are replying to.

But my point was, that in real game testing, when you don't have a hash move along the PV (which is not very common) it seems that most of the time a non-losing capture or a killer move is good enough, and those come with less effort than an IID search. In single positions, IID usually wins when it is used and doesn't hurt when it is not.

[hgm]

Code: Select all

 
thisScore = -Search( depth - 1, -beta, -alpha, ply + 1, pvMove );
pvMove = FALSE;

Not sure what you are replying to.

How would you improve this textbook pseudocode?

Code: Select all

thisScore = -Search( depth - 1, -b, -alpha, ply + 1 ); 
if ( thisScore > alpha && thisScore < beta ) 
	thisScore = -Search&#40; depth - 1, -beta, -alpha, ply + 1 );

[Edmund]

Code: Select all

 
thisScore = -Search( depth - 1, -beta, -alpha, ply + 1, pvMove );
pvMove = FALSE;

Not sure what you are replying to.

But my point was, that in real game testing, when you don't have a hash move along the PV (which is not very common) it seems that most of the time a non-losing capture or a killer move is good enough, and those come with less effort than an IID search. In single positions, IID usually wins when it is used and doesn't hurt when it is not.

At a PV node you are not interested in a move that is "good enough" as searching the best move first will improve the bounds and make all the following searches more efficient.