www.delorie.com/gnu/docs/gnugo/gnugo_119.html   search  
 
Buy GNU books!


GNU Go Documentation

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003