Go and computersThe 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.
|