Re: computer-go: Sharing Go modules - ready for download

[Heikki Levanto <heikki@xxxxxx>]

On Mon, Jun 18, 2001 at 08:32:14PM +0200, Patrick Stiegeler wrote:
> the question is also open for the rest of the group: does
> anyone know about such 2 dimensional pattern matching algorithms
> that need nearly as little as possible comparisons?

I once speculated about this. 

I assume a pattern is a n by n square consisting of white, black, empty,
out-of-board, or some reasonable combination of those (black or empty, empty
or out-of-board...). There should be an anchor point in the middle of the
pattern. (n may have to be as large as the board!). 

I would take all patterns, and produce all the translations and mirror
images of them at compile time.

Then I would search through the pattern space, and find the one test that
divides the space most equally in two. Repeat recursively for each half of
the space, until you have single patterns left. Implement what ever special
conditions or actions you need at the leaf.

This is about the best I can think of matching a large number of patterns
against a given place on the board. You still have to repeat for each point
on the board, though.  

One optimization would be to keep a list of possible patterns for each board
point, and eliminate those that reach outside the board from that list.

Another one would be to keep incremental lists of all possible patterns for
all points, and update when ever a stone is played. I suspect this might get
nasty, especially when stones are being captured...

Of course you may ask yourself if you have to match every pattern to every
position? Depends what you use the patterns for, of course. If they propose
moves with some weights, you may start with more promising patterns, and
ignore those that propose the same moves with much less importance that the
best proposal found so far. Or if you use patterns to connect groups, you
can stop matching once you have established that groups are connected...


Thoughts and comments, anyone?

-H

-- 
Heikki Levanto  LSD - Levanto Software Development   <heikki@xxxxxxxxxxxxxxxxx>