
A theory of game trees, based on solution trees
Wim Pijls, Arie de Bruin ?
Abstract
In this paper, a theory of game tree algorithms is presented, entirely
based upon the concept of solution tree. Two types of solution trees are
distinguished: max and min solution trees respectively. We show that a
game tree algorithm actually constructs a superposition of a max and a min
solution tree. For algorithms searching a game tree, a cutoff criterion is
suitable. A cutoff criterion in terms of solution trees will be formulated,
which can be used to eliminate nodes from the search without affecting the
result. Finally, we will see, how solution trees and the related cutoff criterion
are applied in the major game tree algorithms.
Keywords: Game tree search, Minimax search, Solution trees, Alphabeta,
SSS*, MTD, (Nega)Scout, Proof Number Search.
1 Introduction
A game tree models the behavior of a twoplayer game. The nodes in such a tree
represent positions of a game, whereas edges represent moves. Given a payoff in
the leaves of a game tree, the best move in each position can be determined by
means of the minimax function. Over the years, many algorithms have been designed,
which determine the minimax value of a game tree, given a payoff value in
the leaves. Although the minimax function is defined using all nodes of the tree,
every algorithm tries to inspect a number of nodes as small as possible. In this
paper, it turns out that the notion of a solution tree is a key notion in the theory
of game tree algorithms. There are two types of solution trees: max and min
solution trees respectively. First, we show that every algorithm computing the
minimax value of a game tree constructs a max and a min solution tree. Next, we
present a general cutoff criterion for searching game trees. This criterion will be
explained in terms of solution trees. In the remainder of this paper, we discuss
the role of solution trees in five wellknown algorithms, viz. alphabeta, SSS*,
MTD, Scout and Proof number Search.
We deal only with fixed depth algorithms. In practice, mostly iterative deepening
is used. But even with iterative deepening, at one given level, still a fixed depth
method is needed.
This paper is organized as follows. The sections 2 and 3 discuss basic concepts. In Section 2, the concept of a solution tree is introduced, and its relation to the game tree value is explained. In Section 3, we show that there is a close
?Erasmus University Rotterdam, P.O.Box 1738, 3000 DR Rotterdam, The Netherlands, email: fpijls,[email protected]