Re: [computer-go] Pattern Matcher

[Vincent Diepeveen <diep@xxxxxxxxx>]

Hello Frank,

It doesn't matter how good it predicts moves. The only important question is: 

"At what speed can you predict for unknown position X the moves"

It's not even interesting if your code is inefficient. We sure will manage
as professional programmers to change the amateur coding to faster code.
Speedups of a factor 5 of amateur code are not uncommon.

But some indication would be nice.

In fact bigger speedups are possible. Last few days i helped a biologist
(evolutionary researcher) with some software. The program trivially is just
busy searching trees and constructing all kind of floating point matrice.

A single indicative test takes 2 months.

After some optimizing it still is dead slow. The 2 months back to 1 month.

Now other software using a more 'guessing' approach to form the
evolutionary trees is doing the same job in 30 seconds.

A speedup of a factor 3600 * 24 = 86400.

So there is hope when it is slow. Please tell us what you do in order to
get a score assigned list (of course unsorted, during the search you simply
pick each time the highest score out of it. Though that is O(n^2) for the
entire list it is sequential code which doesn't get mispredicted by
processor and if you have a cutoff it is just a single O(n)). Called
Picksort. For a dumb implementation of it see GNUCHESS 1988 (4.0, do NOT
confuse it with the crippled gnuchess 5.0).

At 16:27 8-11-2004 +0100, Frank de Groot wrote:
From: "Vincent Diepeveen" <diep@xxxxxxxxxxxxxxxxx>
>Subject: Re: [computer-go] Pattern Matcher
>
>
>> Let's summarize: you work on a module that can order moves hopefully
>better
>> as it regurarly picks the correct moves.
>
>Well.. Perhaps I have to be more clear.
>My pattern module is the result of a Fuseki opening library.
>I generalized it to patterns.
>
>To my surprise the module was able to predic on average 15% of all pro moves
>in unseen games.
>As I do not play Go, I started to analyze what is happening.
>It turned out that the module had become an expert at Joseki and following
>up on Joseki.
>In the extreme, it knew rare Joseki, it suggested the "correct" moves in
>huge patterns that only occured a dozen times in half a million games etc.
>
>It also knows "Tesuji" and "Good shape".
>
>I do not know exactly what this is good for, in a Go program.
>I know it is a very good Fuseki & Joseki module, as it predicts 50% of pro
>moves during those stages on average.
>
>I know from chess that opening books are considered important.
>I discovered that in Go this leads to very high pro-prediction during the
>first 100 moves.
>This lead me to believe that this pattern system is very relevant, as the
>opening stage in Go is the stage where the most pointns are secured and
>"reading" is just about impossible. When there are 12 stones on the board,
>statistical analysis results are more useful than search.
>
>My pattern system will first and foremost be used to secure a very good
>first 50 moves.
>Making sure that the strategic part of the opening is very good.
>
>For the rest.. No idea yet.
>The smallest pattern matcher is very fast, and it is possible that I put the
>most important patterns in the (future) cache.
>In that case it may be interesting to use in search, but I am sceptical.
>
>I intend to harvest potential eye shapes and potential connectivity patterns
>and use that in search instead.
>
>> If i want to do it say 100000 times a second at an opteron 2.0Ghz, can i
>do
>> it with your software?
>
>The big wins in a Go game are achieved at the opening stage.
>Go is totally different from chess in that in Go, you slowly surround
>territory.
>My pattern system knows how to do that in the opening.
>
>The opening is based on simple Fuseki/Joseki books in current Go programs,
>and heuristics.
>
>When my tactics module is as strong as the tactics module of the
>competition, my pattern module will wipe the floor with them because it will
>play a hell of a better Joseki and good shape. It will kick the crap out of
>any manually entered pattern system. But of course that is a religious
>opinion, just as yours are :)
>
>I want to stress that you might know much about computer chess, but you have
>never demonstrated to know the first thing about computer Go :)
>
>
>_______________________________________________
>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/