Re: computer-go: Machine Learning and Go

[Konstantin <konst@xxxxxxxxxxxxxxxx>]

On Thu, 25 May 2000, Thore Graepel wrote:

> Hello everyone,
> 
> we have just completed the first stage of our project "A machine
> learning approach to the game of go" and have summarised the results in a
> little paper.  You can download the paper from
> 
> http://stat.cs.tu-berlin.de/~guru/publications.html
> 
> It is called "Go, SVM, Go" and we submitted it to NIPS2000.
> 
> I thought you might be interested in this because we use a new approach of
> converting a graph-based representation into feature vectors that enable us
> to learn some aspects of good and bad "shape". These methods are then used to
> learn good Tsume-Go moves and to play on a 9x9 board after learning from game
> records. I would be delighted to receive some comments and suggestions. Also, if
> you have any questions, please feel free to ask.
> 
> Thore
> 
> -- 
> Thore Graepel | Technical University Berlin
> FB13 (CS) | FR6-9 (STAT) | Franklinstr. 28/29 | 10587 | Berlin | Germany 
> +49 30 314 22577 (phone) | +49 30 314 25901 (fax)
> guru@xxxxxxxxxxxxxxxxx | http://stat.cs.tu-berlin.de/~guru
> 



Excellent work! I am working along the same lines myself (ie. graph theory
and "CFG" applied to go) although I am not into machine learning.
The construction of your "CFG" is by the way a standard construction in
graph theory called a contraction. A good reference on graph theory (although
quite advanced) that treats contractions and minors is Diestel, R.: Graph
Theory. GTM 173 Springer Verlag 1997.
Although I think that graph theory in general is the right tool to treat
go, I have found "CFG" to be inadequate for some situations like seki
for example.

Here are some comments on your paper:
1) On page 1 "Trump and Taylor..." should read "Tromp and Taylor..."
2) On page 3 the formal definition of CFG should be made more exact. See
eg. Diestel for a precise definition. You mention nothing about deleting
multiple edges between supernodes of different colour.
3) On page 4 "living groups are represented by a coloured node with two
dangling empty points". This is not entirely true. For example
e-b-e-b-e is alive while e-b-e-b and e-b-e-w<ee are of course not. (e
stands for an empty node, b for black e for white. Use your
imagination...) A false eye is not always false!
4) ********* I did not understand section 2.2 at all. More precise
definitions are desirable, especially for RSF.
5) On page 6, game record a) move 29 appears twice and move 39 is missing.
6) It took me a while to understand what SVM stands for. Maybe you can
include the abbreviation when you mention support vector machine in the
abstract.
7) On page 6 "The test of the pudding..." should read "The proof of the
pudding..."
8) On page 7 "International Go Server..." should read "Internet Go
Server..."
9) On page 7 "We would like to provide..." should read "We provide..."



PS. I find move 16 on game record b) quite an impressive move for a
computer to make. Maybe there is hope for a good go program after all...


Please keep us informed of further developments.
/K