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.
If you'd rather see an ascii representation, go Here
Figure 1 shows the "bent four" shape placed in a variety of positions.
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
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 (T.Wolf@qmw.ac.uk) 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.
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.
"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
Back to my home page