A framework for game tree algorithms

Wim Pijls,
Arie de Bruin
Erasmus University Rotterdam
P.O.Box 1738, NL-3000 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 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 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