RE: [computer-go] Pattern Matcher (was M.Boon-Library)

["Mark Boon" <tesuji@xxxxxxxxx>]

I'm racking my brain trying to remember what kind of speed we had in term of
pattern-matching, but I don't remember. It's been too long. There was a day
I knew all these things to the finest details. 2 million/s. sounds pretty
good, but...

You're not very precise in your information. How many moves in the games? At
how many points? Is the 2 million made up of 5 games, average 250 moves
each, average 200 legal moves each move, times 8? (It's the only combination
I can think of that would make 2 million.)

At some point I decided I hadn't ever seen a useful pattern that didn't have
any stones in them, so I decided I only needed to look for a match at points
where there's a stone. So I don't understand why you look at legal moves,
but maybe you came to the opposite, equally valid, conclusion that there are
no useful patterns with no empty points in them. Except that the number of
stones is generally much smaller than the number of legal moves.

You also say 8 sizes. Do you mean rotations and color-inversion? There's no
need to do it 8 times. Looking up all the rotations and color-inversions at
once takes only marginally longer than looking for a pattern in a specific
rotation, so that would waste almost a factor 8.

I agree that it matters how many patterns you have and how big they are. But
only up to a limited point. For a small number of small patterns like I had
in Goliath (1650 patterns of 5x5) I used a 5-point hashing followed by
linear bit-mapping, which was pretty fast. Probably hard to beat in speed.
The more sophisticated pattern-matcher is slower for these numbers, but it
scales to large numbers without getting much slower. So then I don't think a
large number of patterns affects the pattern-matcher other than in memory
usage.

Although I don't see use for an 8-million pattern database in most Go
programs, I suppose it might get to something like that when you try to do
automatic pattern learning. I expect the number of patterns more to be in
the neighborhood of several ten thousands, and maybe hundred thousands for
storing joseki. Goliath had a separate pattern-matcher for a few thousand
joseki moves, but I think it should be possible to make something that suits
all purposes. Also I'm of the opinion that there are different patterns for
different purposes, so I'm expecting to use it more than once per move on
different sets of patterns.

I must admit I've never looked at the GNU source and I have a
pattern-matcher that I think is fine without getting infected by the GPL
virus, but I was just wondering what it would take to make something useful
generally available.

> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx]On Behalf Of Frank de Groot
> Sent: Tuesday, October 26, 2004 19:15
> To: computer-go
> Subject: Re: [computer-go] Pattern Matcher (was M.Boon-Library)
>
>
> From: "Mark Boon" <tesuji@xxxxxxxxxxxxxxxxx>
> >
> > To be honest though, I have no idea how my pattern-matcher compares in
> > speed
> > with others. So my first question is what would be good metrics
> to compare
> > them?
>
> I think it matters, speed-wise, how many patterns you intend to store and
> what size(s) they are. My pattern matcher can go though 5 games in 1 sec.
> and find any pattern around a legal move in that time, including chain
> liberty metrics and stone metrics.
>
> This translates to about 2 million lookups/sec. , looking at 8
> pattern sizes
> around every legal point, including string liberties and string sizes of
> adjacent chains.
>
> The patterns vary in size from very small to the size of the
> board and the
> database size is 8 million.
>
> With all optimizations implemented I think the speedup could be 3x but at
> the moment it isn't worth it.
>
> When you want a simple database that has no more than a few thousand
> hand-coded patterns, I would say, use the GNU Go source.
>
> _______________________________________________
> computer-go mailing list
> computer-go@xxxxxxxxxxxxxxxxx
> http://www.computer-go.org/mailman/listinfo/computer-go/
>

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/