[gnugo-devel] corner matcher documentation

[Paul Pogonyshev]

this patch adds documentation for corner matcher. revisions, editions
and grammar corrections are welcome ;) it also adds a `continue' to
the corner matcher (a tiny missed optimization).

Paul


Index: doc/patterns.texi
===================================================================
RCS file: /cvsroot/gnugo/gnugo/doc/patterns.texi,v
retrieving revision 1.13
diff -u -p -r1.13 patterns.texi
--- doc/patterns.texi   2 May 2002 18:33:36 -0000       1.13
+++ doc/patterns.texi   24 May 2003 20:10:33 -0000
@@ -16,6 +16,7 @@
 * grid optimization::             The ``grid'' optimization.
 * Joseki Compiler::               The joseki compiler.
 * Ladders in Joseki::             Example: ladders in joseki.
+* Corner Matcher::                A special matcher for joseki patterns.
 @end menu
 
 @node Patterns Overview, Pattern Classification, Patterns, Patterns
@@ -1638,7 +1639,7 @@ and a constraint
 ;xplay_attack(A,B,C,D,*)
 @end example
 
address@hidden Ladders in Joseki,  , Joseki Compiler, Patterns
address@hidden Ladders in Joseki, Corner Matcher , Joseki Compiler, Patterns
 @comment  node-name,  next,  previous,  up
 @section Ladders in Joseki
 
@@ -1713,3 +1714,123 @@ to the four intersections and a comment:
 
 The appropriate constraint (autohelper macro) will then be added
 to the Joseki @file{.db} file.
+
address@hidden Corner Matcher, , Ladders in Joseki, Patterns
address@hidden  node-name, next,  previous,       up
address@hidden Corner Matcher
+
address@hidden implementation of pattern matching
address@hidden joseki
address@hidden corner matcher
+
+GNU Go uses a special matcher for joseki patterns.  It has certain constraints
+on the patterns it can match, but is much faster and takes far less space to
+store patterns than the standard matcher.
+
+Patterns used with corner matcher have to qualify the following conditions:
+
address@hidden @bullet
address@hidden They must be matchable only at a corner of the board (hence the 
name of
+the matcher).
address@hidden They can consist only of @samp{O}, @samp{X} and @samp{.} 
elements.
address@hidden Of all pattern values (@pxref{Pattern Values}), corner matcher 
only
+support @code{shape(x)}.  This is not because the matcher cannot handle other
+values in principle, just they are currently not used in joseki databases.
address@hidden itemize
+
+Corner matcher was specifically designed for joseki patterns and they of
+course satisfy all the conditions above.  With some modifications corner
+matcher could be used for fuseki patterns as well, but fullboard matcher
+does its work just fine.
+
+The main idea of the matcher is very same to the one of DFA matcher
+(@pxref{Pattern matching with DFA}): check all available patterns at once,
+not a single pattern at a time.  A modified version of DFA matcher could be
+used for joseki pattern matching, but its database would be very large.
+Corner matcher capitalizes on the fact that there are relatively few
+stones in each such pattern.
+
+Corner pattern database is organized into a tree.  Nodes of the tree are
+called ``variations''.  Variations represent certain sets of stones in a
+corner of the board.  Root variation corresponds to an empty corner and a
+step down the tree is equivalent to adding a stone to the corner.  Each
+variation has several properties:
+
address@hidden @minus
address@hidden stone position relative to the corner,
address@hidden a flag determining whether the stone color must be equal to the 
first
+matched stone color,
address@hidden number of stones in the corner area (see below) of the variation 
stone.
address@hidden itemize
+
+By corner area we define a rectangle which corners are the current corner of
+the board and the position of the stone (inclusive).  For instance, if the
+current board corner is A19 then corner area of a stone at C18 consists
+of A18, A19, B18, B19, C18 and C19.
+
+Variation which is a direct child of the root variation matches if there
+is any stone at the variation position and the stone is alone in its
+corner area.
+
+Variation at a deeper level of the tree matches if there is a stone of
+specified color in variation position and the number of stones in its
+corner area is equal to the number specified in variation structure.
+
+When a certain variation matches, all its children has to be checked
+recursively for a match.
+
+All leaf variations and some inner ones have patterns attached to them.
+For a pattern to match, it is required that its @emph{parent} variation
+matches.  In addition, it is checked that pattern is being matched for
+the appropriate color (using its variation ``stone color'' field) and
+that the number of stones in the area where the pattern is being matched
+is indeed equal to the number of stones in the pattern.  The ``stone
+position'' property of the pattern variation determines the move suggested
+by the pattern.
+
+Consider this joseki pattern which has four stones:
+
address@hidden
+------+
+......|
+......|
+.O*...|
+.XXO..|
+......|
+......|
address@hidden example
+
+To encode it for the corner matcher, we have to use five variations,
+each next being a child of previous:
+
address@hidden {Tree level} {Position} {``other''} {Number of stones}
address@hidden Tree level @tab Position @tab Color @tab Number of stones
address@hidden 1 @tab R16 @tab ``same'' @tab 1
address@hidden 2 @tab P17 @tab ``same'' @tab 1
address@hidden 3 @tab Q16 @tab ``other'' @tab 2
address@hidden 4 @tab P16 @tab ``other'' @tab 4
address@hidden 5 @tab Q17 @tab ``same'' @tab 1
address@hidden multitable
+
+The fifth variation should have an attached pattern.  Note that the stone
+color for the fifth variation is ``same'' because the first matched stone
+for this pattern is @samp{O} which stands for the stones of the player
+to whom moves are being suggested with @samp{*}.
+
+The tree consists of all variations for all patterns combined together.
+Variations for each patterns are sorted to allow very quick tree branch
+rejection and at the same time keep the database small enough.  More
+details can be found in comments in file @file{mkpat.c}
+
+Corner matcher resides in @file{matchpat.c} in two functions:
address@hidden()} and @code{do_corner_matchpat()}.  The former computes
address@hidden array which holds number of stones in corner areas of
+different intersections of the board for all possible transformations.
address@hidden()} also matches top-level variations.
address@hidden()} is responsible for recursive matching on the
+variation tree and calling callback function upon pattern match.
+
+Tree-like database for corner matcher is generated by @code{mkpat} program.
+Database generator consists of several functions, most important are:
address@hidden()}, @code{corner_variation_new()},
address@hidden()} and @code{corner_add_pattern()}.
Index: engine/matchpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/matchpat.c,v
retrieving revision 1.55
diff -u -p -r1.55 matchpat.c
--- engine/matchpat.c   28 Apr 2003 13:44:34 -0000      1.55
+++ engine/matchpat.c   24 May 2003 20:13:04 -0000
@@ -1288,6 +1288,7 @@ do_corner_matchpat(int num_variations, s
        ASSERT1(board[move] == EMPTY, move);
 
        callback(move, callback_color, pattern, trans, pattern_stones, stones);
+       continue;
       }
     }