Computer Go
Computer Go

The year 1997 was a bad one for world chess champion Gary Kasparov -- defeated by Deep Blue, an IBM computer designed to play chess. This result might lead us to assume that go would also be an easy game for a computer to play well. Its rules are few and simple. Unlike chess, with its different pieces and complicated rules, go is played only with black and white stones of equal value, seemingly compatible with the binary nature of computers. The object of go is to control more territory than your opponent, so the best move in any position is simply the one that gives the maximum amount of territory -- a simple counting procedure, a chore computers excel at. But it is not so easy.

Indeed, fewer than 100 lines of computer code are needed to program a computer to play go. Add a few more lines to the program and the computer will be able to evaluate the amount of territory controlled by each side. But when it comes to tactics and strategy, the best go-playing programs are not much stronger than a beginner.

One reason chess can be programmed to such a high level is that it is essentially a tactical game in which material gain is important. The most sophisticated chess programs look ahead seven or eight moves to determine the best way to get a material or positional advantage. In go, however, material gains are strongly linked to strategic considerations. A tactical success, such as the capture of a large group in one part of the board, might actually be a game-losing blunder.

Another factor making go more difficult to program than chess is the size of the board. On the standard 19x19 grid there can be anywhere from 100 to over 300 possible moves to consider, so the number of possible variations is far greater than in chess, making exhaustive whole-board searches, as chess programs perform, impractical. Moreover, considering that go players routinely look more than 10 moves deep, it would not make for a strong program. In most chess positions there are usually around 30 possible moves, and 95 percent of human players make mistakes within a search horizon of three or four moves.

If a computer is to play go well, it will not be able to rely on brute force; it will have to be programmed to play intelligently. Heuristics will have to constitute a large part of the program. In chess the two main heuristics are material gain and mobility. The problem in go is that there are so many principles that constitute a good move; there is no one dominating factor. The most likely candidate that comes to mind for an evaluation function is "size of territory." But to quantify the concept of territory is not so simple.

Superficially, certain kinds of defensive moves may not seem to have a territorial meaning. In fact, in the short term they let one's opponent gain more territory. But it is essential that they be played because they maximize the efficiency of other stones. Ultimately, such moves, if they are good, will translate into territorial gains on another part of the board. In some positions a group may not define territory, but it radiates influence that, with skillful play, can be turned into territory elsewhere. In other cases moves must be made to maintain the integrity of a position. Such moves may seem to duplicate the work of other stones in a particular locale, but if they are omitted, the local position could collapse.

Of course there are moves that directly take territory, but it is hard to instruct the computer to recognize when such moves should be made. Clearly, quantifying a general concept of territory for go that a computer can understand is not easy.

It would be possible to compile heuristics for go, but they would give contradictory suggestions as to where a move should be played and therefore would contribute little to increasing the strength of a go program. Strength in go relies too much on intuition, an area where computers, as yet, have almost no ability.

Go is a more promising model for exploring artificial intelligence than is chess because of its complexity. Most applied AI tasks take place in the real world, but this is a `noisy' domain, therefore making problems difficult to solve. Go has many features in common with the targets of applied AI while providing a clean environment in which to solve these problems. Although many are skeptical that computers will ever be able to compete on equal terms with even moderately strong amateur go players, the challenge of go could well provide the impetus for many of the advances yet to be made in artificial intelligence.

Richard Bozulich