Re: computer-go: Pattern search/matching

[David Denholm <Dave.Denholm@xxxxxxxxxxxxx>]

"Jeff Massung" <jmassung@xxxxxxxxxxxxxxxxx> writes:

> How have any of you performed pattern matching quickly (ie hash/tree) with 
> patterns that allow for indices marked "don't care"?  Right now, for each of 
> code I've just done brute force search, but am having a hard time thinking 
> of a more ellegant method.  All my hash functions don't work, and my trees 
> aren't working either.

gnugo can do matching with 'dont care'.  It can also do 'either X or empty'
and 'either O or empty'

The algorithm we use is :  (% indicating binary)

 encode blank as %00
        white as %01
        black as %10

Then each pattern element is tested by and-ing with one pattern and comparing
with a second.

  Test for blank, white or black  by anding with %11 then comparing with required value
           white-or-blank is  and with %10 then compare with 0
           black-or-blank is  and with %01 then compare with 0

Because we are doing bitwise operations, we pack elements together
into 32-bit words, so we can do the matching on 16 pattern elements (4x4)
in one operation.



dd
-- 
David Denholm            daved@xxxxxxxxxxxxxxxxx
Citrix Systems UK Ltd.   http://www.citrix.com/