Re: [computer-go] Spiral pattern matching and data structures

[Evan Daniel <evanbd@xxxxxxxxx>]

On Thu, 20 Jan 2005 13:25:47 -0700, Anders Kierulf <anders@xxxxxxxxxxxxxxxxx> wrote:
> > ..OO             reverse sente sagari
> > .OYX
> > .*..
> > ....
> > ----
> >
> > that only match somewhere at the edge, and the diagonal spiral tends
> > to find out faster whether the anchor ('Y') has the right distance to
> > the edge.
> 
> Why not test the distance of Y to the edge before even starting to check
> whether all the points in the spiral match?

Because GNU Go uses a DFA-based matcher that checks all patterns
simultaneously, and doesn't have such information readily available. 
The big benefit is that matching time is close to O(1) wrt number of
patterns.

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