High level ideas...

[Matt Gokey <mgokey@xxxxxxxxxx>]

Here is an idea that has been swarming in my head.  Bear in mind it is
very high level and roughly defined.  I have no idea if it is at all
feasible or even has any potential.  Please comment, as I would like
your opinions to help decide whether to continue (the regulars on this
mailing list are the true experts in this field).  Also, if you or
someone you know of has tried anything like this please let me know.

First, some assumptions...

1st assumption:

I know life and death analysis is a critical part of go playing for
people and computers, but I've been recently thinking that determining
accurately a group's status is really not too useful if  the play of
earlier stones is not leading towards the desired state.  Isn't this
true?  Aren't we making playing decisions far prior to the ability to
read out life or death status, and if so doesn't that potentially lead
to a poor position as easily as a good one?  How do programs make
decisions that will probably lead to life defensively and death
offensively?  And even worse how does a program decide that a particular
area/group is important in the overall strategy and therefore not make
fruitless moves?

2nd assumption:

There are primarily two reasons commonly stated for why searching
methods do not work in go like in chess.  One that the tree unimaginably
large and therefore cannot be searched, and two that no good simple
evaluation function exists that can be used to accurately score and
compare positions.  Now ignoring the 1st for a moment, wouldn't an
evaluation function using common characteristics like territory, group
safety, some positional analysis (corners, edge, shapes), influence,
etc. be useful if you could get far enough out in the tree?  Yes or no?
Keep in mind I don't care that its not possible to expand the tree.  How
deep would you need to go in the opening, middle, end?  If it would be
effective then we're left with only one reason - the size of the tree.

3rd assumption:

What properties of go can be exploited.  I see primarily two: the
relative static board state, and relative independence between loosely
defined areas on the board.  The board state changes slowly and
incrementally, usually.   As the game progresses the level of dependence
changes with little or no dependence by the late endgame.  Along with
this the "crystallization" of local areas also occurs.   In this stage,
as I believe Martin Mueller has shown, the game can be played as a sum
of local games as in combinatorial game theory.  Comments?

My thoughts:

A bit vague and probably not that well described, but maybe it will
spark discussion, or maybe its just downright crazy!

Chunking search, as I call it.  The gist of the idea is to use chunking
to identify potential areas and local goals.  Then use several local
goal achievements (i.e. a set of assumed moves) for each locality as an
atomic "move" in the search tree (a move as such could be made up of 2
to 10 or more stones as an example).  The division and determination of
goals would probably use common heuristic and algorithmic methods.  The
search could be an alpha beta variant and possibly use other advanced
search methods like rational searches, probability distribution, etc.
The idea being not really to search the tree, but to sample the tree in
order to find areas likely to be significant and goals likely to have
payoff later.  By chunking moves we can get deeper into the tree.  This
could even potentially be done with multiple hierarchical levels, or on
a smaller scale for life and death analysis.  Local goals/areas that
conflict with each other could be hot spots that need attention and move
ordering could be used to determine moves that minimize the opp good
points, and maximize player good points.

"Staticness" of board allows ability to hold all evaluation data
incrementally as part of the tree.  The eval fn only need calculate
weighted scores.

Many parts of this method would be amenable to parallelism as well, and
it could be done on opp time too.

I know its not that well thought out, but please comment.  Any potential
here?

Matt