[computer-go] Do'nt cares in Pattern Matching

[Chrilly]

A possibility for a pattern matcher is to distribute the patterns in bins. 
This method is decribed in "A Pattern Matcher for Goliath" by Mark Boon.
Mark used the center-point and the 4 Adjacent stones as the bin-index. There 
are 243 different combinations of these 5 points. Gives 243 bins.
When searching a matching pattern for a point x, one needs only to search 
the much shorter lists of patterns in the corressponding bin.

The problems are do'nt cares. Mark "solved" the problem by not allowing 
do'nt cares on these 5 points. Thats not really nice, at least the Suzie Go 
expert has protested against this restriction.

A brute-force solution is to replace one don't care by 3 different patterns. 
2 do'nt cares, would be already 9. (Although my expert is already happy with 
1 don't care).

Is there any better solution?

There are numerous other searching techniques. E.g. Martin Mueller uses 
according his thesis a Patricia-Tree. How does one solve the do'nt care 
problem in Patricia-Trees?
Gnu-Go uses DFA's. Has a DFA a problem with Don't cares?

Personally I like the Mark Boon approach most. Hashing is usually fast and 
the method is simple. But the don't care is a little bit nasty. Any other 
approaches around?

Chrilly