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 trees, the outcomes evaluated at the tip nodes are vectors, where each dimension of the vector represents a distinct criterion of merit. This leads to an interesting variant of the game tree searching problem where corresponding to every game playing strategy of a player, several outcomes are possible depending on the individual priorities of the opponent. In this paper, we identify the necessary and sufficient conditions 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 sets of outcomes at the root node. We also identify shallow and deep pruning conditions for partial order game trees and present a partial order search algorithm on lines similar to the α-β pruning algorithm for conventional game trees.