[comp.ai] Computer Go Challenge

landman%hanami@Sun.COM (Howard A. Landman) (04/21/89)

In article <3724@sdsu.UUCP> wintermute@tr.wrld (Wintermute) writes:
>Now that Taiwan's Acer Group and the Ing Chang-Ki Wei-Ch'i Educational
>Foundation have offered a prize of 40 million Taiwanese dollars
>(about $1.3 million US) to anyone who can by the year 2000 program a
>version of the game that can beat a professional Go player, are there
>any takers out there?

Where have you been?  Why do you think Bruce Wilcox, David Fotland, Lynn Beus,
and I were in Taipei last November?  (Not to mention a host of Europeans and
Japanese and others).

>Looks like it's time to start using some AI techniques.)  :-D

No, that's been tried already (Wilcox, Nemesis).  It seems to be being left
in the dust by other approaches.  My territory estimator (Poka) is nearly
as strong as Wilcox's entire program, for example, and neither of them have
a prayer against the better programs like Codan.  These were around 12 kyu
last November, and the general expectation is that November 1989 will see
programs around 9 to 10 kyu battling it out for the top prize.

Current programs are running on <2 MIP machines and take about an hour per
game.  In 2000 they'll be running on 100 MIP machines, and have 7 hours or
more per game.  So we should be aiming at about 4 MIP-hours per move, that is,
an algorithm that can productively use 2 hours of Mac II time (or 20 minutes
of SparcStation 1 time) average per move.  Expanding the depth and width of
tactical search is one way to use more time, but I don't think it will give
the maximal improvement.  Pro class programs will have to do EVERYTHING well;
openings, tactics, life & death, positional judgement, and endgame.

On the other hand, some studies of my pro game database indicate that pros
routinely make hundreds of points of errors per game; so the possibility
that a program might someday beat them is quite real.  And the exploding
development of a solid mathematical theory of the endgame, based on Conway
and Berlekamp's work, promises programs that play rapid and accurate yose.
It's a very exciting time in computer Go this year.

	Howard A. Landman
	landman@hanami.sun.com

vu0112@bingvaxu.cc.binghamton.edu (Cliff Joslyn) (04/21/89)

In article <100234@sun.Eng.Sun.COM> landman@sun.UUCP (Howard A. Landman) writes:
>On the other hand, some studies of my pro game database indicate that pros
>routinely make hundreds of points of errors per game; so the possibility
>that a program might someday beat them is quite real.  And the exploding
>development of a solid mathematical theory of the endgame, based on Conway
>and Berlekamp's work, promises programs that play rapid and accurate yose.

Fascinating, I thought as much!  Could you explicate on the above
reference, and any theory you have about how to measure sente, point
value vs. threat value, ko involvement, etc.  In my games I try to be
sensitive to these issues, but usually end up just confusing myself.

-- 
O---------------------------------------------------------------------->
| Cliff Joslyn, Cybernetician at Large
| Systems Science, SUNY Binghamton, vu0112@bingvaxu.cc.binghamton.edu
V All the world is biscuit shaped. . .

jf@cci632.UUCP (Jens Fiederer) (04/22/89)

In article <100234@sun.Eng.Sun.COM> landman@sun.UUCP (Howard A. Landman) writes:
>On the other hand, some studies of my pro game database indicate that pros
>routinely make hundreds of points of errors per game; so the possibility
>that a program might someday beat them is quite real.  And the exploding
>development of a solid mathematical theory of the endgame, based on Conway
>and Berlekamp's work, promises programs that play rapid and accurate yose.
>It's a very exciting time in computer Go this year.
>
>	Howard A. Landman
>	landman@hanami.sun.com

