Subject: Re: alpha-beta

From: [email-masked] (Peter Tax)
Date: Thu, 29 Apr 93 12:25:53 +0200

Hello Michael,

First, a request, and then a statement that might lead to some
interesting discussion.

>You can FTP it at external.nj.nec.com, file /pub/eric/game.ps.Z.

Request: Would it be possible to mail me a text-only copy?
I don't think I have anything that recognizes .ps.Z format on my Mac,
and I'd be very interested to see what this new tree search strategy
would mean for Abalone.

 From what I read in this newsgroup, there are basically two problems
in implementing a good Abalone-playing program using a statical board
evaluator and an alpha-beta search strategy, namely:

1) Statical board evaluators play too defensively;
2) Alpha-beta does not allow you to think deep enough.

Since I believe I have an elegant solution for 1),
I'd be interested in a solution for 2) as well.

About problem 1):
In the University of Waterloo contest, I tried to get a discussion
started about the following statemement (which didn't work, so I'll
try again here):

Statement: The risk for a single ball of being pushed off in a certain
direction decreases exponentially with its distance from the edge
in that direction.

If this statement is true, which I'll try to make plausible below, this
gives a nice basis to build a positional evaluation function upon.
So, why would this be true? Read on!

My first idea was to start with a very simple evaluation function: 
the closer a ball is to the edge, the worse. This means simply 
giving each of the 61 fields on the board a positional value 
determined by the distance (minimal or average or whatever) from 
the edge. Since you can think of a ball pushed off the board as 
having a distance of zero from the edge, it's not difficult to 
understand this should more or less work. With this approach, the 
evaluation of a  board is very simple. Sum all the values of the 
fields you have a ball on, substract all the values of the fields 
your opponent has a ball on, and thatUs it. 
Now take care: I did NOT tell you HOW to derive a positional value 
 from a distance. You may have assumed a simple lineair relation 
would do fine, and of course this is what I first trie too. This 
basic strategy more or less works: when given weak or random 
counterplay, this strategy groups all its balls in the centre of 
the board, and then effectively does nothing. It just tries to 
keep or regain the centre, and then tries to stay there. Quite 
boaring.
I soon realised that to make the strategy play more agressively, 
it should not just be rewarding to move towards the center, but 
also to push your opponent away from the center, even if this 
means moving away from the center yourself! Now it may appear to 
be impossible to assign positional values to the individual fields 
that make this behaviour appear 'automatically', but the nice 
thing is, itUs not. It does, however, pose some interesting 
constraints to the positional values. (Now IUm getting to 
my statement.)
In my program, I decided to assign a ball an 'arbitrary' value of 
1024, and give each field a number of 'malus points' (the opposite 
of bonus points). A ball actually on the board always has a value 
of 1024 - the malus points for its position at a minimum distance 
of n from the edge, called M(n); only a hypothetical ball at an 
infinite distance from the edge would really have the theoretical 
maximum value of 1024. Now how should the malus points be assigned 
to make the strategy both agressive as well as oriented towards the 
center?
Consider this example: you have two balls at D4 and C3 (distance 
 from the edge: 4 and 3) lined up with an enemy ball at B2 
(distance from the edge: 2). Suppose you want to have a strategy 
that 'likes' to push the enemy ball outwards, what would this mean 
for the 'malus points' M(4), M(3) and M(2) for the fields? 
Assuming the strategy simply adds all your malus points, 
substracts all your opponents malus points, and tries to minimize 
the result the following should be true:
M(4) + M(3) - M(2) > M(3) + M(2) - M(1) 
(M(n) ::= malus points for a field at a min. distance n from the 
edge)
Of course, the strategy would stink if, given the opportunity, it 
would't push off the ball next move, so also
M(3) + M(2) - M(1) > M(2) + M(1) - M(0) 
and in general:
M(n+3) + M(n+2) - M(n+1) > M(n+2) + M(n+1) - M(n) <=>
M(n+3) > 2 * M(n+1) - M(n) <=>
M(n) > 2 * M(n+1) - M(n+3),
making the equation M(n) = 2 * M(n+1) - M(n+3) interesting. I'm 
not a mathematician, so you won't get an exact solution from me, 
but if you neglect the small  -M(n+3) term, and solve the simpler
M(n) = 2 * M(n+1),
a solution is
M(n) = C * 2**(-n).
Anyhow, you can see the malus points should decrease very rapidly 
with increasing n. In my program, I choose 2**(10-n), which is 
easy to implement in C and would make a ball pushed off really be 
gone since 1024 - 2**(10-0) is 0 (so far for arbitrary values).
I'm not suggesting every good positional strategy should 
necessarily be this 'agressive'; for example, you could consider a 
strategy that does not favour pushing its opponent away from the 
center in a 2-to-1 position, but does do so in a 3-to-2 position, 
in which case you could do with a slightly slower but still 
faster-than-lineair decreasing M(n). But I do believe that, in 
general, an (almost) exponentially decreasing malus points 
function is required to make a positional strategy sufficiently 
bloodthirsty.

