I've been giving some thought recently to what a finite state machine for the Japanese rules of go would look like. The more I think about it, the more complex encoding the full rules will be.
Which isn't to say that trying to build an FSM is necessarily a bad thing...
GoBase is a website run by Dutch go player Jan van der Steen. In comprises three main parts, a large and actively maintained database of games (including even the minor rounds of current contests), a set of life and death problems and news stories taken from a diverse range of places, including the computer-go mailing lists, recent contest results and articles.
Personally I find that the articles are the best part of the site, and recent ones such as Pieter Mioch's world amateur go championships give an insight into the go world that game results and life and death problems (both available elsewhere) don't.
The first paper is literally a statement of problems, whereas the second reports on using GAs to tune the computationally expensive answer to the problem, i.e. picking values for using in the heuristics.
The results of using the GA were actually quite reassuring. Improvements of 8-20% over the hand-tuned solution are reported.
This is an interesting paper about the challenges of finding a good evaluation function for genetic algorithms. They use GAs to evolve a two populations, tested against each other. Interestingly there is this quote:
For Nim, a perfect solution can be found after about 150 million games with parameters tuned well. Typically, success in the competition for Nim is much more balanced between the two population during most of the tun. The first population spends much time trying strategies which employ an incorrect first move. Such strategies can never be perfect, but can be difficult to beat if most other moves had been optimised. Eventually, a strategy employing a correct first move is optimized to the point of perfection.
Evolving a player for go could avoid this problem by using randomised starting points for a significant number of games. This would encourage the evolution of strategies that are truly good in the middle and end game, irrespective of their performance in the opening, thus splitting the problem in two. Maybe random games from an archive could be used as starting positions for solving the end game, splitting it into three?
As mentioned previously I've been thinking about a go protocol, a protocol that is suitable to use everywhere GTP is plus:
The whole concept of "negotiation" is, of course, foreign to GTP, in which there is a controller (which as the name implies is in control) and an engine (which has almost no control).
The other issue is that computers, having effectively infinite patience equalled only by their stupidity, are not very good at negotiation. The issue of end-game negotiation is only of the perennially verbose yet unresolved subjects on the computer-go mailing list (see for example this thread). This undermines my confidence that computer-go programs, left to themselves, will ever reach a consensus.
If they can't be left to themselves, then suddenly we don't have a two-party protocol, we have a multi-way protocol, which opens up new vistas, in terms of complexity and implementation effort…
... a complete can of worms.
I've been reading the GTP (Go Text Protocol) spec (version 2, draft 1, July 2002). It's a tool that everyone seems to use to communicate with computer-go engines, whether it's GUIs communicating with engines, servers communicating with engines or scripts that play engines against each other (twogtp and friends).
I've been thinking about why it's done so well and is so widely implemented:
These appear have completely outweighed the fact that the sections seven and nine of the spec are completely empty and the last six commands are completely undocumented. It also doesn't handle boards above 25x25, to be fair, few if any other programs do either, mainly because the standard notation breaks down when the letters A-H and J-Z are all taken (I is not used).
This got me to thinking whether it might not be possible to define a protocol that covered a broader range of problems.
I've just read "Monte Carlo Go" by Bernd Brügmann, which uses simulated annealing to evaluate positions when playing go. The system is not particularly effective, mainly because of the very slow cooling required to play well.
I know it goes completely against all the theory behind the solution, but I can't help but think that maybe one could do better than random plays. I particular, it seems to me that the best ranked positions from not n are likely to at least be candidates for move n+1.
Bayesian Pattern Ranking for Move Prediction in the Game of Go by David Stern, Ralf Herbrich and Thore Graepel at Cambridge / Microsoft uses nested patterns with learnt priority (rank) to "obtain a probability distribution for professional play over legal moves in a given position." Trained using a corpus of 20000 professional games they also discuss building a million game corpus of variable-level games (presumably games played on internet go servers?).
It seems to me that the problem they're setting out to solve isn't the one they need to solve―at the end of the day generating reasonable moves is the goal, and pro moves are only an approximation. There is also the problem that the system assumes that the board positions and the opponents' moves are reasonable. There were some clear attacks against early computer chess players which worked by playing unreasonable moves to get out of the opening book.
Another issue is the shape of he pattern. The patterns are (effectively) circular, whereas there are many, many, go proverbs suggesting that they should be biased towards the board edge (where territory is to be made) over the center.
I recently got an account on the IGS go server. It seems very good, there always seem to be some high dan games to watch, and no shortage of players lower down the ranks to test my metal on.
When signing up they sent me a rather intimidating email which I've included below. On closer inspection, it turns out that the rules down seem to be particularly onerous, but it certainly looked intimidating. Interestingly, the message doesn't appear to be on the website, so I'm posting them here. Some parts are anonymized:
A recent comment suggested that I use GoGui as the starting point for my implementation.
GoGui is a GTP <==> GUI toolkit implemented in Java and licenced under the GPL. Reusing someone elses code has great appeal, of course, but it's not entirely clear whether it'll do what I want it to do. In particular it's not clear at first glance whether the model of a game and a move is sufficiently flexible.
I'll have to check it out...
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:
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
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/
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/
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
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
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/
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/
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
