Path: utzoo!utgpu!water!watmath!clyde!cbosgd!ucbvax!husc6!bbn!denbeste
From: denbeste@bbn.COM (Steven Den Beste)
Newsgroups: comp.sys.amiga
Subject: There are no good computer GO players
Message-ID: <6250@cc5.bbn.COM>
Date: 24 Jan 88 04:27:09 GMT
Organization: Bolt Beranek and Newman, Inc., Cambridge, MA
Lines: 43

There does not exist a good computer GO player that I have heard of, on any
machine up to and including a Cray. The reason is that all the approaches which
have been developed over the years for Chess (mostly at CDC to try to win the
Levy bet - which they failed) don't work well for GO.

Briefly, the algorithm consists of two parts: A section which determines all
possible moves for a player in a given board position and a section which gives
a given board position a metric of desirability.

With these two, you trace a tree of the N best moves for me, followed by the M
best moves for my opponent at each of the results of those N moves, followed
by...

These are known as "plies" I think, and once the approach was worked out,
making the computers better consisted of two things: Making the evaluation code
better, and making the computer evaluate more positions per move.

This won't work for GO for two reasons: instead of perhaps 40 possible moves in
an average board position, in GO it is often more than 250 - and any of them
might be the one you want to make. Worse is this: There is no easy metric on
board positions for desirability. In chess you use things like "-3 for ever
major piece in jeopardy of being taken without an equal loss by the other
side", "+5 if the opposing king is in check", "-5 if my king is in check" etc.
(examples pulled from my ear - don't quote me.)

It ain't that easy with GO (as any experienced player can tell you).


Someone here asked about a GO program - I know nothing about specifics, but I'd
be willing to bet much bucks that one of three things are true about it:

1. It plays TERRIBLY.

2. It doesn't play at all but allows two humans to play on the Amiga. (useless
- a board is better)

3. It plays GO-MOKU (also known as "five-in-a-row" a game as different from GO
as checkers is from chess)


-- 
Steven C. Den Beste,   Bolt Beranek & Newman, Cambridge MA
denbeste@bbn.com(ARPA/CSNET/UUCP)    harvard!bbn.com!denbeste(UUCP)