Re: The progress of computer Go

[Jeremy Thorpe <jthorpe@xxxxxxxxxxxx>]

i find this kind of (meta) discussion about go playing programs to be
extremely interesting, so let me advance my own hypothesis about the
future of go playing programs:  first of all, i believe that this kind of
program that Dan is talking about will become harder and harder to improve
even though it is the easiest way to implement a reasonably strong agent.
remember that ManyFaces is around 14k on igs, and has been around for
years. my hypothesis is that the champion go playing program in a few
years will implement a genetic algorithm, and will acquire skill through
playing with versions of itself.  the hard code will be something like
10,000 lines of C++ code and have only a handful of top level procedures,
although the soft code (code that evolves) may easily be as big as those
programs Dan is talking about.

the challenge, of course, is to write an efficient "language" for the
program to use, and to write efficient training algorighms so that you get
meaningful progress in, say, a day of training.  the language concept
deserves elaboration.  for example, you might have an agent be simply a
collection of rules: each rule has a clause and a recommendation.  for
example: "if there is a corner without stones around, play at a 3-4 point"
or "if there are many empty spaces nearby, don't play right on the edge"
there need be only a few primitive concepts in the language, such as
"own stone," "enemy stone," and "empty space," and the board size
(input and output domains).  bigger concepts such as "liberty," "group,"
"eye," "half-eye," "dead," "alive," "cut," "connected," "weak," "strong"
could be defined in the soft code and reused many times by other rules in
the soft code, so that you could get rules like "if a group is weak, try
to make two eyes."  interestingly, there might be different ways of
defining an eye--primitive definitions that might not be right every time
to piecemeal definitions for each case--corner, side, middle.

so the programmer's job is to find a suitable language, mutation scheme,
and selection scheme.  the selection scheme also might include space and
time performance in order to encourage small and efficient algorithms.
the downside, or perhaps beauty of this scheme is that the code running in
the resulting agent will be essentially unreadable by human beings, just
as the brains of other animals are essentially unreadable.  

well, thanx for reading.  cheers!

-jeremy

Jeremy Thorpe                         "all living organisms require 
Mechanical Engineering student @           information to function"
University of California, Riverside    

On Mon, 5 Oct 1998 Compgo123@xxxxxxxxxxxxxxxxx wrote:

> I have been away from programming Go for about a year. Recently I down loaded
> and read through the most recent message archive. My impression is that the
> discussions in this mailing list is now more toward the implementing specific
> techniques in the program compared to the discussion of basic techniques
> sometime ago. There are more and stronger Go programs in both the commercial
> market and Computer Go tournaments. I think it's very important to evaluate
> the real ranking of the most strong Go programs. I went through the game
> between Goemate and Sauri Ishihara. However, I have to say that the game is
> played at a level between 10 to 13 kyu on IGS. Of course, one has to give
> credit to Goemate's ability in both fighting and positional jugdement. In more
> than one occasions in the game, it successfully used attacks to defuse its
> weaknesses at the proper time. I also went through the first Silver Igo's game
> posted by David Fortland. This game seems represent the mentality of present
> day strong Go programs. That is to choose stable josekis, establish a base,
> grab territory, then extend from the base. The game may be dull. But who
> cares? As long as can win the tournament. I'm sure, as Go programs evolve,
> this situation will change.
> 
> At present time, the only feasible way to write a strong Go program is to
> incorporate Go knowledge into the program. Unless there are breakthroughs in
> mathematical theories or in computer hardwares, this seems to be the way to
> go. Then the question is how high can Go programs reach in Go playing levels
> with this approach? I think it's possible to reach professional 1 dan level
> with this approach in not too distant future. At present time, I think it's a
> realistic goal is to reach higher than 5 kyu  levels on IGS. I think such a
> program will consists of about 40,000 lines of C program with about 300
> subroutines. Plus many MBs (100 MB or less?) of data files. Any program with
> content less than this is hopeless in reaching above playing levels. This will
> give many Go program starters an idea where he or she is standing at. Then
> another question is how much has to be the increase in  Go program content to
> reach professional 1 dan level? I think the program content has to increase at
> least 30% to 50% from above level to reach professional 1 dan level.
> 
> 
> Dan Liu
>