Subject: position evaluation

From: [email-masked] (Kevin McCarty)
Date: Fri, 23 Apr 93 13:30:27 PDT

Let me add some to Mark's reply.  He and I have had discussions in the
past about the general strategy of game tree search for games like
Abalone.  I would be interested in provoking a general discussion of
this topic.

Game tree search, aided by alpha-beta pruning, assumes the validity
and relevance of the evaluation function used at the leaves of the
search tree.  The fact that you can look deep into the game tree and
evaluate the strength of positions there gives advantage over evaluating
the strength of the current position only in two cases:

1)  The depth of lookahead allows you to discover a forced win, or avoid
    a fatal blunder (a forced win by your opponent).

2)  The positional strength-- as evaluated by your function--
    of the position at the end of the principal continuation is
    significantly different from that of the current situation.

At one extreme, if we had position evaluation functions that were
sophisticated enough, we wouldn't need to look very far ahead.
In other words, the value of lookahead as in 1) would be subsumed
by the evaluation in 2).  The downside is that sufficiently smart
evaluation functions would be very expensive to compute.

At the other extreme, if we could look far enough ahead in the game
tree, we wouldn't need very sophisticated position evaluation functions.
If you look ahead far enough, the only evaluation function you ever need
is "did someone win yet?"  In other words, being in a strong position is
in the end irrelevant; the only thing that matters is whether you win or
not.  The meaning of 2) is ultimately completely subsumed in 1); the
ultimate position evaluation function returns the result:  "this position
guarantees a win/loss".

So, as a practical matter, searching a game tree always involves a
tradeoff between depth of search you can afford to make and cost of
computing a position evaluation at the leaves.  Cost of computing a
position evaluation is proportional to how realistically the position
evaluation takes account of what's most important for a truly strong
position.

If you dumb down your position evaluation function (or if you're not
sure what it takes to make a smart one), you can afford to search deeper
in the tree.  But if you can't search deep enough to see wins or losses,
significant positional gains detected as in 2) above may be completely
delusional.

Conversely, if you could tell just by looking what makes a position
strong, you wouldn't need to search so deep.

Thus it is interesting to see what elements various people think to
include in position evaluation.  One can differentiate three categories
of elements (in increasing order of computation expense): material,
position (e.g. distance from edge), and configuration.

Question: what elements of configuration (e.g. connectivity, shape)
are signficant for Abalone, and how can they be cheaply computed?

One way to do a scientific investigation of this effect is to look at
how the evaluation of a given position and its possible moves changes as
the depth of search is increased.  An evaluation function is "good" to
the degree to which it can succesfully predict the  result of searching
the game tree further.  It is "bad" or misleading to the extent that
the identification of the principal continuation fluctuates
significantly as the search depth increases.  (Note however that this
may sometimes just be due to the fact that some positions contain
critical possibilities and pitfalls for the two players.)
-- 
Kevin McCarty ([email-masked])