Re: computer-go: Pattern matching

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

Since there are too many available moves at each position to do a
brute force search, go programs must do a very selective search.  So
plausible move generation is very important.

I think most programs start with just some code for move generation, but
soon it gets large and unwieldy.  A pattern database provides a way  to
organize and easily extend the move generator.

In Many Faces, the local tactics move generator is still coded as a few
thousand lines of C.  The connection analyzer is mostly C, but augmented
with about 212 patterns for recognizing various interesting one point
jump shapes.  The full board move generator is several thousand lines
of C, augmented with about 1500 patterns.  The biggest set of patterns is
for suggesting moves to enclose or run away.  I couldn't come up with a
good, simple algorithm to find good enclosing or running moves, so instead
I just enumerated all of the shapes in a pattern library.  It's only about
400 patterns.  I find that it is much easier and less buggy to enumerate
a set of patterns than to try to code something in C.  The other large
set of patterns suggests endgame moves (also about 400 patterns).  Again
it is pretty easy to enumerate all of the common endgame shapes with
their approximate values.

My tactical analyzer move generator is mostly driven by liberty count
considerations rather than shape, so a pattern matcher would not be so
useful.

I found the one point jump connections to be the hardest to analyze
correctly, since their connectivity so often depends on various
kinds of double peeps.  Rather than read all of the combinations,
the pattern generator can suggest only interesting lines and save a lot of
time.  And it is much easier to add a new pattern that to change the
C code.

My eye shape evaluator is still in C (4500 lines).  I would prefer to
have it be based on a pattern/shape library, but I never had time
to convert it, and the current code works pretty well.

If you just match patterns to suggest moves without evaluating or doing
lookahead, your program will be very weak.  This appraoch has been tried
many times.  But a good pattern database is a very useful part of the
go programmer's toolkit.

Another advantage of using patterns rather than C for move generation, is
that it will make it easier to add learning to the program later.

I have found an 8x8 maximum pattern size to be enough in almost all cases.
I have separate databases for full board opening move generation and 
Joseki move generation.

So for me, pattern matching is essential to the program's strength.  I can't
even imagine the amount of extra work involved in coding all that knowledge in
C.

Choosing patterns is easy.  I look at games the program played, and when it
makes a bad move because a pattern is missing, I add it.  Since patterns are
suggesting moves, not evaluating them, there is no issue with having too many 
patterns, or multiple similar patterns that suggest the same move.  All moves
are suggested for a reason, which leads to a natural partitioning of patterns
into classes.  I have a graphical pattern editor built into the program,
so adding patterns takes very little time, and the result can be tested 
immediately.

David Fotland

At 12:35 PM 10/29/99 MDT, Jeff Massung wrote:
>How effective has pattern matching really been in Go programs?  How does one 
>choose which patterns to include with the program?  And how is one pattern 
>on the board weighed more than another matching pattern elsewhere on the 
>board?
>
>In my experience programming AI, neural nets, and recognition programs, 
>pattern matching is only good for "OCR" type programs, and which against 
>weak players is good at games, is lousy unless a neural network allows the 
>patterns to grow (and in Go, that would not be acceptable - how big should 
>the pattern be? and there are too many combinations).
>
>I'd love any comments :).
>
>Jeff
>
>______________________________________________________
>Get Your Private, Free Email at http://www.hotmail.com
>
>