Partial Order Bounding

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

• revised version, compressed pdf, 476k.

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.

• pdf

Supporting Data

• Semeai test files and test results