Searching game trees under a partial order

doi:10.1016/0004-3702(94)00085-9

Searching game trees under a partial order

1996-04-01

6

OA

AI

DOI：10.1016/0004-3702(94)00085-9

原文链接

查看原文

摘要

En 中文

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 cu-p pruning algorithm for conventional game trees.

Keyword:

ALPHA-BETA

Searching game trees under a partial order

摘要

AI总结

期刊

机构

引用论文