page 1  (36 pages) 2  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 cut-off 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, Alpha-beta, SSS*, MTD, (Nega)Scout, Proof Number Search.

1 Introduction

A game tree models the behavior of a two-player 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 well-known 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]