Skip navigation

Standard Performance Evaluation Corporation

Facebook logo LinkedIn logo Twitter logo
 
 

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.