                    GNU GO 2.0 OVERVIEW

This document is an overview of the GNU GO 2.0 internals. Detailed
documentation of how any one module or routine works may be found in
the comments in the source files.

                       DEFINITIONS

In this document wherever we define a concept we use CAPITAL LETTERS
for the term being defined.

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 recomputed. 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.

Roadmap
-------

The files making up GNU Go 2.0 are as follows.

main.c      : Miscellaneous book-keeping (parsing args, signal
              handlers, etc.) sgf file interfaces (reading and writing)
              high level game playing (collecting moves from genmove(),
              keeping track of passes, etc.) Contains very little
              knowledge about go : only that each side plays
              alternately, and that two passes marks the end of the
              game.
              

gmp.c       : This is the Go Modem Protocol interface (courtesy of 
              William Shubert and others). This takes care of all the 
              details of exchanging setup and moves with Cgoban, or any 
              other driving program recognizing the Go Modem Protocol.

sethand.c   : Initially populate the board with handicap stones.

showbord.c  : This contains showboard(), which draws an ASCII
              representation of the board, depicting dragons (stones 
              with same letter) and status (color). This was the 
              primary interface in GNU GO 1.2, but is now a debugging 
              aid.
                  
genmove.c   : This file contains genmove(), is the routine responsible
              for generating the next move. Opening moves are
              generated directly in this file, but it calls on
              other modules for other moves. The modules called
              by genmove are shapes() (in shapes.c), attacker()
              and defender (in attdef.c), semeai() (in semeai.c)
              and eye_finder (in attdef.c). Each module proposes
              moves, each with a value, and genmove() selects the
              one with the highest value.

dragon.c    : This contains make_worms() and make_dragons(). These
              routines are executed before the move-generating
              modules shapes(), attacker(), defender(), semeai()
              and eye_finder. They find all the worms and dragons
              and collect important information about them, such
              as how many liberties each has, whether (in GNU Go's
              opinion) the string or dragon can be captured, etc. 
              This information remains unchanged until the next
              move, with one exception: some patterns can move
              the point of defense of a friendly worm which is under 
              attack.

halfeyes.c  : This module, called by make_dragons() uses a pattern 
              matcher to recognise false eyes and half eyes.

hey.db      : Database of half eye and false eye patterns, in 
              human-readable form.

hey.h       : Database of half eye and false eye patterns compiled from 
              hey.db by mkpat. Do not edit this file---instead
              make changes to hey.db.

attdef.c    : This file contains attacker(), defender() and 
              eye_finder(), three of the move generators called by 
              genmove(). The module attacker() proposes moves which 
              attack enemy strings, while defender() proposes moves 
              which defend friendly strings. The reading necessary to 
              decide whether a string can be captured or defended is
              contained in reading.c, and has already been called
              by make_worms(). If a string can be defended, there
              may be different possible defensive moves, and some 
              of the patterns found by shapes() may move the points 
              of defense. This is the only case where data compiled 
              by make_worms() and make_dragons() is changed by a later 
              routine. Because of this feature, shapes() is called 
              before defender().           

              Also in attdef.c is eye_finder(). This module looks
              for dragons having one and a half eyes. If such a
              dragon (of either color) is found, eye_finder()
              proposes making or destroying the half eye.

semeai.c    : This contains semeai(), the module which tries to
              win capturing races.

shapes.c    : This file contains shapes(), the module called by
              genmove() which tries to find moves which match a
              pattern. The pattern matcher has some sophisticated
              features described in more detail in PATTERNS. 
              Briefly, the pattern may take into account both
              friendly and opposing strength in the area, a
              string's escape potential, whether or not the
              pattern makes or breaks a valuable connection,
              whether it involves a dragon classified as dead,
              and it can also call a helper function hand
              tailored to the program which typically does some 
              further reading to decide whether the pattern is
              appropriate.

matchpat.c  : This file contains matchpat(), which looks for
              patterns at a particular board location.

helpers.c   : These are help functions to assist in evaluating
              moves by matchpat.

patterns.db : This contains the pattern database in human
              readable form. See PATTERNS for documentation.

patterns.c  : Pattern data, compiled from patterns.db by mkpat.

patterns.h  : Header file relating to the pattern databases.

liberty.h   : Header file for the whole program. 


Utility files and routines
--------------------------

reading.c : low-level reading routines used throughout : ladders, nets, etc.
---------   The reading code makes use of a stack onto which board
            positions can be pushed. The parameter stackp is zero if
GNU Go is examining the true board position; if it is higher than zero,
then GNU Go is examining a hypothetical position obtained by playing
several moves. Depth of reading is controlled by a parameter depth.
This has a default value DEPTH (in liberty.h), which is set to 7 in the
distribution, but it may also be set at the command line using the -D
option. If depth is increased, GNU Go will be stronger and slower.

