Partial Order Bounding

Partial order bounding as an alternative approach to evaluation in game tree search. This method allows the use of partially ordered evaluations in any game tree search algorithm that was originally designed to use boolean values or numbers, for example alpha-beta or proof-number search.

The established game tree searching methods use a scalar evaluation function and a minimax-based backup rule. There are many theoretical algorithms in the literature that replace such simple scalar values by something more expressive, such as a probability distribution, an interval, or some other partially ordered set of values. However, previous algorithms have attempted to propagate these values through the search tree, leading to both restrictions on the type of partial orders allowed and to complex backup procedures for sets of incomparable options.

Partial order bounding overcomes these problems by comparing partial order evaluations only in the leaves of a game tree, and backing up only boolean values through the tree. The closely related algorithm Linear Extension - POB (LE-POB) uses standard alpha-beta search with values from a suitably constructed linear extension of the partially ordered set.

Potential research topics


M. Müller. Partial Order Bounding: A new Approach to Evaluation in Game Tree Search. Artificial Intelligence Journal, 129(1-2), 279-311, 2001.

M. Müller. Partial Order Evaluation in Game Tree Search, and its Application to Analyzing Semeai in the Game of Go. Workshop on Search Techniques for Problem Solving Under Uncertainty and Incomplete Information, Weixiong Zhang and Sven Koenig, Cochairs, AAAI 1999 Spring Symposium Series, 101--106, AAAI, 1999.

Supporting Data

Created: Sep 26, 2000 Last modified: Jun 19, 2009

Martin Müller