SEARCHING GAME TREES UNDER A PARTIAL ORDER

The problem of partial order game tree search arises from game playing situations where multiple, conflicting and non-commensurate criteria dictate the merit of a position of the game. In partial order game tre es, the outcomes evaluated at the tip nodes are vectors, where each di mension of the vector represents a distinct criterion of merit. This l eads to an interesting variant of the game tree searching problem wher e corresponding to every game playing strategy of a player, several ou tcomes are possible depending on the individual priorities of the oppo nent. In this paper, we identify the necessary and sufficient conditio ns for a set of outcomes to be inferior to another set of outcomes for every strategy. Using an algebra called Dominance Algebra on sets of outcomes, we describe a bottom-up approach to find the non-inferior se ts of outcomes at the root node. We also identify shallow and deep pru ning conditions for partial order game trees and present a partial ord er search algorithm on lines similar to the cu-p pruning algorithm for conventional game trees.