8 Tree Searching Algorithms: H. Kaindl

8 Tree Searching Algorithms
H. Kaindl
8.1 Introduction
Much of the work on search in artificial intelligence deals with trees. These are
usually defined implicitly by a so-called problem representation, and the process
of searching for a solution of the given problem can be represented by a search
tree (more generally an acyclic graph, because of transpositions). For instance,
in games like chess, the board positions correspond to nodes (or vertices) and the
moves to directed arcs. This chapter reviews and critiques search algorithms for
two-player game trees. The emphasis is on those algorithms which are currently
most useful in computer-chess practice.
8.2 Background
While the game of chess could be solved in principle, this is not possible within
any practical time and space limits. Hence we have to make decisions for a
"good" next move without knowing the game theoretic values of the positions
resulting from the legal moves available from the current position. These
decisions usually have to be based on heuristic estimates, which are normally
represented simply by point values ranging over an interval of integer numbers
(or, for theoretical purposes, real numbers). Given that the game theoretic
values are win, loss and draw, what is the exact meaning of these heuristic
approximations?
Most of the interpretations of heuristic values in the AI literature are rather
vague. Such a value estimates the situation for one player according to its
quality (Winston 1977), worth (Nilsson 1980), merit, strength or probability to
win (pearl 1984). While the last of these interpretations is the most concrete
one, it is also rather problematic (Horacek, Kaindl and Wagner 1987). Palay
(1983) presents an interpretation as an approximation of a delphic value. This
would be supplied by an oracle using the same scale as the evaluation function
that is used to estimate the values heuristically.
Regardless of the interpretation of these point values, their assignment to
the game situations induces a partial ordering. Of course, it is conceptually
questionable to represent everything about the value of a position by a single
number, especially since there is no information about the reliability of the
estimates involved. Here we will also sketch approaches using intervals and
T. A. Marsland et al. (eds.), Computers, Chess, and Cognition

© Springer-Verlag New York Inc. 1990
134 Tree Searching Algorithms
probability distributions as values. However, since point values are most

frequently used, we will primarily emphasize methods based on them.
Given an evaluation function, we could make our move decision at the root
quite simply. All the children nodes (immediate successors) are generated and
evaluated, and one of them leading to the maximal value is chosen.
Unfortunately, experience shows that move decisions based on this method are
usually bad. Hence, the usual paradigm is to select the next move on the basis of
bounded loolcahead search which normally cannot proceed all the way to goal
nodes (known wins, losses, or draws). It is interesting to note that for single
agent problem solving, nearly all work is centered around finding complete
solutions. Although the idea of bounded lookahead search has been occasionally
used for guiding the search for a complete solution (Rosenberg and Kestner
1972), only recently (Korf 1990) pointed out that for single agent problem
solving in a real-time setting, actions must be committed before their ultimate
consequences are known.
However, when the search probes deeper and the leaf nodes are assigned
heuristic values, the question arises what to do with these. How can they be
used appropriately for the decision at the root? Let us assume that one of the
moves to a child position with maximal value is chosen. The question remains,
how are these dynamic values computed from the static values of the
corresponding leaf nodes? Usually this is done according to so-called back-up
rules.
8.2.1 Minimaxing
In practice, the most successful approach for backing up point values is
minimLlXing. It can be considered a generalization of the game theoretic
relationship between accurate values, possibly even for an infinite set of values.
Although these values are normally heuristic, they are used as if they were
accurate.
The key assumption is that in a game between two players, MAX and MIN,
MAX on move always selects the mLlXimum of the values of his children nodes,
whereas MIN takes the minimum. Applying this rule recursively over the entire
game tree, a minimax value can be computed.
Instead of looking at all the values in the tree from one side's point of view,
it is usual to assume that the static evaluationfunctionf(n) represents its value
from the viewpoint of the side on move in the evaluated position. Hence, the
following definition of the back-up rule uses this negamax formulation to
compute the value MM of a tree:
(1) MM (n) := f (n) forleaf node n , and
(2) MM (n) := maxi (-MM (ni» for all children ni of n.
Figure 8.1 shows a simple example of how these values are propagated in a tree.
The path connecting the root with the leaf node whose static value becomes the
minimax value is called the principal variation.
Usually, the primary interest is not the minimax value of the tree itself, but
rather the move to be selected at the root. In accordance with this back-up rule,

8 Tree Searching Algorithms: H. Kaindl

Uploaded by

Copyright:

Available Formats

8 Tree Searching Algorithms: H. Kaindl

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

8 Tree Searching Algorithms: H. Kaindl

Uploaded by

Copyright:

Available Formats

8 Tree Searching Algorithms

T. A. Marsland et al. (eds.), Computers, Chess, and Cognition

probability distributions as values. However, since point values are most

You might also like