Re: computer-go: Neural networks

["Richard Brown" <rbrown@xxxxxxxx>]

heikki@xxxxxxxxxxxxxxxxx wrote:
> 
> On Wed, May 16, 2001 at 01:17:22PM +0100, Julian Churchill wrote:
> > The actual idea is to use a neural network trained on some professional
> > games, as a sort of ultra fast pattern matcher, but it would also pick up
> > trends and general techniques to apply to playing Go as it was trained,

[...]

Observing professional play -- as opposed to using other sorts of input
--
is absolutely fundamentally necessary for this to work.  What you want
to
do, basically, is _categorize_ or _classify_ individual behaviors.

Behavior in go can range from the sublime to the ridiculous.  The trick
is telling those apart.

> Personally I remain rather sceptical about this ever working, but wish you
> good luck anyway.
> 
> The problem - or at least one of them - is that to appreciate the value of a
> move, you need to know a lot of the context, far more than just a pattern of
> black and white stones.

[...]
Yes.  I have to agree with all of Heikki's comments, and yet... I remain
less skeptical than he.  I think that neural nets using _appropriate_
input vectors would work well.  The problem is, what do you measure?

> One of my dreams has been to use a neural network for evaluating positions.
> Not based on a board image at all, but on a great number of carefully
> prepared key numbers. Unfortunately Ihave never had the time to dig deeper
> into it. If there is interest, I can try to explain my ideas here, if only
> to get them shot down...

Sure!  I'd love to hear them.  Preparing those key numbers is the
difficult part, isn't it?

As Heikki has shown us, there's a lot going on in a given go game at
any one moment.  As a result, it's very difficult to encapsulate this
context into an appropriate input for a neural network, or, in more
general terms, into input patterns of some sort that may be categorized
by either supervised or unsupervised classification (machine learning).

So, although I understand the source of Heikki's skepticism, I still
feel that the best programs of the future will use these techniques.
Perhaps not neural nets _per_se_, but some sort of pattern
classification.
(Neural nets are one method in a vast array of pattern classification
techniques.)

What we want to do, basically, is _categorize_ or _classify_ individual
behaviors, where a "behavior" is a move (plus its context).  To keep
things simple for the purposes of this discussion, we can suppose that
-- at least for the time being -- we are concerned with only two
classes:  Those behaviors in which a professional might indulge, and
those behaviors in which _no_ professional would ever indulge.
(These two classes are used as an example; there might be others.)

Observing thousands of pro games, and millions of individual behaviors,
we build a database (perhaps using Heikki's key numbers).  Then, given
an arbitrary behavior from an arbitrary game, we want to -- at least --
assign it to one of our two (or more) classes.  In our example, if we
have assigned each possible vacant point of this board state to one of
these two classes, then what we have done is ruled out most possible
behaviors.  (At a wild guess, isn't it the case that greater than 90%
of all possible go moves are garbage?  And pro moves represent the
best, what, 1% or 2% of all the possible moves?  Am I wrong?)

Now the game tree is manageable.  Min and max to heart's content.

One interesting feature of a go behavior (chosen move + context) is
that, when a move has been chosen, and a stone placed on the board,
_all_of_the_other_ potential behaviors have been ruled out.  So, a
behavior includes information not only about the actual that was chosen
from a particular game state, or context, but also about all the moves
that weren't chosen in that same context.

Just as for "events" in experimental particle physics, we can keep
statistics about each behavior.  The "relative frequency" of a behavior
is the number of times it was chosen, divided by the number of times it
was _possible_ to choose it.  This collection of relative frequencies
represents a probability distribution across the data, so that when
we see a novel behavior (_thousands_ of _possible_ novel behaviors
occur in just _one_ game of go, so we need a way of dealing with them!)
we attempt to classify it into one of our categories.  This we do by
noticing the relative freqencies of those patterns in the data to
which this novel pattern is _similar_.

As to what makes one pattern similar to another, and what the degree
of similarity is, quite depends on the actual structure of the data.

Is go easier, or harder, than experimental particle physics?

> Best of luck to your project, and keep us posted. I would love to hear that
> my scepticism was unfounded!

I just want to say, "Me, too!"  Good luck to all, and I too hope to
hear that Heikki's skepticism is unfounded.

-- 
Richard L. Brown       Office of Information Services
Unix Guy               University of Wisconsin System Administration
                       780 Regent St., Rm. 246
rbrown@xxxxxxxxxxxxxxxxx        Madison, WI  53715