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.hgm wrote: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.bob wrote:yes, but PVS is a significant win, compared to fail-soft, which is essentially no change once you use 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.