Subject: Re: Tested Peter Tax's program

From: [email-masked] (Gilles Boccon-Gibod)
Date: Tue, 11 May 93 15:30:16 PDT

I've played with Peter Tax's Mac Abalone too, and found it very easy to
use.
My first conclusion are:
It plays well for a simple strategy.
The three strategies are quite alike,
If you don'y have a quadra, you should not use the 3-plies depth, but
this is not a big problem, because the program is not much different
at 1 or 2 plies than at 3.
The major problem in my opinion are that the program is not aware that
a given position can yield the end of the game, so if you already have
pushed 5 of his balls out and offer one of your balls as a sacrifice
(i.e. if it pushes it out, then you can also push on of his), it will
accept it so you will win.
I am not a good player (I have hardly played more than a dozen games
against a human player), though I can beat the program each time. But
may be this is due to the fact that I found a tactic that works all the
times with this program (to concentrate a block in the center of the
board, then begin to push-and-retract until the opponent is too much
spread over the board, then push his balls out).
I've read Peter Tax's sources

I'd very much like to be able to try other programs if some exist. I am
currently writing my own abalone-playing program on a mac (and on unix
too), so that I can test it against other programs or humans.

I've read that there was an MITAbalone, and I would love to try it if
any one could mail it to me (I don't have FTP yet).

Could anyone give some advice on good books on computer-game-playing
strategies and algorithms.
Thanks.

-- Gilles --

---

From: [email-masked] (Ulrich Mayring)
Date: Wed, 12 May 93 12:57:36 MET DST

> 
> Hello Ulrich,
> 
> Glad to read you more or less appreciate my program,
> after all the trouble you went through getting it.
> Thanks for the posting of the short review too.
> 
I do appreciate it very much, my criticism is just to show you some
problems you may not be aware of.

> You did not mention the nice sounds - they took me 2 days to record,
> and they're even more or less useful- they draw your attention when
> the Mac makes a move.

Well, unfortunately the sounds are lost on me, because here is a Terminal-
room, where people want to work, so I can't really turn it up...

> The same. The best strategy of the three is, I think, Terminator III.
> It's sometimes very slow indeed at 3 plies indeed, especially when it's
> in deep trouble - I think this is somehow a consequence of using
> alpha-beta.
> I usually play it at 2 plies, and try to lose no balls at all,
> to make it a real challenge.
> At 2 plies, I think 6-2 is about my average score.
> At 3 plies, I usually win too, but, like you, I have to be careful to
> keep concentrated, and 6-3 or 6-4 is more typical, although I still
> keep getting better in beating my own program.

Hmm... strange, I think Darth Vader at 2 plies is the best. Most definetly
Bill GAtes at 3 can be beaten 6-0, but I also lost against him, when I
wasn't careful. But all this can to some extent be attributed to my own
style of play, which tends to forsake position every once in a while. So
we all seem to agree that your program plays good enough to beat anyone of
us at least sometimes. That's a very good result for a first try, Peter.

However, there's one problem: (In addition to the one, that no end-check
is made). If I place my marbles all on the outermost circle, the computer#
will not make good on this. Instead it moves senselessly about in the center
of the board. Unfortunately that get me nowhere either, so it's a stalemate.

Another thing is that whenever I succeed in controlling the center of the
board, it's a big win everytime, because the program can't really do any-
thing against that. On the other hand if it occupies the center it becomes
very hard for me. So that is an argument for Abalone being a purely positional
game. The problem is that in the beginning of the game very often a stalemate
position can occur, unless I make offensive moves. If I play defensively the
program doesn't attack me, so even a novice should be able to score a draw
against the program everytime. Also, I only played games where the program
was black, on that one occasion where I had black I occupied the center
easily and won the game shortly after.

