Re: [Please Help] Pattern Matching Comparison

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

I use 8x8 bitmaps with an 8 bit hash to limit the pattern matching
to a subset of the patterns.  This is fast enough for a few thousand
patterns.  I've published details elsewhere.  You should be able to 
find them.

David

At 12:40 AM 3/12/99 -0800, Mousheng Xu wrote:
>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
>
>