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 
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 
- The value of
- At an inner min node (where the minimizing player is to make a move) the value of
- At an inner max node the value of
This definition leads to the following algorithm for the computation of
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
Intermediate values in the depth first left to right computation of an evaluation function
Here 
at the root node. The essential point of alpha beta pruning is that it identifies when this intermediate value remains constant even when 
A lattice 
Lemma: When 
Since 
and
is obtained from
by the substitution
.
and
is obtained from
by the substitution
.
So the sequence
and the sequence
The following inequalities are a direct consequence of our lemma above. The sequences
for all indices 
Alpha Beta pruning (strong version): At the first index 
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
Also note that the distributive property of the lattice
There is a weaker version of alpha beta pruning based on alternative sequences 
So 
These can be proved by induction and the distributive property of the lattice 
Comparing these equalities it follows that 
Alpha Beta pruning: If the value
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 
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.
and the result of Ginsberg on alpha beta pruning is sharpened in the next post, potentially leading to more aggressive pruning in game tree searches.
assigned to them. Is there a way, given the values at the leaves, to define an evaluation function on the entire tree? Let’s first assume that both players in fact use an (unspecified) linear extension 
of the partial order 
to select their optimal move. (Dasgupta et al call such a linear extension a strategy. See the intermezzo below for why it is fair to assume that both players use the same strategy.) Here is an example how this linear extension can be used to define an evaluation function on a tree of positions. The symbols “
” at the leaf nodes indicate some (not necessarily equal) values in 
, the space of all functions that map linear extensions of 
as constant functions: 
for all linear extensions 
then define an element 
by 
where 
by 
where 
have a greatest lower bound 
then 
is a lower bound for 
and 
but not necessarily the greatest lower bound. End of remark.
. End of example.
to the leaf nodes based on some heuristics.
ordered by their maximizing order and 
ordered by their minimizing order. If 
and 
respectively to distinguish them from the lattice operators in CNF and DNF. The following statements identify the normal forms of 
and 
respectively. The sublattice 
is isomorphic to 
.
and 
respectively. The sublattice 
is isomorphic to 
.
is a lattice. The empty set (which is a finite antichain) is maximal for any maximizing order and minimal for any minimizing order. Therefore the elements 
are such that 
for all linear extensions 
(which suffices since by symmetry then also 
and 
).
. For any 
there exists a linear extension 
and
and 
then 
.
since, being an antichain, no element of 
other than 
itself can be entirely contained in 
. In particular all 
with 
must contain 
. Since this holds for any 
for all 
and hence 
.
as shorthand for 
and 
. Our goal in this post is to introduce a sensible way to compare finite (possibly empty) antichains in 
implies 
. Throughout this series of posts the symbol 
is called a lower set if for all 
and 
implies that 
. Any subset 
by the definition
for some 
.
are antichains such that 
then 
. Similarly one can define upper sets and the smallest upper set 
containing 
be nested lower sets. Then there is a linear extension 
and all elements 
and 
the strict inequality 
then this lemma simply states that there exists a linear extension. A more important consequence is the following.
. Moreover, for any 
.
and the lower set 
in the lemma. For the second part take 
and the two lower sets 
and 
. Since 
it is greater than all other elements in 
of best moves for player MAX to choose from while the second move leads to a finite set 
when MIN plays the first move and 
when MIN plays the second. For player MIN this means that the first move is preferred over the second precisely when 
. If this relation holds for all possible linear extensions then the first move for MIN is universally better than the second. We can take this as the definition for a minimizing order 
on finite antichains in 
. This definition is potentially rather awkward, quantifying over all linear extensions, but it can be drastically simplified as I will now show.
then for each 
there is a 
such that 
also holds and therefore 
. Then according to our lemma there is a linear extension such that 
for this particular linear extension. In this case the relation 
define the relation 
.
now indicates the smallest upper set containing 
as 
or alternatively for all finite subsets as 
.
and 
and 
hold. This also shows that these are different partial orders in general.
.
where the letters in a node select all elements that are exactly in these subsets and in no others. So “A” means 
and “A, B” means 
and so on. The top two nodes together form the set 
and the bottom two nodes 
. Directed edges leaving a node indicate that for each 
in one of the target sets such that 
. The edges together encode the information obtained from the relations 
of more than one antichain is preferred over 
where the index might depend on the choice of linear extension. However, it turns out that in this case there must be an index 
. In other words, player MIN prefers a set of antichains over 
and 
. Suppose that 
for all indices 
such that 
. Then 
for all indices 
denote the set of finite (possibly empty) antichains in the partially ordered set 
and a least upper bound 
. In that case it is easy to see that 
has a greatest lower bound 
. If every non-empty finite subset 
has a least upper bound 
then the same holds for 
. If every non-empty finite subset 
then the same holds for 
be finite antichains. The union 
is a finite subset of 
be the set of minimal elements in 
is an antichain and because 
for all indices 
. If 
is any lower bound then for each 
such that 
since 
is an upper bound for 
there exist 
such that 
for all indices 
. Let 
be the set of minimal elements
.
is an antichain and 
by the above. Now 
and so it is the least upper bound. This shows that under the given condition 
. Pushing an element 
onto a stack 
is defined by
.
is generated by 
) but more importantly they capture the requirements of a set. The relation 
expresses that all elements in a set have multiplicity one (I will come back to this in a moment) and 
that a set is unordered. Here are the definitions of some sensible set operations:
. On the other hand, the following multiplicity function is not well defined even though it might look acceptable at first glance: 
. The problem here is that 
is symmetric but not idempotent and does not respect the relations 
is well defined.
is projection on the first coordinate:
:
such that 
and 
for all 
. If the Taylor expansion of 
for all integer 
. Moreover, such functions are in one-to-one correspondence with probability measures on the unit circle 
as follows. Let 
be a probability measure on 
for 
be its Fourier coefficients
.
, 
and 
is the complex conjugate of 
. If 
with respect to the Lebesgue probability measure that is holomorphic on some neighborhood of 
.
on a neighborhood of the closed disc 
as follows:
.
for all 
, for all 
and therefore 
between probability measures and functions with positive real part also holds for 
be any holomorphic function on a neighborhood of the closed disc 
.
be the holomorphic function such that 
, so the coefficients of 
.
has the Laurent expansion
for all 
. Now the sequence 
. Let 
be the left shift operator, so 
for all 
and indices 
. Then the Laurent series above can be rewritten as
denotes the sesquilinear form on 
. Now define a holomorphic function 
on a neighborhood of the closed disc 
.
and therefore 
on the disc 
is not injective however, since 
and 
map to the same function if 
on the unit circle 
(mod p) for all integers m. So the polynomial ![f = X^p-X \in \mathbb{Z}[X]](http://s0.wp.com/latex.php?latex=f+%3D+X%5Ep-X+%5Cin+%5Cmathbb%7BZ%7D%5BX%5D&bg=ffffff&fg=333333&s=0 "f = X^p-X \in \mathbb{Z}[X]")
has the property that 
(mod p) for all integers m. Since 
is an integral domain, any polynomial in ![\mathbb{Z}[X]](http://s0.wp.com/latex.php?latex=%5Cmathbb%7BZ%7D%5BX%5D&bg=ffffff&fg=333333&s=0 "\mathbb{Z}[X]")
of degree d that is not divisible by p has at most d roots in 
is also minimal in that sense. What can we say if we replace the prime p by just any positive integer n? In other words, what can we say about ![f \in \mathbb{Z}[X]](http://s0.wp.com/latex.php?latex=f+%5Cin+%5Cmathbb%7BZ%7D%5BX%5D&bg=ffffff&fg=333333&s=0 "f \in \mathbb{Z}[X]")
if 
. Let 
for coprime integers m and q. Then f is divisible by m.”
by
.
is a monic polynomial of degree d in 
as before. Then there exist coefficients 
such that
.
has integer coefficients and since m and q are coprime the equation above implies that m divides f.
is a linear subspace then either 
contains a vector with positive coordinates 
contains a non-zero vector with non-negative coordinates.”
then either there is a vector 
such that the inner product 
is positive for all 
or the convex hull 
of 
contains the origin.”
be the 
matrix with 
as its rows. Then the columns of 
have minimal norm. If 
then 
and 
is any point in the convex hull then the line segment from 
to ![t \in (0,1]](http://s0.wp.com/latex.php?latex=t+%5Cin+%280%2C1%5D&bg=ffffff&fg=333333&s=0 "t \in (0,1]")
we have
.
and in particular this holds for all 
. Done!
