In this last post of this series of three I will discuss alpha beta pruning. The context will be evaluation functions on game trees that take values in a distributive lattice. Of course a prime example would be the linear lattice over the partially ordered set but this post does not depend on specific features of this linear lattice. The result is a description of alpha beta pruning for distributive lattices that is a slightly improved version of that given by Ginsberg et al in their paper “Alpha Beta pruning under partial orders” from 2001.
Alpha Beta pruning is a way to compute the value of an evaluation function on a game tree for the root node by visiting as little child nodes as necessary. See the previous post for a more extensive introduction to evaluation functions. Here I will only briefly recall the recursive definition of an evaluation function on a game tree that takes values in a lattice . I will assume that has a minimal and maximal element denoted by and . The normal forms and of the linear lattice are examples of this.
- The value of for a leaf node is given by some heuristic game evaluation function (e.g. chess piece values).
- At an inner min node (where the minimizing player is to make a move) the value of is defined recursively as the greatest lower bound in of all values of on direct child nodes.
- At an inner max node the value of is defined as the least upper bound of all values of on direct child nodes.
This definition leads to the following algorithm for the computation of . This algorithm is also the basis of further considerations on ways to prune parts of the game tree that are irrelevant for the computation of on the root node.
function f(node) local value if node is a leaf node then value = heuristic position value of node elseif node is a min node then value = 1 for child in all children of node do value = value ∧ f(child) end else value = 0 for child in all children of node do value = value ∨ f(child) end end return value end
The structure of this naive algorithm is simple. To compute the value at a min node start with the maximal value then iterate over all child nodes and adjust the node’s value by taking the greatest lower bound with the value of a child node. At a max node the procedure is similar but starts off with the minimal value and repeatedly takes the least upper bound. The computation recurses depth first left to right over all child nodes, where “left to right” is according to the enumeration order of child nodes. Move ordering does not play a role in this naive algorithm but it can play a big role in alpha beta pruning in terms of the number of pruned nodes. I will not address move ordering in this post. During execution of the algorithm the state of the computation is schematically depicted below. As in the example in the previous post I will assume that the top node is a min node.
Here and are the intermediate values that are computed for the inner min and max nodes respectively. The symbol indicates all subtrees located to the left of the current path of computation in the tree. These are the subtrees for which a value is already (recursively) computed. When the computation progresses each intermediate value descends from and each ascends from . When we would cut the computation short at the point depicted above then the algorithm would track back up and yield the final outcome
at the root node. The essential point of alpha beta pruning is that it identifies when this intermediate value remains constant even when gets larger in the remainder of the computation. Because in that case any further children of the node marked in the diagram will not contribute to the final result and can be pruned (skipped). In the picture above the search path ends with a max node but that is irrelevant for alpha beta pruning as we will see.
A lattice has a canonical partial order where is equivalent to (or alternatively ). The lattice operators and indeed result in the greatest lower bound and least upper bound with respect to this ordering. The following lattice property is the key point in alpha beta pruning.
Lemma: When and then and .
Since the greatest lower bound is also a lower bound for and and is therefore less than or equal to the greatest lower bound . The other inequality is derived similarly. For sequences and in define sequences and recursively by
- and is obtained from by the substitution .
- and is obtained from by the substitution .
So the sequence starts with
and the sequence with
The following inequalities are a direct consequence of our lemma above. The sequences and satisfy
for all indices . In particular is an ascending sequence, is a descending sequence, each is a lower bound for and each is an upper bound for . If or for some index then both sequences are constant from that point onwards. The values in the sequences and are precisely those obtained from aborting the computation of the evaluation function for the root node at min node (sequence ) or at max node (sequence ). Hence further nodes can be pruned from the computation as soon as both sequences yield equal values.
Alpha Beta pruning (strong version): At the first index where either or further subnodes of max node or min node can be pruned.
Note that this formulation of alpha beta pruning resembles “classical” alpha beta pruning for totally ordered sets in that we have an ascending sequences of high values and a descending sequence of low values and nodes can be pruned as soon as these values coincide. There is also an unfortunate difference between the two. In classical alpha beta pruning the high and low values are easy to compute progressively as a simple maximum or minimum value. In contrast high and low values in the pruning algorithm above are not so simple to compute. Since they are computed deepest node first it requires constant back tracking. Moreover, computation of and can be much more expensive than taking simply the maximum or minimum of two numbers.
Also note that the distributive property of the lattice is not used at all in this version of alpha beta pruning! This does not contradict the results of Ginsberg et al since they formulate alpha beta pruning (in particular “deep pruning”) differently. I will briefly come back to this point at the end of this post.
There is a weaker version of alpha beta pruning based on alternative sequences and that are easier to compute. The consequence is however that it may take longer before the ascending high values and descending low values allow cut off, resulting in less aggressive pruning. The weaker estimates for high and low values follow from the following identities (where the distributive property of is now essential). Let and define two new sequences and by
So is the least upper bound of the values of all max nodes above min node and is the greatest lower bound of the values of all min nodes above max node . If we take and then for all indices the following equalities hold:
These can be proved by induction and the distributive property of the lattice . Taking in the first equation and in the second results in
Comparing these equalities it follows that implies and implies . This leads to the following version of alpha beta pruning.
Alpha Beta pruning: If the value of min node gets less than or equal to or the value of max node gets greater than or equal to then further child nodes can be pruned.
This is a slightly different formulation of alpha beta pruning than Ginsberg et al use in their paper. What they call (shallow or deep) pruning comes down to either for some at min node or for some at max node . These are stronger conditions than those we found above and will therefore prune fewer nodes in general.
Here is an algorithmic formulation of alpha beta pruning. The value of the root node is computed by
f(root, 0, 1).
function f(node, α, β) local value if node is a leaf node then value = heuristic position value of node elseif node is a min node then value = 1 for child in all children of node do value = value ∧ f(child, α, β ∧ value) if value ≤ α then break end end else value = 0 for child in all children of node do value = value ∨ f(child, α ∨ value, β) if value ≥ β then break end end end return value end
To sum up the results of this post: I described two versions of alpha beta pruning that allow to prune nodes from the computation of an evaluation function with values in a distributive lattice at the root node. The first, strong, version has the disadvantage that it is computationally more difficult than the second. Both versions are stronger (potentially prune more nodes) than the method described in the paper by Ginsberg et al.