Game tree searching by min/max approximation

摘要

We present an iterative method for searching min/max game trees based on the idea of approximating the “min” and “max” operators by generalized mean-valued operators. This approximation is used to guide the selection of the next leaf node to expand, since the approximations allow one to select efficiently that leaf node upon whose value the (approximate) value at the root most highly depends. Experimental results from almost 1,000 games of Connect-Four1 suggest that our scheme is superior to minimax search with alpha-beta pruning, for the same number of calls to the move routine. However, our scheme has higher overhead, so that further work is needed before it becomes competitive when CPU time per turn is the limiting resource.