Go and computers
The year 1997 was a bad year for world chess champion Gary
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
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×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 ones 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 gos complexity, it could provide the vehicle to help make important advances in artificial intelligence. Most
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.