RE: [computer-go] Pattern Matcher (was M.Boon-Library)

["Persson, Magnus" <persson@xxxxxxxxxxxxxxxxxx>]

I could probably write pages about pattern matching in general and in my
program viking4. But I will try to be brief.

I have an editor which edits patterns that basically has about the same
expressive power as the patterns of gnugo. There are for example about
40 different conditions that can be simple such as specifying the number
of liberties, or more complex as calling a function that determine if a
block of stones is captured.

Without the editor I would not be able to do what I do.

3000 Attack L&D
3500 Defence L&D
5500 Connections and eyes
5250 Captures with eyevalues
3000 Full board move generation and shape patterns
400 Small endgame minimum temperatures
(and this is far from completed work)


A very nice feature of my editor is that it automatically tries to copy
text from the clipboard and interpret it as a pattern name.

A typical debugging procedure for me is to

a) Inspect the data structures in my program (I write a lot of code to
visualize everything my program does. If I cannot see it I cannot debug
it. Running the debugger is a last resort.).
b) There are a lot of lists of patterns that matched a position.
c) I click on the pattern that matched (the program copies the name of
pattern to the clipboard)
d) I go to the editor, loads the file in question, clicks on search
(using the name in the clipboard)
e) Now I can either "edit" or "copy and edit" the pattern
f) I save.
g) Let the program load all pattern files and compute the best move and
see if the change worked.

Making a good editor is difficult. I use a lot of keyboard shortcuts to
set the current meaning of a mouse click. The constraints are set using
a right button click popup menu. One has to avoid large mouse movements
at all costs or you will not be able to edit patterns on the scale I
have been doing for several years now.

---

Having codes for "empty/my stone" and "empty/opponent stone" is a good
thing IMO. Simply if you do not need it then you do not have to use it.

Having one such code in the patterns just means it replaces 2 patterns,
but if you have two it replaces 4 patterns and with three it replaces 8
etc.
So it saves a lot of work if you need to edit patterns. As a side note I
often find myself adding a pattern and then have to add about 10 small
variations of the basic pattern and if I had some nice constraint in
code instead that would be very helpful. The success of any pattern
system probably depend on how much can be done algorithmically instead
of patterns. David Fotland wrote that he has been successful in avoiding
the need for patterns by doing most things with algorithms. Probably
several 1000 of my patterns could be replaced with such code with little
loss of performance (perhaps even a gain).

I often have very big patterns with a lot "empty/my stone"- and
"empty/opponent stone"-codes because for example I can give a pattern
the following meaning:

"Play this move only if the player does not have a move in this area
because if you do this situation is too complex for this pattern to be
valid". It is a method of making pattern less general and more specific.
This avoids for example moves that defends one group but damage another
one nearby.

My program needs very specific patterns. Everything I say here always
depends on the purpose of each class of patterns and how far you try to
push them. If you only want to generate all moves that might be a good
move in a position then I think 200 patterns will work well. But if you
want to know which moves are better than others then 2000 patterns are a
minimum. It all depend on what you try to do.

By the way there was a source of confusion here about two different ways
of defining patterns. Frank de Groot has patterns which covers fixed
areas. Whereas I think Mark Boon, GnuGo and my patterns are all of
arbitrary shape. Since some sort of decision tree finally make the
matching this has no cost (sort of). It also means that carefully
handmade patterns are very specific and will only match when it can
guarantee too be useful.

Automatically harvested patterns (I have done some experiments with
this) has to compromise with different fixed shapes where large patterns
are very specific compared to more general ones Compared to hand made
patterns fixed pattern thus almost always become too specific or too
general. If some one could come up with an automatic method for
generating patterns with free shape for all types of patterns then
*that* would be a great breakthrough for computer go. My impression is
that Frank has been able to push the limit of what one can do with fixed
patterns and with his fast pattern matching it will be very interesting
to see what he can do with all the computing power left for other things
than pattern matching.

---

So what should the output of pattern be? I have some none specified
"marks" in my pattern language which can be used by the program for any
purpose. For example these marks could mean: play any of these moves, do
not play any of these moves, are these points secure territory, these
points are good shape etc.. By having 1 or two kinds of neutral markers
like this is a simple way to quickly design patterns with new very
specialized meanings.

But I think it is a good idea to be able to specify move trees for both
players. 

Patterns should also have numbers associated with them for priorities or
classification into subtypes.


So that was a lot about pattern matching. If you think I wrote something
strange it is probably because I use patterns in some special way. Note
that I never use patterns to make decisions about moves. Decisions come
from evaluation of moves searching shallow/full board or searching the
state of weak groups. 

I match patterns only in places where they are meaningful using
different decision trees for different types of patterns. Some patterns
are matched (centered) on stones and some are matched on empty positions
that are candidate moves. Or some are only matched on liberties (for
example captured stones has at least one liberty left, so such patterns
are only matched for such liberties).

Hopefully you also found some of my little secrets in the blurb above.
But I warn you! My current "patterns to the max approach" is 7-8 stones
weaker than the state of the art programs. The problem of patterns is
that you never get enough of them and those you end up with has to be
updated and changed. If you are careful you can find universal patterns
that are sort of correct, but that is far from easy.

--
Magnus Persson
Center for Adaptive Behavior and Cognition
Tel: +49-(30)-82406-350
Cell phone: +49 163 6639868

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/