Subject: Re: subscribe

From: [email-masked] (Peter Tax)
Date: Fri, 16 Apr 93 15:32:04 +0200

> A friend of mine who does not have Internet access has programmed
> a game playing program using alpha-beta pruning of the game tree
> and is interested in contacting others who have done similar things.

Hello Kevin,

I made an Abalone-playing program for the Macintosh myself,
and I use alpha-beta pruning as well.
I started using a minimax strategy (same without pruning),
but found out it is hardly possible to go three plies deep this way.
Several people (among them Ed Dengler, also in this list) pointed out
I should use alpha-beta pruning instead, and this really helped.
Using a simple (but fast) board evaluation function, the program can
go three plies deep and still perform acceptably on a Mac.
I don't know exactly what your friend wants to know or see;
if it's source code, my program as a whole is very Mac-specific,
but the strategy part of it is more or less plain C.
But since your friend already made a program himself, he is most likely
more interested in a general description of some possible strategies,
so he can incorporate them in his program.
Ed Dengler recently organised a contest for Abalone-playing programs,
and there were (I think) 5 entries other than mine, so it should be
possible to get some general ideas for strategies via him.
(Ed, if you read this, I did not receive the descriptions of the other
 programs, so I don't know if you posted them.
 If you did, [email-masked] would be interested in them, and so would I)

In my program, I implemented a few very similar strategies.
The strategies are all based on positional value,
sometimes combined with connectivity.
A reasonably strong, but still very simple board evaluation function is:

board_value = 0
for all fields, do:
    if the current player has a ball on it
						 	board_value += 1024
        board_value -= positional_value (field)
        for all six direct neighbours do
            if this player also has a ball on this neighbour field
                board_value += 32
    else if a different player has a ball on it:
        same computation, but with the signs reversed
return board_value

The interesting thing here is obviously the positional value assigned
to the field. For this, I use the following function
(the values should be stored in a table for efficiency, of course):

postional_value (field)
pos_value = 0
in all six directions do
    dist = distance from the edge in this direction
    pos_value += 1 << (10 - dist)
return pos_value / 6

You can use many variations on the positional value/connectivity theme,
of course, but this is a good starter.
Alternative, but definately weaker strategies, I already tried are:
- use the minimal distance from the edge in postional_value instead of
  the weighted average
- don't use connectivity at all
- don't use positional value at all
- use a lineair relation between positional value and edge-distance

Improvements are possible by using a more subtle connectivity
measure (field/direction-dependant). I have one strategy that is
slightly better than the simple one described here.

I'd be interested to hear from your friend; if he comes up with some
nice ideas, I'd like to hear abour them, and maybe add them as new
strategies to my program (if he doesn't mind, of course).
Also, I'd be interested in completely different approaches.

By the way, if your friend has (access to a) Mac, you can download my
program from the most important Mac archives (mac.archive.umich.edu,
sumex-aim.stanford.edu) or mirroring sites.

Peter Tax ([email-masked], [email-masked])
---
[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] (Kevin McCarty)
Date: Fri, 23 Apr 93 13:24:04 PDT

In reply to Peter Tax, my friend Mark Perkins replies:

Hello Peter,

I am glad to hear from another Abalone programmer.  I am also anxious to
try out your board evaluation function in comparison to my (simpler)
function.

The board evaluation function which I am currently using is even simpler
than yours in that it does not consider connectivity at all.  The
position values I use are:

                  10    12    15    12    10
               12    40    45    45    40    12
            15    45    60    65    60    45    15
         12    45    65    80    80    65    45    12
      10    40    60    80   100    80    60    40    10
              etc.

board_value = 0
for all fields, do:
    if the current player has a ball on it
        board_value += 200 + positional_value (field)
    else if a different player has a ball on it:
        same computation, but with the signs reversed
return (board_value - 2800);

This seems to give reasonable behavior (at least against my meager
abilities), although it can be overly defensive at times. I have
never played my program against another program, but I have played
against it quite a bit myself.

Recently, I set it up my program so that it would take as input an
actual game and provide as output (1) the minimax value of the actual
player's move, (2) the minimax value of the computer's best move, and
(3), the computer's best move.  I have then been running this on the
games recorded as part of the "Waterloo Arbitrary Game Competition".  I
can then look at the results to see, for example, how much other
programs agree with mine, or in what kind of situations there is strong
disagreement.  Looking down 5 levels, it takes an average of about 1
minute per move per player to generate the output I described above (on
a Dell 486P/50 PC running DOS).

In the not-to-distant future, I hope to implement your board evaluation
function in a version of my program so I can try it out against mine. If
and when I complete that task, I'll let you know how it turns out.

Mark Perkins
-- 
Kevin McCarty ([email-masked])

---

From: [email-masked]
Date: Mon, 26 Apr 93 11:20:56 +0200

>abilities), although it can be overly defensive at times. I have

I think that for game trees the size of abalone ones an evaluation
function based on more information should be used. The fact that (some)
abalone programs play overly defensive is in my opinion due to a game
design flaw; I should not be possible for a player to be able to block
all progress. Although I have never seen a proof of this assumption it
still looks intuitively true (no good reason, I know).

I think that simple AlphaBeta is not ideal for abalone due to the large
branching factor of the game-trees. The MIT program for example won
easily with conspiracy number search against an earlier version of
compalone although it seemed to have the a worse static evaluation (both
using AlphaBeta, my program won). I therefore think that real success in
Abalone playing progs involves some algorithm ``research''.

Cheers
	- ant

---

From: [email-masked] (Michael P. Frank)
Date: Mon, 26 Apr 93 13:33:17 EDT

> Abalone playing progs involves some algorithm ``research''.

Speaking of advanced search strategies, there is a very interesting
paper by two guys at NEC that describes a new algorithm for game-tree
search.  It uses probability distributions instead of single numbers
to evaluate nodes, and it expands the tree in those places that have
the highest expected utility.  It's very elegant.

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

> 	- ant

   , ,                       __               [email-masked]
  /|/| .  _ |_   _   _  |   |_  _  _  ,_  |,  Clinical Decision-Making Group
 / | | | (_ | | (_| (-' |   |  |  (_| | | |\  MIT Lab for Computer Science

545 Technology Sq. rm. 421, Cambridge, MA 02139. (617) 253-2351 (fax -5060)