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.
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.
Tuesday, June 14, 2005
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.
Saturday, June 11, 2005
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.
Wednesday, June 08, 2005
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:
From: IGS PANDANET SERVER
Date: 8 Jun 2005 15:39:48 +0900
Subject: IGS registration, _______
This is an automated message to confirm that your IGS Pandanet registration
was successful. Please read this letter carefully.
Welcome to IGS Pandanet. If you have received this letter, you will know
that you have successfully registered. Your password is contained within
this letter. You may change your password at any time. If you do not use your
account within 20 hours if its being registered, it will be automatically
deleted. If your account is still treated as a guest account after entering
IGS PandaNet, it probably means you incorrectly entered your login name,
or your account expired, and you will have to _register again_ (please DO NOT
send email, or a COPY of this registration letter back to IGS Pandanet saying
your account does not work, or is being treated as a guest account --- simply
Sometimes you may experience problems connecting to IGS Pandanet. If this is
the case, try the alternate port number, which is 7777, instead of 6969. You
may also try using the IP address, 18.104.22.168 6969. We recommend using
the IP numbers 22.214.171.124 6969 instead of the 'symbolic' (name address)
Example: telnet igs.joyjoy.net 7777
telnet 126.96.36.199 6969 (This is the IP address)
telnet 188.8.131.52 7777 (This is the IP address)
** Again, we recommend using the IP numbers 184.108.40.206 6969 instead of
the the 'symbolic' (name address) igs.joyjoy.net 6969
**READ this registration letter _carefully_. All users are expected to
know the usage rules, terms, and conditions. All users are also encouraged
to read the 'motd' (Message Of The Day), upon entering IGS Pandanet. The motd
often contains important announcements and information concerning coming events.
To read the motd at any time, just enter: help motd
If you are new to IGS Pandanet, enter help for a list of the basic starting
You can 'ftp' client software with a graphic interface for use with
and other general Go software from the Go ftp archive site:
If you use a WEB browser, use:
If you are using a PC, we recommend the 'Panda Egg', which is a client with
a graphic interface for IGS Pandanet. The 'Panda Egg' comes in four language
versions: English, Japanese, Korean, and Chinese.
If you are using UNIX or Linux, we recommend 'xgospel'.
If you are using a Macintosh, try 'goservant' or 'macgo'.
If you need help with ftp, enter help ftp the next time you are on
For support and help with client software, please contact the client writer
for the client you decide to use, and not the IGS Pandanet administrators.
The IGS Pandanet administrators do not provide client software assistance.
The clients are not written by IGS Pandanet. Clients for use with IGS Pandanet
are written by Go enthusiasts for the convenience of other Go players.
Some client writers request a small fee for their work. Fees are paid to client
writers and do not go to IGS Pandanet.
IGS Pandanet administrators do not correct games or alter game results.
It is the responsibility of each person to carefully read the help files before
playing and scoring a game. Also, IGS Pandanet administrators do not become
involved in or settle disputes between players. Therefore, please do not ask
them to change game results or settle disputes.
** NOTE: Not all players on IGS Pandanet speak or understand English.
Therefore, many non-English players do not ask for a game, but will instead
simply send you a game request without asking if you are interested in playing a
game. Please be aware of this fact and do not become upset if you receive
random game requests. Some Asian software programs will send automatic
responses in English to specific questions, statements, and situations, but
this does not necessarily mean that the person using that client speaks
For your information, IGS Pandanet ranks are stronger by about 2 - 3 ranks over
most other rating systems. Please take this into account when considering
setting your rank on IGS Pandanet.
1) To set your rank on IGS Pandanet, enter:
2) To change your email address on IGS Pandanet, enter:
Note: Your email address may be deleted if it is found to be outdated, and
your account will be treated as a guest account until you update the
address. To update your address, see: help addresshchange
1) Unused accounts are automatically deleted after a certain number of
days. For that number, enter: uptime
2) To change your password on IGS Pandanet, enter: help password
3) You can mail yourself any help file from IGS Pandanet with:
mail me filename
Note: 'filename' is the name of the help message or announcement
We hope you enjoy using IGS Pandanet.
[rev. April 1, 2002]
** OWNERSHIP AND ACCEPTABLE USE OF I.G.S. **
IGS Panda Net ("IGS") is owned and operated by PandaNet, Inc.
Panda Net is located at: Shin-Kokusai Bldg. 3-4-1 Marunouchi Chiyoda-ku,
Tokyo 100-0005, Japan.
The users of IGS represent a variety of countries, languages,
cultures, and personalities. It is easy for misunderstandings to occur.
All users are asked to be patient with others, and to be polite at all
times, especially when using the group communication features of IGS.
Please remember that some IGS users are children. Users should not make
any communication or message on IGS which is threatening, abusive,
disruptive, vulgar, obscene, or unlawful, or which encourages conduct that
would constitute a criminal offense, give rise to civil liability, or
otherwise violate any local, state, national or international law. Use of
IGS for promotion or advertising of commercial products or services, or
promotion or advertising of any other Go-server (or any other internet
site, facility, or WWW page), without the express, written consent of the
IGS adminstrators, is prohibited. Statements made by the users of IGS do
not necessarily reflect the views or opinions of Panda Net, and Panda Net
disclaims any responsibility for all such statements.
In general, internet users are welcome to share the use of IGS,
unless the user's authority to access IGS has been suspended or revoked.
Panda Net reserves the right, for any reason whatsoever and at the absolute
discretion of the IGS administrators, to restrict certain capabilities
(such as "shout" and "kibitz") for any IGS account, and to temporarily or
indefinitely suspend or revoke the authorization of any person or persons
to access IGS. Unauthorized access to IGS may subject the offender to such
criminal and civil liabilities as may be provided by applicable law.
From time to time, Panda Net or IGS may sponsor or co-sponsor certain
activities on IGS designated as "special events" (such as tournaments,
professional competitions, or lessons). The use of IGS for these special
events is intended for the personal benefit of IGS users only.
Reproduction or retransmission of any "special event" on any other internet
or bbs server, without the prior written consent of the IGS administrators,
is prohibited. Panda Net reserves all legal rights and remedies in respect
to any such unauthorized reproduction or retransmission. We hope that all
IGS users will enjoy these special events!
** LIMITATION ON LIABILITY/ DISCLAIMER OF WARRANTIES **
IGS IS PROVIDED ON AN "AS IS, AS AVAILABLE" BASIS. PANDA NET INC.
MAKES NO WARRANTIES, EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO,
THOSE OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE, WITH RESPECT TO
THE USE OF IGS, IGS-RELATED SOFTWARE OR RELATED DOCUMENTATION, OR WITH RESPECT
TO THE ACCURACY, RELIABILITY, COMPLETENESS, OR CONTENT OF ANY INFORMATION
PRESENTED ON IGS. UNDER NO CIRCUMSTANCES, INCLUDING NEGLIGENCE, WILL PANDA
NET BE LIABLE FOR ANY INCIDENTAL, INDIRECT, OR CONSEQUENTIAL DAMAGES THAT MAY
RESULT FROM THE USE OF, OR INABILITY TO USE, IGS. BECAUSE SOME JURISDICTIONS
LIMIT OR PROHIBIT THE EXCLUSION OR LIMITATION OF LIABILITY FOR INCIDENTAL
OR CONSEQUENTIAL DAMAGES, THE ABOVE LIMITATION MAY NOT APPLY TO IGS USERS
IN SUCH JURISDICTIONS. IN SUCH JURISDICTIONS, PANDA NET'S LIABILITY WILL BE
LIMITED TO THE GREATEST EXTENT PERMITTED BY LAW.
Use by any person of IGS constitutes acceptance by said person of the
terms and conditions of this policy statement. This statement is stored in
a "help" file at IGS. IGS users may review the current version of this
statement by using the "help usage" or "mail me usage" commands.
** You can change your password to one easier to remember with the
'password' command. On IGS Pandanet, type help password
Do not lose or forget your password. It is your responsibility to know
your password and to make backups. Administrators do not provide
passwords upon request.
SAVE this registration letter. It contains information you
may need later.
The password for the account _______ is ________
Head office (JAPAN), Noguchi Manabu
PANDANET USA, Mark Okada
PANDANET Europe, Jan van der Steen
Tuesday, June 07, 2005
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...