[gnugo-devel] The Module Formerly Known As Endgame

[Eric]

--- Evan Daniel <address@hidden> wrote:

> 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

Ok, I will stop calling my idea 'Endgame Module'. I
didn't know there was such concensus about the notion
of endgame. The new name for my idea is 'The Module
Formerly Known as Endgame' ;)

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

Planning is essentially brute force search too, if you
want to do it well anyways, in my opinion.

In 1995, we learned how to make brute force more
efficient: instead of immediately starting to build a
search tree, the program first builds a
polynomial-sized graph. Second, the program searches
the graph. So there are 2 phases, and the program's
execution switches back and forth between the 'build'
phase and the 'search' phase.

The points here are that some automatic inferencing is
being done during the build phase, and that the build
phase inferences will subsequently be used to guide
the search phase.

Further, since the graph is polynomial in size, and
since it takes polynomial time to build the graph,
then the inferences are coming to us at a cheap cost.
They are being computed *outside* of the search space.
Because search is too expensive.

This was the lesson of the paper:

Blum, A. and Furst, M.L. 1995, "Fast Planning Through
Planning Graph Analysis". In Proc. International Joint
Conference on Artificial Intelligence, pp. 1636-1642.
---------------

However, the 'efficiency' of Planning is one thing and
the 'nature' of Planning is another thing all
together.

What distinguishes Planning from the classical notion
of brute force search is the formal definitions
underlying its children-generation function (i.e. its
instructions on how to expand a search tree node).

The children-generation function of an AI Planner
typically makes use of objects called 'domain
operators' or, more loosely, 'domain actions'.

A domain action is a triple, <p,n,e>, where 'p' is the
preconditions that must exist before the action can be
taken, 'n' is a string representing the name of the
action, and 'e' is the effect of taking the action
(both 'p' and 'e' are formal logic sentences).

The point is that since we now have domain actions, it
is possible to define 2 directions of search. The
forward direction, called 'bottom-up', searches the
space of 'world states', so that the Planner can know
which situations are "possible".

The backward direction of search, called 'top-down',
searches the space of 'goals', so that the Planner can
know which situations are "relevant" for solving its
current problem.

In the forward direction, every search tree node has
some world state information. The program picks up
each of the domain actions one at a time, and looks to
see if the 'precondition' of the action is true in the
current state. If it is, then the action can be used
to expand the current search tree node, i.e. to
generate the next set of children nodes.

In the backward direction, every search tree node has
some goal/subgoal information. Here, the program picks
up each of the domain actions one at a time, and looks
to see if the action and contribute to any of its
current set of goals, e.g. if any of the goals appear
in the 'effect' of the action. If the action is deemed
to be effective, or relevant, then the action can be
used to expand the current search tree node.

The point is that people intuitively thought top-down
search would be more efficient than bottom-up search,
because top-down search knows something about its goal
that it needs to solve.

But the funny thing about it is, as it turns out,
sometimes it is better to know something about your
goal, and sometimes it is not! Wow. People never
expected this result.

Because of their disappointment, most AI Planning
folks have gone a different direction from what I
outline above. They are re-casting the Planning
problem as a Constraint Satisfaction problem. In other
words, procedural programming. Silly rabbits ;)

But me, what I do with my planner is to glue the
top-down and bottom-up.

So that's the end of my 'Introduction to Planning'
speech. All this stuff gets done automatically, behind
the scenes. This is all internal implementation
details of the planner itself.

The important question for GNU Go is: Now that I have
a planner, what do I do with it?...

Cheers,

Eric