Re: computer-go: Pattern matching

["Gary Boos" <gboos@xxxxxxx>]

MFG has a "...seperate database..."  for the opening.
MFG got outplayed in the opening by SmartGo at the congress.
Can you comment on the code (i.e. not the database) that is
used to help play the opening (which seems to be a weak
area for MFG) ?
        Gary
------
------

-----Original Message-----
From: David Fotland <fotland@xxxxxxxxxxxxxxxxx>
To: computer-go@xxxxxxxxxxxxxxxxx <computer-go@xxxxxxxxxxxxxxxxx>
Date: Saturday, October 30, 1999 5:24 PM
Subject: Re: computer-go: Pattern matching


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