## Game trees under a partial order part 2: Evaluation functions

The first part of this series introduced the maximizing and minimizing orders on finite antichains in any partially ordered set $(X, \leq)$. In this second part I will show how these orders and their properties are used to define evaluation functions on game trees. The previous post was mainly based on the paper “Searching game trees under a partial order” by P. Dasgupta et al. In this second post I will show how it is related to another paper “Alpha-Beta pruning under partial orders” by M. Ginsberg et al from 2001. This second paper has an interesting different approach. Instead of starting with a partial order from the beginning it investigates what structure an evaluation function on a game tree must have to satisfy some reasonable constraints. The answer they find is that such an evaluation function must be defined on a lattice, that is, a set with operators “greatest lower bound” $\wedge$ and “least upper bound” $\vee$. An evaluation function is then defined recursively, starting at the leaves. The minimizing player combines the values of subnodes with $\wedge$ while the maximizing player uses $\vee$. Moreover, Ginsberg et al show that such an evaluation function allows alpha beta pruning (which I will define in detail in the next post) exactly if the lattice is distributive. While the paper by Ginsberg references that of Dasgupta the relation between the two is not made very explicit. This post will give a very precise and (I think) satisfying relation between the two papers ultimately improving the results of both: The work of Dasgupta is formalized in terms of lattice theory and can now be applied to any partially ordered set, not just $\mathbb{R}^n$ 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.

Consider a game tree in which a min and max player make moves in turn. Suppose that leaf nodes in this tree get a value in the partially ordered space $X$ 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 $\prec$ of the partial order $\leq$ 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 “$\bullet$” at the leaf nodes indicate some (not necessarily equal) values in $X$. The greatest lower bound and least upper bound $\wedge$ and $\vee$ are taken with respect to the linear extension $\prec$.

An evaluation function based on a linear extension (or strategy)

In this example the minimizing player is to move and the tree represents possible move developments that are considered. The value at inner nodes is defined recursively based on the linear extension: The minimizing player takes the minimum (the greatest lower bound) of the subnodes while the maximizing player takes the maximum (the least upper bound). This leads to a value for the top node in $X$ and the minimizing player will select a move that leads to this minimum.

Intermezzo. Assuming that the min player in this example uses an unspecified linear extension (or “strategy” as Dasgupta calls them) to select moves is central in our considerations. But why is it fair to assume that the max player uses the same strategy? The reason is simple. Suppose the max player uses a different strategy or in fact any system at all (even random decisions) to select moves. In that case the altered evaluation function would assign to each node a value that is less than or equal to the value obtained from equal strategies (when compared with the min player’s linear extension). This follows from the recursive definition of the evaluation function. Since the min player’s goal is to reach a minimal value, the worst case scenario is to assume that the opponent uses the same strategy. End of intermezzo.

Any evaluation function defined as above still depends on the choice of linear extension, so different linear extensions give different evaluation functions. What we are looking for instead is a way to define a single evaluation function based only on the given partial order on $X$. There is a nice trick to turn the example above into exactly such a function, but it requires to alter the target space. To define the new target space start with $\mathscr{F}(X, \leq)$, the space of all functions that map linear extensions of $\leq$ to $X$. The evaluation defined above at any node can be regarded as an example of such a function by treating the linear extension $\prec$ in its definition not as fixed but as a variable. Let me make this more precise based on the following observations:

1. There is a canonical embedding $\iota: X \hookrightarrow \mathscr{F}(X, \leq)$ as constant functions: $\iota_x(\prec) = x$ for all linear extensions $\prec$.
2. If $f, g \in \mathscr{F}(X, \leq)$ then define an element $f \wedge g \in \mathscr{F}(X, \leq)$ by $(f \wedge g)(\prec) = f(\prec) \wedge g(\prec)$ where $\wedge$ in the right hand side refers to the minimum with respect to $\prec$.
3. If $f, g \in \mathscr{F}(X, \leq)$ then define an element $f \vee g \in \mathscr{F}(X, \leq)$ by $(f \vee g)(\prec) = f(\prec) \vee g(\prec)$ where $\vee$ in the right hand side refers to the maximum with respect to $\prec$.
4. Since any totally ordered set is a distributive lattice with respect to its minimum and maximum operators $\wedge$ and $\vee$ it follows that the definitions above turn $\mathscr{F}(X, \leq)$ into a distributive lattice and therefore also into a partially ordered set.

The entire space $\mathscr{F}(X, \leq)$ is too big for our purpose, therefore I define $\mathscr{L}(X, \leq)$, the linear lattice over $(X, \leq)$ as the smallest sublattice of $\mathscr{F}(X, \leq)$ that contains $X$. Then $\mathscr{L}(X, \leq)$ is still a distributive lattice. The linear lattice $\mathscr{L}(X, \leq)$ will serve as the target space for evaluation functions on game trees under the partial order $(X, \leq)$.

Remark. The set $X$ embeds into $\mathscr{L}(X, \leq)$ as a partially ordered set but not always as a lattice. For example if $x, y \in X$ have a greatest lower bound $x \wedge y \in X$ then $\iota_{x \wedge y}$ is a lower bound for $\iota_x$ and $\iota_y$ but not necessarily the greatest lower bound. End of remark.

Example. If $(X, \leq)$ is a totally ordered space then $\mathscr{L}(X, \leq) = (X, \leq)$. End of example.

