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

Well-known algorithms for the evaluation of the minimax function in game trees are alpha-beta [Knuth] and SSS* [Stockman]. An improved version of SSS* is SSS-2 [Pijls-1]. 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 alpha-beta and the SSS-2 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, Tic-tac-toe, 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 pay-off of that position.
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 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 f-values. The bold lines in this figure define a so called solution tree, which is to be defined in Section 4.