[Please Help] Pattern Matching Comparison

[Mousheng Xu <xu@xxxxxxxxxx>]

Dear All,

    I am now working hard on pattern matching, but find myself very dumb. So I
want some help from you guys.
    There are serveral ways to do pattern matching, currently I am comparing the
following 4:
    1. PAT Tree: guess all of you guys know what it is. If not, go read some
algorithm books.
    2. Zobrish hasing: guess all of you guys know what it is. If not, go read the
previous discussions of this list.
    3. Silly Number hashing: the hash key is just a numerical representation of
the board of interest. If you use 0 for empty, 1 for black, 2 for white, 3 for
jie, then you can use 2 bits to represent one poisiton on the board.
    4. Pattern tree: just an ordinary tree. Basically you can view it as a SGF
tree.

    Here is what I think we want from patterns:
    1. exact pattern matching. Obviously, you find an exact pattern match, get the
move.
    2. subpattern matching. If you want to match the whole board with the whole
pattern base, most of time you won't find a match except at the beginning of the
game. You want to match a portion of the board against the pattern base. In this
case, you won't to do subpattern matching.
    Any other use of patterns???

    Besides the above capabilities, you also want to consider space & time. Given
a board size 100 (positions), pattern size 20 (consecutive moves), and roughly
1000 patterns, here are my brief thoughts:

     PAT Tree: easy to do exact & sub pattern matching. The problem is space. It
takes about 4 ^ 100 = 10^60 tree nodes. You know how terribly big 10^60 is. Some
of you on this list (Mark the Ph.D.?) was using PAT, I don't know how he could
handle so big a PAT tree.
    Zobrist hashing: it's space & time wise. The problem is subpattern matching. I
don't see a convenient way to do a subpattern matching. Many of you on this list
are using Zorist hashing, how do you guys do subpattern matching?
    Silly Number hashing: very similar to Zobrist hashing. It's space & time
efficient & it can do both exact & subpattern matching. Why people are not using
it often?
    Pattern tree: space & time is not a problem. But it's not efficient for
subpattern matching. You cannot efficiently get into the internal nodes without
starting from the root.

    Any disucssion? Tutoring? Hints? ...
    Thanks a lot.

-- Mousheng Xu