An evaluation function on a game tree is now defined recursively, as in the picture above, as follows.

1. Assign values in $X \subseteq \mathscr{L}(X, \leq)$ to the leaf nodes based on some heuristics.
2. Define the value of an inner min node as the greatest lower bound in $\mathscr{L}(X, \leq)$ of the values of all its direct successors.
3. Define the value of an inner max node as the least upper bound in $\mathscr{L}(X, \leq)$ of the values of all its direct successors.

Note that this construction is completely in line with the results of Ginsberg et al. The fact that $\mathscr{L}(X, \leq)$ is a distributive lattice even implies that alpha beta pruning should be applicable in the recursive computation of the evaluation function. I will address that part in the next post.

The linear lattice may seem rather abstract but the fact that it is distributive and generated by $X$ means that each element can be put in both a disjunctive and conjunctive normal form built from elements of $X$ only. These normal forms can be described directly in terms of minimizing and maximizing orders as introduced in the first post. This will identify the linear lattice with what Dasgupta et al call “dominance algebra”. Define two partially ordered spaces, suggestively called $\textrm{CNF}(X, \leq)$ and $\textrm{DNF}(X, \leq)$, by applying the star order extension twice as in the picture below:

Two step construction of DNF (top) and CNF (bottom)

So $\textrm{CNF}(X, \leq)$ is the set of finite antichains in $(X^{\ast}, \leqslant)$ ordered by their maximizing order and $\textrm{DNF}(X, \leq)$ the set of finite antichains in $(X^{\ast}, \eqslantless)$ ordered by their minimizing order. If $\prec$ is a linear extension of $\leq$ I denote it’s minimum and maximum operators by $\curlywedge$ and $\curlyvee$ respectively to distinguish them from the lattice operators in CNF and DNF. The following statements identify the normal forms of $\mathscr{L}(X, \leq)$.

CNF: For any partially ordered space $(X, \leq)$ the space $\textrm{CNF}(X, \leq)$ is a lattice with minimal and maximal elements $\mathbf{0} = \{\varnothing\}$ and $\mathbf{1} = \varnothing$ respectively. The sublattice $\textrm{CNF}(X, \leq) \setminus \{\mathbf{0}, \mathbf{1}\}$ is isomorphic to $\mathscr{L}(X, \leq)$ via the rule $x(\prec) = \curlywedge \{ \curlyvee s \mid s \in x\}$.

DNF: For any partially ordered space $(X, \leq)$ the space $\textrm{DNF}(X, \leq)$ is a lattice with minimal and maximal elements $\mathbf{0} = \varnothing$ and $\mathbf{1} = \{\varnothing\}$ respectively. The sublattice $\textrm{DNF}(X, \leq) \setminus \{\mathbf{0}, \mathbf{1}\}$ is isomorphic to $\mathscr{L}(X, \leq)$ via the rule $x(\prec) = \curlyvee \{ \curlywedge s \mid s \in x\}$.

I will only show the CNF case. In the previous post we saw that any maximizing order always has a greatest lower bound operator $\wedge$ and it also has a least upper bound operator $\vee$ if its base space has one. Since in particular $(X^{\ast}, \leqslant)$ always has a least upper bound operator, this shows that $(X^{\ast \ast}, \leqslant)$ 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 $\mathbf{0} = \{\varnothing\}$ and $\mathbf{1} = \varnothing$ are minimal and maximal elements for this lattice respectively. A simple verification shows that the given evaluation rule at least defines a surjective homomorphism onto $\mathscr{L}(X, \leq)$ so it remains to prove that this homomorphism is also injective (meaning that the conjunctive normal form is unique). Suppose $A, B \in \textrm{CNF}(X, \leq)$ are such that $A(\prec) = B(\prec)$ for all linear extensions $\prec$. I will show that this implies $A \subseteq B$ (which suffices since by symmetry then also $B \subseteq A$ and $A = B$).

Let $a \in A$. For any $x \in a$ there exists a linear extension $\prec$ such that

1. $x$ is maximal in the lower set ${\downarrow} a$ and
2. if $y \in X$ and $y \prec x$ then $y \in {\downarrow} a$.

This implies that $A(\prec) = x$ since, being an antichain, no element of $A$ other than $a$ itself can be entirely contained in ${\downarrow} a$ and therefore must have a maximum greater than $x$. Then by assumption also $B(\prec) = x$. In particular all $b \in B$ with $b \leqslant a$ must contain $x$ and at least one such element must exist in $B$. Since this holds for any $x \in a$ it follows that $a \subseteq b$ for all $b \in B$ with $b \leqslant a$. This implies that $a = b$ and hence $a \in B$.

Summing up the results of this post: The linear lattice $\mathscr{L}(X, \leq)$ is the natural target space for evaluation functions on game trees based on heuristic evaluation of positions with values in the partially ordered set $(X, \leq)$. Both lattices $\textrm{CNF}(X, \leq)$ and $\textrm{DNF}(X, \leq)$ (minus their maximal and minimal elements) are isomorphic to the linear lattice $\mathscr{L}(X, \leq)$ and explicitly represent elements in their unique conjunctive and disjunctive normal form respectively. In particular the CNF and DNF lattices are themselves distributive and isomorphic. The isomorphisms both ways correspond to what in the paper by Dasgupta et al is called “MAX to MIN” and “MIN to MAX”.

In the next and final post in this series I will discuss alpha beta pruning for game trees under a partial order.