
A framework for game tree algorithms
Wim Pijls,
Arie de Bruin
Erasmus University Rotterdam
P.O.Box 1738, NL3000 DR Rotterdam,
The Netherlands,
[email protected]
Abstract
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 alphabeta algorithm is the depthfirst search instance and H*
is a best first search instance. Furthermore two new algorithms, Maxsearch
and Minsearch, are presented, both as bestfirst search instances. Maxsearch
is close to SSS* [Stockman] and SSS2 [Pijls2], 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 wellknown facts about game trees, search trees and
algorithms defined on them.
A critical path in a game tree is a path from the root to a terminal such that the
minimax value is constant along this path. Hence, in a game tree with minimaxvalue
f , f(x) = f for each node x on a critical path. A critical path represents
an optimal strategy for each player. A node on a critical path is called critical.
In all game tree algorithms, the tree is explored step by step, i.e., in each step
a new node of the tree is visited or generated, depending on whether the tree
is given explicitly or defined implicitly by some rule. So, at each moment during
execution of a game tree algorithm, there is a set of nodes which has been
generated up to that moment. This subtree of the game tree will be called the
search tree. In the sequel we will only consider search trees with the property
that for each node either all its children are included in the search tree or none.
All algorithms in this paper will generate such search trees.
When a part of the game tree has been explored, an upper and a lower bound