[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: "Mark Boon" <tesuji@xxxxxxxxxxxxxxxxx>

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.)
Exactly :)
We all know that the average game is 250 moves I assume, I said I use 8 patterns..
Those 8 patterns are all matched in order of size, starting with the largest. When the largest is not found, it will try the second largest etc.

At some point I decided I hadn't ever seen a useful pattern that didn't have
any stones in them,
I found it very useful to place a stone in an empty corner :)
I do not play Go myself so I am not going to tell the program where to play in a corner. It finds that out by itself by statistical analysis of *empty* patterns..
I have sometimes harvested only patterns that had stones in them but the difference is just about nothing, as even a large pattern with 1 stone can have max. about a dozen or so invariant representations. Like I said I use million of patterns so it's irrelevant.


You also say 8 sizes. Do you mean rotations and color-inversion?
Nope.
I mean sizes. I said, the pattern sizes range from small to the size of the entire board.

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 already explained how my system works here (you complained about it actually).
I explained how cache latency compensates for keeping 16 versions of hash keys.


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.
5x5 patterns I can match against a multi-million database with incredible speed. About the speed of the bandwidth of the RAM. I would guess hundreds of millions / sec.
The only bottleneck is RAM access times, not CPU speed.


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.


That is what I am doing.
This is how my program predicts pro moves.



I expect the number of patterns more to be in
the neighborhood of several ten thousands, and maybe hundred thousands for
storing joseki.
I can't say what is what (Fuseki, Joseki, good shape etc) but with a few patterns you can come a long way, yes. I found that 8 million however is a nice compromise between various factors.

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.
I don't know. I worked an incredibly long time on my matcher but it is extremely versatile and extremely fast. And most of the time I spent on the *learning* module which is something completely differrent. The pattern system can store anything, like: "medium connectivity with one almost-sure eye, the smallest adjacent chain is 7 stones and there are 23 stones on these locations" (all rotmircolrev normalized).

With patterns of say 7 x 7 I would guess that the matching speed is tens of millions/sec., meaning it could be used in a search tree to help prune moves.

Harvesting the patterns is a nervous thing because I use 500,000 games to extract them from. Often, when it's done, I find a bug during the learning phase and I have to re-do the harvesting phase.


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