All this being said, the program still plays amazingly well, unless you treat
it like a computer and make 'stupid' moves to confuse it. And, I think these
experiences will be relatively the same for all programs based mainly on
positional evaluation. If you allowed use of a larger board, I think a 
positional strategy will become worse and worse the larger the board becomes,
because then it will need a real strategy. Is this something you could
implement easily? I think that would be very interesting.

Finally, the last problem is the one of perception. As humans we tend to
'overlook' moves, sometimes we move amazingly stupid and sometimes amazingly
intelligent. An algorithm is more balanced, I think. The thing here is now,
that the board on the screen is a little too small, so I find myself making
more stupid moves than on my 'real' Abalone board. (Of course that may partly
be attributed to 3D vs. 2D. But making the window a bit bigger or even
scalable is another suggestion I find useful.

Good, that's enough for today and I would like to say thank you to Peter for
making this great program available to all of us.

Ulrich

---

From: [email-masked] (Peter Tax)
Date: Thu, 13 May 93 15:45:05 +0200

> of the board. Unfortunately that get me nowhere either, so it's a stalemate.

Yes, that's true. According to the evaluation function, the computer is
in a very good position, and the only improvement it is able to see, is
to push you even closer to or over the edge. To see the moves that would
actually push marbles off, more plies would be needed.
The funny thing is, unexpirienced players often end up in this utterly
hopeless position (believe me; I tested the program on some friends):
they get kicked out of the center, get pushed to the outer circles,
and can save most of their marbles only by leaving them there.
The frustrating thing about this is, whenever you try to 'regroup',
you move marbles inward, often getting them in touch with the computer's
marbles, and the computer, now 'seeing' your marbles, pushes them out
again, so whether it's initially  a stalemate position by your own
choise or not, in the end, the computer chooses to keep it that way.

> thing against that. 

Also true. If you beat a positional strategy on its own terms, it's
completely defeated. But this must be true for strategies in general.

> If you allowed use of a larger board, I think a positional strategy
> will become worse and worse the larger the board becomes,
> because then it will need a real strategy.

Maybe, maybe not. My intuition tells me you're probably right, but
it also tells me the world is flat. The added complexity may make it
more difficult not to oversee the obviously good (counter)moves.

> Is this something you could

Not easily, because I did not anticipate this, and there are some hard-
wired tables in the program. On the other hand, it looks like a useful
and interesting generalisation, so I may take a closer look at it.

> Finally, the last problem is the one of perception. As humans we tend
> to 'overlook' moves, sometimes we move amazingly stupid and sometimes
> amazingly intelligent. An algorithm is more balanced, I think.

I think so too; what this appears to mean to me is, in computer
terms, humans use a different, 'risky' pruning strategy.
If I'd have to try to program a 'humanoid' playing strategy,
I think I should start with a positional evaluation function similar
to the one I have now, and concentrate on the pruning mechanism.
It's completely normal for a human player to think 8 plies deep,
and it's also completely normal to overlook an obviously good move at
only 0, 1 or 2 plies deep.
Together, this suggests some very rigorous pruning.
Thinking about it, doesn't 'having a plan' (which is what we usually
claim to do) just mean considering ONLY the moves that seem to
contribute to the plan in the near future, discarding all others?
Something like 'This doesn't look good; let's not think about it'
Anyhow, I received the Game Tree Search paper yesterday. I haven't read
it yet (it looked a bit too difficult to read after a day's work),
but I'm curious if there is some nice pruning mechanism described in
it that's more advanced than pruning out what you *know* is wrong
(alpha-beta pruning).

> The thing here is now, that the board on the screen is a little too
> small, so I find myself making more stupid moves than on my 'real'
> Abalone board. (Of course that may partly be attributed to 3D vs. 2D
> But making the window a bit bigger or even scalable is another
> suggestion I find useful.

Click the size box in the upper right corner of the window to
get the bigger window size. The small size is the default size; I made
the default size that small so people with a compact Mac (plus, SE)
can use the program 'as is'. The size you last selected is saved in the
preferences file. The bigger size looks better on a 640*480 monitor.

---
[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.
? _