www.delorie.com/gnu/docs/gnugo/gnugo_119.html

search

	Buy GNU books!

GNU Go Documentation

10. Worms and Dragons

10.1 Worms
10.2 Amalgamation		How two Worms are amalgamated.
10.5 Connection		Connections.
10.6 Half Eyes and False Eyes
10.7 Dragons		Union of WORMS.
10.8 Colored Dragon Display		Colored display of DRAGONS.
10.9 Worm and Dragon Functions

Before considering its move, GNU Go collects some data in several arrays. Two of these arrays, called worm and dragon, are discussed in this document. Others are discussed in See section 11. Eyes and Half Eyes.

This information is intended to help evaluate the connectedness, eye shape, escape potential and life status of each group.

Later routines called by genmove() will then have access to this information. This document attempts to explain the philosophy and algorithms of this preliminary analysis, which is carried out by the two routines make_worm() and make_dragon() in `dragon.c'.

A worm is a maximal set of vertices on the board which are connected along the horizontal and vertical lines, and are of the same color, which can be BLACK, WHITE or EMPTY. The term EMPTY applied to a worm means that the worm consists of empty (unoccupied) vertices. It does not mean that that the worm is the empty set. A string is a nonempty worm. An empty worm is called a cavity. If a subset of vertices is contained in a worm, there is a unique worm containing it; this is its worm closure.

A dragon is a union of strings of the same color which will be treated as a unit. The dragons are generated anew at each move. If two strings are in the dragon, it is the computer's working hypothesis that they will live or die together and are effectively connected.

The purpose of the dragon code is to allow the computer to formulate meaningful statements about life and death. To give one example, consider the following situation:

OOOOO OOXXXOO OX...XO OXXXXXO OOOOO

The X's here should be considered a single group with one three-space eye, but they consist of two separate strings. Thus we must amalgamate these two strings into a single dragon. Then the assertion makes sense, that playing at the center will kill or save the dragon, and is a vital point for both players. It would be difficult to formulate this statement if the X's are not perceived as a unit.

The present implementation of the dragon code involves simplifying assumptions which can be refined in later implementations.