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

["David Fotland" <fotland@xxxxxxxxxxxxxxx>]

I think it depends a lot on what the patterns are to be used for, and
how may of them there are.  In Many Faces, I use patterns to suggest moves
for full board look ahead only.  Tactical move generation is hard coded C.
I only have about 2000 patterns (with don't cares like Gnu go, and extra
conditions
similar to Goliath).  I use an 8 bit hash and a linear search through one of
the 256 linked lists.  It's not very efficient, but pattern matching is only
about 1% of the runtime, so there is no need for further optimization.

My patterns are any size or shape up to 8x8, and are stored as three 64-bit
bitmaps.

I have an ASCII file format and a graphical editor.

Each pattern has a move tree attached for each side, not just a single move,
and
each move has a heuristic value associated with it.

David

> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx 
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx] On Behalf Of Mark Boon
> Sent: Tuesday, October 26, 2004 9:49 AM
> To: computer-go
> Subject: [computer-go] Pattern Matcher (was M.Boon-Library)
> 
> 
> One of the things I was planning for a second version of this 
> library was including a pattern-matcher. Not the one that is 
> in Goliath (it's fast but too cluncky), but a much better one 
> we had in the Tsume-Go program. I'm sure every existing Go 
> program has a pattern-matcher of some sort, and every future 
> Go program will need one.
> 
> 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?
> 
> Next what I want to bring up is of practical nature. Although 
> a pattern-matcher of stones is the essential core of a 
> pattern-matcher, to be really useful some other issues are 
> involved. The first one is storage. In the past I've always 
> stored patterns in files, but it's actually very cumbersome. 
> Nowadays I'd store them in a database. The second issue is 
> that of something I call 'extra conditions' attached to 
> patterns. Stone patterns only get you so far, I need to be 
> able to include information as 'this stone is not in atari', 
> or 'this point is a false eye'. Since the latter information 
> is very closely tied to the data structures of the Go 
> program, it's not easy to separate out the pattern-matcher 
> from this application-specific part.
> 
> The way these extra conditions are represented in my 
> application is by a simple string of the following form: 
> <letter-code><coordinate><operation-code><value> Some 
> examples are: L3,2>1 or e4,5!0 which would mean something 
> like: the stone at 3,2 has more than 1 liberties and the 
> point at 4,5 is not eye-space.
> 
> Anyway, at the moment I have some spare time which I could 
> put into making a good pattern-matcher available. But there's 
> little point if there's already a public one available unless 
> mine is substantially faster. So I'd need some way to 
> compare. Probably as important as the pattern-matcher itself 
> is a pattern-editor. Generally this takes more programming 
> time than the matcher, but here also the handling of the 
> extra conditions make it not so clear how to make something 
> that is generally useful.
> 
> I'd be interested to hear some opinions and/or ideas on this.
> 
> _______________________________________________
> 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/