This file contains:

 attack()       : Determines whether a string can be captured. Looks
                  for ladders and nets. Capable of reading in some
                  detail. If stackp exceeds the parameter depth it
                  tries fewer moves --- reading beyond this depth
                  it will find ladders but will miss many nets.                  

 safe_move()    : Determines whether a move results in a string
                  which cannot be captured by any of the variations
                  considered by attack.
      
 readlad1()     : Read out a ladder attack on a group with one liberty

 readlad2()     : Read out a ladder attack on a group with two 
                  liberties

 basicnet3()    : Try to capture a string with three liberties

 find_cap2()    : Try a capping attack (geta) on a group with two 
                  liberties

 chainlinks()   : Find the CHAIN surrounding a string. This is the
                  set of adjacent strings of the opposite color.

 break_chain()  : Looks for a string in the chain surrounding a
                  given string which is in atari.

 break_chain2() : Looks for a string in the chain surrounding a
                  given string which can be captured. Unlike
                  break_chain, it tries attacks on strings
                  which may have more than one liberty.

 find_defense() : Looks for a defensive move to defend a string.
                  Called by genmove

 snapback()     : see if a potential capture is actually a snapback.


Also some misc. functions:

utils.c :  board utility functions :  (rename utils.c or boardutil.c ?)
----

 legal()        : Determines whether a move is legal.

 trymove()      : Pushes the board position on the stack,
                  increments stackp, places the stone on the board if 
                  the move is legal, removes captures and increments 
                  stackp.

 pushgo()       : Pushes the board position on the stack and
                  increments stackp.

 popgo()        : Pops the stack.

 approxlib() : counts liberties, but as an optimisation, can be given
               an upper limit, above which it can stop counting.

 count() : low level helper for approxlib(), but is used by other fns


 updateboard() : place a piece on the board, remove prisoners, and update
                 state information (for ko)

 gprintf() : printf-like fn (see below under TRACING)

 TRACE, VTRACE, DEBUG ()  - see below

 abortgo()  : Wrapper around abort() which dumps the stack. Usually
              this is invoked by means of the macro ASSERT (see
              ASSERTIONS) below.



Data Structures
---------------

The most important global variable is p[][], which is the go board.
Each element contains EMPTY, WHITE or BLACK.

The state of the board can be saved and restored using pushgo()
and popgo().

p[][] should not be written to directly. Trial moves should
be made using trymove(), which pushes the board, places the
piece, checks the move is legal, and updates the board.
popgo() undoes the move.  When a move is actually made,
updateboard() places the piece and removes prisoners.

approxlib() / count() can be called without actually placing
a piece. They report what the number of liberties would be
if a given piece was placed.

Other important data structures are dragon[][] and worm[][].
These contain information about groups of stones, whether
they are alive or dead, where they can be attacked, whether
they are cutting groups (split enemy groups), etc.

size, lib, and libi[],libj[] are global variables written
to by count() / approxlib(). They contain the size of
the group, and the number and positions of the liberties.

*NOTE* : if the count is truncated because it reaches the
limit on the number of liberties, then size and lib may
be smaller than the true value.

Other variables tend to be private to individual modules : 
half_eyes[][] is between dragon.c and halfeyes.c, stackp
is part of the stack implementation, plast[][] is part of
the ko history stuff, etc.




Coding styles and conventions
-----------------------------   
              
         
TRACING
-------

A function gprintf() is provided. It is a cut-down printf, supporting
only %c,%d,%s, and without field widths, etc. It does, however, add
two useful facilities :

  %m : takes two parameters, and displays a formatted board co-ordinate

  indentation : trace messages are automatically indented to reflect
                the current stack depth, so it is clear during read-ahead
                when it puts a move down or takes one back.

As a nasty workaround, %o at the beginning of the format string suppresses
the indentation.


gprintf() is intended to be wrapped by one of the following:


  TRACE(fmt, ...)  : print the message if the 'verbose' variable > 0.
                     (verbose is set by -t on the command line)


  VTRACE(fmt, ...) : Verbose trace, only if verbose > 1
                     (not currently used)


  DEBUG(flags, fmt, ...) : while TRACE is intended to afford an overview
                      of what GNU GO is considering, DEBUG allows occassional
                      in depth study of a module, usually needed when something
                      goes wrong. 'flags' is one of the DEBUG_* symbols in
                      liberty.h.   The DEBUG macro tests to see if that
                      bit is set in the 'debug' variable, and prints the
                      message if it is.  The debug variable is set using the
                      '-d' command-line option.




ASSERTIONS
----------

related to tracing are assertions. Developers are strongly encouraged
to pepper their code with assertions to ensure that data structures
are as they expect. For example, the helper functions make assertions
about the contents of the board in the vicinity of the move they
are evaluating.

ASSERT() is a wrapper around the standard C assert() function.
In addition to the test, it takes an extra pair of parameters
which are the co-ordinates of a "relevant" board position.

If an assertion fails, the board position is included in
the trace output, and showboard() and popgo() are called
to unwind and display the stack.



FIXME
-----

We have adopted the convention of putting the word FIXME
in comments to denote known bugs, etc.

(Ideally the 2.0 release will have no FIXME's, but we'll
 have to see what happens !!!)


