An Eye Shape library for Computer Go

The shape library is available as a Java applet that you can play against, and generally use to study tsumego.

When solving life-and-death problems, one of the hardest things for a computer to determine is when to stop a search. Benson's proof describes the circumstances where groups are unconditionally safe, but a practical problem solver should stop much sooner: when a group is safe assuming best play. Safety heuristics can be pretty reliable if the number of liberties is large enough and the position is simple enough, but it is useful to have a library of solved positions to bridge the gap between the absolute safety described by Benson's algorithm and the highly probable safety for groups with lots of liberties. This article describes some aspects of such a library.

There are only 164 distinct "eye shapes" up to size 7 (533 up to size 8), but we must also consider the orientation and location of the shape, the connectivity of the stones surrounding it, the number of outside liberties, the player to make the first move, and the status of the stones that would be the capturing stones if the shape is dead. Many small scale life-and-death problems involve KOs, and a few shapes can be played either for a Ko or for a Seki. In these situations, the status of a particular shape can't be considered in isolation from the global situation. When all these factors are considered, the number of distinct positions, with possibly different solutions, is very large.

Figure 1

A small B&ampW gif

If you'd rather see an ascii representation, go Here

Figure 1 shows the "bent four" shape placed in a variety of positions.

Accordingly, the library contains life-and-death information for the following combinations:
    164   shapes (plus a few auxiliary shapes)
  x   9   different positions on the board
  x 2^n   different patterns of "dropped in" 
          stones of the opponent's color
  x   2   (moving first or second)
  x  ~3   0-2 outside liberties, plus more for some shapes

  for a total of 560,523 Solved positions in the library

Some interesting numbers

of 560,523 solved positions in the library For each of these 560k positions, I store the outcome and the move that leads there. This allows me to reconstruct the game tree (assuming best play) from any position found in the library, and to make tactical decisions about the best course of play (ie; to continue to fight or to give up) without performing a search.

Construction and Representation notes:

My program builds its library of shapes by brute force, one generation at a time, starting with a single stone and adding additional stones in all possible ways. While building the set of shapes, it detects equivalent isomers by generating all 8 isomers of each new shape and comparing them to all previously generated shapes.

Once the complete set of shapes is generated, the program builds a discrimination network of simple tests that can rapidly recognize any of the shapes any orientation or permutation in any position on the board. Using a hashing algorithm based on ideas of Zorbrist citation)

sidelight for programmer-weenies Originally, I used an extremely clever bit of lisp code that generated a discrimination network, consisting of a preliminry hash plus an automatically generated function for each hash collision. Zorbrist' hash algorithm blew it all away (I found it 25 years late!) and incidentally made it simpler and faster.

Taken together, this provides most of the machinery needed to recognise a shape "on the board" and locate the applicable entry in the shape database.

The database was generated by searching, using the same problem solver which now uses the database as a shortcut. The original search which built the database ran for weeks. The resulting database occupies approximately 1.5 megabytes. At first, a significant number of errors existed, mainly due to bugs in the problem solver, and due to the fact that any errors were immediately used to generate other bogus "solutions". However, since about 1987 (I've been at this a long time!) the shape library has been completely stable.

Since June 1994, I have had the opportunity to test my problem solver (and therefore the underlying shape library) against a thousands of Tsumego problems provided by Thomas Wolf ( and have had to make exactly 3 minor corrections. I consider this to be a pretty solid demonstration of the fundamental soundness of the library.

How to use the shape library:

In the following discussion, "the shape" means the eye shape itself, "the surrounding stones" means the stones which surround the eye shape, and "the capturing stones" means the oppose-colored stones that surround the capturing stones.

The raw information in the shape library can only be used when the external conditions assumed by the library are actually present. In addition to recognizing the shape and characterizing its position on the board, we also need to know the connectivity and liberty count of the surrounding stones, and must have a reliable estimate the status of the capturing stones.

Ascii figures

Provided for the poor unfortunates who don't have a graphical interface. Also, not incidentally, relics from when I originally wrote this.

figure 1

        "C"                          "D"
    - - - - - - - - - - - - - - - - - - - - -
    |       o x                   x o   x   |
    | o o   o x                   x o o o   |
    | x x o o x                   x x x o o |
    |   x x x x                       x x x |
    |                                       |
    |                                       |
    |                                       |
    | x x x x x   x x x x x x     x x x x x |
    | o o o o x   x o o o o x x   x o o o o |
    |       o x   x o     x o x   x o       |
    | o o   o x   x o o o   o x   x o o o   |
 "B"|   o o o x   x x x o o o x   x x x o o |
    | x x x x x       x x x x x       x x x |
    |                                       |
    |                                       |
    | x x x x x                   x x x x x |
    | o o o o x                   x o o o o |
    |   x x o x                   x o     x |
 "A"| o o   o x                   x o o o   |
    - - - - - - - - - - - - - - - - - - - - -
Go Back
comments/suggestions to:

Back to my home page