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

[Eric]

--- Gunnar Farnebäck <address@hidden> wrote:

> 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,

Oh.

> but certainly there's space for further
> improvements.

Ok.

> 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?

The endgame module needs to:

1. Decompose the Go board into local game boards.
2. For each local game board, decide whether or not to
invoke the planner.
3. For each invocation of the planner, pass the state,
goal, and domain operators.
4. Gather all of the local plans that are returned for
all of the local games.
5. Pick (or even more intriguingly, generate) the next
move based upon an analysis of the local plans, in
concert with GNU Go's pre-existing move generation
strategy.

Regarding the planner, think of it as any other
function. It requires 3 arguments - state, goal,
operators - and returns a plan. In fact, my planner is
quite terse, consisting of about 4 pages of code.

Further, viewing the planner as a function has the
really nice property that, as AI Planning technology
matures, outdated planning systems can simply be
"popped out" and replaced by more modern ones, without
any changes to the endgame module.

> Are you interested in getting it into
> the mainline GNU Go
> or do you regard it as a private research project?

Not really sure what you mean by this, but I'll take a
stab at it:

The Semsyn engine itself has already been completed,
and is proprietary. However, most planning systems
being developed these days adhere to the "standard"
PDDL (Planning Domain Definition Language) which
originated from Yale University.

If GNU Go treats the planner as a black box, then it
is not necessary to distribute the planner as integral
to the GNU Go engine. Users of GNU Go can simply
"plug-in" their favorite flavor of planner.

The bulk of the work being proposed currently involves
writing the endgame module and modelling the Go
domain, i.e. designing the domain operators. And yes,
I intend to leave these pieces in the public domain
(or free, or whatever is the proper terminology).

If I did not answer your question, then please ask me
again.

> > 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 your defense, now that I think about it the
intended audience of my planner description is the AI
Planning community. I need to write one for the
general public. So much to write, so little time ...
ho hum.

> > 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"?

Not very. As with any other application, I need to
find domain experts who are willing to help out. Know
of any?

I downloaded GNU Go only 3 months ago. Although I have
spent many hours playing GNU Go since then, as well as
occasionally logging in to Yahoo Games and playing
against other humans, the game is still intimidating,
and there are lots of sleepless nights on the horizon.

However, I am not entirely put off by this. Because
whether the application is unmanned space craft,
unmanned aerial vehicles, industrial robotics,
household robotics, robotic cars, or even the game of
Go, the driving force behind AI Planning technology is
that the programmer cannot possibly foresee (and
thereby pre-program) every single situation that the
program will encounter, and that the program should
have the ability to "think" for itself.

> > 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?

Translation - draw a square around each dragon.

> > 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.

Ok.

> > 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.

Guilty as charged! There is a lot of work to do here.
For the meantime, I just want something quick and
dirty. You know, a "proof of concept" thingy.

If I can get it to work, then I wanna know in months,
not years. If I cant get it work, then there's no
point in thinking about it any further.

> > 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.

Forget I mentioned it, Gunnar. It's an implementation
detail. But you get the gist of the proposal, right?

Cheers,

Eric