Sounds convincing, doesn't it?
Combined with some tree search algorithm superior to Alpha-Beta,
this may play quite strong, I think.
--------
---
[email-masked] (Peter Tax)

? LOOK
You are in a brighly lit room. There is a screen device in front of you.
North and East are doors. There is a manager behind you.
? N
The door is locked.
? _

---

From: [email-masked] (Ulrich Mayring)
Date: Mon, 3 May 93 13:22:21 MET DST

> and I'd be very interested to see what this new tree search strategy

==========================================================================
Please send it to [email-masked] too. That's me. I have managed to
get rid of the .Z (hint: use uncompress FILE), but the .ps is tough, since
I don't have a Postscript printer to my disposition.
==========================================================================

> 1) Statical board evaluators play too defensively;

Only when doing a certain kind of board analysis, in our case a center-based
positional evaluation. Other analyses are imaginable where the clustering
of marbles is only one parameter of several. Say, you have three more para-
meters, namely No. of marbles of opponent and myself, No. of secure positions
(i.e. three marbles in a row) and No. of marbles at the very edge of the
board. The last one is completely unpositional, of course, but since it is
only one of four parameters, it evens out. Now, with these four parameters
you definitely have an automaton, which doesn't play boring at all. I can
say that, because we tried it. The problem with this approach is that the
suggested parameters above are too arbitrarily chosen. They do not work so
well together as to promote a real strategy. But this is IMHO only a problem
of selecting the right parameters and maybe making this selection dependent
on the game situation.

> 2) Alpha-beta does not allow you to think deep enough.
Please clarify this one. I always thought that Alpha-Beta is an optimization
of Minimax, so it should allow you to search deeper than Minimax alone.

> So, why would this be true? Read on!

[I did and found it interesting. Then you conclude:]

> this may play quite strong, I think.

It appears to be pretty good for a positional evaluator, because it is not
center-bound. But tell me one more thing, which I didn't quite grasp:
Does every board position have the base value of 1024, or do the center ones
have slightly more? It may even be feasible to give them something like
1100 or so, what do you think?

Ulrich

---

From: [email-masked] (Michael P. Frank)
Date: Mon, 3 May 93 14:06:33 EDT

> and I'd be very interested to see what this new tree search strategy

Unfortunately, I don't have a plain text copy.  If you really want to
read the paper and you don't have a Postscript printer or previewer,
you might try contacting the authors: Eric B. Baum
<[email-masked]> and Warren D. Smith
<[email-masked]>, and they would probably give you their TeX
source, which would be more readable than the postscript.

Bear in mind that the paper is pretty technical.  I'll go ahead and
type in the abstract, and you can determine from that whether you want
to go to more trouble to get it:

Title: Best Play for Imperfect Players and Game Tree Search
Authors: Eric B. Baum and Warren D. Smith
DRAFT April 23, 1993

Abstract:
	We propose a new approach to game tree search. We train up an
evaluation function which returns, rather than a single number
estimating the `value' of a position, a probability distribution
P_L(x).  P_L(x) is the probability that if we expanded leaf L to some
depth, the backed up value of leaf L would then be found to be x.  We
describe how to propagate these distributions efficiently up the tree
so that at any node n we compute without approximation the probability
node n's negamax value is x given that a value is assigned to each
leaf from its distribution.  After we are done expanding the tree, the
best move is the child of the root whose distribution has highest
mean.  Note that we take means at the child of the root *after*
propagating, whereas the normal (Shannon) approach takes the mean at
the leaves before propagating, which throws away information.
	Now we model the expansion of a leaf as selection of one value
from its distribution.  The total utility of all possible expansion is
then by definition the ensemble sum over those possible leaf
configurations for which the current favorite move is inferior to some
alternate move, weighted by the probability of the leaf configuration
and the amount the current favorite move is inferior.  We propose as
the natural measure of the expansion importance of leaf L, the
expected absolute change in this utility when we expand leaf L.  We
support this proposal with several arguments including an
approximation theorem valid in the limit that one expands until the
remaining utility of expansion becomes small.
	In summary, we gather distributions at the leaves, propagate
exactly all this information to the root, and incrementally grow a
tree expanding approximately the most interesting leaf at each step.
Under reasonable conditions, we accomplish all of this in time O(N),
where N is the number of leaves in the tree when we are done
expanding.  That is, we pay only a small constant factor overhead for
all of our bookkeeping.

-Mike