Apparently, at least one pro disagrees: Kato Masao has stated (boasted?)
that God (to avoid religious disagreements here, assume that hypothetical
entity/process that makes no mistakes at Go could give him ONE handicap
stone  That would put the figure for Kato at about 10 points of errors
per game.  Is Kato lying, or are the other pros really that much worse?

Jens

landman%hanami@Sun.COM (Howard A. Landman) (04/22/89)

>In article <100234@sun.Eng.Sun.COM> landman@sun.UUCP (Howard A. Landman) writes:
>>On the other hand, some studies of my pro game database indicate that pros
>>routinely make hundreds of points of errors per game; so the possibility
>>that a program might someday beat them is quite real.  And the exploding
>>development of a solid mathematical theory of the endgame, based on Conway
>>and Berlekamp's work, promises programs that play rapid and accurate yose.

In article <2089@bingvaxu.cc.binghamton.edu> vu0112@bingvaxu.cc.binghamton.edu.cc.binghamton.edu (Cliff Joslyn) writes:
>Fascinating, I thought as much!  Could you explicate on the above
>reference, and any theory you have about how to measure sente, point
>value vs. threat value, ko involvement, etc.

None of the above work is published.  I've been in email correspondence with
Berlekamp and a couple of other people, and I spent 6 hours at Berlekamp's
house one evening.  He's making progress at a tremendous rate - most of the
results are less than 3 months old.  Before talking to him, I was able to
apply Conway's theory to find the temperature of a move.  This is useful
because the simple greedy algorithm of playing the move with the highest
temperature can be proved to be asymptotically correct; that is, if you have
multiple copies of the game, and either player is allowed to play in any copy,
then the highest temperature move is best in the limit of a large number of
copies of the game.  However, on a single board, there can be situations
where there is a large gap in temperatures where the correct strategy
is to play so as to get the last large move.  For example, suppose
there are three large moves left: 100 points in gote (A, temperature 50),
49 points in reverse sente (B, temperature 49), and 96 points in gote
(C, temperature 48), plus a bunch of small moves (all temp <= 10).  Then
the correct strategy is not to grab the highest temperature move, because
that leads to you getting A, but your opponent grabs B in sente and then
takes C.  Instead, you should take B, your opponent takes A, and you take C.
This way you get 2 out of 3 big points instead of 1 out of 3.

This is what professionals mean when they talk about getting the last big
point in the opening.  And they do this kind of analysis all the time in
the endgame.

Note that the addition of another large gote move, say 94 points in gote
(D, temperature 47), means that A might be the best move again.  Please
work this out for yourself

My application of the theory gives a precise mathematical (and graphical!)
meaning to "sente", "gote", "double sente", and even vague concepts like
exactly when something "becomes" sente or double sente.  But the explanation
is rather complicated and requires an understanding of the basic theory in
On Numbers And Games or Winning Ways v.1.  I hope to publish something
eventually, but right now it's all I can do to keep up with Berlekamp's
progress, and try to look at how this applies in real games.

Berlekamp has gone beyond mere temperature, to expressing games as
"overheated" simpler games, and playing in the simpler games.  This
allows him to distinguish (for example) some temperature 1 moves as
being infinitesimally better than other temperature 1 moves.  He can
construct problems in which this difference is the margin between
winning and losing.  I think even pro 9 dans would have trouble solving
these problems.

	Howard A. Landman
	landman@hanami.sun.com

landman%hanami@Sun.COM (Howard A. Landman) (04/23/89)

In article <28044@cci632.UUCP> jf@ccird3.UUCP (Jens Fiederer) writes:
>In article <100234@sun.Eng.Sun.COM> landman@sun.UUCP (Howard A. Landman) writes:
>>On the other hand, some studies of my pro game database indicate that pros
>>routinely make hundreds of points of errors per game; so the possibility
>>that a program might someday beat them is quite real.

>Apparently, at least one pro disagrees: Kato Masao has stated (boasted?)
>that God (to avoid religious disagreements here, assume that hypothetical
>entity/process that makes no mistakes at Go could give him ONE handicap
>stone  That would put the figure for Kato at about 10 points of errors
>per game.  Is Kato lying, or are the other pros really that much worse?

Obviously, I think Kato is either lying or deluded.  I vaguely recall one
game (I think between Sakata and Shuko) where there was a big running fight
worth about 75 points.  Post-game analysis showed that both players had
made blunders that SHOULD, with correct play, have given the battle to the
other player.  I think there were about 6 such errors in the space of 20
moves or so.  That's 225 points of errors per player.  Not counting all
the other moves in the game.

More typically, it's easy to imagine that many moves in the opening could
be small errors.  At a couple of points per move, it doesn't take very
long to exceed 10 points.  I strongly doubt that Kato could get 50 moves
into a game without making 20 points of errors.

	Howard A. Landman
	landman@hanami.sun.com

jansteen@cwi.nl (Jan van der Steen) (04/27/89)

In the Dutch Go magazine 16-6 (august 1979) an article was
published which amongst other dealing with the classification
of Go players. The author of this article is Prof. Dr. K. Heine
(Wilhelmshaven, Germany).

= Quote start =

In the next graph, different results of Go games is measured against
the strength of the players involved:


    spread in results
            |
          50|                                             .
            |                                        .
          40|                                   .
            |                              .     *
          30|                         *
            |                    .  *
          20|               *
            |          *  *
          10|     .*   
            |. *
       _.___|_______________________________ strength (Japanese system)
            |     |     |     |     |     |
            0     5D    1k    5k    10k   15k


        Some conclusions:

        - Perfect Go is played by someone who is able to give a
          9 Dan professional a four stone handicap.
        - The average size of the result is proportional to the
          quality of the game.
        - ...

= Quote end =


Interesting, isn't it?


-- 
	-=-=-=-=-=-=-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-
   	 Jan van der Steen,		CWI the Netherlands
   	 jansteen@cwi.nl	  (or uunet!mcvax!jansteen)
	-=-=-=-=-=-=-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-