Thu, August 01, 2002

Go much faster, much better

A New York Times article (free registration required) describes the complexities of creating a computer program that can play Go. Unlike the logical play of chess, where computers are able to beat grandmasters, Go is a game of pattern matching and intuition where casual human players can generally beat the best computer programs. Strong human Go players seem to be able to evaluate the board and intuitively make the best moves. The challenge in creating a computer Go player is that processing speeds are currently too slow and that evaluating the board is notoriously difficult:

In the course of a chess game, a player has an average of 25 to 35 moves available. In Go, on the other hand, a player can choose from an average of 240 moves. A Go-playing computer would take about 30,000 years to look as far ahead as Deep Blue [the chess-playing computer that five years ago not only beat but thoroughly humbled Garry Kasparov, the world champion at the time] can with chess in three seconds, said Michael Reiss, a computer scientist in London.

For a computer program to be able to play Go, we will need to greatly improve computer pattern matching techniques and probably create programs that learn from their mistakes. Perhaps someday this will be possible. In the meantime, let’s enjoy playing this ancient game.

The article also reminded me of a scene in the movie A Beautiful Mind (Recommended!). Early in the movie, the mathematician John Nash plays Go and gets frustrated at losing. In a deleted scene available on the DVD we’re shown that the experience motivated the real Nash to create his own game called Hex. He also is responsible for a mathematical proof that the first player should win the game. I need to figure out how to play this, too.

Where does trivial stupidity lead to?     Pi and a Beautiful Mind