Re: computer-go: Discarding the rubbish moves

[Richard Brown <rbrown@xxxxxxxx>]

Darren Cook wrote:

> This subject interests me a lot at the moment; as it would be off-topic
> I started a new thread.

It rather interests me too.

> Heikki Levanto wrote:
> > Anyway, in any given go position, there are a small number of
> > reasonable moves that can be considered, and a great number of
> > totally stupid moves that no human would even consider.

Heikki has made a very important observation.  I hereby dub it
"Levanto's Observation", in honor of the observer.

> > Any go
> > program must be able to discard the 90% of rubbish moves quickly.

Yes, this is extremely important.  Strong programs of the future will
use such a razor in an early phase. I believe that the actual percentage
will be higher.  I'll go out on a limb and predict 97%.

> > Here a simple move evaluation could make sense. (especially since
> > the same move may be totally irrelevant or the best possible,
> > depending if there is anything more valuable around...)

There is a clear benefit from a razor which, for any potential move,
correctly places it into one of two classes:

        o-  Moves that no reasonable player would ever even consider.

        o-  Other.

For some suitable definition of "reasonable".

The "Other" category comprises ~3%, says I.

> What rules are there for vetoing moves? I'm interested at two levels:
>    1. Proveably bad moves
>    2. Pro level at 99.9%
> 
> By pro level I mean an algorithm (or database) that would veto moves in
> a board position and at 99.9% of the time it wouldn't veto the move the
> pro played. I'm more interested in type 1 as I'm interested in solving
> endgames, but type 2 is more useful for a general purpose playing program.

[Darren's Type 1 examples deleted.]

> What other positions are there like this? Has anyone made a list, or
> done research on this?

As the type 1 examples are a subset of moves that pro _would_ veto,
I reckon a type 2 algorithm would veto them, too.

A type 2 algorithm/database can be constructed by observation of pro
games.  The question is, what to observe?  That is, what _features_
does one extract from the positions, and the moves chosen -- and those
_not_ chosen! -- in such positions as those which arise when observing
games?  [That's the "feature extraction" phase of "pattern recognition"
with "supervised learning" of patterns; interested readers may Google
for those.]  Feature extraction is a crucial step in writing something
like Darren's "type 2" algorithm.  Oh, and of course, storage and
retreival
of patterns must happen within the bounds of space and time, and the
data
should be insensitive to translations and rotations of the plane, and
insensitive also to the order in which the data arrives (that is, to
the order in which positions/moves are observed).  Blah, blah, blah.

During the feature extraction phase, information that is useless, or
redundant, or irrelevant, is discarded, and we are left with a handful
of numbers, in a d-dimensional vector on the reals, that represent the
essential features of a particular (position,move) pair.  (There may
be more than one way to do this; what exactly _are_ the essential
features of interest?)

Assuming that one extracts suitable features from the positions/moves,
there is the problem of what to do when one encounters a pattern that
is not in the data.  (As when playing an actual game!)  Then it is
necessary to have a metric which tells us the degree of similarity of
the new pattern to patterns that we already know something about.
I need to know _how_much_ an arbitrary pattern is like patterns I know.

Correctly classifying a move as garbage is a huge savings in lookahead.

But what makes one classifier better than another?  This is measurable
by how often it is wrong; that is, how often it incorrectly vetos a
move,
only to see a pro play it.  (Darren's .1%)  Somewhat harder to tell, is
how often a classifier didn't veto a move that it should have.  (Don't
we have to ask every pro?)

Assuming that one has a suitable metric, then various techniques can
be used (their success depends on the nature of the data).  Neural nets,
"linear classifiers", "non-linear classifiers" [just Googling for these
last two can be enlightening] and my current favorite, a little thing
called the "k nearest neighbor" rule.  "Hopfield networks", "Boltzmann
machines", "Voronoi diagrams", "convex hulls", and "Delaunay
triangulations"
are left as an exercise for the reader who hasn't fallen asleep yet.

I'm still trying to get my head around the fact that it is possible to
extract an _infinite_ amount of information from a finite amount of
data.

Ah, well, the nice thing about being an amateur mathematician is that
I have nothing to prove.

-- 
Richard L. Brown       Office of Information Services
Unix Guy               University of Wisconsin System Administration

"Go is the damnedest thing I've ever seen."