A Look at SPEC95
An Introduction to 099.go
By Alexander Carlton
Hewlett-Packard
Cupertino, Calif.
Note: This is the first in series of articles examining the new SPEC95
benchmark suites.
Published September, 1995; see disclaimer.
The CINT95 benchmark 099.go uses several techniques common in the field of
artificial intelligence to play the ancient Asian game of Go. This program,
written by David Fotland, is based upon a version of his commercially
successful programs sold under the names 'Cosmos' and 'The Many
Faces of Go'. Versions of this code have been leading contenders in
international competition.
Go and Computers
It has been said that if Chess is a battle, then Go is an entire war. Go is
a game of territory, surrounding and defending one's own while
simultaneously attacking and penetrating your opponent's. Go is a much
more difficult artificial intelligence problem than Chess, and must be
attempted with a knowledge-intensive approach rather than just a brute
force search. While computer Chess is a relatively well understood problem,
computer Go is still an advancing science where the human player is still
well ahead of the robotic brain.
The best Chess programs do work by brute force, looking ahead many more
moves than the opponent and sometimes using special-purpose hardware to
make simple judgements about board positions. This approach does not work
in Go. The number of possible games is vastly higher (roughly 10^750,
versus 10^450). There are more legal moves in a turn (several hundred,
compared to a dozen or so in Chess) and there are more turns in a game
(around 300, compared to about 80), and judging a board position is much
more difficult (due to the more subtle interplay between pieces in Go).
Design Characteristics
'The Many Faces of Go' is one of the strongest Go programs
commercially available. Versions of this program have won the United States
Computer Go competitions in 1988, 1991, and 1992, with current version is
ranked 11 kyu in the United States. It is based on traditional AI
techniques, such as alpha-beta search, rule-based systems, and pattern
matching.
Go knowledge is incorporated into 'Many Faces of Go' in five major
areas. First, low-level Go knowledge such as connectivity, eyes, potential
eyes, and territory, and so forth, is built into the program's logic.
Second, there is the dynamic knowledge, information in various levels of
abstraction about the state of the current position, that is built up in
successive passes. Third, there is a rule-based expert system that suggests
plausible moves for full board evaluation. Fourth, there is a database of
standard joseki (corner patterns). Finally, there is a further database of
8x8 patterns for other situations.
This code was originally developed in the very early '80s on a
minicomputer rated at the time at 1/2 MIPS. This code has already been
ported to such divergent platforms as VAXen, high-end HP UNIX workstations,
MS-DOS PCs, and even a pocket-sized PenPoint computer. The version of code
used for this benchmark comes from the UNIX workstation which does not have
an attempt to squeeze the data structures into the smallest possible space.
Benchmark Workload
For use as a benchmark, the program had its user interface removed and has
been configured to play against itself, by playing alternating sides. A
record of the chosen moves is reported and used to verify accurate and
consistent execution. The benchmark reference workload is set up to play
three games on an oversized (21 x 21) board. For each of the three games
one side is given increasingly larger handicaps. The result is that the
program works through three completely different games.
For More Information
The following sources are points in the World Wide Web where more
information can be found.
While Go books are not as common in U.S. libraries as Chess books, your
local library should be able to get some. Otherwise contact your nearest Go
club. In the United States, try:
American Go Association
Box 397, Old Chelsea Station
New York, NY 10113
Alex Carlton, Cupertino, Calif., is one of the many people from
Hewlett-Packard working on SPEC. He was recently the Project Lead for
099.go.
