Friday, January 30, 2009

Go is like Crack

Go is something unearthly . . . If there are sentient beings on other planets, then they play Go.

-- Emmanuel Lasker, former World Chess Champion

I played Go for the first time a few months ago. Fortunately for me, I didn't play enough to understand how amazing it is. That changed this week, and my work-Go balance (Go-life balance?) has tanked as a result.

Go is an ancient, originally Chinese game played between two people with black and white stones on a 19x19 grid. The rules are really simple:
* black goes first
* you take turns putting stones on the vertices (or passing)
* if a connected group of stones is completely surrounded, it's captured
* the ko rule: you can't create the same board twice
* the game ends after two consective passes
* territory consists of empty vertices surrounded by your stones. Each vertex is worth a point, as is each captured stone. whoever has the most points at the end wins
* to make things fair, a komi compensates white for going second, usually by 6.5 or 7.5 points. The extra .5 ensures that games are never tied -- they have a binary outcome.

Chess is Baroque by comparison. Despite its simplicity, Go is very deep. The average chess position has about 25 legal moves available to the current player. A typical Go move is chosen from about 250. (Since it's a 19x19 grid, the first move can go on any one of 361 vertices.)

The real reason I started playing Go, though, isn't because of its simplicity, beauty, or depth. It's because Go is fun and because I learned that computers can't do it.

In 1999, IBM's Deep Blue beat Garry Kasparov in tournament chess. It was a giant machine with about 4000 special-purpose chips, dedicated to evaluating literally billions of chess positions per second. In other words, Deep Blue beat Kasparov by brute-force attack, thinking as far as forty moves ahead on some turns. A very intelligent person lost to a machine with lots of number-crunching power, but no intelligence at all.

Go is not like Chess. There are simply too many possibilities for any kind of exhaustive search. Like Chess, humans play it with advanced pattern recognition and and with directed strategies. Go differs from other games, however, because humanlike intelligence seems to be the only way to play well. Humans balance lots of difficult trade-offs -- is it better to keep playing in a part of the board with lots of activity, or to jump away and stake out a territory claim somewhere else? Is it better to go for secure territories along the sides of the board or influence over the center? Better to finish an impenetrable fortress or to branch out and make a bigger, more porous one? Questions like that take experience, intuition, and lots of pattern recognition to answer well. They can't easily be forced with faster algorithms and bigger supercomputers.

The best Go-playing programs today are using Monte Carlo sampling, like the stuff I blogged about earlier. Running on computers three orders of magnitude faster than Deep Blue, they're on par with skilled amateurs. Earlier this month, one program became the first to defeat a professional Go player in a tournament match--by accepting a massive nine-stone handicap. For now, Go is a game where real intelligence isn't just helpful, but required. There are few others like it.

Go is simple, yet radically open-ended, and it seems like a uniquely human game. Could it be AI-hard? We'll find out. Lots more info and links at the Stanford Go Club. I would write more, but the night is young, and it just became my turn to place a stone.

1 comment:

shuyu ding said...

fascinating. we need to play go sometime.