2

page 2 (26 pages)
1		3

l l
25

5 8 7 2 8

l
8 l
2 l
7 l
2 l
1 l
8 l
4

?
?
?
?
?

QQQQQ

@
@@

?
?
?

S
S
S

?
?
?

A
A
A

?
?
?

@
@
@

?
?
?

A
A
A

Figure 1: A game tree with f-values.

The value f(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. In any node n the move for each player to optimize the pay-off is the transition to a child node c such that f(c) = f(n). In this way, MAX tries to maximize and MIN tries to minimize the profit of MAX. Therefore, an optimal play will proceed along a critical path, which is defined as a path from the root to a leaf such that f(n) has the same value for all nodes n in the path. All nodes in this path have a game value equal to the game value of the root.

For some game trees, heuristic information on the minimax value f(n) is available for any node. This information can be expressed as a pair H = (U; L) where U and L are heuristic functions mapping the nodes of the game tree into the real numbers, such that U(n) >= f(n) >= L(n) for any node n and U(n) = f(n) = L(n) for every terminal n. The heuristic functions thus denote an upper bound and a lower bound respectively of the minimax value. A heuristic pair H = (U; L) is called consistent if U(c) <= U(n) for every child c of a given max node n, and L(c) >= L(n) for every child c of a given min node. From now, we assume that an input instance consists of a pair (G; H), called an informed game tree, where G denotes a game tree and H a pair of consistent heuristic functions. If heuristic information is discarded or is not available at all, we define U(n) = +1 and L(n) = ?1 for every non-terminal node n.

In order to compute the minimax value of a game tree, several algorithms have been developed. The brute force approach would compute the minimax function in each node of the game tree according to the definition. Each feasible algorithm has its own method to avoid examining the entire tree.