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 be a partially ordered set. It suffices to consider only finite sets for our application but the presented theory applies to any set and we will not assume finiteness. I will write as shorthand for and . Our goal in this post is to introduce a sensible way to compare finite (possibly empty) antichains in . An antichain is a subset of in which any two distinct elements are unordered. Recall that a linear extension of is a total order on that is consistent with in the sense that implies . Throughout this series of posts the symbol always indicates a linear extension and and denote the minimum (greatest lower bound) and maximum (least upper bound) for this linear extension respectively.
A subset is called a lower set if for all and the inequality implies that . Any subset can be extended to a smallest lower set containing by the definition
for some .
Note that if are antichains such that then . Similarly one can define upper sets and the smallest upper set containing .
Lemma: Let be nested lower sets. Then there is a linear extension of such that for all indices and all elements and the strict inequality holds.
If we take then this lemma simply states that there exists a linear extension. A more important consequence is the following.
Corollary: If is an antichain then there exists a linear extension such that for any and the inequality implies that . Moreover, for any this extension can be chosen such that is maximal in .
The first part follows by taking 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 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 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 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 . Suppose that player MIN is in a situation where only two moves are possible. The first move will lead to a finite set of best moves for player MAX to choose from while the second move leads to a finite set . Then player MAX will select the maximum 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 and express it as . This definition is potentially rather awkward, quantifying over all linear extensions, but it can be drastically simplified as I will now show.
If then for each there is a such that . In particular, for any linear extension the inequality also holds and therefore . So holds in this case. Now assume instead that there is an such that . Then according to our lemma there is a linear extension such that for all and so for this particular linear extension. In this case the relation 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 define the relation as or alternatively for all finite subsets as .
Similar considerations (with the roles of the MIN and MAX player reversed) lead to the following definition of a maximizing order, where now indicates the smallest upper set containing :
Maximizing order: For finite antichains define the relation as or alternatively for all finite subsets as .
The minimizing order expresses that the minimizing player MIN prefers the set of game positions over while the maximizing order expresses that player MAX prefers over . It is not difficult to check that the maximizing and minimizing orders are in fact partial orders on finite antichains in . Note that when are finite antichains and then and . In particular for any finite antichain the inequalities and 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 and .
Descending chains in the transitivity proof
The nodes in the diagram correspond to subsets of 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 the source set there exists in one of the target sets such that . The edges together encode the information obtained from the relations and . Since descending chains must be finite each chain starting in (top row) must eventually reach (bottom row) and transitivity follows. End of intermezzo.
Until now I only considered the conditions under which a single antichain is preferred over an antichain for player MIN, which is expressed by . 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 of more than one antichain is preferred over . That would mean that for any linear extension there is some index such that where the index might depend on the choice of linear extension. However, it turns out that in this case there must be an index such that already . In other words, player MIN prefers a set of antichains over if and only if some member of that set is already preferred over . This again follows from the lemma. Let be a linear extension such that for all and . Suppose that for all indices . Then for each index there is an such that . Then for all indices and therefore the set is not preferred over .
Let denote the set of finite (possibly empty) antichains in the partially ordered set . Then both and 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 is a lattice when all non-empty finite subsets have a greatest lower bound and a least upper bound . In that case it is easy to see that and are uniquely defined. The following theorems give sufficient conditions for and to be lattices.
Maximizing lattice: In the partially ordered set every non-empty finite subset has a greatest lower bound . If every non-empty finite subset has a least upper bound then the same holds for and so is a lattice.
Minimizing lattice: In the partially ordered set every non-empty finite subset has a least upper bound . If every non-empty finite subset has a greatest lower bound then the same holds for and so is a lattice.
I will prove only the maximizing lattice property, so the partial order on is the maximizing order in what follows. Let be finite antichains. The union is a finite subset of but not necessarily an antichain. Let be the set of minimal elements in , that is, those elements which have no smaller elements in . Then is an antichain and because is finite for all indices . So is a lower bound for . If is any lower bound then for each there is a such that . This means that since and so is the greatest lower bound.
Now suppose every non-empty finite subset has a least upper bound . If is an upper bound for then for all there exist such that for all indices and so . Let be the set of minimal elements
Then is an antichain and by the above. Now is itself also an upper bound for and so it is the least upper bound. This shows that under the given condition is a lattice.
To sum up the results of this post: For any partially ordered set we constructed a minimizing and a maximizing partial order on the set of finite antichains in . 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.