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

["Mark Boon" <tesuji@xxxxxxxxx>]

> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx]On Behalf Of Paul Pogonyshev
> Sent: Thursday, January 20, 2005 23:03
> To: computer-go
> Subject: Re: [computer-go] Spiral pattern matching and data structures
>
>
> Anders Kierulf wrote:
> > Question: When checking the spiral of points around an anchor,
> you probably
> > repeat that for all symmetries? Or do you include the symmetric
> patterns in
> > the DFA?
>
> We have a single DFA, which is matched 8 times, once for each symmetry
> transformation.  We tried to build pre-rotated DFAs, but they turned out
> to be so huge, that they were not worth it.
>

This surprises me. I think the number of leafs in the DFA tree is equal to
the number of patterns you try to store. The number of internal nodes is
smaller than that. So the DFA becomes more or less 8 times as big, but you
don't need to copy the actual patterns 8 times. So the total memory cost of
the pattern-matcher when building the DFA 8 ways is actually smaller than 8
times. Lookup speed increases significantly though so to me that definitely
justifies using a bit more memory.

It depends on how many patterns you store of course, but I thought number of
patterns in GNU Go was in the thousands only. Or maybe GNU Go's DFA is of a
different nature than mine, which is already hinted at by your remark no
pointers are used.

My DFA consists of pointers to the nodes that make up the DFA. Although the
shape of the stored points starts out as a spiral, the order is also
implicitly represented by the DFA itself. That way each subtree can modify
the point-order to maximise the discriminating behaviour of the
spiral-points specially tailored to the subset of patterns stored under that
particular sub-tree.

As to edge detection: my pattern-matcher currently does the check for edges
after the fact, when the DFA reaches a leaf in the matching process. As Eric
Boesch pointed out here a while ago though, it's possible to store any
discriminating feature in the DFA you like. So the optimal strategy is to
insert nodes in the DFA that do the edge detection at the point where this
edge feature becomes the most discrimitating feature of the (subset of)
patterns you try to store. I haven't implemented anything like that yet
though. I would first want to get an idea of the speed-gain it would give,
it's not obvious to me the gain would be very large. Checking on a
black-white-empty feature always splits the set in three, and I don't think
an edge feature can beat that very often.

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