## Game trees under a partial order part 1: Partial orders

I’ve been interested in the subject of alpha-beta pruning of game trees for quite some time now. It has always struck me as unsatisfactory however that it relies on a total order of game positions (in the form of an evaluation function). It would be much more natural to evaluate game positions based on several distinct features and select best moves on this richer set of information. This means essentially that the total order of game positions is replaced by a partial order. There are a number of articles that explore this idea. The theory is, somewhat surprisingly maybe, quite a bit more involved than it is for total orders. The problem is that with a partial order there is now often not a single best move to choose from and the bookkeeping to handle all these choices is rather intricate. This first post in a series of three is based on a foundational paper “Searching game trees under a partial order” by P. Dasgupta et al, published in 1996. The motivation for these posts was firstly because it is a fascinating subject but also because I found the paper rather difficult to read and understand.  I think that a more mathematical style would help the overall presentation of the subject and  that is what I will try to accomplish in this series of blogs. This first post concentrates on the concept of partial orders underpinning the concept of game tree evaluations later on. That said, this post is also interesting in itself as a result in the theory of partial orders, even without the context of its application in game trees.

Let $(X, \leq)$ be a partially ordered set. It suffices to consider only finite sets $X$ for our application but the presented theory applies to any set and we will not assume finiteness. I will write $a < b$ as shorthand for $a \leq b$ and $a \neq b$. Our goal in this post is to introduce a sensible way to compare finite (possibly empty) antichains in $X$. An antichain is a subset of $X$ in which any two distinct elements are unordered. Recall that a linear extension $\prec$ of $\leq$ is a total order on $X$ that is consistent with $\leq$ in the sense that  $x < y$ implies $x \prec y$. Throughout this series of posts the symbol $\prec$ always indicates a linear extension and $\curlywedge$ and $\curlyvee$ denote the minimum (greatest lower bound) and maximum (least upper bound) for this linear extension respectively.

A subset $S \subseteq X$ is called a lower set if for all $x \in S$ and $y \in X$ the inequality $y \leq x$ implies that $y \in S$. Any subset $S \subseteq X$ can be extended to a smallest lower set containing $S$ by the definition

${\downarrow}S = \{ y \in X \mid y \leq x$ for some $x \in S\}$.

Note that if $S, T \subseteq X$ are antichains such that ${\downarrow} S = {\downarrow} T$ then $S = T$. Similarly one can define upper sets and the smallest upper set ${\uparrow} S$ containing $S$.

Lemma: Let $S_1 \subseteq \dotsc \subseteq S_n = X$ be nested lower sets. Then there is a linear extension $\prec$ of $\leq$ such that for all indices $j < k$ and all elements $x \in S_j$ and $y \in S_k \setminus S_j$ the strict inequality $x \prec y$ holds.

If we take $n = 1$ then this lemma simply states that there exists a linear extension. A more important consequence is the following.

Corollary: If $S \subseteq X$ is an antichain then there exists a linear extension $\prec$ such that for any $x \in S$ and $y \in X$ the inequality $y \prec x$ implies that $y \in {\downarrow} S$. Moreover, for any $x \in S$ this extension can be chosen such that $x$ is maximal in ${\downarrow} S$.

The first part follows by taking $n=2$ and the lower set $S_1 = {\downarrow} S$ in the lemma. For the second part take $n = 3$ and the two lower sets $S_1 = {\downarrow}(S \setminus \{x\})$ and $S_2 = {\downarrow} S$. Since $x \in S_2 \setminus S_1$ it is greater than all other elements in $S$ for the resulting linear extension.

Linear extensions are in a sense the “hidden variables” in the theory of game trees under a partial order. If game positions are only partially ordered then searching for moves will most likely not result in a single best move but in a finite set of best moves. Nevertheless a player must still choose a single move from such a set. I will make the fundamental assumption that both players use an otherwise unspecified linear extension $\prec$ to make their choice. (Dasgupta et al call the linear extension they use a “strategy”. Moreover they consider situations where both players use a different strategy. This turns out to be unnecessary as we will see in the next post.) Then the “minimizing player” MIN always selects a minimum move according to $\prec$ while the “maximizing player” MAX always selects a maximum move. Clearly different linear extensions lead to different gameplay for both players but nevertheless this idea will lead to a definition of gameplay that only depends on the underlying partial order and not on a particular choice of strategy. In what follows the central idea is therefore to single out properties that hold for all possible linear extensions and are “universal” in that sense.

