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.
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.
Martin Müller