Learning Go and Computer Go
A blog about learning go and learning computer go. A go beginner tries to improve his game and use their software engineering skills to build a computer go player. Entries about their go reading, computer go reading, go playing, go improvement, go concepts (seki, ko, miai, etc) and progress building the computer go player.
Saturday, November 11, 2006
Sunday, July 31, 2005
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.
Monday, June 27, 2005
Sunday, June 26, 2005
About problems in generalizing a tsumego program to open positions (1996) and Optimizing GoTools' Search Heuristic using Genetic Algorithms (2004).
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?
Saturday, June 25, 2005
As mentioned previously I've been thinking about a go protocol, a protocol that is suitable to use everywhere GTP is plus:
- Ruleset negotiation
- Handicap and komi negotiation
- Extendable (extensible for you Americans) for unusual boards (large sizes and so forth)
- End-game negotiation for the liveness of groups (and thus score)
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:
- It has a clear objective (communication between a master and a computer-go engine)
- It does what it needs and as little as possible else (unnecessary commands in the reference implementation as namespaced out)
- It is as simple as possible
- It leaves out the issue of haggling over rules (Chinese/Japanese/New Zealand/etc), komi and handicapping.
- It leaves out the issue of arranging who is to play
- There is a widely available, high quality reference implementation (GNU Go) which is useful in itself
- It is clearly better than the protocol it replaced (GMP)
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.