Using Aspiration Windows for Minimax Algorithms

Abstract

This paper is based on investigations of several algorithms for computing exact minimax values of game trees (utilizing backward pruning). Especially, the focus is on trees with an ordering similar to that we have actually found in game playing practice. We compare the algorithms using two different distributions of the static values, the uniform distribution and a distribution estimated from practical data. Moreover, this is the first systematic comparison of using aspiration windows for all of the usual minimax algorithms. We analyse the effects of aspiration windows of varying size and position. The use of an aspiration window not only makes alpha-beta search competitive, but there also exists previously unpublished dependencies of its effects upon certain properties of the trees. In general, the more recently developed algorithms with exponential space complexity are not to be recommended for game-playing practice, since their advantage in having to visit fewer nodes is more than outweighed under practical conditions by their enormous space requirements. Finally, we propose a method for an analytic determination of estimates of the optimal window size, presupposing evidence about some characteristic properties of the domain of application. In summary, we discovered and found empirical evidence for several effects unpredicted by theoretical studies