[computer-go] Don't cares in Pattern Matching

[Eric Boesch]

"Chris Fant" <chrisfant at gmail.com> wrote:
>On 6/14/06, Eric Boesch <ericboesch at hotmail.com> wrote:
>>Pattern matching can require a time/space tradeoff. If the patterns are 
>>very
>>irregular and full of holes, then an attempt to minimize time usage by
>>treating each don't-care case that is tested as three or four different
>>patterns could lead inevitably to space usage that grows expontentially 
>>with
>>the number of patterns, as Chrilly alluded to.
>
>Actually it grows linearly with the number of patterns and
>exponentially with the average number of don't-cares per pattern.

The number of absolute don't-cares depends on how you choose to search the 
pattern space, though. The pattern set {{a1=w,b1=b,c1=empty}, {b1=w}} 
involves a don't-care if you test a1 first (because you will still have to 
test the second pattern no matter what result you get) but it involves none 
if you test b1 at the root of a decision tree (or DAG, or acyclic FSM) and 
then do the other tests only if b1 is black. On the other hand, there is no 
way to get around don't-cares in the set 
{{a1=w,b1=b},{a1=w,a2=empty},{b1=b,a2=empty}}. My point was that for some 
abnormal pattern sets, the number of don't-cares in your tree blows up no 
matter how you arrange your tests, so minimizing time by minimizing the 
height of the DAG means you end up with a number of leaves that is 
exponential in the number of patterns.

For a larger pathological example, suppose you have a set of 1000 patterns 
that each consist of 4 random intersections on the 9x9 board being assigned 
a random color (with the other 76 points being don't-care). The minimal 
height of a decision tree for these patterns is at most 81, but the number 
of leaves in such a tree would be impossibly large. In this case I'm not 
sure it's possible in practice to meaningfully improve on the naive solution 
of testing each of the 1000 patterns in turn.

These pathological random patterns have less to do with real pattern 
matching in go than with general decision trees, which I believe is a 
reasonably mature subject where we're not going to come up with new results 
by just doing a few back-of-the-envelope calculations. The results might 
easily be new to *me*, though. I should spend less time talking about 
subjects I'm only vaguely familiar with...