
Searching informed game trees
Wim Pijls,
[email protected]
Arie de Bruin
[email protected]
Erasmus University Rotterdam, P.O.Box 1738, 3000 DR Rotterdam,
The Netherlands.
Abstract
Wellknown algorithms for the evaluation of the minimax function in game trees are alphabeta [Knuth] and SSS* [Stockman]. An improved version of SSS* is SSS2 [Pijls1]. All these algorithms don't use any heuristic information on the game tree. In this paper the use of heuristic information is introduced into the alphabeta and the SSS2 algorithm. Extended versions of these algorithms are presented. The subset of nodes which is visited during execution of each algorithm is characterised completely.
1 Introduction
In this paper several methods are discussed to compute the minimax function on
a game tree with heuristic information.
Game trees are related to two person games with perfect information like Chess,
Checkers, Go, Tictactoe, etc. 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 the position given by n. The terminals in the tree are
positions in the game for which a real valued evaluation function f exists giving
the so called game value, the payoff of that position.
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
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:
f(n) = max ff(c) j c a child of ng, if n is a max node,
min ff(c) j c a child of ng, if n is a min node.
We adopt the convention that the minimax value of a game tree T , denoted by f(T ), is the minimax value of the root of this tree. In Figure 1 an example of a game tree is shown labeled with its fvalues. The bold lines in this figure define a so called solution tree, which is to be defined in Section 4.