A framework for game tree algorithms
Wim Pijls, Arie de Bruin · RePub (Erasmus University Rotterdam) · 1993
A unifying framework for game tree algorithms is GSEARCH, designed by Ibaraki [Ibaraki 86]. In general, a relatively great deal of memory is necessary for instances of this framework. In [Ibaraki 91A] an extended framework, called RSEARCH, is discussed, in which the use of memory can be controlled. In this paper variants of above frameworks are introduced, to be called Gsearch and Rsearch respectively. It is shown that, in these frameworks, the classical alpha-beta algorithm is the depth-first search instance and H* is a best first search instance. Furthermore two new algorithms, Maxsearch and Minsearch, are presented, both as best-first search instances. Maxsearch is close to SSS* [Stockman] and SSS-2 [Pijls-2], whereas Minsearch is close to dual SSS*. 1 Introduction A game tree algorithm is an algorithm computing the minimax value of a game tree. We will recall a few well-known facts about game trees, search trees and algorithms defined on them. A critical path in a game tree is a p...