Based on this idea we will construct minimizing and maximizing orders on finite antichains of $X$. Suppose that player MIN is in a situation where only two moves are possible. The first move will lead to a finite set $A \subseteq X$ of best moves for player MAX to choose from while the second move leads to a finite set $B$. Then player MAX will select the maximum $\curlyvee A$ when MIN plays the first move and $\curlyvee B$ when MIN plays the second. For player MIN this means that the first move is preferred over the second precisely when $\curlyvee A \preceq \curlyvee B$. 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 $\leqslant$ on finite antichains in $X$ and express it as $A \leqslant B$. This definition is potentially rather awkward, quantifying over all linear extensions, but it can be drastically simplified as I will now show.

If $A \subseteq {\downarrow} B$ then for each $x \in A$ there is a $y \in B$ such that $x \leq y$. In particular, for any linear extension the inequality $x \preceq y$ also holds and therefore $\curlyvee A \preceq \curlyvee B$. So $A \leqslant B$ holds in this case. Now assume instead that there is an $x \in A$ such that $x \not \in {\downarrow} B$. Then according to our lemma there is a linear extension such that $y \prec x$ for all $y \in B$ and so $\curlyvee B \prec \curlyvee A$ for this particular linear extension. In this case the relation $A \leqslant B$ does not hold. This justifies the definition below. An alternative formulation that works for all finite subsets is included as a small bonus. See the intermezzo for some more background.

Minimizing order: For finite antichains $A, B \subseteq X$ define the relation $A \leqslant B$ as $A \subseteq {\downarrow} B$ or alternatively for all finite subsets as $(A \setminus B) \subseteq {\downarrow}(B \setminus A)$.

Similar considerations (with the roles of the MIN and MAX player reversed) lead to the following definition of a maximizing order, where ${\uparrow} A$ now indicates the smallest upper set containing $A$:

Maximizing order: For finite antichains $A, B \subseteq X$ define the relation $A \eqslantless B$ as $B \subseteq {\uparrow} A$ or alternatively for all finite subsets as $(B \setminus A) \subseteq {\uparrow}(A \setminus B)$.

The minimizing order expresses that the minimizing player MIN prefers the set of game positions $A$ over $B$ while the maximizing order expresses that player MAX prefers $B$ over $A$. It is not difficult to check that the maximizing and minimizing orders are in fact partial orders on finite antichains in $X$. Note that when $A, B \subseteq X$ are finite antichains and $A \subseteq B$ then $B \eqslantless A$ and $A \leqslant B$. In particular for any finite antichain $A \subseteq X$ the inequalities $\varnothing \leqslant A$ and $A \eqslantless \varnothing$ hold. This also shows that these are different partial orders in general.

Intermezzo. The alternative formulation of the maximizing and minimizing orders results in partial orders on all finite subsets. These partial orders are then almost but not quite identical to what Dasgupta et al call “procedure compare.” Where Dasgupta et al prefer a non-empty set over an empty one in that procedure, the maximizing and minimizing orders always prefer the empty set over a non-empty one as already stated before. The transitivity property requires some attention and can be proved by the nice picture below, where it is assumed that $A \eqslantless B$ and $B \eqslantless C$.

Descending chains in the transitivity proof

The nodes in the diagram correspond to subsets of $A \cup B \cup C$ where the letters in a node select all elements that are exactly in these subsets and in no others. So “A” means $A \setminus (B \cup C)$ and “A, B” means $(A \cap B) \setminus C$ and so on. The top two nodes together form the set $C \setminus A$ and the bottom two nodes $A \setminus C$. Directed edges leaving a node indicate that for each $a$ in the source set there exists $b$ in one of the target sets such that $b < a$. The edges together encode the information obtained from the relations $A \eqslantless B$ and $B \eqslantless C$. Since descending chains must be finite each chain starting in $C \setminus A$ (top row) must eventually reach $A \setminus C$ (bottom row) and transitivity follows. End of intermezzo.

Until now I only considered the conditions under which a single antichain $A$ is preferred over an antichain $B$ for player MIN, which is expressed by $A \leqslant B$. However, player MIN will often have to choose from more than two possible moves so we also have to consider conditions under which a set $\{A_1, \dotsc, A_n\}$ of more than one antichain is preferred over $B$. That would mean that for any linear extension $\prec$ there is some index $j$ such that $\curlyvee A_j \preceq \curlyvee B$ where the index might depend on the choice of linear extension. However, it turns out that in this case there must be an index $j$ such that already $A_j \leqslant B$. In other words, player MIN prefers a set of antichains over $B$ if and only if some member of that set is already preferred over $B$. This again follows from the lemma. Let $\prec$ be a linear extension such that $x \prec y$ for all $x \in B$ and $y \not \in {\downarrow} B$. Suppose that $A_j \not \leqslant B$ for all indices $j$. Then for each index $j$ there is an $x_j \in A_j$ such that $x_j \not \in {\downarrow} B$. Then $\curlyvee B \prec x_j \preceq \curlyvee A_j$ for all indices $j$ and therefore the set $\{A_1, \dotsc, A_n\}$ is not preferred over $B$.

