Subject: I still don't like positional values...

From: [email-masked] (Ulrich Mayring)
Date: Thu, 29 Apr 93 23:46:15 MET DST

Well,

Leaving aside for a moment the fact that our program will right now not win a
single game against a positional evaluator, I still don't like the idea of
doing positional evaluation solely dependent on who is in the center of the
board. I think with the broad trees that abalone generates a minimax strategy
is bound to fail against a good human player, if it is based on positional
value alone.
An improvement would e.g. be to compute 'clusters' that are marginally stronger
in the center of the board than in some place between the center and the edges
and lots stronger than any not-clustered position, where the marbles don't
connect to each other well, even if some of them occupy center positions. We
did implement this cluster strategy and it appears to do, well say 20% better
than positional value based on the center of the board. But it is not enough
to beat a good human player.
Also, to get a little philosophical here, any strategy based on minimax is
not a strategy, but an accumulation of tactics. We found that if we present
the automaton with a set of moves (as a minimax does) it sometimes delays
good moves, because they are of equal worth when done later. Of course the
opponent almost always foils the scheme then, if given the chance. Also,
a set (or if you like set of sequences) of moves is a somehow arbitrary
collection of do-this do-thats, once the evaluator becomes too intelligent.
The program does not play Abalone, it merely computes it.
Of course, it is now our turn to come up with a more intelligent evaluation
strategy and so far no-one has seen or played against our prog. I can only
say that my partner got a little frustrated with the minimax way of doing
things stupidly, but fast. Is there a better way? I'll keep you informed...

Uli.

---

From: [email-masked] (Michael P. Frank)
Date: Fri, 30 Apr 93 12:36:21 EDT

Ulrich has a very good point, that minimax (and related current
techniques) are a very poor and limited way of doing game-playing;
very different from the way humans play, showing no long-term strategy
at all.  AI people have tried, and mostly failed, to make progress
along this front.

In my Master's research, I am trying to work out general algorithms
for working with abstract, long-term goals.  One application of this
is to improve the state-of-the-art in game playing by showing how to
write programs that can do real strategy, in a top-down way, working
from high-level goals to low-level tactics and moves.

If I have any success at this, I'll let you folks know.

-Mike