For the alpha-beta pruning to be more effective, the interval (α, β) should be as small as possible. In aspiration search, we limit the interval artificially and are ready to handle cases in which the search fails and we have to revert to the original values. The search fails at internal node v if all of its subtrees have their minimax values outside the assumed range (α , β ) (i.e. every subtree value e /∈ (α , β )). Because minimax (and negamax) method with alpha-beta pruning always returns values within the search interval, the out-of-range value e can be used to recognize a failed search. As noted by Fishburn (1983), we can add a fail-soft enhancement to the search by returning a value e that gives the best possible estimate of the actual alpha-beta range (i.e. e is as close as possible to it with respect to the information gathered in the failed search). Principal variation search (PVS) – introduced by Finkel and Fishburn (1982) and renamed by Marsland and Campbell (1982) – does the search even more intelligently. A node in a game tree belongs to one of the following types: (i) α-node, where every move has e ≤ α and none of them gets selected; (ii) β-node, where every move has e ≥ β; (iii) principal variation node, where one or more moves has e>α but none of them has e ≥ β. PVS assumes that whenever we find a principal variation move when searching a node, we have a principal variation node. This assumption means that we will not find a better move for the node in the remaining children. Simply put, once we have
For the alpha-beta pruning to be more effective, the interval (α, β) should be as small as
possible. In aspiration search, we limit the interval artificially and are ready to handle cases
in which the search fails and we have to revert to the original values. The search fails at
internal node v if all of its subtrees have their minimax values outside the assumed range
(α
, β
) (i.e. every subtree value e /∈ (α
, β
)). Because minimax (and negamax) method
with alpha-beta pruning always returns values within the search interval, the out-of-range
value e can be used to recognize a failed search. As noted by Fishburn (1983), we can add
a fail-soft enhancement to the search by returning a value e that gives the best possible
estimate of the actual alpha-beta range (i.e. e is as close as possible to it with respect to
the information gathered in the failed search).
Principal variation search (PVS) – introduced by Finkel and Fishburn (1982) and renamed by Marsland and Campbell (1982) – does the search even more intelligently. A node
in a game tree belongs to one of the following types:
(i) α-node, where every move has e ≤ α and none of them gets selected;
(ii) β-node, where every move has e ≥ β;
(iii) principal variation node, where one or more moves has e>α but none of them has
e ≥ β.
PVS assumes that whenever we find a principal variation move when searching a node,
we have a principal variation node. This assumption means that we will not find a better
move for the node in the remaining children. Simply put, once we have
Step by step
Solved in 3 steps
