Friday, August 04, 2006

Computers Can't Play Go

When Garry Kasparov was beaten, to his furious humiliation, by IBM's Deep Blue chess computer in 1997, it left human players pondering their future. Draughts, Othello, backgammon, Scrabble: by the start of this century, each had been all but conquered by machines.

But don't worry. Almost a decade later, with Moore's Law still at work, there is still a board game in which humans reign supreme. The game is Go, an oriental game of strategy. It sounds superficially easy. The board is a 19 by 19 grid of intersecting lines. The pieces (called "stones") are black or white, and identical. Once placed on the board, they do not move (unless surrounded and captured) or change colour. The object is to use one's stones to surround as many blank intersections (called "territory") as possible. And that's about it.

Even the lure of a US$1 million prize for the first program to beat a human professional went uncollected after the deadline passed in 2000. No program has yet come close to meeting the challenge. Now, however, there may be a new attack on this outpost of humanity.
An Guardian article.