GNU GO OVERVIEW
This document is an overview of the GNU Go internals. Further
documentation of how any one module or routine works may be found in
the comments in the source files.
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
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.
The engine of GNU Go takes a positions and a color to move and
generates the (supposedly) optimal move. This is done by the function
genmove() in src/genmove.c.
The move generation is done in two passes:
1) information gathering
2) actual move generation based on the information gathered in pass 1.
First we have to collect as much information as possible about the
current position. Such information could be life and death of the
groups, moyo status, connection of groups and so on. Information
gathering are performed by the following functions, called in this
- make_worms Collect information about all connected sets of stones
(strings) and cavities. This information is stored in
the worm array.
- make_dragons Collect information about connected strings, which are
called dragons. Important information here is number
of eyes, life status, and connectedness between
- make_moyo Calculate the "territory", "moyo" and "area" for both
sides. "Territory", as used here, is a somewhat
looser term than we are used to, but in the end it
coincides with the actual points. "Moyo" is the area
of influence which could become territory if the other
side does nothing about it, and "area" is weaker but
bigger than moyo.
make_worms and make_dragons are documented more in detail in
docs/DRAGON and some algorithms in make_moyo are documented in
Once we have found out all about the position it is time to generate
the best move. Moves are proposed by a number of different move
generators with a value attached to them. The values are compared and
the best move is picked. If two or more moves have the same value,
one of them is picked at random.
The move generators in version 2.4 are:
- fuseki Generate a move in the early fuseki. This module
is undocumented but will be replaced by something
better in the future.
- semeai Find out if two dead groups of opposite colors are
next to each other and, if so, try to kill the other
group. This module is probably the one in the worst
condition currently and badly in need of improvement.
- shapes Match a number of patterns on the current position.
Each pattern is matched in 8 different combinations of
rotation and mirroring. If the pattern matches, a so
called "constraint" may be tested which makes use of
reading to determine if the pattern should be used in
the current situation. Such constraints can make
demands on number of liberties of strings, life and
death status, and reading out ladders, etc.
The patterns can be of a number of different classes
with different goals. There are e.g. patterns which
try to attack or defend groups, patterns which try to
connect or cut groups, and patterns which simply try
to make good shape. See the file docs/PATTERNS for a
complete documentation of patterns.
- attacker Looks for strings of the opposite color with three
liberties or less and tries to kill them.
- defender Looks for strings of my color with three liberties or
less and tries to defend them.
- eye_finder Finds groups of either color which can make two eyes
in the next move and looks for the vital point in the
- revise_semeai If no move is found yet, change status of opponent
groups involved in a semeai from DEAD to UNKNOWN.
After this, genmove runs shapes again to see if a new
move turns up.
- fill_liberty Fill a common liberty. This is only used at the end
of the game. If necessary a backfilling or
backcapturing move is generated.
The GNU Go engine is contained in two directories, src/ and
patterns/. Code related to the user interface, reading and
writing of smart go format files and testing are found in
the directories interface/, sgf/ and regression/. Code borrowed from
other GNU programs is contained in utils/. Documentation is in docs/.
In this document we will describe the all individual files comprising
the engine code in src/ and patterns/. In interface/ we mention one
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.
In src/ there are the following files:
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
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.
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
filllib.c : code to force filling of dame (backfilling if necessary)
at the end of the game.
fuseki.c : this module generates fuseki (large scale opening)
moves at the beginning of the game. This file is
undocumented but will be replaced by something better
in the future.
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.
hash.c : hashing code used by for reading. See READING for
hash.h : header file for hash.c.
liberty.h : Header file for the whole program.
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
matchpat.c : This file contains matchpat(), which looks for
patterns at a particular board location.
moyo.c : This file contains code to estimate territory and
influence. See docs/MOYO for details.
reading.c : This file contains code to determine whether any given
string can be attacked or defended. See docs/READING
semeai.c : This contains semeai(), the module which tries to
win capturing races.
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
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
optics.c : This contains the code to recognize eye shapes,
documented in docs/EYES.
worm.c : This file contains code which is run at the beginning
of each move cycle, before the code in dragon.c, to
determine the attributes of every string.
utils.c : An assortment of utilities, described in greater
The directory patterns/ contains files related to pattern matching.
Currently search for 3 types of patterns: move generation patterns
(in patterns.db and similar files such as hoshi.db, compiled from
hoshi.sgf---see docs/PATTERNS for details); eyeshape patterns (in
eyes.db---see docs/OPTICS) and connection patterns (in conn.db,
discussed in docs/DRAGONS).
The following list contains, in addition to distributed source files
some intermediate automatically generated files such as patterns.c.
These are C source files produced by "compiling" various pattern
databases, or in some cases (such as hoshi.db) themselves
automatically generated pattern databases produced by "compiling"
joseki files in Smart Go Format.
conn.db : database of connection patterns.
conn.c : automatically generated file, containing connection
patterns in form of struct arrays, compiled by mkpat
eyes.c : automatically generated file, containing eyeshape
patterns in form of struct arrays, compiled by mkpat
eyes.h : header file for eyes.c.
eyes.db : database of eyeshape patterns. see docs/EYES for
helpers.c : These are helper functions to assist in evaluating
moves by matchpat.
hoshi.sgf : Smart Go Format file containing 4-4 point openings
hoshi.db : automatically generated database of 4-4 point opening
patterns, make by compiling hoshi.sgf
joseki.c : Joseki compiler, which takes a joseki file in
Smart Go Format, and produces a pattern database.
komoku.sgf : Smart Go Format file containing 3-4 point openings
komoku.db : automatically generated database of 3-4 point opening
patterns, make by compiling komoku.sgf
mkeyes.c : pattern compiler for the eyeshape databases. This
program takes eyes.db as input and produces eyes.c
mkpat.c : pattern compiler for the move generation and connection
databases. Takes patterns.db+hoshi.db+komoku.db+sansan.db
+mokuhadzushi.db+takamoku.db and produces patterns.c, or
takes conn.db and produces conn.c.
mokuhazushi.sgf : Smart Go Format file containing 5-3 point openings
mokuhazushi.db : pattern database compiled from mokuhadzushi.sgf
sansan.sgf : Smart Go Format file containing 3-3 point openings
sansan.db : pattern database compiled from sansan.sgf
takamoku.sgf : Smart Go Format file containing 5-4 point openings
takamoku.db : pattern database compiled from takamoku.sgf.
patterns.c : Pattern data, compiled from patterns.db by mkpat.
patterns.h : Header file relating to the pattern databases.
patterns.db : This contains the pattern database in human
readable form. See PATTERNS for documentation.
Utility files and routines in src/utils.c
Only a portion of these functions are documented here.
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
pushgo() : Pushes the board position on the stack and
popgo() : Pops the stack.
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
utils.c : board utility functions :
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 captures, and update
state information (for ko)
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()
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
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 workaround, %o at the beginning of the format string suppresses
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.
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
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.
We have adopted the convention of putting the word FIXME
in comments to denote known bugs, etc.