
Solution Trees as a Basis for Game Tree Search
Arie de Bruin, Wim Pijls, Aske Plaat?
Technical Report EURCS9404, May 1994
Erasmus University, Department of Computer Science
P.O.Box 1738, 3000 DR Rotterdam, The Netherlands
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, alphabeta, and SSS2. A general procedure for the construction of a solution tree, based on alphabeta and NullWindowSearch, is given. Furthermore two new examples of solution tree basedalgorithms are presented, that surpass alphabeta?i.e., never visit more nodes than alphabeta, and often less. Keywords: Game tree search, alphabeta, solution trees, algorithms.
1 Introduction
Game trees are related to two person zero sum games with perfect information like TicTacToe, 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 payoff 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
maxnode or minnode, 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 payoff 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 payoff 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.