Partial Order Evaluation in Game Tree Search, and its Application to Analyzing Semeai in the Game of Go

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Volume

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Contents

We revisit the problem of constructing an evaluation function for game tree search. While the standard model assumes a numeric evaluation function, partial orders have some desirable properties for constructing a more meaningful evaluation. However, previous partial order tree search algorithms have been quite complex. We introduce partial order bounding (POB), simple new method that uses partial order evaluations in game tree search. We also discuss the use of partial order move evaluation for move ordering and for pruning dominated moves during search. We show an application of the method to capturing races called semeal in Go. We show that liberty and eye counts of blocks in a semeai can be used to construct a partial order evaluation. In experiments, we show the resulting speedups compared to standard minimax search methods.