I don't hate Microsoft - I just love freedom. Microsoft hates freedom. So we're enemies.

The Unique Problem of Go

Date/Time Permalink: 10/11/07 11:46:50 am
Category: Linux Gaming

A Go board I drew in POVray

This Slashdot article reminded me of one of my favorite games. It is about the continuing effort to try to make computers good at Go.

Go is an active topic in the free software community. There's the excellent GNU-Go engine, the CGoban GUI front end, and then there was Hikarunix, the Linux live CD devoted entirely to the game of Go. It is a shame to see that Hikarunix appears to have closed since this review was written. Here's the Wikipedia article on it. Damn, I'd be happy to host that distro myself, if anybody out there is connected to the project and reading this, and it's not too late.

I also blush a little bit whenever I hear a discussion of the difficulty of programming Go, because... I took a shot at it. This was back in my grasshopper days when I was tinkering with the SDL library and C. At the time, GNUGo was much slower, and I tried to make a one-piece engine and GUI front-end, that would be faster. It's fast alright, and it plays worse than a drunk monkey.

It was an experimental theory of mine. I looked at Conway's game of Life, the Go board, and thought, "What if you tried to make the computer play its pieces like a cellular automation?" And so, my Go game had no clue about how to win the game, but instead played according to a set of rules. It would evaluate each move with numeric values that were added and subtracted according to the rules, then pick from amongst the highest-scoring moves using a bubble-sort.

First, I coded an array of integer board position values, which gave a slight bias for playing along the fourth and third lines of the edges and corners. Then I made a huge algorithm which would sweep the board, noting which spaces were enclosed by a color, which stones were part of which group, how many liberties each group had, what influence each space had (i. e. if the nearest stones were all one color, even if it wasn't enclosed), and so on.

Then the rules. Like the crackpots who pursue perpetual motion, I was naively convinced that if I could put in the right rules in the right balance, decent Go playing would magically occur. Some of the rules were pretty easy to get right, such as not playing into one-stone atari and not filling in your own eyes. It could spot when it had the opportunity to capture a large group. And because I gave it an aversion to putting too many stones in one place, it tended to surround territory instead of filling in huge blocks.

But the rest of the rules faltered. Due to the subtle nature of Go strategy, or due to my own inability to do it right, I never got it to a basic strategy level. I was particularly frustrated at getting it to close off an opening in the event of a peep. It is also prone to obvious boners like playing a single stone right on the edge in the middle of nowhere or not recognizing a ladder, and it is woefully vulnerable to captures, particularly snap-backs.

Like I say, I was researching an idea. It is certainly a time-consuming little hobby...

If you're confused at the jargon I'm bandying about, the fantastic Sensei's Library is the place to start. It is a Wiki-like database of information for everything Go-related you could possibly imagine. The sheer size of the database helps to underline the point that Go is one flaming heck of a complex game.

If anybody else out there has been taking an individual stab at programming Go, do please talk about it in the comments. Maybe we could trade notes. I used to say GNUGo is good enough, but I have recently beaten it, which means that soon I'll be beating it regularly if I play it enough. Perhaps Go is just one of those things that computers weren't meant to be incredibly good at.

Update: According to Distrowatch, Hikarunix is discontinued. You can still get it from this download server.

I am going to try to find out more. Go really *needs* a Linux distro - the FOSS resources for it are scattered to the four winds, and a tight distro like Damn Small Linux (which is what Hikarunix is built on) is a perfect match. It really is valuable to both the Linux and Go communities to have it all on one iso, ready to boot.

Follow me on Twitter for an update every time this blog gets a post.
Stumble it Reddit this share on Facebook

suddenly the moon