[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [gnugo-devel] address@hidden: Re: GNU go and Artificial Intelligence
From: |
David G Doshay |
Subject: |
Re: [gnugo-devel] address@hidden: Re: GNU go and Artificial Intelligence?] |
Date: |
Wed, 29 Sep 2004 14:17:25 -0700 |
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