# 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

- Investigate evaluation
function design using partial orders, including methods for learning such
evaluations from data.
- Experiment with transforming existing scalar
evaluation functions to partial orders.
- Study partial order
bounding in the context of single-agent search and optimization.

## Publications

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