Properties of the above example:

• a 4x4 grid,
• an edge at (0,0), (0,1), (0,2) and (0,3),
• a white stone at (2,3).

Pattern representation

A pattern can be any kind of rectangular shape. Only stones and edges are part of the pattern representation, empty space is implicit (it's the stones that matter!). In order to get the pattern of a go grid, a left-right / bottom-top scan has to be done. E.g. in the above grid start the scan from edge (0,0) => empty (3,0), then (0,1) => (3,1) etc. While doing the scan, keep track of the delta_x and delta_y with respect to the previous hit (stone/edge). Thus, the above go grid is represented as ((edge,0,0), (edge,0,1), (edge,0,1), (edge,0,1), (white,2,0)).

Another example (note that first hit always starts with coord (0,0)):

Pattern Tree

Patterns are inserted in a tree-like data structure which I call the pattern tree or simply ptree. The ptree will be used to search for patterns in a given game position. To insert a pattern:

• start at root of tree (no triples yet)
• match the first triple of the pattern e.g. (black,0,0) with one of the above triples
• if match then walk down 1 level of the tree (which lists the children of the matched triple)
• if no match then create an additional triple
• repeat until the pattern doesn't have any triples left

Inserting pattern ((black,0,0),(white,1,1)) results in this tree:

• (black,0,0)
  • (white,1,1)

Inserting pattern ((black,0,0),(black,1,1)) gives:

• (black,0,0)
  • (white,1,1)
  • (black,1,1)

Finally, inserting pattern ((white,0,0)) gives:

• (black,0,0)
  • (white,1,1)
  • (black,1,1)
• (white,0,0)

Searching for patterns

Once all patterns are inserted into the ptree, we can use it to search for patterns in a game position. In order to search we do a left-right / bottom-top scan. Each hit (stone/edge) we create a new pattern node instance which essentially:

• just keeps track of where we are in the ptree (i.e. at which node we are),
• it's creation coordinate (x,y).

While scanning, this new pattern node instance then searches for patterns relative to its creation coordinate (x,y) and its location in the ptree (the children of its node are relevant). That's the basic idea! And it works :-) When a node instance has a hit (which means a stone has been found that is part of at least one ptree pattern) then a new node instance is created. The original is also kept (because a node can have several children). Because patterns are marked in the ptree, a node instance know whether it has found a pattern or not.
Now, there're a lot of nasty details I left away e.g.

• in order to reduce tree size, patterns/grids are 'normalized'(so that mirrored/reflected variants of the same pattern are only inserted once)
• some post-processing is needed (empty space checks before the first and after the last stone to make the rectangle complete)
• etc.

Send me an email if you're interested in the source code (C++).
PieterBeyens