Solution Trees as a Basis for Game Tree Search

Arie de Bruin, Wim Pijls, Aske Plaat?

Technical Report EUR-CS-94-04, May 1994

Erasmus University, Department of Computer Science

P.O.Box 1738, 3000 DR Rotterdam, The Netherlands

[email protected]

Abstract

A game tree algorithm is an algorithm computing the minimax value of the root of a game tree. Many algorithms use the notion of establishing proofs that this value lies above or below some boundary value. We show that this amounts to the construction of a solution tree. We discuss the role of solution trees and critical trees in the following algorithms: Principal Variation Search, alpha-beta, and SSS-2. A general procedure for the construction of a solution tree, based on alpha-beta and Null-Window-Search, is given. Furthermore two new examples of solution tree based-algorithms are presented, that surpass alpha-beta?i.e., never visit more nodes than alpha-beta, and often less. Keywords: Game tree search, alpha-beta, solution trees, algorithms.

1 Introduction

Game trees are related to two person zero sum games with perfect information like TicTac-Toe, Checkers, Chess, and Go. Each node in a game tree represents a game position. The root represents a position of the game, for which we want to find the best move. The children of each node n correspond to the positions resulting from one move from that position. The leaves in the tree are positions in the game for which an integer valued evaluation function ? exists giving the so called game value, the pay-off in that position. A game tree is assumed to remain unchanged during the search for the best move, in the sense that we do not look into search enhancements like iterative deepening [Sch89].

We assume that the two players are called MAX and MIN. A node n is marked as max-node or min-node, if in the corresponding position it is max's or min's turn to move respectively. We assume that MAX moves from the start position.
The evaluation function can be extended to the so called minimax function, a function which determines the value for each player in any node. The definition is:

?(n) = max f?(c) ? c is a child of ng, if n is a max node,
min f?(c) ? c is a child of ng, if n is a min node.

In Figure 1 an example of a game tree is shown labeled with its ?-values. The squares represent max nodes, the circles min nodes. For a game tree G with root r, the value ?(r) is also called the minimax value of G, denoted by ?(G). A game tree algorithm is an algorithm computing the root successor with the highest pay-off for MAX?the best move for MAX?or the minimax value of a game tree, from which we can easily infer the best move.

The value ?(n) in any node n (n not necessarily a max node) indicates the highest attainable pay-off for MAX in the position n, under the condition that both players will play optimally in the sequel of the game according to the evaluation function ?. In any node n

?Tinbergen Institute, Erasmus University, and Department of Computer Science, Erasmus University.