My Friday Night Files

A great site by Jan van Rongen. It's not new, just new to me... It's amazing the different takes people have on the same game...

Go in the mainstream english press

I came across this article googling around for go stuff. It's unusual to see go coverage in english except at specialist sites (which are understandably biased in their coverage). Despite some trying, I've had no luck crafting a google query that catches anything significant --- mainly because go is such a common word on the internet and in press writing.

An implementation plan

If I'm going to write a computer go player, I need a plan. Plans drawn at this stage are inevitably only approximations, but here's my current plan:

• Infrastructure – the framework to hang the rest on
  • SGF parser
  • SGF writer (simpler that the parser since it only needs to handle the properties I'm actually using)
  • a graphic goban (so i can play the program)
  • GTP client (so I can play my program against other people and other programs)
  • GTP engine (so i can organise play-offs)
  • test suite (so ease debugging)
• Opening: a classical opening book, assembled from pro and senior-amateur games. Also code to handle symmetry.
• Mid-game: a genetic algorithm prioritising a list of relatively complex template patterns.
• End-game: a theorem prover, perhaps along the lines of gotools, but with incremental additions of knowledge to the database as positions are proven safe/unsafe.

One advantage of have separate beginning, middle and end games is that I can develop, test and debug them separately.

GNU Go wins

For the first time ever I won a couple of games against GNU Go with only 2 stones handicap. Of course, now I've boasted about it I'll have a run of bad luck.

I'm certainly getting better, but I'm not entirely sure which of my go-related activities is having the big effect, whether it's playing in person (which I'm doing once every week or two at a local go club), playing against bots (mainly GNU Go and igowin), studing go gome (which I haven't done much of for a couple of weeks), playing against real people (maybe two games twice a week) or even reading computer go related papers and planning my own system. Probably a combination of all of them.

GNU Go: http://www.gnu.org/software/gnugo/gnugo.html

igowin / Many faces of go http://www.netcom.com/~fotland/manyfaces.html

Computer Go: an AI Oriented Survey

I've just finished "Computer Go an AI Oriented Survey" by Bruno Bouzy and Tristan Cazenave. A very long survey, packed with so many details that I suspect I'll need to reread it in a week or two. As well as surveying a wide range of techniques used to tackle go, it also discusses some of the representations used by specific implementations.

There were quite a few interesting pieces about the end game, and I shall have to read some of the primary papers (which all seem to be listed in the very extensive bibliography).

I was surprised both at the lack of genetic algorithm approaches used with patterns (as opposed to neural networks) mentioned and also at the fact that all researchers seem to be opting for light weight patterns rather than complex patterns, both of which seem promising to me.

The final paragraph contains a very interesting explanation for the wide gap in perceived strength of go programs: that human player can learn the faults of a computer go player over a series of games, and systematically exploit them. Whereas a human player quickly learns in at least a shallow sense to fix faults as they are repeated exploited (or at least alters play to fight their exploitation), computer go players are static and cannot adapt themselves.

Computer Go an AI Oriented Survey: http://www.ai.univ-paris8.fr/~cazenave/CG-AISurvey.pdf

Home page for Bruno Bouzy: http://www.math-info.univ-paris5.fr/~bouzy/Go.html

Home page for Tristan Cazenave: http://www.ai.univ-paris8.fr/~cazenave/

An Improved Safety Solver for Computer Go

I've just read "an improved safety solver for computer go" by Xiaozhen Niu and Martin Müller, describing their work on the program 'explorer.' Focusing entirely on the end game, it seeks to prove that safe groups are indeed safe. Building on the work of Benson (I _really_ must track down a copy of that paper), and develop new algorithms for complex regions using merging to join them together. Very interesting stuff. I think part of the reason I find it appealing is that it is proof based rather the heuristic.

Their methodology seems a little unusual, in that they are building what is essentially a theorem proving tool, but only trialling it on positive examples, which seems little unsafe. Maybe I missed something or they discuss it in a different paper.

They introduce their algorithms in pseudo-code, which is convenient.

This kind of approach seems very appealing to me, perhaps because such non-heuristic work seems more solid than other work I've read, a better base to build upon.

The Computer Go Group at Univresity of Alberta: http://www.cs.ualberta.ca/~games/go/

There is death in the hane

This is a proverb I seem to regularly loose sight of, before being re-taught by various opponents, both human and robotic (igowin seems particularly good at teaching me this lesson). Hopefully by naming my account after the proverb, I'll stand some chance of remembering it.

I suspect that my problem is a symptom of my difficulty drawing a line between strategy and tactics, too often I play an attachment without really considering whether I mean to start a fight and my opponent immediately answers with a hane and I suffer a loss. The loss isn't necessarily the stone I attached with, of course, but it's there somewhere.

igowin / Many faces of go: http://www.netcom.com/~fotland/manyfaces.html

Some thoughts on rules

I've been thinking about rules and rulesets in go.

A plurality of rulesets is unfortunate, in that it significant complicates the problem, giving several targets to aim for when building a computer go player. Fortunately few, if any, computer go players are sufficiently advanced for differences between rulesets to become a significant factor. Also, the fact that there are several rulesets potential gives computer go researchers and others choices about which rulesets to use.

Many computer go players choose to ignore certain rules, including avoid capture by seki and even ko. Noting but not modelling certain aspects of the problem is of course a classic feature of decomposition-based problem solving styles used in computer science and mathematics (and one which I'm sure my system will eventually have, once I have a system to have such features).

Personally I'm a fan of the New Zealand rules, because: (a) they're clearly stated; (b) they are stated in a way that suits my current purposes (i.e. in a mathematical way); (c) they don't have exceptions; (d) they don't have a history of change and (e) they are widely and correctly understood (perhaps largely because of the previous reasons). On the other hand, they exist in a cultural wasteland, there is a dearth of pro-level games on record using the New Zealand ruleset and none of the "famous" games have been played using them. This is not a serious issue, of course, if one is learning oneself, but if one is building a computer go player there are a number of uses for a larger corpus of pro-level games---pattern extraction, statistical comparisons and finding example end-games. It is also less of an issue if one is evolving (or proving) a system from first principals.

The New Zealand ruleset: http://homepages.ihug.co.nz/~barryp/rules.htm

Pattern matching in the game of go

I’ve been reading "pattern matching in the game of go" by Peter Drake, Jim Levenick, Loring Veenstra and Amanda Venghaus. The paper describes Orego, which uses variable-sized pattern matching with patterns extracted from expert games to play 9x9 games.

The details of the position normalisation are given and very interesting, using a lexical ordering. Unfortunately they seem to be closely tied not just to the board size but to the maximum size of the pattern. It also lacks wildcards and ignores ko.

It would be very interesting to see how much better the system would have worked with thousands (or tens of thousands) of training games rather than 100.

The caption to Figure 3 seems mangled.

"Our interpretation is that patterns extracted from recorded games are useful _assuming a reasonable opponent_. The single pattern players produced such bizarre moves that the games devolved into complicated fights, where patterns are not terribly useful. Rutquist (2000) reported a similar effect in experiments using a genetic algorithm to evolve players capable of defeating the relatively strong GNU Go program."

Peter Drake’s home page: http://www.lclark.edu/~drake/

Orego home page: http://www.lclark.edu/~drake/go/

GNU Go: http://www.gnu.org/software/gnugo/gnugo.html

SGF parser

I now have a javacc grammar for SGF files. It seems to work on the basics, but there are several things it doesn’t do yet, including (a) interpret character set information, (b) interpret handicaps (c) interpret end games and (d) do anything meaningful for comments, annotations or similar.

It has some very basic junit tests, but I need to do something more rigorous. I suspect that I need something to validate it against SGFC. Since SGFC is a c program, I suspect I’ll have to do this using ant or something.

Junit: http://www.junit.org/

Javacc: https://javacc.dev.java.net/

SGF: http://www.red-bean.com/sgf/

SGFC: http://www.red-bean.com/sgf/sgfc/

The go-playing program called Go81

I’m reading "the go-playing program called Go81" by Tapani Raiko, which uses a very interesting "ant" approach. This relies on a very local (3x3) pattern matching and simple stochastic search. Potentially the approach is very nicely parallelisable, but it doesn't seem intuitive to me (although I admit that I may be biased by the fact that this is the first serious go program I’ve read up on that I can beat easily, which may be prejudicing me against the approach).

The author discusses miai points (as something that may be leveraged by a future version of the game), which got me thinking about miai in terms of symmetry. The more I think about it, the more different forms of symmetry seems like an under-exploited feature of go and possibly an effective technique for reducing search space.

I've played the game online (presumably the Go81console variant), and noticed that the way to bet it is to not connect, just play very lightly and prevent it from forming eyes.

Tapani Raiko’s home page: http://www.cis.hut.fi/praiko/

Go81: http://www.cis.hut.fi/praiko/go81/

The paper: http://www.cis.hut.fi/praiko/papers/go_step.pdf