Let $X^{\ast}$ denote the set of finite (possibly empty) antichains in the partially ordered set $X$.  Then both $(X^{\ast}, \eqslantless)$ and $(X^{\ast}, \leqslant)$ are partially ordered sets with the maximizing and minimizing order respectively. Later on the lattice structure of such partial orders will play an important role. A partially ordered set $(X, \leq)$ is a lattice when all non-empty finite subsets $S \subseteq X$ have a greatest lower bound $\wedge S$ and a least upper bound $\vee S$. In that case it is easy to see that $\wedge S$ and $\vee S$ are uniquely defined. The following theorems give sufficient conditions for $(X^{\ast}, \eqslantless)$ and $(X^{\ast}, \leqslant)$ to be lattices.

Maximizing lattice: In the partially ordered set $(X^{\ast}, \eqslantless)$ every non-empty finite subset $S \subseteq X^{\ast}$ has a greatest lower bound $\wedge S \in X^{\ast}$. If every non-empty finite subset $T \subseteq X$ has a least upper bound $\vee T \in X$ then the same holds for $X^{\ast}$ and so $(X^{\ast}, \eqslantless)$ is a lattice.

Minimizing lattice: In the partially ordered set $(X^{\ast}, \leqslant)$ every non-empty finite subset $S \subseteq X^{\ast}$ has a least upper bound $\vee S \in X^{\ast}$. If every non-empty finite subset $T \subseteq X$ has a greatest lower bound $\wedge T \in X$ then the same holds for $X^{\ast}$ and so $(X^{\ast}, \leqslant)$ is a lattice.

I will prove only the maximizing lattice property, so the partial order on $X^{\ast}$ is the maximizing order in what follows. Let $S_1, \dotsc, S_n \in X^{\ast}$ be finite antichains. The union $S = S_1 \cup \dotsc \cup S_n$ is a finite subset of $X$ but not necessarily an antichain.  Let $\min(S) \subseteq S$ be the set of minimal elements in $S$, that is, those elements which have no smaller elements in $S$. Then $\min(S)$ is an antichain and because $S$ is finite $\min(S) \eqslantless S_j$ for all indices $j$. So $\min(S)$ is a lower bound for $\{S_1, \dotsc, S_n\} \subseteq X^{\ast}$. If $S' \in X^{\ast}$ is any lower bound then for each $x \in S$ there is a $y \in S'$ such that $y \leq x$. This means that $S' \eqslantless \min(S)$ since $\min(S) \subseteq S$ and so $\min(S)$ is the greatest lower bound.

Now suppose every non-empty finite subset $T \subseteq X$ has a least upper bound $\vee T \in X$. If $U' \in X^{\ast}$ is an upper bound for $\{S_1, \dotsc, S_n\} \subseteq X^{\ast}$ then for all $y \in U'$ there exist $x_1 \in S_1, \dotsc, x_n \in S_n$ such that $x_j \leq y$ for all indices $j$ and so $\vee\{x_1, \dotsc, x_n\} \leq y$. Let $U \subseteq X$ be the set of minimal elements

$U = \min \left\{ \vee \{x_1, \dotsc, x_n\} \mid (x_1, \dotsc, x_n) \in S_1 \times \dotsc \times S_n \right\}$.

Then $U$ is an antichain and $U \eqslantless U'$ by the above. Now $U$ is itself also an upper bound for $\{S_1, \dotsc, S_n\}$ and so it is the least upper bound. This shows that under the given condition $(X^{\ast}, \eqslantless)$ is a lattice.

To sum up the results of this post: For any partially ordered set $(X, \leq)$ we constructed a minimizing and a maximizing partial order on the set $X^{\ast}$ of finite antichains in $X$. These indicate when a set of outcomes is universally preferred (under all linear extensions) over another set by a minimizing and maximizing player respectively. For these “star extended” partially ordered sets we defined the lattice operations of taking the greatest lower bound and least upper bound (when these exist). In the next post in this series we will start to explore actual game trees under a partial order, starting with the definition of evaluation functions.