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

[Gunnar Farnebäck <gunnar@xxxxxxxxxxxxxx>]

Mark wrote:
> First of all I find your patterns very hard to read. Maybe this gets better
> with a good editor?

We use standard text editors and find the patterns easy enough to read
and write that nobody so far has decided that writing a dedicated
editor is worth the trouble.

> I've heard about others using the '(opponents) stone or empty' but I find it
> rarely useful. Although technically it happens that two patterns are the
> same except for a position where there could be a stone or empty, as a Go
> player I find that they are so inherently different that I would make an
> extra pattern.

I would agree with you if it weren't for the fact that the pattern
constraints can make up for those differences, in particular
constraints involving tactical or connection reading.

> Would it add more than a few percent in the number of
> patterns in your case?

Yes, we are not talking a few percent larger but many times larger.
Patterns like

  Pattern F410a
  
  ?xx......?            extend
  ?xx.O....?
  ?xx....*.?
  ?xx.......
  ?xx.......
  ----------
  
  :8,FEdt,shape(3)
  
  ?xx......?
  ?ab.O....?
  ?cd....*.?
  ?xx.......
  ?xx.......
  ----------
  
  ; x_alive_somewhere(a,b,c,d)

would expand to quite a large number without wildcards. Sure, many of
them wouldn't really be needed in most reasonable games but this way
is easier. The main drawback, of course, is that it does invite to
writing overly general patterns.

> On the other hand I think using a coordinate is easier on the eyes
> than cluttering the patterns with As and Bs.

This is indeed a question of taste. Let's just say that I would never
want to switch.

> Generating C-code is not going to work for me, although it probably could
> just as easily be generating Java code.

Yes, it certainly could.

> But the real question is: how does it perform? My pattern-matcher
> takes all the patterns in a set and (tries to) constructs an optimal
> decision-tree to match the patterns in the least number of steps.

For the time-critical pattern sets we compute a DFA (deterministic
finite automaton) which I suppose amounts to more or less the same
thing.

> I wonder if by generating C-code you can reach the same kind of
> optimization.

The C-code is used for the constraints and is called if the geometric
matcher finds that the stones on the board match the pattern.

> I suppose in principle it should be possible, but it
> seems so much more difficult to me. Or maybe it comes down to
> roughly the same thing?

I don't think there's a big difference in the end. I'm sure it's
possible to increase the speed somewhat with more structure in the
constraints but we have gained a lot from having them very flexible.

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