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

[Gunnar Farnebäck]

Eric wrote:
> I have developed a general-purpose Artificial
> Intelligence Planning algorithm and engine, and I am
> interested in applying the technology to develop an
> endgame module for GNU Go.

Fine. The endgame is not GNU Go's weakest part, rather one of the
stronger, but certainly there's space for further improvements.

Just to be clear what we are talking about, would this endgame module
be a stand-alone piece of code that can be integrated into GNU Go or
would it need to depend on some library or similar for your planning
algorithms? Are you interested in getting it into the mainline GNU Go
or do you regard it as a private research project?

> A description of the planner, called Semsyn, can be
> found at http://www.semsyn.com. Essentially, the
> Semsyn approach is a formal integration of what has
> historically been viewed as mutually exclusive,
> opposing directions of AI search.
>
> [...]
>
> In particular, the results of the 2004 IPC are
> entirely incomprehensible. Don't take my word for it.
> Judge for yourself:
> 
> http://ls5-www.cs.uni-dortmund.de/~edelkamp/ipc-4/

Well, although I have a Ph.D. in Computer Vision, both the description
of your planner and the IPC results are equally incomprehensible to
me. ;-) It would probably have helped if I ever had taken an AI
course.

> In recent months I have studied the pertinent research
> on the game of Go, including the documentation of GNU
> Go. So here is how I envision the GNU Go endgame
> module taking shape:

How experienced are you at playing go yourself and how skilled are you
at evaluating endgame positions "manually"?

> Analogous to the combinatorial game theory approach I
> define a dynamic set of local games, e.g. for each
> dragon in the current turn of play, the corresponding
> local game board is the smallest board surrounding the
> dragon in which the dragon can still fit.

This didn't quite make sense to me. Maybe you can illustrate with an
example in an actual position?

> Since local game boards are (hopefully) smaller than
> the entire Go board, an AI planner can simulate full
> (local) lookahead. It may also be efficient to
> consider the size and stone-density of a local board,
> and to fire the planner only under desirable
> circumstances.

Splitting into local games is generally a quite difficult problem.
Conservative splitting usually gives fairly big local areas while
small local areas may require rather speculative splitting.

> As regards the GNU Go endgame module, we have the
> following:
> 
> INITIAL STATE: The state of a local game is completely
> determined by the state of the corresponding local
> board - a one dimensional array of vertices where, in
> the usual way, 0=empty, 1=white, 2=black.

Ok.

> DOMAIN OPERATORS: Domain operators place stones on the
> board and remove stones from the board in accordance
> with the rules of Go.

Check.

> GOAL SPECIFICATION: For each local game, there is both
> an offensive and a defensive strategy to consider.
> Therefore the planner will have to be fired twice for
> the different goals.
> 
> The offensive goal is to remove all opponent stones
> from the board, given an unlimited number of friendly
> moves, with the caveat that something less than total
> annihilation is acceptable.
> 
> Similarly, the defensive goal must be such that it
> causes the computation of all ways that the opponent
> can remove friendly stones from the board. Once these
> are known it is necessary to subsequently block the
> opponent moves.

Endgame is only occasionally about capturing stones but more often
about securing and destroying territory. Your description sounds more
like life and death analysis. Maybe I've misunderstood something.

> NOTE: Here it can be seen another way of reducing the
> search complexity, in addition to reducing the global
> game to a number of local games: since the planner
> will be fired for each turn of play, the offensive
> goal search can disregard enemy moves, while the
> defensive goal search can disregard friendly moves.

I'm not sure what this means. Again an example might be enlightening.

/Gunnar