Benefits of using multivalued functions for minimaxing

摘要

Minimaxing has been very successful in game-playing practice, although a complete explanation of why it has been that successful has not yet been given. In particular, it has not been shown why it should be useful—as it is in practice—to use multivalued evaluation functions. Such functions have many distinct values as their result and can discriminate between positions according to the heuristic knowledge represented in these values. In this paper, we modify a basic pathological model by adding two assumptions regarding multivalued evaluation functions. These assumptions, non-uniformity of error distribution and dependency of heuristic values, directly relate to the properties of multivalued evaluation functions as used in practice. Simulation studies of our multivalued model have exhibited sharp error reductions for deeper searches using minimaxing. This behavior corresponds to observations in practice. The error reductions are primarily due to the improved evaluation quality as search depth increases. This phenomenon of lower probability of static evaluation errors with increasing search depth is revealed through our model, although the same evaluation function is used at all levels of the tree, and although its general error probability is independent of the depth. Essentially, with increasing search depth, the evaluation function is more frequently used on such positions which can be more reliably evaluated by a multivalued function with the assumed properties. This effect together with the ability to discriminate between positions of different “goodness” leads to the benefits of using multivalued evaluation functions (of appropriate granularity) for minimaxing.