Playing Lately: Go
I recently got hooked on playing (and watching) Go on an the "Pandanet" Internet Go Server. It's fun, it's free, and it's one of the most challenging and entertaining board games I've ever played.

For those not in the know, Go is to Asia what Chess is to Europe. Except Go is approximately a thousand years older. The rules are much simpler than chess. You play on a (usually) 19 x 19 square grid. You place stones on the intersection of lines on the grid. You alternate turns with the other player (one plays white stones, the other plays black). Your objective is to surround as much territory (empty grid intersections) by your stones as possible - well, more than your opponent. Once stones are placed on the grid, they don't move (unless captured).

Stones of the same color that are next to each other (horizontally or vertically) are connected and form an army. That army lives or dies TOGETHER. An army of stones is captured if it has no empty grid intersection next to any of its stones, and the captured stones are worth one point to the opponent at the end of the game (the same as surrounded empty grid intersections).

And that's pretty much the rules. There are some exceptions and special cases - like the rule of Ko which prevents players from going into an infinite loop alternating capturing of a single stone. But the rules are gloriously simple, yet infinitely tricky to master.

I was first introduced to Go in college. As part of a course in advanced Artificial Intelligence, we had to learn how to play Go, and write a program to play an intelligent game of Go. Part of our midterm and final grade was determined by pitting the student's Go-playing programs together in a tournament. The student who's program won the tournament got an A ... the second place winner got an A-, third place got a B+, and so on. It was a small class, and I think you were guaranteed at least a C if your program played a better-than-random game.

What makes Go so interesting for AI is that it's not as tractable to "brute force" searching as chess. In chess, there are only a handful of valid moves available in the mid-game, and most of those can be discarded early in a search as being "unproductive." (It's through a technique called "minimax" with Alpha-Beta pruning...) That allows the computer to "play" the game virtually several moves ahead, which is better than most players (and competitive, nowadays, with the grandmasters of the game).

On the other hand, in Go the search space is HUGE and it takes a long time for many moves to be clearly identified as "good" or "bad." The first move on the Go board has 19 x 19, or 361 possible moves. The second move has 360 possibilities. And so forth. So to exhaustively search four moves ahead from the very first move, that's 361 x 360 x 359 x 358 total moves that have to be evaluated.... almost 17 billion moves! So Go-playing programs have to use other, "fuzzier" tricks, and still can't play much better than a beginner.

So it's still a human-dominated sport. The bad news is, it's tough (especially here in the U.S.) to find someone who knows how to play Go and is willing to play. Naturally, the Internet comes to the rescue.

I actually played once while still in college (and the Internet Go Server was a "brand new thing.") It was still largely a TelNet operation - I don't know if I had a client program or not. I ended up playing a Korean. He even warned me of mistakes I was making in my game, but I couldn't see what I was doing wrong and made the mistakes anyway. Needless to say, he cleaned my clock.

So I guess it took me over a decade to get up the nerve to try it again. :) I still suck, and still get my clock cleaned when playing non-beginners. But the neat thing about the IGS and the client I'm using is that I can watch far-better players playing their games (including broadcasts of professional tournament games), participate in chat to kibbitz with other observers about the game (VERY helpful, as some players will explain why certain moves were made, etc.), and even call up a "trial" board of the current game in progress to experiment with various moves before committing. You can also save complete (or incomplete) games to play them back to study them.

This is nothing too spectacular for players who have been using Chess clients for a long time, I'm sure. But it's nifty, free entertainment :)

And now... here's the zinger.

I wonder if it would be possible to put together a similar "Go Playing" tournament for AI programs. Maybe using Python or something. Keep it all open-source. Players upload their AI, and it gets run on a server. The master program would have to use it's "best guess" to determine scoring at the end of the game (one of the OTHER problems with Go that doesn't exist in chess... it is hard for the computer to even determine the game's score accurately, let alone analyze a position...)

I'm WAY too pegged for time to do this anytime soon. But it's an interesting thought. Is there anything already like this out there?

Labels: Mainstream Games

- posted by The Rampant Coyote @ 11:20 PM (Permalink)