[gnugo-devel] endgame module for GNU Go

[Eric]

Hello,

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.

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.

Semsyn does not depend upon incomplete heuristics nor
inflexible optimization strategies in order to cope
with the combinatorial explosion of the search space,
and this is a radical departure from the conventional
approach of building planning systems that are not
guaranteed to find solutions.

Throughout its development, Semsyn has participated in
the bi-annual International Planning Competition
(IPC), as part of the conferences on Automated
Planning and Scheduling, and the system is competitive
with highly optimized planners that sacrifice
functionality in order to achieve runtime performance.

Along with the completion of Semsyn's development, it
was my sincerest wish to help move the AI Planning
community towards a more objective measure of overall
planner performance. However, I am afraid that they
are (rightfully) more concerned with publishing and
obtaining funding for their own research than they are
with pushing the state-of-the-art envelope.

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/

Because of this I am led away from a purely
research-oriented agenda, and I feel that some
consideration of the application side of the
technology is the best way to further its development.
Thus my interest in GNU Go.

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:

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.

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.

When the planner is fired it automatically synthesizes
a plan (a sequence of moves) for either surrounding
enemy or defending territory. The trick is to convert
the problem of Go into an AI Planning problem.

An AI Planning problem consists of an INITIAL STATE, a
GOAL SPECIFICATION, and a set of DOMAIN OPERATORS.
Domain operators are used to transition the system
from one state to another, ideally ending in a state
that satisfies the goal specification.

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.

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

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.

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.

Of course once all of the offensive and defensive
plans for all of the local games have been found, it
is still necessary to pick the best plan to execute.
This is analogous to summing the local games, and
requires further thought as well as some
experimentation.

One goal of the AI Planning approach is to add a
logical component to a system that is otherwise
heavily dependent upon pattern-matching. A second, but
not least, goal is to leverage recent advances in AI
Planning technology for speeding up NP search.

All comments, questions, and suggestions regarding
this proposal are greatly appreciated.

Best regards,

Eric Parker