Go and computers

The year 1997 was a bad year for world chess champion Gary Kasparov-he was defeated by Deep Blue, an IBM computer designed to play chess. This result might lead you to believe 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 equal-valued black and white stones, which would seem to make it 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 player of that move 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 find the best way to give a material or a 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 be a game-losing blunder.

Another factor that makes go more difficult to program than chess is the size of the board. On the standard 19 x 19 grid, there can be anywhere from 100 to over 300 possible moves to consider. Thus, making exhaustive whole-board searches, as chess programs do, is 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 oversights 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 programed to play intelligently. In other words, 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 get 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 elsewhere. 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 the 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, which 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, so they would contribute little to increasing the strength of a go program. Strength in go relies too much on intuition and pattern recognition. These are the areas where computers, as yet, have almost no ability.

Because of go's complexity, it could provide the vehicle to help make important advances in artificial intelligence. Most applied-AI tasks take place in the real world, but this is a "noisy" domain that makes problems difficult to solve. Go has many features in common with the targets of applied AI and it also provides a clean environment in which to solve these problems. Although I am skeptical that computers will ever be able to compete on equal terms with even moderately strong amateur go players, the challenge of go might provide the impetus for many of the future advances that will be made in artificial intelligence.

Seki

There are special cases in which stones do not need to have eyes to live. An example of this is shown in Diagram 1. The two marked black and white groups are confronting each other. Black and White each fill an outside liberty with 1 and 2. There are now two inside liberties remaining.

However, if Black ataris with 1 in Diagram 2, he also puts himself into atari, so White would capture at "a." For the same reason, White cannot play at 1 in Diagram 3, since he would also put himself into atari and be captured by Black "a." Therefore, it is better for both players to sit tight and do nothing. At the end of the game, both groups in Diagram 1 remain on the board and the points between them are not counted as territory. This position is called "seki" in Japanese.