Computer Go

Unlike chess, computer programs playing Go still have a long way to go. Their current level of play is somewhere between 5 and 10 kyu (weak amateur play), with the playing strength dropping significantly as you learn the weaknesses of a particular program.

Writing a strong Go program is one of the most challenging and exciting problems in computer science. It’s a well-defined problem, expert knowledge is readily available, progress is clearly measurable, and yet programs are still weak. If we can’t make progress on such a clear-cut problem, how can we trust computers to excel in other domains?

Part of the challenge is that the approach that worked so well in computer chess doesn’t work in Go. Brute force search worked well for chess thanks to a relatively simple evaluation function combined with a limited number of moves at every turn. In Go, the average number of legal moves is 200 rather than 38, and there’s no simple evaluation function. Also, the visual nature of Go helps humans more than computers. However, while brute force can’t be applied directly, we think some of the lessons learned from chess can be applied to Go.

Update: The preceding paragraphs were written before the success of Monte Carlo based programs. Using massive computing power, the strongest programs are now close to professional strength on 9x9, and have won 7-stone handicap games against professional players. SmartGo on the iPhone is using our own Monte Carlo engine, and we will be integrating that engine into the desktop program in future versions.

Read More About Go

The New York Times article by Katie Hafner talks about the challenge of writing a Go program, and mentions SmartGo as well as other programs. And did you notice them playing Go in the movie "A Beautiful Mind"?

This long article by Mark Athitakis in SF Weekly features Anders Kierulf as well as other Go players and programmers. The "Go Crazy" slant is unfortunate, but on the whole, it's interesting reading.