Re: [gnugo-devel] address@hidden: Re: GNU go and Artificial Intelligence?]

[David G Doshay]

On Sep 29, 2004, at 5:33 AM, Arend Bayer wrote:

> The research group of Prof. Althoefer in Jena, Germany,
> has made a couple of experiments (in go and chess) with what they call
> "Dreihirn". A human go player is allowed to choose between the two  
> moves
> suggested by two go programs. ... when
> doing this experiment with only one program, and the human being  
> allowed
> to choose between the two top moves, it works much worse. The reason is
> that the two alternatives are too similar in nature; so more generally
> when preparing the alternatives, the computer engine has to make sure
> that the alternatives are truly different.

Ole,

I direct a small research effort at UC Santa Cruz. My primary interest  
is Physics,
but as a preliminary step in my research we are playing Go. My interest  
is in
multiple-length-scale phenomena in general, and in Physics I focus on  
the
Renormalization Group theory of magnetic phase transitions.

        http://currents.ucsc.edu/04-05/07-26/cluster.html

Our program, which is called SlugGo because the banana slug is the  
mascot of
UCSC and because the program runs so slowly even on a cluster of new  
fast
CPUs, is an extension of GNU Go.

From Paul Pogonyshev's description of GNU Go's methods for making  
decisions
you can tell that GNU Go works on the problem at several levels. SlugGo  
works,
to the extent possible, at the larger scale of the whole board, using  
GNU Go as a
move generator. Paul also mentions move generators.

SlugGo uses a method something like the research Arend mentions above,  
except
that GNU Go is our only move generator. However, just as GNU Go does in  
its
internal move evaluations, SlugGo asks GNU Go to generate moves from two
different perspectives: one for our move now (US) and one from the  
perspective of
the opponent, that is to say what moves it would find  interesting if  
we were to pass
on this move and allow them to play two moves in a row (THEM).

As a side note, from the very beginning of our project we developed our  
basic
infrastructure with an eye towards using as wide a variety of move  
generators
and evaluators as we can obtain or have the time to develop. Our  
project is still
quite new so we have only used GNU Go so far. But we could integrate  
move
generators or evaluators using completely different algorithms or  
methods
(neural nets, genetic algorithms, intelligent agents ... whatever).

Unlike the research Arend mentions above, SlugGo does not restrict  
itself to the
single top move from each perspective. SlugGo inspects GNU Go's  
internal data
structures to extract a number of top moves for US and THEM, and then  
culls from
those lists a shorter set of candidate moves for further analysis and  
evaluation,
noting in particular the moves in the US list that are in or very near  
moves in the
THEM list. From this shorter list of candidate moves SlugGo does whole  
board
lookahead, using repeated calls to GNU Go to generate the successive  
board
positions from each candidate move. While branching at each deeper  
level in this
whole board lookahead is the obvious thing to do, we have found a  
surprising
degree of success in doing deep unbranched lookahead (this point is a  
possible
subject for further research). At the end of the lookahead sequence we  
use two
GNU Go evaluation functions, one for influence and another for  
territory with
influence heavily weighted towards the beginning of the game and  
territory
heavily weighted towards the end, to add  to GNU Go's value for the  
candidate
moves. Finally, we select the move with the highest total value.

A set of diagrams describing the process can be found at:

http://cowboy.directgames.net:81/research/SlugGo/documentation/sluggo- 
system_overview.pdf

From my perspective the important point is that SlugGo simply adds to  
GNU Go
one more layer in a hierarchy of levels of evaluation, each of which  
uses lower
levels for move generation and evaluation.

Of particular interest to me is that even though it would seem simpler  
to treat GNU
Go as a "black box" move generator, to properly implement the  
algorithms we have
to reach down into GNU Go to get access to algorithms which work at   
smaller
scales (neither my explanation above or the system-overview slides give  
specific
details on this point; this work is still in progress). It is this  
interaction between the
length scales of Go that makes it a research project that grabs my  
attention.

As per the Currents link above, I hope that our research in Go will  
lead to techniques
that impact work in phase transitions and protein folding. Impacts on  
other biological
fields are possible, but quite speculative. After all, Go is all about  
small units that
cannot live on their own grouping together to make living units. I find  
Go the perfect
physicists model for life: the simple interactions appeal to the  
reductionist way
physicists like to think about problems, and the overall richness of  
the resulting
dynamics keeps things very interesting.

I hope this helps with your article. Please feel free to ask clarifying  
questions, either
on this list or privately.

And please, send this list a link to your article when you submit it. I  
am interested
in your article whether it is accepted for publication or not.

Cheers,
David