[computer-go] State of the art of pattern matching

[Mark Boon]

On 29-mrt-08, at 14:13, terry mcintyre wrote:

> Considering how inexpensive memory is, and how
> branches cause processor pipelines to stall, it seems
> to make sense to convert "don't care" patterns into
> however many fixed patterns would be equivalent. If
> there are three "don't care elements", which could be
> instantiated three ways, then 3^3 patterns would
> replace one, for example. If these were converted into
> optimized assembler, per Jacques' suggestion, the
> pattern matcher would be extremely fast.

Yes, of course.

Maybe I'd need to do an experiment at some point and compute from the  
pattern-set that I have and see how many fixed patterns that results  
into. I'm a bit afraid though of the worst case scenario where you  
have a pattern that doesn't quite fit in the 3-manhatten-distance  
mask. There are 16 4-distance points, so if you spill ino that by one  
point you get 3^15 or a little over 14 million patterns. Multiplied  
by 3 for every don't-care point within less than 4 distance. Ouch.

Mark

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://computer-go.org/pipermail/computer-go/attachments/20080329/29b15d55/attachment.htm