Re: [gnugo-devel] endgame module for GNU Go

[Evan Daniel]

On Mon, 6 Sep 2004 15:32:30 -0700 (PDT), Eric <address@hidden> wrote:
> --- Evan Daniel <address@hidden> wrote:
> 
> > I think that if you are interested and able to write
> > a piece of
> > software that meets the above requirements, you will
> > find ample help
> > in the details of how to hook it into GNU Go and how
> > to play Go
> > endgames; if you want, I can offer some comments on
> > the technical side
> > of what you've mentioned so far.
> 
> Could you please, Evan? I would be eternally in your
> debt.

First, I would suggest reading Sensei's Library for information on Go
endgames.  It seems to be the best place online to learn about; there
are also books, which I think were mentioned.

Second, I think you might want to more clearly define your problem
space.  What exactly do you mean by endgame?  The endgame is
traditionally broken into the small and large endgames.  The large
endgame starts basically as soon as all the groups and territories on
the board are clearly defined and either alive or dead, and frequently
includes some fairly large moves; the small endgame is the very small
value moves at the end, worth a small handful of points (5 or less is
probably a reasonable cutoff, but don't quote me on that).

For the small endgame, you might do well to read about combinatorial
game theory.  Frequently small endgames can be examined from that
standpoint quite successfully.  The large endgame, on the other hand,
can be quite complex and there is no "easy" answer.  I think that GNU
Go plays much better in the late endgame than in the early endgame, so
there is more to be gained in the large endgame.

A note on breaking up the board:  This is a nontrivial task in itself.
 In general, if you can accurately decompose the board and determine
correct valuations for the pieces, CGT techniques will tell you where
to play globally.  Your suggestion of draw a square around each dragon
is far too simplistic -- many times a dragon is strongly alive
independent of endgame questions, and is part of multiple different
pieces of territory, each of which can be handled separately for
endgame reading purposes.  Similarly, if a dragon is not entirely
alive, you may need to include fairly large areas around it to avoid
missing something important.

In general, I find the concept of a planner interesting.  I know very
little about it, but intuitively it sounds like an attempt to play the
game in a manner more like people do -- look at goals, look at
options, and determine which options can achieve which goals and how
well.  Is that the basic idea?  If so, I imagine it will result in
mixed successes -- I imagine it will work well in some areas, but my
guess is that until you put in a lot of time tuning it to play go (as
opposed to non-domain specific planning), you will find that more
traditional brute force searches win on efficiency, and likely to a
degree that distinguishes useable from not.

And finally, if you truly intend to spend a significant amount of time
on this, I would suggest that at least some of it be spent teaching
yourself to play go.  While there are plenty of strong players willing
to answer questions, I think you will find the gain in efficiency from
knowing how to play reasonably well yourself to be very high.  There
is no need for you to become an expert, but playing at a medium to
medium high kyu level is probably neccessary in the long term.

HTH

Evan Daniel