Go
Go
Go
Edition 3.8
February, 2009
Copyright ⃝c 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 and 2009 Free
Software Foundation (http://www.fsf.org), Inc.
Permission is granted to make and distribute verbatim or modified copies of this manual
is given provided that the terms of the GNU Free Documentation License (see Section A.5
[GFDL], page 217, version 1.3 or any later version) are respected.
Permission is granted to make and distribute verbatim or modified copies of the program
GNU Go is given provided the terms of the GNU General Public License (see Section A.1
[GPL], page 206, version 3 or any later version) are respected.
i
Table of Contents
....................................................... 1
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1 About GNU Go and this Manual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Copyrights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Authors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Thanks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.5 Development . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1 GNU/Linux and Unix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Configure Options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.1 Ram Cache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.2 Default Level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.3 Other Options. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Compiling GNU Go on Microsoft platforms . . . . . . . . . . . . . . . . . . . . . 7
2.3.1 Building with older visual studio. . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3.2 Building with Visual Studio project files . . . . . . . . . . . . . . . . . . . 8
2.3.3 Building with Nmake makefiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3.4 Building with MinGW Makefiles . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3.5 Building with MSYS makefiles (MinGW) . . . . . . . . . . . . . . . . . . 9
2.3.6 Building on cygwin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.7 Testing on Windows: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Macintosh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3 Using GNU Go . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1 Getting Documentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Running GNU Go via CGoban . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 Other Clients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.4 Ascii Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.5 GNU Go mode in Emacs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.6 The Go Modem Protocol and Go Text Protocol . . . . . . . . . . . . . . . 13
3.7 Computer Go Tournaments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.8 Smart Game Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.9 Invoking GNU Go: Command line options . . . . . . . . . . . . . . . . . . . . . 14
3.9.1 Some basic options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.9.2 Monte Carlo Options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.9.3 Other general options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.9.4 Other options affecting strength and speed. . . . . . . . . . . . . . . . 17
3.9.5 Ascii mode options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.9.6 Development options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.9.7 Experimental options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
ii
6 Move generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
6.2 Generation of move reasons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
6.3 Detailed Descriptions of various Move Reasons . . . . . . . . . . . . . . . . 42
6.3.1 Attacking and defending moves . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6.3.2 Threats to Attack or Defend. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6.3.3 Multiple attack or defense moves . . . . . . . . . . . . . . . . . . . . . . . . . 42
6.3.4 Cutting and connecting moves . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6.3.5 Semeai winning moves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
6.3.6 Making or destroying eyes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
6.3.7 Antisuji moves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
6.3.8 Territorial moves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
6.3.9 Attacking and Defending Dragons . . . . . . . . . . . . . . . . . . . . . . . . 43
6.3.10 Combination Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
6.4 Valuation of suggested moves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
6.4.1 Territorial Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.4.2 Strategical Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.4.3 Shape Factor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.4.4 Minimum Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.4.5 Secondary Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
iii
1 Introduction
This is GNU Go 3.8, a Go program. Development versions of GNU Go may be found at
http://www.gnu.org/software/gnugo/devel.html. Contact us at [email protected] if you
are interested in helping.
1.2 Copyrights
Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007 and 2008 by the Free
Software Foundation except as noted below.
All source files are distributed under the GNU General Public License (see Section A.1
[GPL], page 206, version 3 or any later version), except ‘gmp.c’, ‘gmp.h’, ‘gtp.c’, and
‘gtp.h’.
The files ‘gtp.c’ and ‘gtp.h’ are copyright the Free Software Foundation. In the interests
of promoting the Go Text Protocol these two files are licensed under a less restrictive license
than the GPL and are free for unrestricted use (see Section A.6 [GTP License], page 224).
The two files ‘gmp.c’ and ‘gmp.h’ were placed in the public domain by William Shubert,
their author, and are free for unrestricted use.
Chapter 1: Introduction 3
Documentation files (including this manual) are distributed under the GNU Free Docu-
mentation License (see Section A.5 [GFDL], page 217, version 1.3 or any later version).
The files ‘regression/games/golois/*sgf’ are copyright Tristan Cazenave and are
included with his permission.
The SGF files in ‘regression/games/handtalk/’ are copyright Jessie Annala and are
used with permission.
The SGF files in ‘regression/games/mertin13x13/’ are copyright Stefan Mertin and
are used with permission.
The remaining SGF files are either copyright by the FSF or are in the public domain.
1.3 Authors
GNU Go maintainers are Daniel Bump, Gunnar Farneback and Arend Bayer. GNU Go
authors (in chronological order of contribution) are Man Li, Wayne Iba, Daniel Bump,
David Denholm, Gunnar Farnebäck, Nils Lohner, Jerome Dumonteil, Tommy Thorn, Nick-
las Ekstrand, Inge Wallin, Thomas Traber, Douglas Ridgway, Teun Burgers, Tanguy Urvoy,
Thien-Thi Nguyen, Heikki Levanto, Mark Vytlacil, Adriaan van Kessel, Wolfgang Manner,
Jens Yllman, Don Dailey, Måns Ullerstam, Arend Bayer, Trevor Morris, Evan Berggren
Daniel, Fernando Portela, Paul Pogonyshev, S.P. Lee and Stephane Nicolet, Martin Holters,
Grzegorz Leszczynski and Lee Fisher.
1.4 Thanks
We would like to thank Arthur Britto, David Doshay, Tim Hunt, Matthias Krings, Pi-
otr Lakomy, Paul Leonard, Jean-Louis Martineau, Andreas Roever and Pierce Wetter for
helpful correspondence.
Thanks to everyone who stepped on a bug (and sent us a report)!
Thanks to Gary Boos, Peter Gucwa, Martijn van der Kooij, Michael Margolis, Trevor
Morris, Måns Ullerstam, Don Wagner and Yin Zheng for help with Visual C++.
Thanks to Alan Crossman, Stephan Somogyi, Pierce Wetter and Mathias Wagner for
help with Macintosh. And thanks to Marco Scheurer and Shigeru Mabuchi for helping us
find various problems.
Thanks to Jessie Annala for the Handtalk games.
Special thanks to Ebba Berggren for creating our logo, based on a design by Tanguy Ur-
voy and comments by Alan Crossman. The old GNU Go logo was adapted from Jamal Han-
nah’s typing GNU: http://www.gnu.org/graphics/atypinggnu.html. Both logos can be
found in ‘doc/newlogo.*’ and ‘doc/oldlogo.*’.
We would like to thank Stuart Cracraft, Richard Stallman and Man Lung Li for their
interest in making this program a part of GNU, William Shubert for writing CGoban and
gmp.c, Rene Grothmann for Jago and Erik van Riper and his collaborators for NNGS.
1.5 Development
You can help make GNU Go the best Go program.
Chapter 1: Introduction 4
This is a task-list for anyone who is interested in helping with GNU Go. If you want to
work on such a project you should correspond with us until we reach a common vision of
how the feature will work!
A note about copyright. The Free Software Foundation has the copyright to GNU Go.
For this reason, before any code can be accepted as a part of the official release of GNU
Go, the Free Software Foundation will want you to sign a copyright assignment.
Of course you could work on a forked version without signing such a disclaimer. You
can also distribute such a forked version of the program so long as you also distribute the
source code to your modifications under the GPL (see Section A.1 [GPL], page 206). But
if you want your changes to the program to be incorporated into the version we distribute
we need you to assign the copyright.
Please contact the GNU Go maintainers, Daniel Bump ([email protected])
and Gunnar Farnebäck ([email protected]), to get more information and the papers
to sign.
Bug reports are very welcome, but if you can, send us bug FIXES as well as bug reports.
If you see some bad behavior, figure out what causes it, and what to do about fixing it. And
send us a patch! If you find an interesting bug and cannot tell us how to fix it, we would be
happy to have you tell us about it anyway. Send us the sgf file (if possible) and attach other
relevant information, such as the GNU Go version number. In cases of assertion failures
and segmentation faults we probably want to know what operating system and compiler
you were using, in order to determine if the problem is platform dependent.
If you want to work on GNU Go you should subscribe to the GNU Go development
list. (http://lists.gnu.org/mailman/listinfo/gnugo-devel) Discussion of bugs and
feedback from established developers about new projects or tuning the existing engine can
be done on the list.
Chapter 2: Installation 5
2 Installation
You can get the most recent version of GNU Go ftp.gnu.org or a mirror (see
http://www.gnu.org/order/ftp.html for a list). You can read about newer versions and
get other information at http://www.gnu.org/software/gnugo/.
In most cases (unless you are building in Cygwin) the preferred way to build GNU Go
on Windows platforms is to use CMake. CMake understands about many versions of Visual
C/Visual Studio, and will generate project/solution files for the tools installed on your
system. So even if you have Visual Studio 6 you may use CMake and dispense with the
distributed .dsp and .dsw files.
2.4 Macintosh
If you have Mac OS X you can build GNU Go using Apple’s compiler, which is derived
from GCC. You will need Xcode.
One issue is that the configure test for socket support is too conservative. On OS/X, the
configure test fails, but actually socket support exists. So if you want to be able to connect
to the engine through tcp/ip (using gtp) you may configure --enable-socket-support.
There will be an error message but you may build the engine and socket support should
work.
Chapter 3: Using GNU Go 11
3 Using GNU Go
komi at the command line GNU Go will have to guess it. It assumes the komi is 5.5 for
even games, 0.5 for handicap games. If this is not what you want, you can specify the komi
at the command line with the ‘--komi’ option, in the Go Modem Protocol Setup window.
You have to set the komi again in the Game Setup window, which comes up next.
Click OK and you are ready to go.
In the Go Modem Protocol Setup window, when you specify the path to GNU Go, you
can give it command line options, such as ‘--quiet’ to suppress most messages. Since the
Go Modem Protocol preempts standard I/O other messages are sent to stderr, even if they
are not error messages. These will appear in the terminal from which you started CGoban.
CGoban. The programmer can concentrate on the real issues without worrying about
drawing stones, resizing the board and other distracting issues.
GNU Go 3.0 introduced a new protocol, the Go Text Protocol (see Chapter 19
[GTP], page 178) which we hope can serve the functions currently used by the GMP. The
GTP is becoming increasingly adopted by other programs as a method of interprocess
communication, both by computer programs and by clients. Still the GMP is widely used
in tournaments.
the other player you may add the option ‘--color <color>’ where <color>
is black or white.
• ‘-L’, ‘--until move ’
Stop loading just before the indicated move is played. move can be either
the move number or location.
• ‘-o’, ‘--outfile filename ’
Write sgf output to file
• ‘-O’, ‘--output-flags flags ’
Add useful information to the sgf file. Flags can be ’d’, ’v’ or both (i.e.
’dv’). If ’d’ is specified, dead and critical dragons are marked in the sgf
file. If ’v’ is specified, move valuations around the board are indicated.
• ‘--mode mode ’
Force the playing mode (’ascii’, ’emacs,’ ’gmp’ or ’gtp’). The default is
ASCII, but if no terminal is detected GMP (Go Modem Protocol) will be
assumed. In practice this is usually what you want, so you may never need
this option.
• ‘--resign-allowed’
GNU Go will resign games if this option is enabled. This is the
default unless you build the engine with the configure option
‘--disable-resignation-allowed’. Unfortunately the Go Modem
Protocol has no provision for passing a resignation, so this option has no
effect in GMP mode.
• ‘--never-resign’
GNU Go will not resign games.
• ‘--resign-allowed’
GNU Go will resign lost games. This is the default.
• ‘--no-ko’
Allow all kinds of board repetition.
• ‘--positional-superko’
Forbid repetition of any earlier board position. This only applies to moves
on the board; passing is always allowed.
• ‘--situational-superko’
Forbid repetition of any earlier board position with the same player to
move. This only applies to moves on the board; passing is always allowed.
• ‘--copyright’: Display the copyright notice
• ‘--version’ or ‘-v’: Print the version number
• ‘--printsgf filename ’:
Create an SGF file containing a diagram of the board. Useful with ‘-l’ and
‘-L’ to create a diagram of the board from another sgf file. Illegal moves
are indicated with the private IL property. This property is not used in
the FF4 SGF specification, so we are free to preempt it.
• ‘--options’
Print which experimental configure options were compiled into the program
(see Section 2.2.3 [Other Options], page 6).
• ‘--orientation n ’
Combine with ‘-l’. The Go board can be oriented in 8 different ways,
counting reflections and rotations of the position; this option selects an
orientation (default 0). The parameter ‘n’ is an integer between 0 and 7.
• ‘--backfill2-depth depth ’
Another depth controlling how deeply GNU Go looks for backfilling moves.
The moves tried below backfill2_depth are generally more obscure and
time intensive than those controlled by backfill_depth, so this parameter
has a lower default.
• ‘-F’, ‘--fourlib-depth depth ’
Deep reading cutoff. When reading beyond this depth (default 7) GNU Go
assumes that any string which can obtain 4 liberties is alive.
• ‘-K’, ‘--ko-depth depth ’
Deep reading cutoff. Beyond this depth (default 8) GNU Go no longer
tries very hard to analyze kos.
• ‘--branch-depth depth ’
This sets the branch_depth, typically a little below the depth. Between
branch_depth and depth, attacks on strings with 3 liberties are considered
but branching is inhibited, so fewer variations are considered. Below this
depth (default 13), GNU Go still tries to attack strings with only 3 liberties,
but only tries one move at each node.
• ‘--break-chain-depth depth ’
Set the break_chain_depth. Beyond this depth, GNU Go abandons some
attempts to defend groups by trying to capture part of the surrounding
chain.
• ‘--aa-depth depth ’
The reading function atari_atari looks for combinations beginning with
a series of ataris, and culminating with some string having an unexpected
change in status (e.g. alive to dead or critical). This command line optio
sets the parameter aa_depth which determines how deeply this function
looks for combinations.
• ‘--superstring-depth’
A superstring (see Section 11.8 [Superstrings], page 121) is an amalgama-
tion of tightly strings. Sometimes the best way to attack or defend a string
is by attacking or defending an element of the superstring. Such tactics
are tried below superstring_depth and this command line option allows
this parameter to be set.
The preceeding options are documented with the reading code (see Section 11.1
[Reading Basics], page 110).
• ‘--owl-branch’ Below this depth Owl only considers one move. Default 8.
• ‘--owl-reading’ Below this depth Owl assumes the dragon has escaped. Default 20.
• ‘--owl-node-limit’
If the number of variations exceeds this limit, Owl assumes the dragon can
make life. Default 1000. We caution the user that increasing owl_node_
limit does not necessarily increase the strength of the program.
Chapter 3: Using GNU Go 19
• ‘--owl-node-limit n ’
If the number of variations exceeds this limit, Owl assumes the dragon can
make life. Default 1000. We caution the user that increasing owl_node_
limit does not necessarily increase the strength of the program.
• ‘--owl-distrust n ’
Below this limit some owl reading is truncated.
• ‘-a’, ‘--allpats’
Test all patterns, even those smaller in value than the largest move found
so far. This should never affect GNU Go’s final move, and it will make it
run slower. However this can be very useful when "tuning" GNU Go. It
causes both the traces and the output file (‘-o’) to be more informative.
• ‘-T’, ‘--printboard’: colored display of dragons.
Use rxvt, xterm or Linux Console. (see Section 5.8 [Colored Display],
page 38)
• ‘--showtime’
Print timing information to stderr.
• ‘-E’, ‘--printeyes’: colored display of eye spaces
Use rxvt, xterm or Linux Console. (see Section 5.8 [Colored Display],
page 38)
• ‘-d’, ‘--debug level ’
Produce debugging output. The debug level is given in hexadecimal, using
the bits defined in the following table from ‘engine/gnugo.h’. A list of
these may be produced using ‘--debug-flags’. Here they are in hexadec-
imal:
DEBUG_INFLUENCE 0x0001
DEBUG_EYES 0x0002
DEBUG_OWL 0x0004
DEBUG_ESCAPE 0x0008
DEBUG_MATCHER 0x0010
DEBUG_DRAGONS 0x0020
DEBUG_SEMEAI 0x0040
DEBUG_LOADSGF 0x0080
DEBUG_HELPER 0x0100
DEBUG_READING 0x0200
DEBUG_WORMS 0x0400
DEBUG_MOVE_REASONS 0x0800
DEBUG_OWL_PERFORMANCE 0x1000
DEBUG_LIFE 0x2000
DEBUG_FILLLIB 0x4000
DEBUG_READING_PERFORMANCE 0x8000
DEBUG_SCORING 0x010000
DEBUG_AFTERMATH 0x020000
DEBUG_ATARI_ATARI 0x040000
DEBUG_READING_CACHE 0x080000
DEBUG_TERRITORY 0x100000
DEBUG_OWL_PERSISTENT_CACHE 0X200000
DEBUG_TOP_MOVES 0x400000
DEBUG_MISCELLANEOUS 0x800000
DEBUG_ORACLE_STREAM 0x1000000
These debug flags are additive. If you want to turn on both dragon and
worm debugging you can use ‘-d0x420’.
Chapter 3: Using GNU Go 21
• ‘--debug-flags’
Print the list of debug flags
• ‘-w’, ‘--worms’
Print more information about worm data.
• ‘-m’, ‘--moyo level ’
moyo debugging, show moyo board. The level is fully documented else-
where (see Section 13.13 [Influential Display], page 142).
• ‘-b’, ‘--benchmark number ’
benchmarking mode - can be used with ‘-l’. Causes GNU Go to play itself
repeatedly, seeding the start of the game with a few random moves. This
method of testing the program is largely superceded by use of the twogtp
program.
• ‘-S’, ‘--statistics’
Print statistics (for debugging purposes).
• ‘-t’, ‘--trace’
Print debugging information. Use twice for more detail.
• ‘-r’, ‘--seed seed ’
Set random number seed. This can be used to guarantee that GNU Go
will make the same decisions on multiple runs through the same game. If
seed is zero, GNU Go will play a different game each time.
• ‘--decide-string location ’
Invoke the tactical reading code (see Chapter 11 [Tactical Reading],
page 110 to decide whether the string at location can be captured, and
if so, whether it can be defended. If used with ‘-o’, this will produce a
variation tree in SGF.
• ‘--decide-owl location ’
Invoke the owl code (see Section 12.1 [The Owl Code], page 125) to decide
whether the dragon at location can be captured, and whether it can be
defended. If used with ‘-o’, this will produce a variation tree in SGF.
• ‘--decide-connection location1 /location2 ’
Decide whether dragons at location1 and location2 can be connected. Use-
ful in connection with ‘-o’ to write the variations to an SGF file.
• ‘--decide-dragon-data location ’
Print complete information about the status of the dragon at location.
• ‘--decide-semeai location1 /location2 ’
At location1 and location2 are adjacent dragons of the opposite color.
Neither is aliveby itself, and their fate (alive, dead or seki) depends on the
outcome of a semeai (capturing race). Decide what happens. Useful in
connection with ‘-o’ to write the variations to an SGF file.
• ‘--decide-tactical-semeai location1 /location2 ’
Similar to ‘--decide-semeai’, except that moves proposed by the owl code
are not considered.
Chapter 3: Using GNU Go 22
• ‘--decide-position’
Try to attack and defend every dragon with dragon.escape<6. If used with
‘-o’, writes the variations to an sgf file.
• ‘--decide-eye location ’
Evaluates the eyespace at location and prints a report. You can get more
information by adding ‘-d0x02’ to the command line. (see Section 8.7 [Eye
Local Game Values], page 66.)
• ‘--decide-surrounded location ’
A dragon is surrounded if it is contained in the convex hull of its unfriendly
neighbor dragons. This does not mean that it cannot escape, but it is often
a good indicator that the dragon is under attack. This option draws the
convex hull of the neighbor dragons and decides whether the dragon at
location is surrounded.
• ‘--decide-combination’
Calls the function atari_atari to decide whether there exist combinations
on the board.
• ‘--score method ’
Requires ‘-l’ to specify which game to score and ‘-L’ if you want to score
anywhere else than at the end of the game record. method can be "esti-
mate", "finish", or "aftermath". "finish" and "aftermath" are appropriate
when the game is complete, or nearly so, and both try to supply an ac-
curate final score. Notice that if the game is not already finished it will
be played out, which may take quite a long time if the game is far from
complete. The "estimate" method may be used to get a quick estimate
during the middle of the game. Any of these options may be combined
with ‘--chinese-rules’ if you want to use Chinese (Area) counting.
If the option ‘-o outputfilename ’ is provided, the result will also be writ-
ten as a comment in the output file. For the "finish" and "aftermath" scor-
ing algorithms, the selfplayed moves completing the game are also stored.
• finish
Finish the game by selfplaying until two passes, then de-
termine the status of all stones and compute territory.
• aftermath
Finish the game by selfplaying until two passes, then
accurately determine status of all stones by playing out
the "aftermath", i.e. playing on until all stones except
ones involved in seki have become either unconditionally
(in the strongest sense) alive or unconditionally dead (or
captured). Slower than ‘--score finish’, and while
these algorithms usually agree, if they differ, ‘--score
aftermath’ is most likely to be correct.
• --score aftermath --capture-all-dead --chinese-rules
This combination mandates Tromp-Taylor scoring. The Tromp-Taylor
ruleset requires the game to be played out until all dead stones are removed,
Chapter 3: Using GNU Go 23
For those dragons that are considered weak, a life and death analysis is made (see
Section 12.1 [The Owl Code], page 125). If two dragons next to each other are found that
are both not alive, we try to resolve this situation with the semeai module.
For a more detailed reference of the worm and dragon analysis (and explanations of
the data structures used to store the information), see See Chapter 7 [Worms and Dragons],
page 47.
The influence code is then called second time to make a detailed analysis of likely
territory. Of course, the life-and-death status of dragons are now taken into account.
The territorial results of the influence module get corrected by the break-in module.
This specifically tries to analyze where an opponent could break into an alleged territory,
with sequences that would be too difficult to see for the influence code.
get captured), strategical effects, connection moves, etc. A large set heuristics is necessary
here, e.g. to avoid duplication of such values. This is explained in more detail in Section 6.4
[Valuation], page 44.
resegment_initial_influence()
compute_refined_dragon_weaknesses() (called again after owl)
for each dragon compute_crude_status()
find_neighbor_dragons()
for each dragon compute surround status
for each weak dragon run owl_attack() and owl_defend()
to determine points of attack and defense
for each dragon compute dragon.status
for each thrashing dragon compute owl threats
for each dragon compute dragon.safety
revise_inessentiality()
semeai():
for every semeai, run owl_analyze_semeai()
find_moves_to_make_seki()
identify_thrashing_dragons()
compute_dragon_influence():
compute_influence()
break_territories() (see Section 13.10 [Break Ins], page 137)
compute_refined_dragon_weaknesses()
Now a summary of the sequence of events during the move generation and selection
phases of genmove(), which take place after the information gathering phase has been
completed:
estimate_score()
choose_strategy()
collect_move_reasons():
worm_reasons(): for each attack and defense point add a move reason
semeai_reasons(): for each dragon2.semeai point add a move reason
owl_reasons(): for each owl attack and defense point add a move reason
break_in_reasons(): for each breakin found add a move reason
fuseki()
break_mirror_go()
shapes(): match patterns around the board (see Section 9.1 [Patterns Overview], page 77)
combinations(): look for moves with a double meaning and other tricks
find_double_threats()
atari_atari()
review_move_reasons()
if ahead and there is a thrashing dragon, consider it
alive and reconsider the position
endgame_shapes()
endgame()
if no move found yet, revisit any semeai, change status of dead opponent
to alive, then run shapes() and endgame_shapes() again
if no move found yet, run fill_liberty()
Chapter 4: GNU Go engine overview 29
4.5 Roadmap
The GNU Go engine is contained in two directories, ‘engine/’ and ‘patterns/’. Code
related to the user interface, reading and writing of Smart Game Format files, and testing
are found in the directories ‘interface/’, ‘sgf/’, and ‘regression/’. Code borrowed from
other GNU programs is contained in ‘utils/’. That directory also includes some code
developed within GNU Go which is not go specific. Documentation is in ‘doc/’.
In this document we will describe some of the individual files comprising the engine
code in ‘engine/’ and ‘patterns/’. In ‘interface/’ we mention two files:
• ‘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.
• ‘main.c’
This contains main(). The ‘gnugo’ target is thus built in the ‘interface/’
directory.
• ‘combination.c’
When something can (only) be captured through a series of ataris or other
threats we call this a combination attack. This file contains code to find
such attacks and moves to prevent them.
• ‘dragon.c’
This contains make_dragons(). This function is executed before the move-
generating modules shapes() semeai() and the other move generators but
after make_worms(). It tries to connect worms into dragons and collect
important information about them, such as how many liberties each has,
whether (in GNU Go’s opinion) the dragon can be captured, if it lives, etc.
• ‘endgame.c’
Code to find certain types of endgame moves.
• ‘filllib.c’
Code to force filling of dame (backfilling if necessary) at the end of the
game.
• ‘fuseki.c’
Generates fuseki (opening) moves from a database. Also generates moves
in empty corners.
• ‘genmove.c’
This file contains genmove() and its supporting routines, particularly
examine_position().
• ‘globals.c’
This contains the principal global variables used by GNU Go.
• ‘gnugo.h’
This file contains declarations forming the public interface to the engine.
• ‘hash.c’ and ‘hash.h’
Hashing code implementing Zobrist hashing. (see Section 11.2 [Hashing],
page 112) The code in ‘hash.c’ provides a way to hash board positions into
compact descriptions which can be efficiently compared. The caching code
in ‘cache.c’ makes use of the board hashes when storing and retrieving
read results.
• ‘influence.c’ and ‘influence.h’.
This code determines which regions of the board are under the influence
of either player. (see Chapter 13 [Influence], page 128)
• ‘liberty.h’
Header file for the engine. The name “liberty” connotes freedom (see Ap-
pendix A [Copying], page 206).
• ‘matchpat.c’
This file contains the pattern matcher matchpat(), which looks for patterns
at a particular board location. The actual patterns are in the ‘patterns/’
directory. The function matchpat() is called by every module which does
pattern matching, notably shapes.
Chapter 4: GNU Go engine overview 31
• ‘surround.c’
Code to determine whether a dragon is surrounded and to find moves to
surround with or break out with.
• ‘utils.c’
An assortment of utilities, described in greater detail below.
• ‘value_moves.c’
This file contains the code which assigns values to every move after all
the move reasons are generated. It also tries to generate certain kinds of
additional move reasons.
• ‘worm.c’
This file contains make_worms(), code which is run at the beginning of each
move cycle, before the code in ‘dragon.c’, to determine the attributes of
every string. These attributes are things like liberties, wether the string
can be captured (and how), etc
• ‘eyes.db’
Database of eyeshape patterns. See Chapter 8 [Eyes], page 60, for details.
• ‘helpers.c’
These are helper functions to assist in evaluating moves by matchpat.
• ‘hoshi.sgf’
Smart Game 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 Game Format, and
produces a pattern database.
• ‘komoku.sgf’
Smart Game 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’ as output.
• ‘mkpat.c’
Pattern compiler for the move generation and connection databases. Takes
the file ‘patterns.db’ together with the autogenerated Joseki pattern files
‘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 Game Format file containing 5-3 point openings
• ‘mokuhazushi.db’
Pattern database compiled from mokuhadzushi.sgf
• ‘sansan.sgf’
Smart Game Format file containing 3-3 point openings
• ‘sansan.db’
Pattern database compiled from ‘sansan.sgf’
• ‘takamoku.sgf’
Smart Game 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.
Chapter 4: GNU Go engine overview 34
• ‘patterns.h’
Header file relating to the pattern databases.
• ‘patterns.db’ and ‘patterns2.db’
These contain pattern databases in human readable form.
4.6.2 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 some 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.
• "outdent"
As a workaround, %o at the beginning of the: format string suppresses the
indentation.
4.6.3 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.
4.6.4 FIXME
We have adopted the convention of putting the word FIXME in comments to denote known
bugs, etc.
whether the reading code (in ‘engine/reading.c’) believes the string can be captured, and
if so, whether it believes it can be defended, which moves it finds to attack or defend the
move, how many nodes it searched in coming to these conclusions. Note that when GNU Go
runs normally (not with ‘--decide-string’) the points of attack and defense are computed
when make_worms() runs and cached in worm.attack and worm.defend.
If used with an output file (‘-o filename ’) ‘--decide-string’ will produce a varia-
tion tree showing all the variations which are considered. This is a useful way of debugging
the reading code, and also of educating yourself with the way it works. The variation tree
can be displayed graphically using CGoban.
At each node, the comment contains some information. For example you may find a
comment:
green = alive
cyan = dead
red = critical
yellow = unknown
magenta = unchecked
To get the colored display, save a game in sgf format using CGoban, or using the
‘-o’ option with GNU Go itself.
Open an xterm or rxvt window.
Execute gnugo -l [filename] -L [movenum] -T to get the colored display.
Other useful colored displays may be obtained by using instead:
6 Move generation
6.1 Introduction
GNU Go 3.0 introduced a move generation scheme substantially different from earlier ver-
sions. In particular, it was different from the method of move generation in GNU Go 2.6.
In the old scheme, various move generators suggested different moves with attached
values. The highest such value then decided the move. There were two important drawbacks
with this scheme:
• Efficient multipurpose moves could only be found by patterns which explicitly looked
for certain combinations, such as a simultaneous connection and cut. There was also
no good way to e.g. choose among several attacking moves.
• The absolute move values were increasingly becoming harder to tune with the increasing
number of patterns. They were also fairly subjective and the tuning could easily break
in unexpected ways when something changed, e.g. the worm valuation.
The basic idea of the new move generation scheme is that the various move generators
suggest reasons for moves, e.g. that a move captures something or connects two strings,
and so on. When all reasons for the different moves have been found, the valuation starts.
The primary advantages are
• The move reasons are objective, in contrast to the move values in the old scheme.
Anyone can verify whether a suggested move reason is correct.
• The centralized move valuation makes tuning easier. It also allows for style dependent
tuning, e.g. how much to value influence compared to territory. Another possibility is
to increase the value of safe moves in a winning position.
ANTISUJI_MOVE
Declare an antisuji or forbidden move.
SEMEAI_MOVE
SEMEAI_THREAT
Win or threaten to win a semeai.
EXPAND_TERRITORY_MOVE
EXPAND_MOYO_MOVE
Move expanding our territory/moyo. These reasons are at the moment treated
identically.
VITAL_EYE_MOVE
A vital point for life and death.
STRATEGIC_ATTACK_MOVE
STRATEGIC_DEFEND_MOVE
Moves added by ’a’ and ’d’ class patterns (see Section 9.2 [Pattern Classifica-
tion], page 78) which (perhaps intangibly) attack or defend a dragon.
OWL_ATTACK_MOVE
OWL_DEFEND_MOVE
An owl attack or defense move.
OWL_ATTACK_THREAT
OWL_DEFEND_THREAT
A threat to owl attack or defend a group.
OWL_PREVENT_THREAT
A move to remove an owl threat.
UNCERTAIN_OWL_ATTACK
UNCERTAIN_OWL_DEFENSE
An uncertain owl attack or defense. This means that the owl code could not
decide the outcome, because the owl node limit was reached.
MY_ATARI_ATARI_MOVE
A move that starts a chain of ataris, eventually leading to a capture.
YOUR_ATARI_ATARI_MOVE
A move that if played by the opponent starts a chain of ataris for the opponent,
leading to capture, which is also a safe move for us. Preemptively playing such
a move almost always defends the threat.
The attack and defend move types can have a suffix to denote moves whose re-
sult depends on a ko, e.g. OWL_ATTACK_MOVE_GOOD_KO. Here ..._GOOD_KO and ..._
BAD_KO correspond to KO_A and KO_B as explained in Section 11.4 [Ko], page 116. See
‘engine/move_reasons.h’ for the full of move reasons.
NOTICE: Some of these are reasons for not playing a move.
More detailed discussion of these move reasons will be found in the next section.
Chapter 6: Move generation 42
nodes one owl read can generate. If this is exceeded, the reading is cut short and the result
is cached as usual, but marked uncertain. In this case an owl uncertain move reason may
be generated. For example, if the owl code finds the dragon alive but is unsure, a move to
defend may still be generated.
When all these values have been computed, they are summed, possibly weighted
(secondary value should definitely have a small weight), into a final move value. This value
is used to decide the move.
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.
7.1 Worms
The array struct worm_data worm[MAX_BOARD] collects information about the worms. We
will give definitions of the various fields. Each field has constant value at each vertex of the
worm. We will define each field.
struct worm_data {
int color;
int size;
float effective_size;
int origin;
Chapter 7: Worms and Dragons 48
int liberties;
int liberties2;
int liberties3;
int liberties4;
int lunch;
int cutstone;
int cutstone2;
int genus;
int inessential;
int invincible;
int unconditional_status;
int attack_points[MAX_TACTICAL_POINTS];
int attack_codes[MAX_TACTICAL_POINTS];
int defense_points[MAX_TACTICAL_POINTS];
int defend_codes[MAX_TACTICAL_POINTS];
int attack_threat_points[MAX_TACTICAL_POINTS];
int attack_threat_codes[MAX_TACTICAL_POINTS];
int defense_threat_points[MAX_TACTICAL_POINTS];
int defense_threat_codes[MAX_TACTICAL_POINTS];
};
• color
The color of the worm.
• size
This field contains the cardinality of the worm.
• effective_size
This is the number of stones in a worm plus the number of empty in-
tersections that are at least as close to this worm as to any other worm.
Intersections that are shared are counted with equal fractional values for
each worm. This measures the direct territorial value of capturing a worm.
effective size is a floating point number. Only intersections at a distance
of 4 or less are counted.
• origin
Each worm has a distinguished member, called its origin. The purpose of
this field is to make it easy to determine when two vertices lie in the same
worm: we compare their origin. Also if we wish to perform some test once
for each worm, we simply perform it at the origin and ignore the other
vertices. The origin is characterized by the test:
worm[pos].origin == pos.
• liberties
• liberties2
• liberties3
• liberties4
For a nonempty worm the field liberties is the number of liberties of
the string. This is supplemented by LIBERTIES2, LIBERTIES3 and
Chapter 7: Worms and Dragons 49
LIBERTIES4, which are the number of second order, third order, and
fourth order liberties, respectively. The definition of liberties of order
>1 is adapted to the problem of detecting the shape of the surrounding
empty space. In particular we want to be able to see if a group is loosely
surrounded. A liberty of order n is an empty vertex which may be
connected to the string by placing n stones of the same color on the board,
but no fewer. The path of connection may pass through an intervening
group of the same color. The stones placed at distance >1 may not touch
a group of the opposite color. Connections through ko are not permitted.
Thus in the following configuration:
The convention that liberties of order >1 may not touch a group of the op-
posite color means that knight’s moves and one space jumps are perceived
as impenetrable barriers. This is useful in determining when the string is
becoming surrounded.
The path may also not pass through a liberty at distance 1 if that liberty
is flanked by two stones of the opposing color. This reflects the fact that
the O stone is blocked from expansion to the left by the two X stones in
the following situation:
X.
.O
X.
We say that n is the distance of the liberty of order n from the dragon.
• lunch
If nonzero, lunch points to a boundary worm which can be easily captured.
(It does not matter whether or not the string can be defended.)
We have two distinct notions of cutting stone, which we keep track of in the separate
fields worm.cutstone and worm.cutstone2. We use currently use both concepts in parallel.
• cutstone
This field is equal to 2 for cutting stones, 1 for potential cutting stones.
Otherwise it is zero. Definitions for this field: a cutting stone is one adja-
cent to two enemy strings, which do not have a liberty in common. The
most common type of cutting string is in this situation:
XO
OX
Chapter 7: Worms and Dragons 50
XO
O.
7.2 Amalgamation
A dragon, we have said, is a group of stones which are treated as a unit. It is a working
hypothesis that these stones will live or die together. Thus the program will not expect to
disconnect an opponent’s strings if they have been amalgamated into a single dragon.
The function make_dragons() will amalgamate worms into dragons by maintaining
separate arrays worm[] and dragon[] containing similar data. Each dragon is a union
of worms. Just as the data maintained in worm[] is constant on each worm, the data in
dragon[] is constant on each dragon.
Amalgamation of worms in GNU Go proceeds as follows. First we amalgamate all
boundary components of an eyeshape. Thus in the following example:
The code for this type of amalgamation is in the routine dragon_eye(), discussed
further in EYES.
Next, we amalgamate strings which seem uncuttable. We amalgamate dragons which
either share two or more common liberties, or share one liberty into the which the opponent
cannot play without being captured. (ignores ko rule).
7.3 Connection
The fields black_eye.cut and white_eye.cut are set where the opponent can cut, and
this is done by the B (break) class patterns in ‘conn.db’. There are two important uses for
this field, which can be accessed by the autohelper functions xcut() and ocut(). The first
use is to stop amalgamation in positions like
..X..
OO*OO
X.O.X
..O..
where X can play at * to cut off either branch. What happens here is that first connection
pattern CB1 finds the double cut and marks * as a cutting point. Later the C (connection)
class patterns in conn.db are searched to find secure connections over which to amalgamate
dragons. Normally a diagonal connection would be deemed secure and amalgamated by
connection pattern CC101, but there is a constraint requiring that neither of the empty
intersections is a cutting point.
A weakness with this scheme is that X can only cut one connection, not both, so
we should be allowed to amalgamate over one of the connections. This is performed by
connection pattern CC401, which with the help of amalgamate_most_valuable_helper()
decides which connection to prefer.
The other use is to simplify making alternative connection patterns to the solid
connection. Positions where the diag miai helper thinks a connection is necessary are
marked as cutting points by connection pattern 12. Thus we can write a connection pattern
like CC6:
:8,C,NULL
?xxx?
XOOb?
Oa..?
where we verify that a move at * would stop the enemy from safely playing at the cutting
point, thus defending against the cut.
XXXXX
OO..X
O.O.X
OOXXX
XXXXX
XOO.X
O.O.X
OOXXX
The "topological" algorithm for determining half and false eyes is described elsewhere
(see Section 8.8 [Eye Topology], page 67).
The half eye data is collected in the dragon array. Before this is done, however,
an auxiliary array called half eye data is filled with information. The field type is 0, or
else HALF_EYE or FALSE_EYE depending on which type is found; the fields attack_point[]
point to up to 4 points to attack the half eye, and similarly defense_point[] gives points
to defend the half eye.
Chapter 7: Worms and Dragons 54
struct half_eye_data {
float value; /* Topological eye value */
int type; /* HALF_EYE or FALSE_EYE */
int num_attacks; /* Number of attacking points */
int attack_point[4]; /* The moves to attack a topological halfeye */
int num_defends; /* Number of defending points */
int defense_point[4]; /* The moves to defend a topological halfeye */
};
7.5 Dragons
The array struct dragon_data dragon[MAX_BOARD] collects information about the drag-
ons. We will give definitions of the various fields. Each field has constant value at each
vertex of the dragon. (Fields will be discussed below.)
struct dragon_data {
int color; /* its color */
int id; /* the index into the dragon2 array */
int origin; /* the origin of the dragon. Two vertices */
/* are in the same dragon iff they have */
/* same origin. */
int size; /* size of the dragon */
float effective_size; /* stones and surrounding spaces */
int crude_status; /* (ALIVE, DEAD, UNKNOWN, CRITICAL)*/
int status; /* best trusted status */
};
Other fields attached to the dragon are contained in the dragon_data2 struct array.
(Fields will be discussed below.)
struct dragon_data2 {
int origin;
int adjacent[MAX_NEIGHBOR_DRAGONS];
int neighbors;
int hostile_neighbors;
int moyo_size;
Chapter 7: Worms and Dragons 55
float moyo_territorial_value;
int safety;
float weakness;
float weakness_pre_owl;
int escape_route;
struct eyevalue genus;
int heye;
int lunch;
int surround_status;
int surround_size;
int semeais;
int semeai_margin_of_safety;
int semeai_defense_point;
int semeai_defense_certain;
int semeai_attack_point;
int semeai_attack_certain;
int owl_threat_status;
int owl_status;
int owl_attack_point;
int owl_attack_code;
int owl_attack_certain;
int owl_second_attack_point;
int owl_defense_point;
int owl_defense_code;
int owl_defense_certain;
int owl_second_defense_point;
int owl_attack_kworm;
int owl_defense_kworm;
};
The difference between the two arrays is that the dragon array is indexed by the
board, and there is a copy of the dragon data at every stone in the dragon, while there
is only one copy of the dragon2 data. The dragons are numbered, and the id field of the
dragon is a key into the dragon2 array. Two macros DRAGON and DRAGON2 are provided
for gaining access to the two arrays.
#define DRAGON2(pos) dragon2[dragon[pos].id]
#define DRAGON(d) dragon[dragon2[d].origin]
Thus if you know the position pos of a stone in the dragon you can access the dragon
array directly, for example accessing the origin with dragon[pos].origin. However if you
need a field from the dragon2 array, you can access it using the DRAGON2 macro, for
example you can access its neighor dragons by
for (k = 0; k < DRAGON2(pos).neighbors; k++) {
int d = DRAGON2(pos).adjacent[k];
int apos = dragon2[d].origin;
Chapter 7: Worms and Dragons 56
do_something(apos);
}
Similarly if you know the dragon number (which is dragon[pos].id) then you can
access the dragon2 array directly, or you can access the dragon array using the DRAGON
macro.
Here are the definitions of each field in the dragon arrray.
• color
The color of the dragon.
• id
The dragon number, used as a key into the dragon2 array.
• origin
The origin of the dragon is a unique particular vertex of the dragon, useful
for determining when two vertices belong to the same dragon. Before amal-
gamation the worm origins are copied to the dragon origins. Amalgamation
of two dragons amounts to changing the origin of one.
• size
The number of stones in the dragon.
• effective size
The sum of the effective sizes of the constituent worms. Remembering that
vertices equidistant between two or more worms are counted fractionally in
worm.effective_size, this equals the cardinality of the dragon plus the
number of empty vertices which are nearer this dragon than any other.
• crude status
(ALIVE, DEAD, UNKNOWN, CRITICAL). An early measure of the life
potential of the dragon. It is computed before the owl code is run and is
superceded by the status as soon as that becomes available.
• status
The dragon status is the best measure of the dragon’s health. It is com-
puted after the owl code is run, then revised again when the semeai code
is run.
Here are definitions of the fields in the dragon2 array.
• origin
The origin field is duplicated here.
• adjacent
• adjacent[MAX_NEIGHBOR_DRAGONS]
Dragons of either color near the given one are called neighbors.
They are computed by the function find_neighbor_dragons(). The
dragon2.adjacent array gives the dragon numbers of these dragons.
• neighbors
Dragons of either color near the given one are called neighbors.
They are computed by the function find_neighbor_dragons(). The
dragon2.adjacent array gives the dragon numbers of these dragons.
Chapter 7: Worms and Dragons 57
• neighbors
The number of neighbor dragons.
• hostile neighbors
The number of neighbor dragons of the opposite color.
• moyo size
• float moyo territorial value
The function compute_surrounding_moyo_sizes() assigns a size and a
territorial value to the moyo around each dragon (see Section 13.2 [Territory
and Moyo], page 128). This is the moyo size. They are recorded in these
fields.
• safety
The dragon safety can take on one of the values
− TACTICALLY DEAD - a dragon consisting of a single worm found
dead by the reading code (very reliable)
− ALIVE - found alive by the owl or semeai code
− STRONGLY ALIVE - alive without much question
− INVINCIBLE - definitively alive even after many tenukis
− ALIVE IN SEKI - determined to be seki by the semeai code
− CRITICAL - lives or dies depending on who moves first
− DEAD - found to be dead by the owl code
− INESSENTIAL - the dragon is unimportant (e.g. nakade stones) and
dead
• weakness
• weakness pre owl
A floating point measure of the safety of a dragon. The dragon weakness is
a number between 0. and 1., higher numbers for dragons in greater need of
safety. The field weakness_pre_owl is a preliminary computation before
the owl code is run.
• escape route
A measure of the dragon’s potential to escape towards safety, in case it
cannot make two eyes locally. Documentation may be found in Section 13.9
[Escape], page 135.
• struct eyevalue genus
The approximate number of eyes the dragon can be expected to get. Not
guaranteed to be accurate. The eyevalue struct, which is used throughout
the engine, is declared thus:
struct eyevalue {
unsigned char a; /* # of eyes if attacker plays twice */
unsigned char b; /* # of eyes if attacker plays first */
unsigned char c; /* # of eyes if defender plays first */
unsigned char d; /* # of eyes if defender plays twice */
Chapter 7: Worms and Dragons 58
};
• heye
Location of a half eye attached to the dragon.
• lunch
If nonzero, this is the location of a boundary string which can be captured.
In contrast with worm lunches, a dragon lunch must be able to defend
itself.
• surround status
• surround size
In estimating the safety of a dragon it is useful to know if it is surrounded.
See Section 13.11 [Surrounded Dragons], page 139 and the comments in
‘surround.c’ for more information about the algorithm. Used in comput-
ing the escape route, and also callable from patterns (currently used by
CB258).
• semeais
• semeai defense point
• semeai defense certain
• semeai attack point
• semeai attack certain
If two dragons of opposite color both have the status CRITICAL or DEAD
they are in a semeai (capturing race), and their status must be adjudicated
by the function owl_analyze_semeai() in ‘owl.c’, which attempts to de-
termine which is alive, which dead, or if the result is seki, and whether it is
important who moves first. The function ‘new_semeai()’ in ‘semeai.c’ at-
tempts to revise the statuses and to generate move reasons based on these
results. The field dragon2.semeais is nonzero if the dragon is an element
of a semeai, and equals the number of semeais (seldom more than one).
The semeai defense and attack points are locations the defender or at-
tacker must move to win the semeai. The field semeai_margin_of_safety
is intended to indicate whether the semeai is close or not but currently this
field is not maintained. The fields semeai_defense_certain and semeai_
attack_certain indicate that the semeai code was able to finish analysis
without running out of nodes.
• owl status
This is a classification similar to dragon.crude_status, but based on the
life and death reading in ‘owl.c’. The owl code (see Section 12.1 [The
Owl Code], page 125) is skipped for dragons which appear safe by certain
heuristics. If the owl code is not run, the owl status is UNCHECKED. If owl_
attack() determines that the dragon cannot be attacked, it is classified
as ALIVE. Otherwise, owl_defend() is run, and if it can be defended it is
classified as CRITICAL, and if not, as DEAD.
• owl attack point
If the dragon can be attacked this is the point to attack the dragon.
Chapter 7: Worms and Dragons 59
The purpose of this Chapter is to describe the algorithm used in GNU Go to determine
eyes.
Each connected eyespace of a dragon affords a local game which yields a local game
tree. The score of this local game is the number of eyes it yields. Usually if the players take
turns and make optimal moves, the end scores will differ by 0 or 1. In this case, the local
game may be represented by a single number, which is an integer or half integer. Thus if
‘n(O)’ is the score if ‘O’ moves first, both players alternate (no passes) and make alternate
moves, and similarly ‘n(X)’, the game can be represented by ‘{n(O)|n(X)}’. Thus {1|1} is
an eye, {2|1} is an eye plus a half eye, etc.
The exceptional game {2|0} can occur, though rarely. We call an eyespace yielding
this local game a CHIMERA. The dragon is alive if any of the local games ends up with a
score of 2 or more, so {2|1} is not different from {3|1}. Thus {3|1} is NOT a chimera.
XXXXX
XOOOX
XO.OOX
XX..OX
XXOOXX
XXXXX
|. X . X X . . X O X O
|X . . . . . X X O O O
|O X X X X . . X O O O
|O O O O X . O X O O O
|. . . . O O O O X X O
|X O . X X X . . X O O
|X O O O O O O O X X O
|. X X O . O X O . . X
|X . . X . X X X X X X
|O X X O X . X O O X O
Here the ‘O’ dragon which is surrounded in the center has open eye space. In the
middle of this open eye space are three dead ‘X’ stones. This space is large enough that
O cannot be killed. We can abstract the properties of this eye shape as follows. Marking
certain vertices as follows:
|- X - X X - - X O X O
|X - - - - - X X O O O
|O X X X X - - X O O O
|O O O O X - O X O O O
|! . . . O O O O X X O
|X O . X X X . ! X O O
|X O O O O O O O X X O
|- X X O - O X O - - X
|X - - X - X X X X X X
|O X X O X - X O O X O
!...
.XXX.!
The marginal vertices are marked with an exclamation point (‘!’). The captured ‘X’
stones inside the eyespace are naturally marked ‘X’.
The precise algorithm by which the eye spaces are determined is somewhat complex.
Documentation of this algorithm is in the comments in the source to the function make_
domains() in ‘optics.c’.
The eyespaces can be conveniently displayed using a colored ascii diagram by running
gnugo -E.
! . X
x
xX.!
:0111
Here notation is as above, except that ‘x’ means ‘X’ or EMPTY. The result of the
pattern is not different if ‘X’ has stones at these vertices or not.
We may abstract the local game as follows. The two players ‘O’ and ‘X’ take turns
moving, or either may pass.
RULE 1: ‘O’ for his move may remove any vertex marked ‘!’ or marked ‘.’.
RULE 2: ‘X’ for his move may replace a ‘.’ by an ‘X’.
RULE 3: ‘X’ may remove a ‘!’. In this case, each ‘.’ adjacent to the ‘!’ which is
removed becomes a ‘!’ . If an ‘X’ adjoins the ‘!’ which is removed, then that ‘X’ and any
which are connected to it are also removed. Any ‘.’ which are adjacent to the removed ‘X’’s
then become ‘.’.
Thus if ‘O’ moves first he can transform the eyeshape in the above example to:
... or !...
.XXX.! .XXX.
However if ‘X’ moves he may remove the ‘!’ and the ‘.’s adjacent to the ‘!’ become
‘!’ themselves. Thus if ‘X’ moves first he may transform the eyeshape to:
!.. or !..
.XXX.! .XXX!
NOTE: A nuance which is that after the ‘X:1’, ‘O:2’ exchange below, ‘O’ is threaten-
ing to capture three X stones, hence has a half eye to the left of 2. This is subtle, and there
are other such subtleties which our abstraction will not capture. Some of these at least can
be dealt with by a refinements of the scheme, but we will content ourselves for the time
being with a simplified model.
Chapter 8: Eyes and Half Eyes 63
|- X - X X - - X O X O
|X - - - - - X X O O O
|O X X X X - - X O O O
|O O O O X - O X O O O
|1 2 . . O O O O X X O
|X O . X X X . 3 X O O
|X O O O O O O O X X O
|- X X O - O X O - - X
|X - - X - X X X X X X
|O X X O X - X O O X O
We will not attempt to characterize the terminal states of the local game (some of
which could be seki) or the scoring.
8.4 An example
Here is a local game which yields exactly one eye, no matter who moves first:
!
...
...!
...
..!
...
..
.X. (nakade)
..
Here is another variation:
Chapter 8: Eyes and Half Eyes 64
! (start)
...
...!
. .
..X!
. !
.!
8.5 Graphs
It is a useful observation that the local game associated with an eyespace depends only on
the underlying graph, which as a set consists of the set of vertices, in which two elements
are connected by an edge if and only if they are adjacent on the Go board. For example
the two eye shapes:
..
..
and
....
though distinct in shape have isomorphic graphs, and consequently they are isomorphic as
local games. This reduces the number of eyeshapes in the database ‘patterns/eyes.db’.
A further simplification is obtained through our treatment of half eyes and false eyes.
Such patterns are identified by the topological analysis (see Section 8.8 [Eye Topology],
page 67).
A half eye is isomorphic to the pattern (!.) . To see this, consider the following two
eye shapes:
XOOOOOO
X.....O
XOOOOOO
Chapter 8: Eyes and Half Eyes 65
and:
XXOOOOO
XOa...O
XbOOOOO
XXXXXXX
These are equivalent eyeshapes, with isomorphic local games {2|1}. The first has
shape:
!....
The second eyeshape has a half eye at ‘a’ which is taken when ‘O’ or ‘X’ plays at ‘b’.
This is found by the topological criterion (see Section 8.8 [Eye Topology], page 67).
The graph of the eye shape, ostensibly ‘....’ is modified by replacing the left ‘.’ by
‘!.’ during graph matching.
A false eye is isomorphic to the pattern (!) . To see this, consider the following eye
shape:
XXXOOOOOO
X.Oa....O
XXXOOOOOO
This is equivalent to the two previous eyeshapes, with an isomorphic local game
{2|1}.
This eyeshape has a false eye at ‘a’. This is also found by the topological criterion.
The graph of the eye shape, ostensibly ‘.....’ is modified by replacing the left ‘.’
by ‘!’. This is made directly in the eye data, not only during graph matching.
Pattern 6141
X
XX.@x
:1122
which e.g. matches in this position:
.OOOXXX
OOXOXOO
OXXba.O
OOOOOOO
Now it may look like ‘X’ could take away both eyes by playing ‘a’ followed by ‘b’,
giving 0122 as eye value. This is where the subtlety of the definition of the first digit in
the eye value comes into play. It does not say that the attacker is allowed two consecutive
moves but only that he is allowed to play "another move". The crucial property of this
shape is that when ‘X’ plays at a to destroy (at least) one eye, ‘O’ can answer at ‘b’, giving:
.OOOXXX
OO.OXOO
O.cOX.O
OOOOOOO
Now ‘X’ has to continue at ‘c’ in order to keep ‘O’ at one eye. After this ‘O’ plays
tenuki and ‘X’ cannot destroy the remaining eye by another move. Thus the eye value is
indeed 1122.
As a final note, some of the eye values indicating a threat depend on suicide to be
allowed, e.g.
Pattern 301
X.X
:1222
OOXX
O.O.
OO.X
Chapter 8: Eyes and Half Eyes 68
A FALSE EYE is an eye vertex which cannot become a proper eye. Here are two
examples of false eyes for O:
OOX OOX
O.O O.OO
XOO OOX
We describe now the topological algorithm used to find half eyes and false eyes. In
this section we ignore the possibility of ko.
False eyes and half eyes can locally be characterized by the status of the diagonal
intersections from an eye space. For each diagonal intersection, which is not within the eye
space, there are three distinct possibilities:
• occupied by an enemy (X) stone, which cannot be captured.
• either empty and X can safely play there, or occupied by an X stone that can both be
attacked and defended.
• occupied by an O stone, an X stone that can be attacked but not defended, or it’s empty
and X cannot safely play there.
We give the first possibility a value of two, the second a value of one, and the last
a value of zero. Summing the values for the diagonal intersections, we have the following
criteria:
• sum >= 4: false eye
• sum == 3: half eye
• sum <= 2: proper eye
If the eye space is on the edge, the numbers above should be decreased by 2. An
alternative approach is to award diagonal points which are outside the board a value of 1.
To obtain an exact equivalence we must however give value 0 to the points diagonally off
the corners, i.e. the points with both coordinates out of bounds.
The algorithm to find all topologically false eyes and half eyes is:
For all eye space points with at most one neighbor in the eye space, evaluate the
status of the diagonal intersections according to the criteria above and classify the point
from the sum of the values.
.X..
XOX. (slightly) better than proper eye
(c) O.OO e < 2
OO.O
O.OO e = 2a
XOX.
.X..
.X..
XOX. proper eye, some aji
(c’) O.OO e ~ 2
OO.O
OXOO e = a + b
X.X.
.X..
.X..
X.X. better than half eye, worse than proper eye
(c’’) OXOO 2 < e < 3
OO.O
OXOO e = 2b
X.X.
.X..
.X...
XOX.. better than half eye, worse than proper eye
(d) O.O.X 2 < e < 3
OO.O.
O.OO. e = 1 + 2a
XOX..
.X...
.X...
XOX.. half eye, some aji
(d’) O.O.X e ~ 3
OO.O.
OXOO. e = 1 + a + b
X.X..
.X...
Chapter 8: Eyes and Half Eyes 71
.X...
X.X.. better than false eye, worse than half eye
(d’’) OXO.X 3 < e < 4
OO.O.
OXOO. e = 1 + 2b
X.X..
.X...
.X...
XOX.. better than false eye, worse than half eye
(e) O.OXX 3 < e < 4
OO.O.
O.OO. e = 2 + 2a
XOX..
.X...
.X...
XOX.. false eye, some aji
(e’) O.OXX e ~ 4
OO.O.
OXOO. e = 2 + a + b
X.X..
.X...
.X...
X.X.. (slightly) worse than false eye
(e’’) OXOXX 4 < e
OO.O.
OXOO. e = 2 + 2b
X.X..
.X...
Summarizing the analysis above we have the following table for the four different
choices of a and b.
case symbolic a=1/2 a=2/3 a=3/4 a=4/5 desired
Chapter 8: Eyes and Half Eyes 72
We can notice that (i) fails for the cases (c”), (d), (d”), and (e). The other three
choices get all values in the correct intervals. The main distinction between them is the
relative ordering of (c”) and (d) (or analogously (d”) and (e)). If we do a more detailed
analysis of these we can see that in both cases ‘O’ can secure the eye unconditionally if he
moves first while ‘X’ can falsify it with ko if he moves first. The difference is that in (c”),
‘X’ has to make the first ko threat, while in (d), O has to make the first ko threat. Thus
(c”) is better for O and ought to have a smaller topological eye value than (d). This gives
an indication that (iv) is the better choice.
We can notice that any value of a, b satisfying a+b=2 and 3/4<a<1 would have
the same qualities as choice (iv) according to the analysis above. One interesting choice
is a=7/8, b=9/8 since these allow exact computations with floating point values having a
binary mantissa. The latter property is shared by a=3/4 and a=1/2.
When there are three kos around the same eyespace, things become more complex.
This case is, however, rare enough that we ignore it.
For this algorithm the strings which are not lively are invisible. Ignoring these, the
algorithm assigns friendly influence to
1. every vertex which is occupied by a (lively) friendly stone,
2. every empty vertex adjoining a (lively) friendly stone,
3. every empty vertex for which two adjoining vertices (not on the first line) in the (usually
8) surrounding ones have friendly influence, with two CAVEATS explained below.
Thus in the following diagram, ‘e’ would be assigned friendly influence if ‘a’ and ‘b’
have friendly influence, or ‘a’ and ‘d’. It is not sufficent for ‘b’ and ‘d’ to have friendly
influence, because they are not adjoining.
uabc
def
ghi
The constraint that the two adjoining vertices not lie on the first line prevents influ-
ence from leaking under a stone on the third line.
The first CAVEAT alluded to above is that even if ‘a’ and ‘b’ have friendly influence,
this does not cause ‘e’ to have friendly influence if there is a lively opponent stone at ‘d’.
This constraint prevents influence from leaking past knight’s move extensions.
The second CAVEAT is that even if ‘a’ and ‘b’ have friendly influence this does not
cause ‘e’ to have influence if there are lively opponent stones at ‘u’ and at ‘c’. This prevents
influence from leaking past nikken tobis (two space jumps).
The corner vertices are handled slightly different.
+---
|ab
|cd
We get friendly influence at ‘a’ if we have friendly influence at ‘b’ or ‘c’ and no lively
unfriendly stone at ‘b’, ‘c’ or ‘d’.
Here are the public functions in ‘optics.c’, except some simple access functions
used by autohelpers. The statically declared functions are documented in the source code.
• void make_domains(struct eye_data b_eye[BOARDMAX], struct eye_data
w_eye[BOARDMAX], int owl_call)
This function is called from make_dragons() and from owl_determine_
life(). It marks the black and white domains (eyeshape regions) and
collects some statistics about each one.
• void partition_eyespaces(struct eye_data eye[BOARDMAX], int color)
Find connected eyespace components and compute relevant statistics.
• void propagate_eye(int origin, struct eye_data eye[BOARDMAX])
propagate eye(origin) copies the data at the (origin) to the rest of the eye
(invariant fields only).
• int find_eye_dragons(int origin, struct eye_data eye[BOARDMAX], int
eye_color, int dragons[], int max_dragons)
Find the dragon or dragons surrounding an eye space. Up to max dragons
dragons adjacent to the eye space are added to the dragon array, and the
number of dragons found is returned.
Chapter 8: Eyes and Half Eyes 74
Attack and defense points for control of the diagonals are stored in the
heye[] array. my_eye is the eye space information with respect to color.
• int obvious_false_eye(int pos, int color)
Conservative relative of topological_eye(). Essentially the same algo-
rithm is used, but only tactically safe opponent strings on diagonals are
considered. This may underestimate the false/half eye status, but it should
never be overestimated.
• void set_eyevalue(struct eyevalue *e, int a, int b, int c, int d)
set parameters into the struct eyevalue as follows: (see Section 8.7 [Eye
Local Game Values], page 66):
struct eyevalue { /* number of eyes if: */
unsigned char a; /* attacker plays first twice */
unsigned char b; /* attacker plays first */
unsigned char c; /* defender plays first */
unsigned char d; /* defender plays first twice */
};
• int min_eye_threat(struct eyevalue *e)
Number of eyes if attacker plays first twice (the threat of the first move by
attacker).
• int min_eyes(struct eyevalue *e)
Number of eyes if attacker plays first followed by alternating play.
• int max_eyes(struct eyevalue *e)
Number of eyes if defender plays first followed by alternating play.
• int max_eye_threat(struct eyevalue *e)
Number of eyes if defender plays first twice (the threat of the first move
by defender).
• void add_eyevalues(struct eyevalue *e1, struct eyevalue *e2, struct
eyevalue *sum)
Add the eyevalues *e1 and *e2, leaving the result in *sum. It is safe to let
sum be the same as e1 or e2.
• char * eyevalue_to_string(struct eyevalue *e)
Produces a string containing the eyevalue. Note: the result string is stored
in a statically allocated buffer which will be overwritten the next time this
function is called.
• void test_eyeshape(int eyesize, int *eye_vertices) /* Test whether the optics
code evaluates an eyeshape consistently. */
• int analyze_eyegraph(const char *coded_eyegraph, struct eyevalue *value,
char *analyzed_eyegraph)
Analyze an eye graph to determine the eye value and vital moves. The eye
graph is given by a string which is encoded with ‘%’ for newlines and ‘O’
for spaces. E.g., the eye graph
!
Chapter 8: Eyes and Half Eyes 76
.X
!...
is encoded as OO!%O.X%!.... (The encoding is needed for the GTP in-
terface to this function.) The result is an eye value and a (nonencoded)
pattern showing the vital moves, using the same notation as eyes.db. In
the example above we would get the eye value 0112 and the graph (showing
ko threat moves)
.X
!.*.
If the eye graph cannot be realized, 0 is returned, 1 otherwise.
Chapter 9: The Pattern Code 77
9.1 Overview
Several pattern databases are in the patterns directory. This chapter primarily discusses
the patterns in ‘patterns.db’, ‘patterns2.db’, and the pattern files ‘hoshi.db’ etc. which
are compiled from the SGF files ‘hoshi.sgf’ (see Section 9.16 [Joseki Compiler], page 98).
There is no essential difference between these files, except that the ones in ‘patterns.db’
and ‘patterns2.db’ are hand written. They are concatenated before being compiled by
mkpat into ‘patterns.c’. The purpose of the separate file ‘patterns2.db’ is that it is
handy to move patterns into a new directory in the course of organizing them. The patterns
in ‘patterns.db’ are more disorganized, and are slowly being moved to ‘patterns2.db’.
During the execution of genmove(), the patterns are matched in ‘shapes.c’ in order
to find move reasons.
The same basic pattern format is used by ‘attack.db’, ‘defense.db’, ‘conn.db’,
‘apats.db’ and ‘dpats.db’. However these patterns are used for different purposes. These
databases are discussed in other parts of this documentation. The patterns in ‘eyes.db’
are entirely different and are documented elsewhere (see Chapter 8 [Eyes], page 60).
The patterns described in the databases are ascii representations, of the form:
Pattern EB112
:8,ed,NULL
Here ‘O’ marks a friendly stone, ‘X’ marks an enemy stone, ‘.’ marks an empty vertex,
‘*’ marks O’s next move, ‘o’ marks a square either containing ‘O’ or empty but not ‘X’. (The
symbol ‘x’, which does not appear in this pattern, means ‘X’ or ‘.’.) Finally ‘?’ Indicates
a location where we don’t care what is there, except that it cannot be off the edge of the
board.
The line of ‘-’’s along the bottom in this example is the edge of the board itself—
this is an edge pattern. Corners can also be indicated. Elements are not generated for ‘?’
markers, but they are not completely ignored - see below.
The line beginning ‘:’ describes various attributes of the pattern, such as its sym-
metry and its class. Optionally, a function called a “helper” can be provided to assist the
matcher in deciding whether to accept move. Most patterns do not require a helper, and
this field is filled with NULL.
The matcher in ‘matchpat.c’ searches the board for places where this layout appears
on the board, and the callback function shapes_callback() in ‘shapes.c’ registers the
appropriate move reasons.
After the pattern, there is some supplementary information in the format:
Chapter 9: The Pattern Code 78
Here trfno represents the number of transformations of the pattern to consider, usu-
ally ‘8’ (no symmetry, for historical reasons), or one of ‘|’, ‘\’, ‘/’, ‘-’, ‘+’, ‘X’, where the
line represents the axis of symmetry. (E.g. ‘|’ means symmetrical about a vertical axis.)
The above pattern could equally well be written on the left edge:
|oOO?
|...X
|..*?
|..o.
|..o?
:8,ed,NULL
The program mkpat is capable of parsing patterns written this way, or for that
matter, on the top or right edges, or in any of the four corners. As a matter of convention
all the edge patterns in ‘patterns.db’ are written on the bottom edge or in the lower left
corners. In the ‘patterns/’ directory there is a program called transpat which can rotate
or otherwise transpose patterns. This program is not built by default—if you think you
need it, make transpat in the ‘patterns/’ directory and consult the usage remarks at the
beginning of ‘patterns/transpat.c’.
• ‘F’
This indicates a fuseki pattern. This is only effective together with either
the ‘j’ or ‘t’ classification, and is used to ensure indeterministic play during
fuseki.
• ‘j’
Slightly less urgent joseki move. These moves will be made after those with
the ‘J’ classification. This adds the ‘e’ and ‘E’ classifications. If the move
has the ‘F’ classification, it also gets a fixed value of 20.1, otherwise it gets
a minimum accepted value of 20. (This makes sure that GNU Go chooses
randomly between different moves that have ‘jF’ as classification.)
• ‘t’
Minor joseki move (tenuki OK). This is equivalent to adding the ‘e’ and
‘E’ classifications together with either a fixed value of 15.07 (if the move
has ‘F’ classification) or a minimum value of 15 (otherwise).
• ‘U’
Urgent joseki move (never tenuki). This is equivalent to the ‘d’ and ‘a’
classifications together with a shape bonus of 15 and a minimum accepted
value of 40.
A commonly used class is OX (which rejects pattern if either side has dead stones).
The string ‘-’ may be used as a placeholder. (In fact any characters other than the above
and ‘,’ are ignored.)
The types ‘o’ and ‘O’ could conceivably appear in a class, meaning it applies only
to UNKNOWN. ‘X’ and ‘x’ could similarly be used together. All classes can be combined
arbitrarily.
?O. ?Ob
.X* aX*
?O. ?Oc
:8,C,wedge_helper
*/
The image on the left is the actual pattern. On the right we’ve taken this image and
added letters to label apos, bpos, and cpos. The position of *, the point where GNU Go
will move if the pattern is adopted, is passed through the parameter move.
int
wedge_helper(ARGS)
{
int apos, bpos, cpos;
int other = OTHER_COLOR(color);
int success = 0;
if (TRYMOVE(move, color)) {
if (TRYMOVE(apos, other)) {
if (board[apos] == EMPTY || attack(apos, NULL))
success = 1;
else if (TRYMOVE(bpos, color)) {
if (!safe_move(cpos, other))
success = 1;
popgo();
Chapter 9: The Pattern Code 82
}
popgo();
}
popgo();
}
return success;
}
The OFFSET lines tell GNU Go the positions of the three stones at ‘a’, ‘b’, and ‘c’.
To decide whether the pattern guarantees a connection, we do some reading. First we use
the TRYMOVE macro to place an ‘O’ at ‘move’ and let ‘X’ draw back to ‘a’. Then we ask
whether ‘O’ can capture these stones by calling attack(). The test if there is a stone at
‘a’ before calling attack() is in this position not really necessary but it’s good practice to
do so, because if the attacked stone should happen to already have been captured while
placing stones, GNU Go would crash with an assertion failure.
If this attack fails we let ‘O’ connect at ‘b’ and use the safe_move() function to
examine whether a cut by ‘X’ at ‘c’ could be immediately captured. Before we return the
result we need to remove the stones we placed from the reading stack. This is done with
the function popgo().
Pattern Conn311
O*.
?XO
:8,C,NULL
O*a
?BO
;oplay_attack_either(*,a,a,B)
Here we have given the label ‘a’ to the empty spot to the right of the considered
move and the label ‘B’ to the ‘X’ stone in the pattern. In addition to these, ‘*’ can also be
used as a label. A label may be any lowercase or uppercase ascii letter except OoXxt. By
Chapter 9: The Pattern Code 83
convention we use uppercase letters for ‘X’ stones and lowercase for ‘O’ stones and empty
intersections. When labeling a stone that’s part of a larger string in the pattern, all stones
of the string should be marked with the label. (These conventions are not enforced by the
pattern compiler, but to make the database consistent and easy to read they should be
followed.)
The labels can now be used in the constraint expression. In this example we have a
reading constraint which should be interpreted as "Play an ‘O’ stone at ‘*’ followed by an
‘X’ stone at ‘a’. Accept the pattern if ‘O’ now can capture either at ‘a’ or at ‘B’ (or both
strings)."
The functions that are available for use in the constraints are listed in the section
‘Autohelpers Functions’ below. Technically the constraint expression is transformed by
mkpat into an automatically generated helper function in ‘patterns.c’. The functions in
the constraint are replaced by C expressions, often functions calls. In principle any valid C
code can be used in the constraints, but there is in practice no reason to use anything more
than boolean and arithmetic operators in addition to the autohelper functions. Constraints
can span multiple lines, which are then concatenated.
Pattern EJ4
...*. continuation
.OOX.
..XOX
.....
-----
:8,Ed,NULL
>antisuji(a)
The line starting with ‘>’ is the action line. In this case it tells the move generation
that the move at a should not be considered, whatever move reasons are found by other
patterns. The action line uses the labels from the constraint diagram. Both constraint and
Chapter 9: The Pattern Code 84
action can be used in the same pattern. If the action only needs to refer to ‘*’, no constraint
diagram is required. Like constraints, actions can span multiple lines.
Here is a partial list of the autohelper macros which are typically called from action
lines. This list is not complete. If you cannot find an autohelper macro in an action line
in this list, consult ‘mkpat.c’ to find out what function in the engine is actually called.
If no macro exists which does what you want, you can add macros by editing the list in
‘mkpat.c’.
• antisuji(a);
Mark ‘a’ as an antisuji, that is, a move that must never be played.
• replace(a,*)
This is appropriate if the move at ‘*’ is definitely better than the move
at ‘a’. The macro adds a point redistribution rule. Any points which
are assigned to ‘a’ during the move generation by any move reason are
redistributed to ‘*’.
• prevent_attack_threat(a)
Add a reverse followup value because the opponent’s move here would
threaten to capture ‘a’.
• threaten_to_save(a)
Add a followup value because the move at ‘*’ threatens to rescue the dead
string at ‘a’.
• defend_against_atari(a)
Estimate the value of defending the string ‘a’ which can be put into atari
and add this as a reverse followup value.
• add_defend_both_move(a,b);
• add_cut_move(c,d);
Add to the move reasons that the move at ‘*’ threatens to cut ‘c’ and ‘d’.
lib(x)
lib2(x)
lib3(x)
lib4(x)
Number of first, second, third, and fourth order liberties of a worm respectively. See
Chapter 7 [Worms and Dragons], page 47, the documentation on worms for definitions.
xlib(x)
olib(x)
Chapter 9: The Pattern Code 85
The number of liberties that an enemy or own stone, respectively, would obtain if
played at the empty intersection ‘x’.
xcut(x)
ocut(x)
Calls cut_possible (see Section 18.1 [General Utilities], page 166) to determine
whether ‘X’ or ‘O’ can cut at the empty intersection ‘x’.
ko(x)
True if ‘x’ is either a stone or an empty point involved in a ko position.
status(x)
The matcher status of a dragon. status(x) returns an integer that can have the values
ALIVE, UNKNOWN, CRITICAL, or DEAD (see Chapter 7 [Worms and Dragons], page 47).
alive(x)
unknown(x)
critical(x)
dead(x)
Each function true if the dragon has the corresponding matcher status and false
otherwise (see Chapter 7 [Worms and Dragons], page 47).
status(x)
Returns the status of the dragon at ‘x’ (see Chapter 7 [Worms and Dragons], page 47).
genus(x)
The number of eyes of a dragon. It is only meaningful to compare this value against
0, 1, or 2.
xarea(x)
oarea(x)
xmoyo(x)
omoyo(x)
xterri(x)
oterri(x)
attack(x)
defend(x)
Chapter 9: The Pattern Code 86
safe_xmove(x)
safe_omove(x)
True if an enemy or friendly stone, respectively, can safely be played at ‘x’. By safe
it is understood that the move is legal and that it cannot be captured right away.
legal_xmove(x)
legal_omove(x)
o_somewhere(x,y,z, ...)
x_somewhere(x,y,z, ...)
True if O (respectively X) has a stone at one of the labelled vertices. In the diagram,
these vertices should be marked with a ‘?’.
odefend_against(x,y)
xdefend_against(x,y)
True if an own stone at ‘x’ would stop the enemy from safely playing at ‘y’, and
conversely for the second function.
does_defend(x,y)
does_attack(x,y)
True if a move at ‘x’ defends/attacks the worm at ‘y’. For defense a move of the
same color as ‘y’ is tried and for attack a move of the opposite color.
xplay_defend(a,b,c,...,z)
oplay_defend(a,b,c,...,z)
xplay_attack(a,b,c,...,z)
oplay_attack(a,b,c,...,z)
the same color starts. The defend functions return true if the worm cannot be attacked in
the position or if it can be attacked but also defended. The attack functions return true
if there is a way to capture the worm, whether or not it can also be defended. If there is
no stone present at ‘z’ after the moves have been played, it is assumed that an attack has
already been successful or a defense has already failed. If some of the moves should happen
to be illegal, typically because it would have been suicide, the following moves are played
as if nothing has happened and the attack or defense is tested as usual. It is assumed that
this convention will give the relevant result without requiring a lot of special cases.
The special label ‘?’ can be used to represent a tenuki. Thus oplay_
defend(a,?,b,c) tries moves by ‘O’ at ‘a’ and ‘b’, as if ‘X’ plays the second move in
another part of the board, then asks if ‘c’ can be defended. The tenuki cannot be the first
move of the sequence, nor does it need to be: instead of oplay_defend(?,a,b,c) you can
use xplay_defend(a,b,c).
xplay_defend_both(a,b,c,...,y,z)
oplay_defend_both(a,b,c,...,y,z)
xplay_attack_either(a,b,c,...,y,z)
oplay_attack_either(a,b,c,...,y,z)
These functions are similar to the previous ones. The difference is that the last *two*
arguments denote worms to be attacked or defended simultaneously. Obviously ‘y’ and ‘z’
must have the same color. If either location is empty, it is assumed that an attack has been
successful or a defense has failed. The typical use for these functions is in cutting patterns,
where it usually suffices to capture either cutstone.
The function xplay_defend_both plays alternate moves beginning with an ‘X’ at ‘a’.
Then it passes the last two arguments to defend_both in ‘engine/utils.c’. This function
checks to determine whether the two strings can be simultaneously defended.
The function xplay_attack_either plays alternate moves beginning with an ‘X’
move at ‘a’. Then it passes the last two arguments to attack_either in ‘engine/utils.c’.
This function looks for a move which captures at least one of the two strings. In its current
implementation attack_either only looks for uncoordinated attacks and would thus miss
a double atari.
xplay_connect(a,b,c,...,y,z)
oplay_connect(a,b,c,...,y,z)
xplay_disconnect(a,b,c,...,y,z)
oplay_disconnect(a,b,c,...,y,z)
xplay_break_through(a,b,c,...,x,y,z)
oplay_break_through(a,b,c,...,x,y,z)
.O. .y.
OXO xXz
and ‘X’ aims at capturing at least one of ‘x’, ‘y’, and ‘z’. If this succeeds ‘1’ is returned. If
it doesn’t, ‘X’ tries instead to cut through on either side and if this succeeds, ‘2’ is returned.
Of course the same shape with opposite colors can also be used.
Important notice: ‘x’, ‘y’, and ‘z’ must be given in the order they have in the diagram
above, or any reflection and/or rotation of it.
seki_helper(x)
Checks whether the string at ‘x’ can attack any surrounding string. If so, return
false as the move to create a seki (probably) wouldn’t work.
threaten_to_save(x)
Calls add_followup_value to add as a move reason a conservative estimate of the
value of saving the string ‘x’ by capturing one opponent stone.
area_stone(x)
Returns the number of stones in the area around ‘x’.
area_space(x)
Returns the amount of space in the area around ‘x’.
eye(x)
proper_eye(x)
marginal_eye(x)
True if ‘x’ is an eye space for either color, a non-marginal eye space for either color,
or a marginal eye space for either color, respectively.
antisuji(x)
Tell the move generation that ‘x’ is a substandard move that never should be played.
same_dragon(x,y)
same_worm(x,y)
Return true if ‘x’ and ‘y’ are the same dragon or worm respectively.
dragonsize(x)
wormsize(x)
Number of stones in the indicated dragon or worm.
add_connect_move(x,y)
add_cut_move(x,y)
add_attack_either_move(x,y)
add_defend_both_move(x,y)
Explicitly notify the move generation about move reasons for the move in the pattern.
halfeye(x)
Returns true if the empty intersection at ‘x’ is a half eye.
remove_attack(x)
Inform the tactical reading that a supposed attack does in fact not work.
Chapter 9: The Pattern Code 89
potential_cutstone(x)
True if cutstone2 field from worm data is larger than one. This indicates that saving
the worm would introduce at least two new cutting points.
not_lunch(x,y)
Prevents the misreporting of ‘x’ as lunch for ‘y’. For example, the following pattern
tells GNU Go that even though the stone at ‘a’ can be captured, it should not be considered
“lunch” for the dragon at ‘b’, because capturing it does not produce an eye:
XO| ba|
O*| O*|
oo| oo|
?o| ?o|
> not_lunch(a,b)
vital_chain(x)
Calls vital_chain to determine whether capturing the stone at ‘x’ will result in one
eye for an adjacent dragon. The current implementation just checks that the stone is not a
singleton on the first line.
amalgamate(x,y)
Amalgamate (join) the dragons at ‘x’ and ‘y’ (see Chapter 7 [Worms and Dragons],
page 47).
amalgamate_most_valuable(x,y,z)
Called when ‘x’, ‘y’, ‘z’ point to three (preferably distinct) dragons, in situations
such as this:
.O.X
X*OX
.O.X
In this situation, the opponent can play at ‘*’, preventing the three dragons from
becoming connected. However ‘O’ can decide which cut to allow. The helper amalgamates
the dragon at ‘y’ with either ‘x’ or ‘z’, whichever is largest.
make_proper_eye(x)
This autohelper should be called when ‘x’ is an eyespace which is misidentified as
marginal. It is reclassified as a proper eyespace (see Section 8.2 [Eye Space], page 60).
remove_halfeye(x)
Remove a half eye from the eyespace. This helper should not be run after make_
dragons is finished, since by that time the eyespaces have already been analyzed.
remove_eyepoint(x)
Remove an eye point. This function can only be used before the segmentation into
eyespaces.
owl_topological_eye(x,y)
Here ‘x’ is an empty intersection which may be an eye or half eye for some dragon,
and ‘y’ is a stone of the dragon, used only to determine the color of the eyespace in question.
Chapter 9: The Pattern Code 90
Returns the sum of the values of the diagonal intersections, relative to ‘x’, as explained in
See Section 8.8 [Eye Topology], page 67, equal to 4 or more if the eye at ‘x’ is false, 3 if it
is a half eye, and 2 if it is a true eye.
owl_escape_value(x)
Returns the escape value at ‘x’. This is only useful in owl attack and defense patterns.
O
.
O
Chapter 9: The Pattern Code 91
:+,C
O
A
O
Pattern CC205
XO
O.
:\,C
AO
OB
OOXX
O.OX
X..O
X.OO
The previous pattern is matched here twice, yet ‘X’ can push in and break one of the
connections. To fix this, we include a pattern:
Pattern CB11
?OX?
O!OX
?*!O
??O?
:8,B
?OA?
OaOB
?*bO
??O?
After this pattern is found, the xcut autohelper macro will return true at any of the
points ‘*’, ‘a’ and ‘b’. Thus the patterns CB204 and CB205 will not be matched, and the
dragons will not be amalgamated.
game window. This does not mean that you have to play the game out to its conclusion.
You may close the CGoban window on the game and GNU Go will close the SGF file so
that you can read it.
If you record a game in SGF form using the ‘-o’ option, GNU Go will add labels to
the board to show all the moves it considered, with their values. This is an extremely useful
feature, since one can see at a glance whether the right moves with appropriate weights are
being proposed by the move generation.
First, due to a bug of unknown nature, it occasionally happens that GNU Go will
not receive the SIGTERM signal from CGoban that it needs to know that the game is over.
When this happens, the SGF file ends without a closing parenthesis, and CGoban will not
open the file. You can fix the file by typing:
at the command line to add this closing parenthesis. Or you could add the ) using an editor.
Move values exceeding 99 (these should be rare) can be displayed by CGoban but
you may have to resize the window in order to see all three digits. Grab the lower right
margin of the CGoban window and pull it until the window is large. All three digits should
be visible.
If you are playing a game without the ‘-o’ option and you wish to analyze a move,
you may still use CGoban’s “Save Game” button to get an SGF file. It will not have the
values of the moves labelled, of course.
Once you have a game saved in SGF format, you can analyze any particular move
by running:
to see why GNU Go made that move, and if you make changes to the pattern database and
recompile the program, you may ask GNU Go to repeat the move to see how the behavior
changes. If you’re using emacs, it’s a good idea to run GNU Go in a shell in a buffer (M-x
shell) since this gives good navigation and search facilities.
Instead of a move number, you can also give a board coordinate to ‘-L’ in order to
stop at the first move played at this location. If you omit the ‘-L’ option, the move after
those in the file will be considered.
If a bad move is proposed, this can have several reasons. To begin with, each move
should be valued in terms of actual points on the board, as accurately as can be expected by
the program. If it’s not, something is wrong. This may have two reasons. One possibility
is that there are reasons missing for the move or that bogus reasons have been found. The
other possibility is that the move reasons have been misevaluated by the move valuation
functions. Tuning of patterns is with a few exceptions a question of fixing the first kind of
problems.
If there are bogus move reasons found, search through the trace output for the
pattern that is responsible. (Some move reasons, e.g. most tactical attack and defense,
do not originate from patterns. If no pattern produced the bogus move reason, it is not a
Chapter 9: The Pattern Code 94
tuning problem.) Probably this pattern was too general or had a faulty constraint. Try to
make it more specific or correct bugs if there were any. If the pattern and the constraint
looks right, verify that the tactical reading evaluates the constraint correctly. If not, this is
either a reading bug or a case where the reading is too complicated for GNU Go.
If a connecting move reason is found, but the strings are already effectively con-
nected, there may be missing patterns in ‘conn.db’. Similarly, worms may be incorrectly
amalgamated due to some too general or faulty pattern in ‘conn.db’. To get trace output
from the matching of patterns in ‘conn.db’ you need to add a second ‘-t’ option.
If a move reason is missing, there may be a hole in the database. It could also
be caused by some existing pattern being needlessly specific, having a faulty constraint, or
being rejected due to a reading mistake. Unless you are familiar with the pattern databases,
it may be hard to verify that there really is a pattern missing. Look around the databases
to try to get a feeling for how they are organized. (This is admittedly a weak point of
the pattern databases, but the goal is to make them more organized with time.) If you
decide that a new pattern is needed, try to make it as general as possible, without allowing
incorrect matches, by using proper classification from among snOoXx and constraints. The
reading functions can be put to good use. The reason for making the patterns as general
as they can be is that we need a smaller number of them then, which makes the database
much easier to maintain. Of course, if you need too complicated constraints, it’s usually
better to split the pattern.
If a move has the correct set of reasons but still is misevaluated, this is usually not a
tuning problem. There are, however, some possibilities to work around these mistakes with
the use of patterns. In particular, if the territorial value is off because delta_terri() give
strange results, the (min)terri and maxterri values can be set by patterns as a workaround.
This is typically done by the endgame patterns, where we can know the (minimum) value
fairly well from the pattern. If it should be needed, (min)value and maxvalue can be used
similarly. These possibilities should be used conservatively though, since such patterns are
likely to become obsolete when better (or at least different) functions for e.g. territory
estimation are being developed.
In order to choose between moves with the same move reasons, e.g. moves that
connect two dragons in different ways, patterns with a nonzero shape value should be used.
These should give positive shape values for moves that give good shape or good aji and
negative values for bad shape and bad aji. Notice that these values are additive, so it’s
important that the matches are unique.
Sente moves are indicated by the use of the pattern followup value. This can usually
not be estimated very accurately, but a good rule is to be rather conservative. As usual it
should be measured in terms of actual points on the board. These values are also additive
so the same care must be taken to avoid unintended multiple matches.
You can also get a visual display of the dragons using the ‘-T’ option. The default
GNU Go configuration tries to build a version with color support using either curses or the
ansi escape sequences. You are more likely to find color support in rxvt than xterm, at
least on many systems, so we recommend running:
gnugo -l [filename] -L [move number] -T
in an rxvt window. If you do not see a color display, and if your host is a GNU/Linux
machine, try this again in the Linux console.
Chapter 9: The Pattern Code 95
Worms belonging to the same dragon are labelled with the same letters. The colors
indicate the value of the field dragon.safety, which is set in ‘moyo.c’.
Green: GNU Go thinks the dragon is alive
Yellow: Status unknown
Blue: GNU Go thinks the dragon is dead
Red: Status critical (1.5 eyes) or weak by the algorithm
in ‘moyo.c’
If you want to get the same game over and over again, you can eliminate the ran-
domness in GNU Go’s play by providing a fixed random seed with the ‘-r’ option.
9.12 Implementation
The pattern code in GNU Go is fairly straightforward conceptually, but because the matcher
consumes a significant part of the time in choosing a move, the code is optimized for speed.
Because of this there are implementation details which obscure things slightly.
In GNU Go, the ascii ‘.db’ files are precompiled into tables (see ‘patterns.h’) by a
standalone program ‘mkpat.c’, and the resulting ‘.c’ files are compiled and linked into the
main GNU Go executable.
Each pattern is compiled to a header, and a sequence of elements, which are (notion-
ally) checked sequentially at every position and orientation of the board. These elements
are relative to the pattern ’anchor’ (or origin). One ‘X’ or ‘O’ stone is (arbitrarily) chosen to
represent the origin of the pattern. (We cannot dictate one or the other since some patterns
contain only one colour or the other.) All the elements are in co-ordinates relative to this
position. So a pattern matches "at" board position (m,n,o) if the the pattern anchor stone
is on (m,n), and the other elements match the board when the pattern is transformed by
transformation number ‘o’. (See below for the details of the transformations, though these
should not be necessary)
a b c d e f g h
Then if the pattern has the following symmetries, the following are true:
We can choose to use transformations a,d,f,g as the unique transformations for pat-
terns with either ‘|’, ‘-’, ‘\’, or ‘/’ symmetry.
Thus we choose to order the transformations a,g,d,f,h,b,e,c and choose first 2 for ‘X’
and ‘+’, the first 4 for ‘|’, ‘-’, ‘/’, and ‘\’, the middle 4 for ‘O’, and all 8 for non-symmetrical
patterns.
Each of the reflection operations (e-h) is equivalent to reflection about one arbitrary
axis followed by one of the rotations (a-d). We can choose to reflect about the axis of
symmetry (which causes no net change) and can therefore conclude that each of e-h is
equivalent to the reflection (no-op) followed by a-d. This argument therefore extends to
include ‘-’ and ‘/’ as well as ‘|’ and ‘\’.
"example"
.OO????????????????
*XX????????????????
o??????????????????
:8,80
4. The elements in a pattern are sorted so that non-space elements are checked before
space elements. It is hoped that, for most of the game, more squares are empty, and
so the pattern can be more quickly rejected doing it this way.
5. The actual tests are performed using an ’and-compare’ sequence. Each board position
is a 2-bit quantity. %00 for empty, %01 for ‘O’, %10 for ‘X’. We can test for an exact
match by and-ing with %11 (no-op), then comparing with 0, 1 or 2. The test for ‘o’ is
Chapter 9: The Pattern Code 97
the same as a test for ’not-X’, ie not %10. So and with %01 should give 0 if it matches.
Similarly ‘x’ is a test that bit 0 is not set.
.X.O....OO
XXXXO.....
.X..OOOOOO
X.X.......
....X...O.
00 10 00 01 00 00 00 00 01 01
10 10 10 10 01 00 00 00 00 00
00 10 00 00 01 01 01 01 01 01
10 00 10 00 00 00 00 00 00 00
00 00 00 00 10 00 00 00 01 00
we can compile this to a composite array in which each element stores the state of a 4x4
grid of squares :
...
??100010 ...
??000000
????????
????????
Similarly, for each pattern, mkpat produces appropriate 32-bit and-value masks for
the pattern elements near the anchor. It is a simple matter to test the pattern with a similar
test to (5) above, but for 32-bits at a time.
− ‘>’ - Actions. These are copied into the patterns file, below the constraint diagram.
− ‘:’ - Colon line. This is a little more complicated, but the colon line of the produced
patterns always start out with ":8,s" for transformation number and sacrifice pat-
tern class (it usually isn’t a sacrifice, but it’s pointless spending time checking for
tactical safety). Then a joseki pattern class character is appended and finally what
is included on the colon line in the comment for the SGF node.
Example: If the comment in the SGF file looks like
F
:C,shape(3)
;xplay_attack(A,B,C,D,*)
the generated pattern will have a colon line
:8,sjC,shape(3)
and a constraint
;xplay_attack(A,B,C,D,*)
;oplay_attack(*,A,B,C,D)
In order to accept the pattern we require that the constraint on the semicolon line
evaluates to true. This particular constraint has the interpretation "Play with alternating
Chapter 9: The Pattern Code 100
colors, starting with ‘O’, on the intersections ‘*’, ‘A’, ‘B’, and ‘C’. Then check whether the
stone at ‘D’ can be captured." I.e. play to this position
--------+
........|
........|
...XX...|
...OXO..|
...OOXX.|
....XO..|
........|
........|
and call attack() to see whether the lower ‘X’ stone can be captured. This is not limited
to ladders, but in this particular case the reading will of course involve a ladder.
The constraint diagram above with letters is how it looks in the ‘.db’ file. The joseki
compiler knows how to create these from labels in the SGF node. ‘Cgoban’ has an option
to create one letter labels, but this ought to be a common feature for SGF editors.
Thus in order to implement this example in SGF, one would add labels to the four
intersections and a comment:
;oplay_attack(*,A,B,C,D)
The appropriate constraint (autohelper macro) will then be added to the Joseki ‘.db’
file.
stones in corner areas of different intersections of the board for all possible transformations.
corner_matchpat() also matches top-level variations. do_corner_matchpat() is responsi-
ble for recursive matching on the variation tree and calling callback function upon pattern
match.
Tree-like database for corner matcher is generated by mkpat program. Database gen-
erator consists of several functions, most important are: corner_best_element(), corner_
variation_new(), corner_follow_variation() and corner_add_pattern().
out
out
In each step of the path, the pattern matcher jumps into a state determined by what
it has found on the board so far. If we have successfully matched one or several patterns in
this step, this state immediately tells us so (in its attribute). But the state also implicitly
encodes which further patterns can still get matched: The information stored in the state
contains in which state to jump next, depending on whether we find a black, white or empty
intersection (or an intersection out of board) in the next step of the path. The state will
also immediately tell us if we cannot find any further pattern (by telling us to jump into
the error state).
These sloppy explanations may become clearer with the definitions in the next section
(Section 10.2 [What is a DFA], page 104).
Reading the board following a predefined path reduces the two dimentional pattern
matching to a linear text searching problem. For example, this pattern
Chapter 10: The DFA pattern matcher 104
?X?
.O?
?OO
B
C4A
5139
628
7
gives the string "OO?X.?*O*?*?" where "?" means ’don’t care’ and "*" means ’don’t care,
can even be out of board’.
So we can forget that we are dealing with two dimensional patterns and consider
linear patterns.
Basically, a DFA is a set of states connected by labeled transitions. The labels are
the values read on the board, in GNU Go these values are EMPTY, WHITE, BLACK or
OUT BOARD, denoted respectively by ’.’,’O’,’X’ and ’#’.
The best way to represent a DFA is to draw its transition graph: the pattern
"????..X" is recognized by the following DFA:
X X X X
. . . . . . X
1 2 3 4 5 6 7 8
O O O O
Pattern "????..X"
This means that starting from state [1], if you read ’.’,’X’ or ’O’ on the board, go to
state [2] and so on until you reach state [5]. From state [5], if you read ’.’, go to state [6]
otherwise go to error state [0]. And so on until you reach state [8]. As soon as you reach
state [8], you recognize Pattern "????..X"
Chapter 10: The DFA pattern matcher 105
Adding a pattern like "XXo" (’o’ is a wildcard for not ’X’) will transform directly
the automaton by synchronization product (Section 10.4 [Building the DFA], page 107).
Consider the following DFA:
. X X X
. . . . . X
1 2 3 4 5 6 7 8
O O O O
O X X . Pattern "????..X"
. O
X
O
X
9 A . B
Pattern "XXo"
By adding a special error state and completing each state by a transition to error
state when there is none, we transform easily a DFA in a Complete Deterministic Finite
state Automaton (CDFA). The synchronization product (Section 10.4 [Building the DFA],
page 107) is only possible on CDFA’s.
Pattern "????..X"
. X X X
. . . . . X
1 2 3 4 5 6 7 8
O O O O
X
O X X . O X O
. O O
X . O
O .
X
9 A . B O 0 X
Error
Pattern "XXo" X
.
The graph of a CDFA is coded by an array of states: The 0 state is the "error" state
and the start state is 1.
----------------------------------------------------
state | . | O | X | # | att
----------------------------------------------------
1 | 2 | 2 | 9 | 0 |
2 | 3 | 3 | 3 | 0 |
3 | 4 | 4 | 4 | 0 |
5 | 6 | 0 | 0 | 0 |
6 | 7 | 0 | 0 | 0 |
7 | 0 | 0 | 8 | 0 |
8 | 0 | 0 | 0 | 0 | Found pattern "????..X"
9 | 3 | 3 | A | 0 |
A | B | B | 4 | 0 |
B | 5 | 5 | 5 | 0 | Found pattern "XXo"
----------------------------------------------------
To each state we associate an often empty list of attributes which is the list of pattern
indexes recognized when this state is reached. In ’‘dfa.h’’ this is basically represented by
two stuctures:
Chapter 10: The DFA pattern matcher 106
/* dfa state */
typedef struct state
{
int next[4]; /* transitions for EMPTY, BLACK, WHITE and OUT_BOARD */
attrib_t *att;
}
state_t;
/* dfa */
typedef struct dfa
{
attrib_t *indexes; /* Array of pattern indexes */
int maxIndexes;
----------------------------------------------------
state | . | O | X | # | att
----------------------------------------------------
1 | 0 | 0 | 2 | 0 |
2 | 3 | 10 | 10 | 0 |
3 | 4 | 7 | 9 | 0 |
4 | 5 | 5 | 6 | 0 |
5 | 0 | 0 | 0 | 0 | 2
6 | 0 | 0 | 0 | 0 | 4 2 1
7 | 5 | 5 | 8 | 0 |
8 | 0 | 0 | 0 | 0 | 4 2 3
9 | 5 | 5 | 5 | 0 |
10 | 11 | 11 | 9 | 0 |
11 | 5 | 5 | 12 | 0 |
12 | 0 | 0 | 0 | 0 | 4 2
----------------------------------------------------
We perform the scan of the string "X..XXO...." starting from state 1:
Current state: 1, substring to scan : X..XXO....
We read an ’X’ value, so from state 1 we must go to state 2.
Current state: 2, substring to scan : ..XXO....
We read a ’.’ value, so from state 2 we must go to state 3 and so on ...
Current state: 3, substring to scan : .XXO....
Current state: 4, substring to scan : XXO....
Current state: 6, substring to scan : XO....
Found pattern 4
Found pattern 2
Found pattern 1
After reaching state 6 where we match patterns 1,2 and 4, there is no out-transitions
so we stop the matching. To keep the same match order as in the standard algorithm, the
patterns indexes are collected in an array and sorted by indexes.
The algorithm used in function ’sync_product()’ builds the minimal product DFA
only by keeping the reachable states. It recursively scans the product CDFA by following
simultaneously the transitions of L and R. A hast table (gtest) is used to check if a state
(l,r) has already been reached, the reachable states are remapped on a new DFA. The CDFA
thus obtained is minimal and recognizes the union of the two patterns sets.
For example these two CDFA’s:
Error state
O
0 O
X O X
X
X Pattern A
1 2 3
Start O
Start O O Pattern B
1 2 3
X
X X
O
0
X
Error state
X Pattern A
3 , 0
X 2 , 0 X O
X
Start O
1 , 1 0 , 0 Error state
X O
O 2 , 2 X O
Pattern B
O 0 , 3
11 Tactical reading
The process of visualizing potential moves done by you and your opponent to learn the
result of different moves is called "reading". GNU Go does three distinct types of reading:
tactical reading which typically is concerned with the life and death of individual strings,
Owl reading which is concerned with the life and death of dragons, and connection reading.
In this Chapter, we document the tactical reading code, which is in ‘engine/reading.c’.
Backfilling is only tried with stackp <= backfill_depth. The parameter backfill_
depth may be set using the ‘-B’ option.
The fourlib_depth is a parameter with a default of only 7. Below this depth, GNU
Go will try to attack strings with four liberties. The fourlib_depth may be set using the
‘-F’ option.
The parameter ko_depth is a similar cutoff. If stackp<ko_depth, the reading code
will make experiments involving taking a ko even if it is not legal to do so (i.e., it is
hypothesized that a remote ko threat is made and answered before continuation). This
parameter may be set using the ‘-K’ option.
• int attack(int str, int *move)
Determines if the string at str can be attacked, and if so, *move returns
the attacking move, unless *movei is a null pointer. (Use null pointers if
you are interested in the result of the attack but not the attacking move
itself.) Returns WIN, if the attack succeeds, 0 if it fails, and KO_A or KO_B
if the result depends on ko [Return Codes], page 110.
Chapter 11: Tactical reading 112
The komaster and (kom_pos) field are documented in See Section 11.4 [Ko],
page 116.
When a new result node is created, ’status’ is set to 1 ’open’. This is then set to 2
’closed’ when the result is entered. The main use for this is to identify open result nodes
when the hashtable is partially cleared. Another potential use for this field is to identify
repeated positions in the reading, in particular local double or triple kos.
typedef struct hashnode_t {
Hash_data key;
Read_result * results;
Chapter 11: Tactical reading 115
11.4 Ko Handling
The principles of ko handling are the same for tactical reading and owl reading.
We have already mentioned (see Section 11.1 [Reading Basics], page 110) that GNU
Go uses a return code of KO_A or KO_B if the result depends on ko. The return code of
KO_B means that the position can be won provided the player whose move calls the function
can come up with a sufficiently large ko threat. In order to verify this, the function must
simulate making a ko threat and having it answered by taking the ko even if it is illegal.
We call such an experimental taking of the ko a conditional ko capture.
Conditional ko captures are accomplished by the function tryko(). This function is
like trymove() except that it does not require legality of the move in question.
The static reading functions, and the global functions do_attack and do_find_
defense consult parameters komaster, kom_pos, which are declared static in ‘board.c’.
Chapter 11: Tactical reading 117
These mediate ko captures to prevent the occurrence of infinite loops. During reading, the
komaster values are pushed and popped from a stack.
Normally komaster is EMPTY but it can also be ‘BLACK’, ‘WHITE’, GRAY_BLACK, GRAY_
WHITE or WEAK_KO. The komaster is set to color when color makes a conditional ko
capture. In this case kom_pos is set to the location of the captured ko stone.
If the opponent is komaster, the reading functions will not try to take the ko at
kom_pos. Also, the komaster is normally not allowed to take another ko. The exception is
a nested ko, characterized by the condition that the captured ko stone is at distance 1 both
vertically and horizontally from kom_pos, which is the location of the last stone taken by
the komaster. Thus in this situation:
.OX
OX*X
OmOX
OO
Here if ‘m’ is the location of kom_pos, then the move at ‘*’ is allowed.
The rationale behind this rule is that in the case where there are two kos on the
board, the komaster cannot win both, and by becoming komaster he has already chosen
which ko he wants to win. But in the case of a nested ko, taking one ko is a precondition
to taking the other one, so we allow this.
If the komaster’s opponent takes a ko, then both players have taken one ko. In this
case komaster is set to GRAY_BLACK or GRAY_WHITE and after this further ko captures are
even further restricted.
If the ko at kom_pos is filled, then the komaster reverts to EMPTY.
In detail, the komaster scheme is as follows. Color ‘O’ is to move. This scheme is
known as scheme 5 since in versions of GNU Go through 3.4, several different schemes were
included.
• 1. Komaster is EMPTY.
− 1a. Unconditional ko capture is allowed.
Komaster remains EMPTY if previous move was not a ko capture.
Komaster is set to WEAK KO if previous move was a ko capture and
kom pos is set to the old value of board ko pos.
− 1b) Conditional ko capture is allowed.
Komaster is set to O and kom pos to the location of the ko, where a
stone was just removed.
• 2. Komaster is O:
− 2a) Only nested ko captures are allowed. Kom pos is moved to the new removed
stone.
− 2b) If komaster fills the ko at kom pos then komaster reverts to EMPTY.
• 3. Komaster is X:
Play at kom pos is not allowed. Any other ko capture is allowed. If O
takes another ko, komaster becomes GRAY X.
Chapter 11: Tactical reading 118
11.5 A Ko Example
To see the komaster scheme in action, consider this position from the file
‘regressions/games/life_and_death/tripod9.sgf’. We recommend studying this
example by examining the variation file produced by the command:
gnugo -l tripod9.sgf --decide-dragon C3 -o vars.sgf
In the lower left hand corner, there are kos at A2 and B4. Black is unconditionally
dead because if W wins either ko there is nothing B can do.
8 . . . . . . . .
7 . . O . . . . .
6 . . O . . . . .
5 O O O . . . . .
4 O . O O . . . .
3 X O X O O O O .
2 . X X X O . . .
1 X O . . . . . .
A B C D E F G H
This is how the komaster scheme sees this. B (i.e. X) starts by taking the ko at B4.
W replies by taking the ko at A1. The board looks like this:
8 . . . . . . . .
7 . . O . . . . .
6 . . O . . . . .
5 O O O . . . . .
4 O X O O . . . .
3 X . X O O O O .
2 O X X X O . . .
1 . O . . . . . .
A B C D E F G H
Now any move except the ko recapture (currently illegal) at A1 loses for B, so B
retakes the ko and becomes komaster. The board looks like this:
Chapter 11: Tactical reading 119
8 . . . . . . . . komaster: BLACK
7 . . O . . . . . kom_pos: A2
6 . . O . . . . .
5 O O O . . . . .
4 O X O O . . . .
3 X . X O O O O .
2 . X X X O . . .
1 X O . . . . . .
A B C D E F G H
W takes the ko at B3 after which the komaster is GRAY and ko recaptures are not
allowed.
8 . . . . . . . . komaster: GRAY
7 . . O . . . . . kom_pos: B4
6 . . O . . . . .
5 O O O . . . . .
4 O . O O . . . .
3 X O X O O O O .
2 . X X X O . . .
1 X O . . . . . .
A B C D E F G H
Since B is not allowed any ko recaptures, there is nothing he can do and he is found
dead. Thus the komaster scheme produces the correct result.
• Komaster is ‘X’:
− Conditional ko capture is not allowed.
− Unconditional ko capture is allowed except for a move at kom_pos. Komaster
parameters unchanged.
11.8 Superstrings
A superstring is an extended string, where the extensions are through the following kinds
of connections:
1. Solid connections (just like ordinary string).
OO
2. Diagonal connection or one space jump through an intersection where an opponent
move would be suicide or self-atari.
...
O.O
XOX
X.X
3. Bamboo joint.
OO
..
OO
4. Diagonal connection where both adjacent intersections are empty.
.O
O.
5. Connection through adjacent or diagonal tactically captured stones. Connections of this
type are omitted when the superstring code is called from ‘reading.c’, but included
when the superstring code is called from ‘owl.c’.
Like a dragon, a superstring is an amalgamation of strings, but it is a much tighter
organization of stones than a dragon, and its purpose is different. Superstrings are encoun-
tered already in the tactical reading because sometimes attacking or defending an element
of the superstring is the best way to attack or defend a string. This is in contrast with
dragons, which are ignored during tactical reading.
will run attack() to determine whether the string can be captured. If it can, it will also
run find_defense() to determine whether or not it can be defended. It will give a count
Chapter 11: Tactical reading 122
of the number of variations read. The ‘-t’ is necessary, or else GNU Go will not report its
findings.
If we add ‘-o output file ’ GNU Go will produce an output file with all variations
considered. The variations are numbered in comments.
This file of variations is not very useful without a way of navigating the source code.
This is provided with the GDB source file, listed at the end. You can source this from GDB,
or just make it your GDB init file.
If you are using GDB to debug GNU Go you may find it less confusing to com-
pile without optimization. The optimization sometimes changes the order in which pro-
gram steps are executed. For example, to compile ‘reading.c’ without optimization, edit
‘engine/Makefile’ to remove the string -O2 from the file, touch ‘engine/reading.c’ and
make. Note that the Makefile is automatically generated and may get overwritten later.
If in the course of reading you need to analyze a result where a function gets its value
by returning a cached position from the hashing code, rerun the example with the hashing
turned off by the command line option ‘--hash 0’. You should get the same result. (If you
do not, please send us a bug report.) Don’t run ‘--hash 0’ unless you have a good reason
to, since it increases the number of variations.
With the source file given at the end of this document loaded, we can now navigate
the variations. It is a good idea to use cgoban with a small ‘-fontHeight’, so that the
variation window takes in a big picture. (You can resize the board.)
Suppose after perusing this file, we find that variation 17 is interesting and we would
like to find out exactly what is going on here.
The macro ’jt n’ will jump to the n-th variation.
(gdb) avar 17
(gdb) dvar 17
jumps to the 17-th defense variation. Both variation sets are found in the same sgf file,
though they are numbered separately.
Other commands defined in this file:
Chapter 11: Tactical reading 123
#######################################################
############### .gdbinit file ###############
#######################################################
define dump
set dump_stack()
end
define ascii
set gprintf("%o%m\n",$arg0,$arg1)
end
define dragon
set ascii_report_dragon("$arg0")
end
define worm
set ascii_report_worm("$arg0")
end
define nv
tbreak trymove
continue
finish
next
end
define jt
while (count_variations < $arg0)
nv
end
Chapter 11: Tactical reading 124
nv
dump
end
define avar
delete
tbreak sgffile_decidestring
run
tbreak attack
continue
jt $arg0
end
define dvar
delete
tbreak sgffile_decidestring
run
tbreak attack
continue
finish
next 3
jt $arg0
end
A node of the move tree is considered terminal if no further moves are found
from ‘owl_attackpats.db’ or ‘owl_defendpats.db’, or if the function compute_eyes_
pessimistic() reports that the group is definitely alive. At this point, the status of the
group is evaluated. The functions owl_attack() and owl_defend(), with usage similar
to attack() and find_defense(), make use of the owl pattern databases to generate the
move tree and decide the status of the group.
The function compute_eyes_pessimistic() used by the owl code is very conserva-
tive and only feels certain about eyes if the eyespace is completely closed (i.e. no marginal
vertices).
The maximum number of moves tried at each node is limited by the parameter MAX_
MOVES defined at the beginning of ‘engine/owl.c’. The most most valuable moves are tried
first, with the following restrictions:
• If stackp > owl_branch_depth then only one move is tried per variation.
• If stackp > owl_reading_depth then the reading terminates, and the situation is de-
clared a win for the defender (since deep reading may be a sign of escape).
• If the node count exceeds owl_node_limit, the reading also terminates with a win for
the defender.
• Any pattern with value 99 is considered a forced move: no other move is tried, and
if two such moves are found, the function returns false. This is only relevant for the
attacker.
• Any pattern in ‘patterns/owl_attackpats.db’ and ‘patterns/owl_defendpats.db’
with value 100 is considered a win: if such a pattern is found by owl_attack or owl_
defend, the function returns true. This feature must be used most carefully.
The functions owl_attack() and owl_defend() may, like attack() and find_
defense(), return an attacking or defending move through their pointer arguments. If
the position is already won, owl_attack() may or may not return an attacking move. If it
finds no move of interest, it will return PASS, that is, 0. The same goes for owl_defend().
When owl_attack() or owl_defend() is called, the dragon under attack is marked
in the array goal. The stones of the dragon originally on the board are marked with goal=1;
those added by owl_defend() are marked with goal=2. If all the original strings of the
original dragon are captured, owl_attack() considers the dragon to be defeated, even if
some stones added later can make a live group.
Only dragons with small escape route are studied when the functions are called from
make_dragons().
The owl code can be conveniently tested using the ‘--decide-owl location ’ option.
This should be used with ‘-t’ to produce a useful trace, ‘-o’ to produce an SGF file of
variations produced when the life and death of the dragon at location is checked, or both.
‘--decide-position’ performs the same analysis for all dragons with small escape route.
+---------
|....OOOOX
|....OOXXX
|..O.OXX..
|.OXO.OX..
|.OX..OO..
|.XXOOOXO.
|..*XXOX..
|....XOX..
|.XX..X...
|X........
Every ‘X’ stone in this position is alive. However the move at ‘*’ produces a position
in which at least one of four strings will get captured. This is a combination.
The driving function is called atari_atari because typically a combination involves
a sequence of ataris culminating in a capture, though sometimes the moves involved are
not ataris. For example in the above example, the first move at ‘*’ is not an atari, though
after ‘O’ defends the four stones above, a sequence of ataris ensues resulting in the capture
of some string.
Like the owl functions atari_atari does pattern-based reading. The database gen-
erating the attacking moves is ‘aa_attackpats.db’. One danger with this function is that
the first atari tried might be irrelevant to the actual combination. To detect this possibility,
once we’ve found a combination, we mark that first move as forbidden, then try again. If
no combination of the same size or larger turns up, then the first move was indeed essential.
• void combinations(int color)
Generate move reasons for combination attacks and defenses against them.
This is one of the move generators called from genmove().
• int atari_atari(int color, int *attack_move, char defense_moves[BOARDMAX],
int save_verbose)
Look for a combination for color. For the purpose of the move generation,
returns the size of the smallest of the worms under attack.
• int atari_atari_confirm_safety(int color, int move, int *defense,
int minsize, const char saved_dragons[BOARDMAX], const char saved_
worms[BOARDMAX])
Tries to determine whether a move is a blunder. Wrapper around
atari atari blunder size. Check whether a combination attack of size at
least minsize appears after move at move has been made. The arrays
saved_dragons[] and saved_worms[] should be one for stones belonging
to dragons or worms respectively, which are supposedly saved by move.
• int atari_atari_blunder_size(int color, int move, int *defense, const char
safe_stones[BOARDMAX])
This function checks whether any new combination attack appears after
move at (move) has been made, and returns its size (in points). safe_
stones marks which of our stones are supposedly safe after this move.
Chapter 13: Influence Function 128
13 Influence Function
• Area
Those parts of the board where one player or the other has a stronger
influence than his opponent are considered area.
Generally territory is moyo and moyo is area. To get a feeling for these concepts,
load an sgf file in a middle game position with the option ‘-m 0x0180’ and examine the
resulting diagrams (see Section 13.13 [Influential Display], page 142).
ooOXxx
o.OXxx
o...xx
------
Then we let ‘O’ make the move at ‘*’ and assume ‘X’ moves first again next. The
territory then becomes (‘X’ is also assumed to have to connect):
OOOXXX
ooOXxx
ooOX.x
oo.O.x
------
We see that this makes a difference in territory of 4, which is what influ-
ence delta territory() should report. Then again, we have followup value, and here also a
reverse followup value. The reverse followup value, which in this case will be so high that
the move is treated as reverse sente, is added by an explicit pattern. Other sources for
followup or reverse followup values are threats to capture a rescue a string of stones. See
the code and comments in the function value_move_reaons for how followup and reverse
followup values are used to adjust the effective move value.
To give an example of territorial value where something is captured, consider the ‘O’
move at ‘*’ here,
XXXXXXXO
X.OOOOXO
X.O..O*O
--------
As before we first let the influence function determine territory assuming X moves
first, i.e. with a captured group:
XXXXXXXO
XxyyyyXO
Xxyxxy.O
--------
Here ‘y’ indicates ‘X’ territory + captured stone, i.e. these count for two points. After
the ‘O’ move at ‘*’ we instead get
XXXXXXXO
X.OOOOXO
X.OooOOO
--------
and we see that ‘X’ has 16 territory fewer and ‘O’ has two territory more, for a total
difference of 18 points.
That the influence function counts the value of captured stones was introduced in
GNU Go 3.2. Previously this was instead done using the effective size heuristic. The
effective size is the number of stones plus the surrounding empty spaces which are closer to
this string or dragon than to any other stones. Here the ‘O’ string would thus have effective
size 6 (number of stones) + 2 (interior eye) + 2*0.5 (the two empty vertices to the left of
the string, split half each with the surrounding X string) + 1*0.33 (the connection point,
Chapter 13: Influence Function 132
split between three strings) = 9.33. As noted this value was doubled, giving 18.67 which
is reasonably close to the correct value of 18. The effective size heuristic is still used in
certain parts of the move valuation where we can’t easily get a more accurate value from
the influence function (e. g. attacks depending on a ko, attack threats).
Note that this section only describes the territorial valuation of a move. Apart
from that, GNU Go uses various heuristics in assigning a strategical value (weakening and
strengthening of other stones on the board) to a move. Also, the influence function isn’t
quite as well tuned as the examples above may seem to claim. But it should give a fairly
good idea of how the design is intended.
Another matter is that so far we have only considered the change in secure territory.
GNU Go 3.2 and later versions use a revised heuristic, which is explained in the next section,
to assign probable territory to each player.
above, but the main property of the propagation still remains, i.e. no intersection is vis-
ited more than once and after being visited no more influence will be propagated to the
intersection.
13.8 Permeability
The permeability at the different points is initially one at all empty intersections and zero at
occupied intersections. To get a useful influence function we need to modify this, however.
Consider the following position:
|......
|OOOO..
|...O..
|...a.X (’a’ empty intersection)
|...O..
|...OOO
|.....O
+------
The corner is of course secure territory for ‘O’ and clearly the ‘X’ stone has negligible
effect inside this position. To stop ‘X’ influence from leaking into the corner we use pattern
matching (pattern Barrier1/Barrier2 in ‘barriers.db’) to modify the permeability for ‘X’
at this intersection to zero. ‘O’ can still spread influence through this connection.
Another case that needs to be mentioned is how the permeability damping is com-
puted for diagonal influence radiation. For horizontal and vertical radiation we just use the
permeability (for the relevant color) at the intersection we are radiating from. In the diag-
onal case we additionally multiply with the maximum permeability at the two intersections
we are trying to squeeze between. The reason for this can be found in the diagram below:
|...X |...X
|OO.. |Oda.
|..O. |.bc.
|..O. |..O.
+---- +----
We don’t want ‘X’ influence to be spread from ‘a’ to ‘b’, and since the permeability
at both c and d is zero, the rule above stops this.
13.9 Escape
One application of the influence code is in computing the dragon.escape_route field.
This is computed by the function compute_escape() as follows. First, every intersection
is assigned an escape value, ranging between 0 and 4, depending on the influence value of
the opposite color.
The escape_route field is modified by the code in ‘surround.c’ (see Section 13.11
[Surrounded Dragons], page 139). It is divided by two for weakly surrounded dragons, and
set to zero for surrounded ones.
In addition to assiging an escape value to empty vertices, we also assign an escape
value to friendly dragons. This value can range from 0 to 6 depending on the status of the
dragon, with live dragons having value 6.
Then we sum the values of the resulting influence escape values over the intersections
(including friendly dragons) at distance 4, that is, over those intersections which can be
joined to the dragon by a path of length 4 (and no shorter path) not passing adjacent to
Chapter 13: Influence Function 136
any unfriendly dragon. In the following example, we sum the influence escape value over
the four vertices labelled ’4’.
. . . . . . . . . . . . . . . . . .
. . . . . X . . O . . . . . X . . O
. . X . . . . . O . . X . 2 . 4 . O
X . . . . . . . . X . . 1 1 2 3 4 .
X O . O . . . . O X O 1 O 1 2 3 4 O
X O . O . . . . . X O 1 O 1 . 4 . .
X O . . . X . O O X O 1 . . X . . O
. . . X . . . . . . 1 . X . . . . .
X . . . . X . . . X . . . . X . . .
. . . . . . . . . . . . . . . . . .
Since the dragon is trying to reach safety, the reader might wonder why compute_
influence() is called with the opposite color of the dragon contemplating escape. To
explain this point, we first remind the reader why there is a color parameter to compute_
influence(). Consider the following example position:
...XX...
OOO..OOO
O......O
O......O
--------
Whether the bottom will become O territory depends on who is in turn to play. This
is implemented with the help of patterns in barriers.db, so that X influence is allowed to leak
into the bottom if X is in turn to move but not if O is. There are also “invade” patterns which
add influence sources in sufficiently open parts of the board which are handled differently
depending on who is in turn to move.
In order to decide the territorial value of an O move in the third line gap above,
influence is first computed in the original position with the opponent (i.e. X) in turn to
move. Then the O stone is played to give:
...XX...
OOO.OOOO
O......O
O......O
--------
Now influence is computed once more, also this time with X in turn to move. The
difference in territory (as computed from the influence values) gives the territorial value of
the move.
Exactly how influence is computed for use in the escape route estimation is all ad
hoc. But it makes sense to assume the opponent color in turn to move so that the escape
Chapter 13: Influence Function 137
possibilities aren’t overestimated. After we have made a move in the escape direction it is
after all the opponent’s turn.
The current escape route mechanism seems good enough to be useful but is not
completely reliable. Mostly it seems to err on the side of being too optimistic.
start_sgftrace
=
break_in D7 E9 F9 G9 E8 F8 G8 H8 G7 H7 J7 H6 J6 H5 J5 H4 J4 H3 J3 H2 J2
= 1 E8
finish_sgftrace vars.sgf
=
start_sgftrace
=
break_in D7 F9 G9 F8 G8 H8 G7 H7 J7 H6 J6 H5 J5 H4 J4 H3 J3 H2 J2
= 1 G7
finish_sgftrace vars1.sgf
This will produce two sgf files containing the variations caused by these calls to the
breakin code. The second file, ‘vars1.sgf’ will contain quite a few variations.
The break in code makes a list of break ins which are found. When it is finished, the
function add_expand_territory_move is called for each break in, adding a move reason.
Chapter 13: Influence Function 139
The break in code is slow, and only changes a few moves by the engine per game.
Nevertheless we believe that it contributes substantially to the strength of the program.
The break in code is enabled by default in GNU Go 3.6 at level 10, and disabled at level 9.
In fact, this is the only difference between levels 9 and 10 in GNU Go 3.6.
In order to compute distances between corners of the convex hull a sorting by angle
algorithm has been implemented. If the distance between a pair enclosing stones is large,
the surround status gets decreased to WEAKLY_SURROUNDED, or even 0 for very large ones.
The sorting by angle must be explained. A small diagram will probably help :
.O.O.
O...O
..X..
O...O
.O.O.
The sorting algorithm will generate this:
.4.5.
3...6
..X..
2...7
.1.8.
That is, the points are sorted by ascending order of the measure of the angle S-G-O,
where S is SOUTH, G the (approximated) gravity center of the goal, and O the position of
the considered hostile stones.
The necessity of such sorting appears when one tries to measure distances between
enclosing stones without sorting them, just by using directly the existing left and right
corners arrays. In some positions, the results will be inconsistent. Imagine, for example a
position where for instance the points 1,2,3,4,6 and 7 were in the left arrary, leaving only 5
and 8 in the right array. Because of the large distance between 5 and 8, the dragon would
have declared weak surrounded or not surrounded at all. Such cases are rare but frequent
enough to require the angle sorting.
The following position:
O.X.O
.....
.O.O.
This is "more" surrounded than the following position:
O.XXXXXX.O
..........
.O......O.
In the second case, the surround status would be lowered to WEAKLY_SURROUNDED.
The surround code is used to modify the escape route field in the dragon2 data
array. When a dragon is WEAKLY SURROUNDED, the escape route is divided by 2. If
the dragon is SURROUNDED, escape route is simply set to 0.
• ‘E’
These patterns add extra influence sources close to some shapes like walls.
This tries to reflect their extra strength. These patterns are not used in
the influence computations relevant for territory valuations, but they are
useful for getting a better estimate of strengths of groups.
• ‘I’
These patterns add extra influence sources at typical invasion points. Usu-
ally they are of small strength. If they additionally have the class ‘s’, the
extra influence source is added for both colors. Otherwise, only the player
assumed to be next to move gets the benefit.
The patterns in ‘barriers.db’ get matched only for ‘O’ being the player next to
move.
• ‘A’
Connections between ‘X’ stones that stop influence of ‘O’. They have to be
tight enough that ‘O’ cannot break through, even though he is allowed to
move first.
• ‘D’
Connections between ‘O’ stones that stop influence of ‘X’. The stones in-
volved can be more loosely connected than those in ‘A’ patterns.
• ‘B’
These indicate positions of followup moves for the ‘O’ stone marked with
‘Q’ in the pattern. They are used to reduce the territory e. g. where a
monkey jump is possible. Also, they are used in the computation of the
followup influence, if the ‘Q’ stone was the move played (or a stone saved
by the move played).
• ‘t’
These patterns indicate intersections where one color will not be able to
get territory, for example in a false eye. The points are set with a call to
the helper non oterritory or non xterritory in the action of the pattern.
The intrusion patterns (‘B’) are more powerful than the description above might
suggest. They can be very helpful in identifying weak shapes (by adding an intrusion
source for the opponent where he can break through). A negative inference for this is that
a single bad ‘B’ pattern, e. g. one that has a wrong constraint, typically causes 5 to 10
FAILs in the regression test suite.
Influence Patterns can have autohelper constraints as usual. As for the constraint
attributes, there are (additionally to the usual ones ‘O’, ‘o’, ‘X’ and ‘x’), attributes ‘Y’ and
‘FY’. A pattern marked with ‘Y’ will only be used in the influence computations relevant for
the territory valuation, while ‘FY’ patterns only get used in the other influence computations.
The action of an influence pattern is at the moment only used for non-territory
patterns as mentioned above, and as a workaround for a problem with ‘B’ patterns in the
followup influence.
To see why this workaround is necessary, consider the follwoing situation:
Chapter 13: Influence Function 142
..XXX
.a*.O
.X.O.
..XXO
We see from the first view of move values that filling dame at P15 is valued highest
with 0.17 points while the correct move at C4 is valued slightly lower with 0.16. The real
problem is of course that C4 is worth a full point and thus should be valued about 1.0.
Now click on C4 to get a list of move reasons and move valuation information.
Everything looks okay except that change in territory is 0.00 rather than 1.00 as it ought
to be.
We can confirm this by choosing the “delta territory for...” button and again clicking
C4. Now B5 should have been marked as one point of change in territory, but it’s not.
Next step is to enter the influence debug tool. Press the “influence” button, followed
by “black influence, dragons known,” and “territory value.” This shows the expected terri-
tory if black locally moves first everywhere (thus “black influence”). Here we can see that
B5 is incorrectly considered as 1.0 points of white territory.
We can compare this with the territory after a white move at C4 (still assuming that
black locally moves first everywhere after that) by pressing “after move influence for...”
and clicking C4. This looks identical, as expected since delta territory was 0, but here it is
correct that B5 is 1.0 points of territory for white.
The most straightforward solution to this problem is to add a non-territory pattern,
saying that white can’t get territory on B5 if black moves first. The nonterritory patterns
are in ‘barriers.db’.
Pattern Nonterritory56
...
X.O
?O.
:8,t
eac
XbO
?Od
;oplay_attack(a,b,c,d,d)
>non_xterritory(e);
In these patterns it’s always assumed that ‘O’ moves first and thus it says that ‘X’
can’t get territory at B5 (‘e’ in the pattern). Now we need to be a bit careful however
since after ‘O’ plays at ‘a’ and ‘X’ cuts in at ‘b’, it may well happen that ‘O’ needs to defend
around ‘d’, allowing ‘X’ to cut at ‘c’, possibly making the nonterritory assumption invalid.
It’s difficult to do this entirely accurate, but the constraint above is fairly conservative and
should guarantee that ‘a’ is safe in most, although not all, cases.
Chapter 14: Monte Carlo Go 145
14 Monte Carlo Go
In Monte Carlo Go the engine plays random games to the end, generating moves
from a pattern database within the context of the algorithm UCT (upper con-
fidence bounds applied to trees). This algorithm allowed the program MoGo
(http://www.lri.fr/~gelly/MoGo.htm, to become the first computer program to defeat
a professional while taking a 9 stone handicap (http://senseis.xmp.net/?MoGo).
GNU Go 3.8 can play 9x9 Go with the option ‘--monte-carlo’ using the UCT
algorithm. For command line options, see See Section 3.9 [Invoking GNU Go], page 14.
During reading, the engine makes incremental updates of local 3x3 neighborhood,
suicide status, self-atari status, and number of stones captured, for each move.
GNU Go’s simulations (Monte Carlo games) are pattern generated. The random
playout move generation is distributed strictly proportional to move values computed by
table lookup from a local context consisting of 3x3 neighborhood, opponent suicide status,
own and opponent self-atari status, number of stones captured by own and opponent move,
and closeness to the previous move. Let’s call this local context simply "a pattern" and the
table "pattern values" or simply "patterns".
There are three built-in databases that you can select using the option
‘--mc-patterns <name>’, where ‘<name>’ is one of
• mc_montegnu_classic
• mc_mogo_classic
• mc_uniform
The first of these is an approximation of the previous random move generation algo-
rithm. The mogo_classic pattern values is an approximation of the simulation policy used
by early versions of MoGo, as published in the report odification of UCT with Patterns
in Monte-Carlo Go (http://hal.inria.fr/inria-00117266) RR-6062, by Sylvain Gelly,
Yizao Wang, Rmi Munos, and Olivier Teytaud. The uniform pattern values is the so called
"light" playout which chooses uniformly between all legal moves except single point proper
eyes.
If you’re not satisfied with these you can also tune your own pattern values with
a pattern database file and load it at runtime with ‘--mc-load-patterns <name>’ adding
your own pattern database.
Let’s start with the uniform pattern values. Those are defined by the file
‘patterns/mc_uniform.db’, which looks like this:
oOo
O*O
oO?
:0
oOo
O*O
---
Chapter 14: Monte Carlo Go 146
:0
|Oo
|*O
+--
:0
Patterns are always exactly 3x3 in size with the move at the center point. The
symbols are the usual for GNU Go pattern databases:
* move
O own stone (i.e. the same color as the color to move)
o own stone or empty
X opponent stone
x opponent stone or empty
? own stone, opponent stone, or empty
| vertical edge
- horizontal edge
+ corner
There’s also a new symbol:
% own stone, opponent stone, empty, or edge
After the pattern comes a line starting with a colon. In all these patterns it says
that the pattern has a move value of 0, i.e. must not be played. Unmatched patterns have
a default value of 1. When all move values are zero for both players, the playout will stop.
Including the three patterns above is important because otherwise the playouts would be
likely to go on indefinitely, or as it actually happens be terminated at a hard-coded limit
of 600 moves. Also place these patterns at the top of the database because when multiple
patterns match, the first one is used, regardless of the values.
When using only these patterns you will probably notice that it plays rather heavy,
trying hard to be solidly connected. This is because uniform playouts are badly biased with
a high probability of non-solid connections being cut apart. To counter this you could try
a pattern like
?X?
O*O
x.?
:20,near
to increase the probability that the one-point jump is reinforced when threatened.
Here we added the property "near", which means that the pattern only applies if the
previous move was played "near" this move. Primarily "near" means within the surrounding
3x3 neighborhood but it also includes certain cases of liberties of low-liberty strings adjacent
to the previous move, e.g. the move to extend out of an atari created by the previous move.
You have to read the source to find out the exact rules for nearness.
We could also be even more specific and say
Chapter 14: Monte Carlo Go 147
?X?
O*O
x.?
:20,near,osafe,xsafe
to exclude the cases where this move is a self atari (osafe) or would be a self-atari
for the opponent (xsafe).
It may also be interesting to see the effect of capturing stones. A catch-all pattern
for captures would be
?X%
?*%
%%%
:10,ocap1,osafe
:20,ocap2
:30,ocap3
where we have used multiple colon lines to specify different move values depending
on the number of captured stones; value 10 for a single captured stone, value 20 for two
captured stones, and value 30 for three or more captured stones. Here we also excluded
self-atari moves in the case of 1 captured stone in order to avoid getting stuck in triple-ko
in the playouts (there’s no superko detection in the playouts).
The full set of pattern properties is as follows:
near The move is "near" the previous move.
far The move is not "near" the previous move.
osafe The move is not a self-atari.
ounsafe The move is a self-atari.
xsafe The move would not be a self-atari for the opponent.
xunsafe The move would be a self-atari for the opponent.
xsuicide The move would be suicide for the opponent
xnosuicide
The move would not be suicide for the opponent.
ocap0 The move captures zero stones.
ocap1 The move captures one stone.
ocap2 The move captures two stones.
ocap3 The move captures three or more stones.
ocap1+ The move captures one or more stones.
ocap1- The move captures at most one stone.
ocap2+ The move captures two or more stones.
ocap2- The move captures at most two stones.
Chapter 14: Monte Carlo Go 148
int board_size;
Intersection board[MAXSIZE];
int board_ko_pos;
float komi;
int white_captured;
int black_captured;
Hash_data hashdata;
Chapter 15: The Board Library 150
These variables should never be manipulated directly, since they are only the front
end for the incremental machinery. They can be read, but should only be written by using
the functions described in the next section. If you write directly to them, the incremental
data structures will become out of sync with each other, and a crash is the likely result.
The board array includes out-of-board markers around the board. To make the
relation to the old two-dimensional board representation clear, this figure shows how the
1D indices correspond to the 2D indices when MAX BOARD is 7.
j -1 0 1 2 3 4 5 6
i +----------------------------------
-1| 0 1 2 3 4 5 6 7
0| 8 9 10 11 12 13 14 15
1| 16 17 18 19 20 21 22 23
2| 24 25 26 27 28 29 30 31
3| 32 33 34 35 36 37 38 39
4| 40 41 42 43 44 45 46 47
5| 48 49 50 51 52 53 54 55
6| 56 57 58 59 60 61 62 63
7| 64 65 66 67 68 69 70 71 72
To convert between a 1D index pos and a 2D index (i,j), the macros POS, I, and
J are provided, defined as below:
All 1D indices not corresponding to points on the board have the out of board marker
value GRAY. Thus if board_size and MAX_BOARD both are 7, this looks like
Chapter 15: The Board Library 151
j -1 0 1 2 3 4 5 6
i +----------------------------------
-1| # # # # # # # #
0| # . . . . . . .
1| # . . . . . . .
2| # . . . . . . .
3| # . . . . . . .
4| # . . . . . . .
5| # . . . . . . .
6| # . . . . . . .
7| # # # # # # # # #
The indices marked ‘#’ have value GRAY. If MAX_BOARD is 7 and board_size is only
5:
j -1 0 1 2 3 4 5 6
i +----------------------------------
-1| # # # # # # # #
0| # . . . . . # #
1| # . . . . . # #
2| # . . . . . # #
3| # . . . . . # #
4| # . . . . . # #
5| # # # # # # # #
6| # # # # # # # #
7| # # # # # # # # #
Navigation on the board is done by the SOUTH, WEST, NORTH, and EAST macros,
#define NS (MAX_BOARD + 1)
#define WE 1
#define SOUTH(pos) ((pos) + NS)
#define WEST(pos) ((pos) - 1)
#define NORTH(pos) ((pos) - NS)
#define EAST(pos) ((pos) + 1)
There are also shorthand macros SW, NW, NE, SE, SS, WW, NN, EE for two step move-
ments.
Any movement from a point on the board to an adjacent or diagonal vertex is guar-
anteed to produce a valid index into the board array, and the color found is GRAY if it is
not on the board. To do explicit tests for out of board there are two macros
#define ON_BOARD(pos) (board[pos] != GRAY)
#define ON_BOARD1(pos) (((unsigned) (pos) < BOARDSIZE) && board[pos] != GRAY)
where the first one should be used in the algorithms and the second one is useful for
assertion tests.
The advantage of a one-dimensional board array is that it gives a significant perfor-
mance advantage. We need only one variable to determine a board position, which means
that many functions need less arguments. Also, often one computation is sufficient for 1D-
coordinate where we would need two with two 2D-coordinates: If we, for example, want
Chapter 15: The Board Library 152
to have the coordinate of the upper right of pos, we can do this with NORTH(EAST(pos))
instead of (i+1, j-1).
Important: The 2D coordinate (-1,-1), which is used for pass and sometimes to
indicate no point, maps to the 1D coordinate 0, not to -1. Instead of a plain 0, use one of
the macros NO_MOVE or PASS_MOVE.
A loop over multiple directions is straightforwardly written:
for (k = 0; k < 4; k++) {
int d = delta[k];
do_something(pos + d);
}
The following constants are useful for loops over the entire board and allocation of
arrays with a 1-1 mapping to the board.
#define BOARDSIZE ((MAX_BOARD + 2) * (MAX_BOARD + 1) + 1)
#define BOARDMIN (MAX_BOARD + 2)
#define BOARDMAX (MAX_BOARD + 1) * (MAX_BOARD + 1)
BOARDSIZE is the actual size of the 1D board array, BOARDMIN is the first index
corresponding to a point on the board, and BOARDMAX is one larger than the last index
corresponding to a point on the board.
Often one wants to traverse the board, carrying out some function at every vertex.
Here are two possible ways of doing this:
int m, n;
for (m = 0; m < board_size; m++)
for (n = 0; n < board_size; n++) {
do_something(POS(m, n));
}
Or:
int pos;
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (ON_BOARD(pos))
do_something(pos);
}
Given an arbitrary board position in the ‘board’ array, this is done by calling incremental_
board_init(). It is not necessary to call this function explicitly since any other function
that needs the information does this if it has not been done.
The interesting part of the code is the incremental update of the data structures
when a stone is played and subsequently removed. To understand the strategies involved
in adding a stone it is necessary to first know how undoing a move works. The idea is
that as soon as some piece of information is about to be changed, the old value is pushed
onto a stack which stores the value and its address. The stack is built from the following
structures:
struct change_stack_entry {
int *address;
int value;
};
In the second case we do not create a new string but extend the neighbor with the
new stone. This involves linking the new stone into the cyclic chain, if needed moving the
origin, and updating liberties and neighbors. Liberty and neighbor information also needs
updating for the neighbors of the new stone.
In the third case finally, we need to join already existing strings. In order not to
have to store excessive amounts of information, we create a new string for the new stone
and let it assimilate the neighbor strings. Thus all information about those can simply be
left around in the ’string’ array, exactly as for removed strings. Here it becomes a little
more complex to keep track of liberties and neighbors since those may have been shared
by more than one of the joined strings. Making good use of marks it all becomes rather
straightforward anyway.
The often used construction
pos = FIRST_STONE(s);
do {
...
pos = NEXT_STONE(pos);
} while (!BACK_TO_FIRST_STONE(s, pos));
traverses the stones of the string with number ‘s’ exactly once, with pos holding the co-
ordinates. In general pos is used as board coordinate and ‘s’ as an index into the string
array or sometimes a pointer to an entry in the string array.
In case the move is a ko capture, the legality of the capture is subject to the komaster
scheme (see Section 11.4 [Ko], page 116).
• int trymove(int pos, int color, const char *message)
Returns true if (pos) is a legal move for color. In that case, it pushes
the board on the stack and makes the move, incrementing stackp. If the
Chapter 15: The Board Library 156
Other board functions are documented in See Section 18.3 [Board Utilities], page 173.
Chapter 16: Handling SGF trees in memory 158
SGF - Smart Game Format - is a file format which is used for storing game records for
a number of different games, among them chess and go. The format is a framework with
special adaptions to each game. This is not a description of the file format standard. Too
see the exact definition of the file format, see http://www.red-bean.com/sgf/.
GNU Go contains a library to handle go game records in the SGF format in memory
and to read and write SGF files. This library - libsgf.a - is in the sgf subdirectory. To
use the SGF routines, include the file ‘sgftree.h’.
Each game record is stored as a tree of nodes, where each node represents a state
of the game, often after some move is made. Each node contains zero or more properties,
which gives meaning to the node. There can also be a number of child nodes which are
different variations of the game tree. The first child node is the main variation.
Here is the definition of SGFNode, and SGFProperty, the data structures which are
used to encode the game tree.
Each node of the SGF tree is stored in an SGFNode struct. It has a pointer to a linked
list of properties (see below) called props. It also has a pointer to a linked list of children,
where each child is a variation which starts at this node. The variations are linked through
the next pointer and each variation continues through the child pointer. Each and every
node also has a pointer to its parent node (the parent field), except the top node whose
parent pointer is NULL.
An SGF property is encoded in the SGFPoperty struct. It is linked in a list through
the next field. A property has a name which is encoded in a short int. Symbolic names of
properties can be found in ‘sgf_properties.h’.
Some properties also have a value, which could be an integer, a floating point value,
a character or a string. These values can be accessed or set through special functions.
Chapter 16: Handling SGF trees in memory 159
An SGFTree contains a pointer to the root node of an SGF tree and a pointer to the
node that we last accessed. Most of the time this will be the last move of an ongoing game.
Most of the functions which manipulate an SGFTree work exactly like their SGFNode
counterparts, except that they work on the current node of the tree.
All the functions below that take arguments tree and node will work on:
1. node if non-NULL
2. tree->lastnode if non-NULL
3. The current end of the game tree.
in that order.
Chapter 17: Application Programmers Interface to GNU Go 160
On top of this, there is a library which helps the application use Smart Game Format
(SGF) files, with complete handling of game trees in memory and in files. This library is
called libsgf.a
The main part of the code within GNU Go is the move generation library which
given a position generates a move. This part of the engine can also be used to manipulate a
go position, add or remove stones, do tactical and strategic reading and to query the engine
for legal moves. These functions are collected into libengine.a.
The game handling code helps the application programmer keep tracks of the moves
in a game. Games can be saved to SGF files and then later be read back again. These are
also within libengine.a.
The responsibility of the application is to provide the user with a user interface,
graphical or not, and let the user interact with the engine.
color value
EMPTY 0
WHITE 1
BLACK 2
There is a macro, OTHER_COLOR(color) which can be used to get the other color
than the parameter. This macro can only be used on WHITE or BLACK, but not on EMPTY.
GNU Go uses two different representations of the board, for most purposes a one-
dimensional one, but for a few purposes a two dimensional one (see Chapter 15 [Libboard],
page 149). The one-dimensional board was introduced before GNU Go 3.2, while the two-
dimensional board dates back to the ancestral program written by Man Lung Li before
1995. The API still uses the two-dimensional board, so the API functions have not changed
much since GNU Go 3.0.
Chapter 17: Application Programmers Interface to GNU Go 162
struct board_state {
int board_size;
Intersection board[BOARDSIZE];
int board_ko_pos;
int black_captured;
int white_captured;
Intersection initial_board[BOARDSIZE];
int initial_board_ko_pos;
int initial_white_captured;
int initial_black_captured;
int move_history_color[MAX_MOVE_HISTORY];
int move_history_pos[MAX_MOVE_HISTORY];
int move_history_pointer;
float komi;
int move_number;
};
typedef struct {
int handicap;
The meaning of handicap should be obvious. to_move is the color of the side whose
turn it is to move.
The SGF tree game_record is used to store all the moves in the entire game, including
a header node which contains, among other things, komi and handicap.
If one or both of the opponents is the computer, the field computer_player is used.
Otherwise it can be ignored.
GNU Go can use a trickle file to continuously save all the moves of an ongoing
game. This file can also contain information about internal state of the engine such as move
reasons for various locations or move valuations. The name of this file should be stored in
outfilename and the file pointer to the open file is stored in outfile. If no trickle file is
used, outfilename[0] will contain a null character and outfile will be set to NULL.
Chapter 17: Application Programmers Interface to GNU Go 165
18 Utility Functions
In this Chapter, we document some of the utilities which may be called from the GNU Go
engine.
through the sequence, the three last coordinate pairs gives a position to be
analyzed by break_through(), to see whether either color has managed to
enclose some stones and/or connected his own stones. If any of the three
last positions is empty, it’s assumed that the enclosure has failed, as well
as the attempt to connect. If one or more of the moves to play turns out to
be illegal for some reason, the rest of the sequence is played anyway, and
break_through() is called as if nothing special happened. Like break_
through(), this function returns 1 if the attempt to break through was
succesful and 2 if it only managed to cut through.
• int play_attack_defend_n(int color, int do_attack, int num_moves, ...)
• int play_attack_defend2_n(int color, int do_attack, int num_moves, ...)
The function play_attack_defend_n() plays a sequence of moves, alter-
nating between the players and starting with color. After having played
through the sequence, the last coordinate pair gives a target to attack or
defend, depending on the value of do attack. If there is no stone present
to attack or defend, it is assumed that it has already been captured. If one
or more of the moves to play turns out to be illegal for some reason, the
rest of the sequence is played anyway, and attack/defense is tested as if
nothing special happened. Conversely, play_attack_defend2_n() plays
a sequence of moves, alternating between the players and starting with
color. After having played through the sequence, the two last coordinate
pairs give two targets to simultaneously attack or defend, depending on
the value of do attack. If there is no stone present to attack or defend, it
is assumed that it has already been captured. If one or more of the moves
to play turns out to be illegal for some reason, the rest of the sequence is
played anyway, and attack/defense is tested as if nothing special happened.
A typical use of these functions is to set up a ladder in an autohelper and
see whether it works or not.
• int play_connect_n(int color, int do_connect, int num_moves, ...)
Plays a sequence of moves, alternating between the players and starting
with color. After having played through the sequence, the two last co-
ordinates give two targets that should be connected or disconnected, de-
pending on the value of do connect. If there is no stone present to connect
or disconnect, it is assumed that the connection has failed. If one or more
of the moves to play turns out to be illegal for some reason, the rest of
the sequence is played anyway, and connection/disconnection is tested as
if nothing special happened. Ultimately the connection is decided by the
functions string_connect and disconnect (see Section 11.10 [Connection
Reading], page 124).
• void set_depth_values(int level)
It is assumed in reading a ladder if stackp >= depth that as soon as a
bounding stone is in atari, the string is safe. Similar uses are made of the
other depth parameters such as backfill_depth and so forth. In short,
simplifying assumptions are made when stackp is large. Unfortunately
any such scheme invites the “horizon effect,” in which a stalling move is
Chapter 18: Utility Functions 168
OX
capturing one of the two ‘X’ strings. The name is a slight misnomer since
this includes attacks which are not necessarily double ataris, though the
common double atari is the most important special case. If safe_stones
!= NULL, then only attacks on stones marked as safe are tried. The value
of the double atari attack is returned in value (unless value is NULL), and
the attacked stones are marked unsafe.
• void unconditional_life(int unconditional_territory[BOARDMAX], int color)
Find those worms of the given color that can never be captured, even if
the opponent is allowed an arbitrary number of consecutive moves. The
coordinates of the origins of these worms are written to the worm arrays
and the number of non-capturable worms is returned. The algorithm is to
cycle through the worms until none remains or no more can be captured.
A worm is removed when it is found to be capturable, by letting the op-
ponent try to play on all its liberties. If the attack fails, the moves are
undone. When no more worm can be removed in this way, the remaining
ones are unconditionally alive. After this, unconditionally dead opponent
worms and unconditional territory are identified. To find these, we con-
tinue from the position obtained at the end of the previous operation (only
unconditionally alive strings remain for color) with the following steps:
1. Play opponent stones on all liberties of the unconditionally alive strings
except where illegal. (That the move order may determine exactly
which liberties can be played legally is not important. Just pick an
arbitrary order).
2. Recursively extend opponent strings in atari, except where this would
be suicide.
3. Play an opponent stone anywhere it can get two empty neighbors. (I.e.
split big eyes into small ones).
4. an opponent stone anywhere it can get one empty neighbor. (I.e. re-
duce two space eyes to one space eyes.) Remaining opponent strings in
atari and remaining liberties of the unconditionally alive strings con-
stitute the unconditional territory. Opponent strings from the initial
position placed on unconditional territory are unconditionally dead.
On return, unconditional_territory[][] is 1 where color has un-
conditionally alive stones, 2 where it has unconditional territory, and
0 otherwise.
• void who_wins(int color, FILE *outfile)
Score the game and determine the winner
• void find_superstring(int str, int *num_stones, int *stones)
Find the stones of an extended string, where the extensions are through
the following kinds of connections:
1. Solid connections (just like ordinary string).
OO
Chapter 18: Utility Functions 170
The following functions are in ‘showbord.c’. Not all public functions in that file are
listed here.
• void showboard(int xo)
Show go board.
xo=0: black and white XO board for ascii game
xo=1: colored dragon display
xo=2: colored eye display
xo=3: colored owl display
xo=4: colored matcher status display
• const char * status_to_string(int status)
Convert a status value to a string.
• const char * safety_to_string(int status)
Convert a safety value to a string.
• const char * result_to_string(int result)
Convert a read result to a string
Chapter 18: Utility Functions 173
Next we come to countlib() and its allies, which address the problem of determining
how many liberties a string has. Although countlib() addresses this basic question, other
functions can often get the needed information more quickly, so there are a number of
different functions in this family.
• int countlib(int str)
Count the number of liberties of the string at pos. There must be a stone
at this location.
• int findlib(int str, int maxlib, int *libs)
Find the liberties of the string at str. This location must not be empty.
The locations of up to maxlib liberties are written into libs[]. The full
number of liberties is returned. If you want the locations of all liberties,
whatever their number, you should pass MAXLIBS as the value for maxlib
and allocate space for libs[] accordingly.
• int fastlib(int pos, int color, int ignore_captures)
Count the liberties a stone of the given color would get if played at pos.
The intent of this function is to be as fast as possible, not necessarily
complete. But if it returns a positive value (meaning it has succeeded),
the value is guaranteed to be correct. Captures are ignored based if the
ignore_captures field is nonzero. The location pos must be empty. The
function fails if there are more than two neighbor strings of the same color.
In this case, the return value is -1. Captures are handled in a very limited
way, so if ignore capture is 0, and a capture is required, it will often return
-1.
• int approxlib(int pos, int color, int maxlib, int *libs)
Find the liberties a stone of the given color would get if played at pos,
ignoring possible captures of opponent stones. The location pos must be
empty. If libs != NULL, the locations of up to maxlib liberties are written
into libs[]. The counting of liberties may or may not be halted when
maxlib is reached. The number of liberties found is returned, which may
be less than the total number of liberties if maxlib is small. If you want
the number or the locations of all liberties, however many they are, you
should pass MAXLIBS as the value for maxlib and allocate space for libs[]
accordingly.
• int accuratelib(int pos, int color, int maxlib, int *libs)
Find the liberties a stone of the given color would get if played at pos. This
function takes into consideration all captures. Its return value is exact in
that sense it counts all the liberties, unless maxlib allows it to stop earlier.
The location pos must be empty. If libs != NULL, the locations of up to
maxlib liberties are written into libs[]. The counting of liberties may
or may not be halted when maxlib is reached. The number of found
liberties is returned. This function guarantees that liberties which are not
results of captures come first in libs[] array. To find whether all the
liberties starting from a given one are results of captures, one may use if
(board[libs[k]] != EMPTY) construction. If you want the number or the
Chapter 18: Utility Functions 175
locations of all liberties, however many they are, you should pass MAXLIBS
as the value for maxlib and allocate space for libs[] accordingly.
Next we have some general utility functions.
• int count_common_libs(int str1, int str2)
Find the number of common liberties of the two strings.
• int find_common_libs(int str1, int str2, int maxlib, int *libs)
Find the common liberties of the two strings. The locations of up to maxlib
common liberties are written into libs[]. The full number of common
liberties is returned. If you want the locations of all common liberties,
whatever their number, you should pass MAXLIBS as the value for maxlib
and allocate space for libs[] accordingly.
• int have_common_lib(int str1, int str2, int *lib)
Determine whether two strings have at least one common liberty. If they
do and lib != NULL, one common liberty is returned in *lib.
• int countstones(int str)
Report the number of stones in a string.
• int findstones(int str, int maxstones, int *stones)
Find the stones of the string at str. The location must not be empty. The
locations of up to maxstones stones are written into stones[]. The full
number of stones is returned.
• int chainlinks(int str, int adj[MAXCHAIN])
This very useful function returns (in the adj array) the chains surrounding
the string at str. The number of chains is returned.
• int chainlinks2(int str, int adj[MAXCHAIN], int lib)
Returns (in adj array) those chains surrounding the string at str, which
has exactly lib liberties. The number of such chains is returned.
• int chainlinks3(int str, int adj[MAXCHAIN], int lib)
Returns (in adj array) the chains surrounding the string at str, which
have less or equal lib liberties. The number of such chains is returned.
• int extended_chainlinks(int str, int adj[MAXCHAIN], int both_colors)
Returns (in the adj array) the opponent strings being directly adjacent to
str or having a common liberty with str. The number of such strings is
returned. If the both colors parameter is true, also own strings sharing a
liberty are returned.
• int find_origin(int str)
Find the origin of a string, i.e. the point with the smallest 1D board
coordinate. The idea is to have a canonical reference point for a string.
• int is_self_atari(int pos, int color)
Determine whether a move by color at pos would be a self atari, i.e.
whether it would get more than one liberty. This function returns true
also for the case of a suicide move.
Chapter 18: Utility Functions 176
2 clear_board
=2
3 play black D5
=3
4 genmove white
=4 C3
5 play black C3
?5 illegal move
6 play black E3
=6
7 showboard
=7
Chapter 19: The Go Text Protocol 179
A B C D E F G
7 . . . . . . . 7
6 . . . . . . . 6
5 . . + X + . . 5
4 . . . + . . . 4
3 . . O . X . . 3
2 . . . . . . . 2 WHITE (O) has captured 0 stones
1 . . . . . . . 1 BLACK (X) has captured 0 stones
A B C D E F G
8 quit
=8
Commands are given on a single line, starting by an optional identity number, fol-
lowed by the command name and its arguments.
If the command is successful, the response starts by an equals sign (‘=’), followed
by the identity number of the command (if any) and then the result. In this example all
results were empty strings except for command 4 where the answer was the white move at
C3, and command 7 where the result was a diagram of the current board position. The
response ends by two consecutive newlines.
Failing commands are signified by a question mark (‘?’) instead of an equals sign, as
in the response to command 5.
The detailed specification of the protocol can be found at http://www.lysator.liu.se/~gunnar/gt
The available commands in GNU Go may always be listed using the command list_
commands. They are also documented in See Section 19.6 [GTP command reference],
page 183.
• ‘regression/regress.pike’
Pike script to run regressions. More feature-rich and powerful than
‘regress.awk’.
• ‘regression/view.pike’
Pike script to examine a single regression testcase through a graphical
board. This gives an easy way to inspect many of the GNU Go internals.
• ‘interface/gtp_examples/twogtp’
Perl script to play two engines against each other. The script essentially
sets up both engines with desired boardsize, handicap, and komi, then
relays moves back and forth between the engines.
• ‘interface/gtp_examples/twogtp-a’
An alternative Perl implementation of twogtp.
• ‘interface/gtp_examples/twogtp.py’
Implementation of twogtp in Python. Has more features than the Perl
variants.
• ‘interface/gtp_examples/twogtp.pike’
Implementation of twogtp in Pike. Has even more features than the Python
variant.
• ‘interface/gtp_examples/2ptkgo.pl’
Variation of twogtp which includes a graphical board.
More GTP applications, including bridges to go servers and graphical user interfaces,
are listed at http://www.lysator.liu.se/~gunnar/gtp/.
To see how a simple but fairly typical command is implemented we look at gtp_
countlib() (a GNU Go private extension command):
static int
gtp_countlib(char *s)
{
int i, j;
if (!gtp_decode_coord(s, &i, &j))
return gtp_failure("invalid coordinate");
if (BOARD(i, j) == EMPTY)
return gtp_failure("vertex must not be empty");
gtp_start_response(GTP_SUCCESS);
Chapter 19: The Go Text Protocol 183
gtp_printf("\n");
return GTP_OK;
}
As we have said, the response should be finished with two newlines. Here we have
to finish up the response ourselves since we already have one newline in place from the last
command printed in the loop.
In order to add a new GTP command to GNU Go, the following pieces of code need
to be inserted in ‘play_gtp.c’:
1. A function declaration using the DECLARE macro in the list starting at line 68.
2. An entry in the commands[] array starting at line 200.
3. An implementation of the function handling the command.
Useful helper functions in ‘gtp.c’/‘gtp.h’ are:
• gtp_printf() for basic formatted printing.
• gtp_mprintf() for printing with special format codes for vertices and colors.
• gtp_success() and gtp_failure() for simple responses.
• gtp_start_response() and gtp_end_response() for more complex responses.
• gtp_print_vertex() and gtp_print_vertices() for printing one or multiple vertices.
• gtp_decode_color() to read in a color from the command arguments.
• gtp_decode_coord() to read in a vertex from the command arguments.
• gtp_decode_move() to read in a move, i.e. color plus vertex, from the command
arguments.
• quit: Quit
Arguments: none
Fails: never
Returns: nothing
Arguments: vertex
Fails: invalid vertex, empty vertex
Returns: attack code followed by attack point if attack code nonzero.
• owl defend: Try to defend a dragon.
Arguments: vertex
Fails: invalid vertex, empty vertex
Returns: defense code followed by defense point if defense code nonzero.
• owl threaten attack: Try to attack a dragon in 2 moves.
Arguments: vertex
Fails: invalid vertex, empty vertex
Returns: attack code followed by the two attack points if
attack code nonzero.
• owl threaten defense: Try to defend a dragon with 2 moves.
Arguments: vertex
Fails: invalid vertex, empty vertex
Returns: defense code followed by the 2 defense points if
defense code nonzero.
• owl does attack: Examine whether a specific move attacks a dragon.
Arguments: vertex (move), vertex (dragon)
Fails: invalid vertex, empty vertex
Returns: attack code
• owl does defend: Examine whether a specific move defends a dragon.
Arguments: vertex (move), vertex (dragon)
Fails: invalid vertex, empty vertex
Returns: defense code
• owl connection defends: Examine whether a connection defends involved dragons.
Arguments: vertex (move), vertex (dragon1), vertex (dragon2)
Fails: invalid vertex, empty vertex
Returns: defense code
• defend both: Try to defend both of two strings
Arguments: two vertices
Fails: invalid vertex, empty vertex
Returns: defend code for the strings. Guarantees there
exists a move which will defend both of the two
with defend_code, but does not return the move.
• owl substantial: Determine whether capturing a string gives a living dragon
Arguments: vertex
Fails: invalid vertex, empty vertex
Returns: 1 if dragon can live, 0 otherwise
• analyze semeai: Analyze a semeai
Arguments: dragona, dragonb
Fails: invalid vertices, empty vertices
Returns: semeai defense result, semeai attack result, semeai move
Chapter 19: The Go Text Protocol 190
• analyze semeai after move: Analyze a semeai after a move have been made.
Arguments: color, vertex, dragona, dragonb
Fails: invalid vertices
Returns: semeai defense result, semeai attack result, semeai move
• tactical analyze semeai: Analyze a semeai, not using owl
Arguments: dragona, dragonb
Fails: invalid vertices, empty vertices
Returns: status of dragona, dragonb assuming dragona moves first
• connect: Try to connect two strings.
Arguments: vertex, vertex
Fails: invalid vertex, empty vertex, vertices of different colors
Returns: connect result followed by connect point if successful.
• disconnect: Try to disconnect two strings.
Arguments: vertex, vertex
Fails: invalid vertex, empty vertex, vertices of different colors
Returns: disconnect result followed by disconnect point if successful.
• break in: Try to break from string into area.
Arguments: vertex, vertices
Fails: invalid vertex, empty vertex.
Returns: result followed by break in point if successful.
• block off: Try to block string from area.
Arguments: vertex, vertices
Fails: invalid vertex, empty vertex.
Returns: result followed by block point if successful.
• eval eye: Evaluate an eye space
Arguments: vertex
Fails: invalid vertex
Returns: Minimum and maximum number of eyes. If these differ an
attack and a defense point are additionally returned.
If the vertex is not an eye space or not of unique color,
a single -1 is returned.
• dragon status: Determine status of a dragon.
Arguments: optional vertex
Fails: invalid vertex, empty vertex
Returns: status ("alive", "critical", "dead", or "unknown"),
attack point, defense point. Points of attack and
defense are only given if the status is critical.
If no vertex is given, the status is listed for all
dragons, one per row in the format "A4: alive".
Arguments: none
Fails: never
Returns: number of connection nodes
• test eyeshape: Test an eyeshape for inconsistent evaluations
Arguments: Eyeshape vertices
Fails: Bad vertices
Returns: Failure reports on stderr.
• analyze eyegraph: Compute an eyevalue and vital points for an eye graph
Arguments: Eyeshape encoded in string
Fails: Bad eyeshape, analysis failed
Returns: Eyevalue, vital points
• cputime: Returns elapsed CPU time in seconds.
Arguments: none
Fails: never
Returns: Total elapsed (user + system) CPU time in seconds.
• showboard: Write the position to stdout.
Arguments: none
Fails: never
Returns: nothing
white_influence (float)
black_influence (float)
white_strength (float)
black_strength (float)
white_attenuation (float)
Chapter 19: The Go Text Protocol 196
black_attenuation (float)
white_permeability (float)
black_permeability (float)
territory_value (float)
influence_regions (int)
non_territory (int)
A19:
color black
size 10
effective_size 17.83
Chapter 19: The Go Text Protocol 197
origin A19
liberties 8
liberties2 15
liberties3 10
liberties4 8
attack PASS
attack_code 0
lunch B19
defend PASS
defend_code 0
cutstone 2
cutstone2 0
genus 0
inessential 0
B19:
color white
.
.
.
inessential 0
C19:
...
Arguments: vertex
Fails: never
Returns: half eye data fields and values, one pair per row
• start sgftrace: Start storing moves executed during reading in an sgf tree in memory.
Arguments: none
Fails: never
Returns: nothing
Warning: You had better know what you’re doing if you try to use this
command.
• finish sgftrace: Finish storing moves in an sgf tree and write it to file.
Arguments: filename
Fails: never
Returns: nothing
Warning: You had better know what you’re doing if you try to use this
command.
• printsgf: Dump the current position as a static sgf file to filename, or as output if
filename is missing or "-"
Arguments: optional filename
Fails: never
Returns: nothing if filename, otherwise the sgf
• tune move ordering: Tune the parameters for the move ordering in the tactical reading.
Arguments: MOVE_ORDERING_PARAMETERS integers
Fails: incorrect arguments
Returns: nothing
• echo: Echo the parameter
Arguments: string
Fails: never
Returns: nothing
• echo err: Echo the parameter to stdout AND stderr
Arguments: string
Fails: never
Returns: nothing
• help: List all known commands
Arguments: none
Fails: never
Returns: list of known commands, one per line
Arguments: value
Fails: invalid arguments
Returns: nothing
• set search limit: mark a vertex for limited search
Arguments: position
Fails: invalid arguments
Returns: nothing
• draw search area: Draw search area. Writes to stderr.
Arguments: none
Fails: never
Returns: nothing
Chapter 20: Regression testing 201
20 Regression testing
The standard purpose of regression testing is to avoid getting the same bug twice. When
a bug is found, the programmer fixes the bug and adds a test to the test suite. The test
should fail before the fix and pass after the fix. When a new version is about to be released,
all the tests in the regression test suite are run and if an old bug reappears, this will be
seen quickly since the appropriate test will fail.
The regression testing in GNU Go is slightly different. A typical test case involves
specifying a position and asking the engine what move it would make. This is compared to
one or more correct moves to decide whether the test case passes or fails. It is also stored
whether a test case is expected to pass or fail, and deviations in this status signify whether
a change has solved some problem and/or broken something else. Thus the regression
tests both include positions highlighting some mistake being done by the engine, which are
waiting to be fixed, and positions where the engine does the right thing, where we want to
detect if a change breaks something.
are executed in the order they appear, but only those on numbered lines are used for testing.
The comment lines starting with #? are magical to the regression testing scripts and indicate
correct results and expected pass/fail status. The string within brackets is matched as a
regular expression against the response from the previous numbered GTP command. A
particular useful feature of regular expressions is that by using ‘|’ it is possible to specify
alternatives. Thus B14|D17 above means that if either B14 or D17 is the move generated in
test case 90, it passes. There is one important special case to be aware of. If the correct
result string starts with an exclamation mark, this is excluded from the regular expression
but afterwards the result of the matching is negated. Thus !P13 in test case 95 means that
any move except P13 is accepted as a correct result.
In test case 100, the brackets on the #? line is followed by an asterisk. This means
that the test is expected to fail. If there is no asterisk, the test is expected to pass. The
brackets may also be followed by a ‘&’, meaning that the result is ignored. This is primarily
used to report statistics, e.g. how many tactical reading nodes were spent while running
the test suite.
The numbers here mean that the test suite took 2.96 seconds of processor time
and 3.22 seconds of real time. The consumption of reading nodes was 614772 for tactical
reading, 3322 for owl reading, and 469 for connection reading. The last line relates to the
variability of the generated moves in the test suite, and 0 means that none was decided by
the randomness contribution to the move valuation. Multiple testsuites can be run by e.g.
./regress.pike owl ld_owl owl1.
It is also possible to run a single testcase, e.g. ./regress.pike strategy:6, a
number of testcases, e.g. ./regress.pike strategy:6,23,45, a range of testcases, e.g.
./regress.pike strategy:13-15 or more complex combinations e.g. ./regress.pike
strategy:6,13-15,23,45 nicklas3:602,1403.
There are also command line options to choose what engine to run, what options to
send to the engine, to turn on verbose output, and to use a file to specify which testcases
to run. Run ./regress.pike --help for a complete and up to date list of options.
Appendix A Copying
The program GNU Go is distributed under the terms of the GNU General Public License
(GPL). Its documentation is distributed under the terms of the GNU Free Documentation
License (GFDL).
Preamble
The GNU General Public License is a free, copyleft license for software and other kinds of
works.
The licenses for most software and other practical works are designed to take away
your freedom to share and change the works. By contrast, the GNU General Public License
is intended to guarantee your freedom to share and change all versions of a program–to
make sure it remains free software for all its users. We, the Free Software Foundation, use
the GNU General Public License for most of our software; it applies also to any other work
released this way by its authors. You can apply it to your programs, too.
When we speak of free software, we are referring to freedom, not price. Our General
Public Licenses are designed to make sure that you have the freedom to distribute copies
of free software (and charge for them if you wish), that you receive source code or can get
it if you want it, that you can change the software or use pieces of it in new free programs,
and that you know you can do these things.
To protect your rights, we need to prevent others from denying you these rights
or asking you to surrender the rights. Therefore, you have certain responsibilities if you
distribute copies of the software, or if you modify it: responsibilities to respect the freedom
of others.
For example, if you distribute copies of such a program, whether gratis or for a fee,
you must pass on to the recipients the same freedoms that you received. You must make
sure that they, too, receive or can get the source code. And you must show them these
terms so they know their rights.
Developers that use the GNU GPL protect your rights with two steps: (1) assert
copyright on the software, and (2) offer you this License giving you legal permission to copy,
distribute and/or modify it.
For the developers’ and authors’ protection, the GPL clearly explains that there is
no warranty for this free software. For both users’ and authors’ sake, the GPL requires
that modified versions be marked as changed, so that their problems will not be attributed
erroneously to authors of previous versions.
Some devices are designed to deny users access to install or run modified versions
of the software inside them, although the manufacturer can do so. This is fundamentally
Appendix A: Copying 207
incompatible with the aim of protecting users’ freedom to change the software. The sys-
tematic pattern of such abuse occurs in the area of products for individuals to use, which
is precisely where it is most unacceptable. Therefore, we have designed this version of the
GPL to prohibit the practice for those products. If such problems arise substantially in
other domains, we stand ready to extend this provision to those domains in future versions
of the GPL, as needed to protect the freedom of users.
Finally, every program is threatened constantly by software patents. States should
not allow patents to restrict development and use of software on general-purpose computers,
but in those that do, we wish to avoid the special danger that patents applied to a free
program could make it effectively proprietary. To prevent this, the GPL assures that patents
cannot be used to render the program non-free.
The precise terms and conditions for copying, distribution and modification follow.
1. SOURCE CODE
The "source code" for a work means the preferred form of the work for making modi-
fications to it. "Object code" means any non-source form of a work.
A "Standard Interface" means an interface that either is an official standard defined
by a recognized standards body, or, in the case of interfaces specified for a particular
programming language, one that is widely used among developers working in that
language.
The "System Libraries" of an executable work include anything, other than the work as
a whole, that (a) is included in the normal form of packaging a Major Component, but
which is not part of that Major Component, and (b) serves only to enable use of the
work with that Major Component, or to implement a Standard Interface for which an
implementation is available to the public in source code form. A "Major Component",
in this context, means a major essential component (kernel, window system, and so
on) of the specific operating system (if any) on which the executable work runs, or a
compiler used to produce the work, or an object code interpreter used to run it.
The "Corresponding Source" for a work in object code form means all the source code
needed to generate, install, and (for an executable work) run the object code and to
modify the work, including scripts to control those activities. However, it does not
include the work’s System Libraries, or general-purpose tools or generally available
free programs which are used unmodified in performing those activities but which are
not part of the work. For example, Corresponding Source includes interface definition
files associated with source files for the work, and the source code for shared libraries
and dynamically linked subprograms that the work is specifically designed to require,
such as by intimate data communication or control flow between those subprograms
and other parts of the work.
The Corresponding Source need not include anything that users can regenerate auto-
matically from other parts of the Corresponding Source.
The Corresponding Source for a work in source code form is that same work.
2. BASIC PERMISSIONS
All rights granted under this License are granted for the term of copyright on the
Program, and are irrevocable provided the stated conditions are met. This License ex-
plicitly affirms your unlimited permission to run the unmodified Program. The output
from running a covered work is covered by this License only if the output, given its
content, constitutes a covered work. This License acknowledges your rights of fair use
or other equivalent, as provided by copyright law.
You may make, run and propagate covered works that you do not convey, without
conditions so long as your license otherwise remains in force. You may convey covered
works to others for the sole purpose of having them make modifications exclusively
for you, or provide you with facilities for running those works, provided that you
comply with the terms of this License in conveying all material for which you do not
control copyright. Those thus making or running the covered works for you must do
so exclusively on your behalf, under your direction and control, on terms that prohibit
them from making any copies of your copyrighted material outside their relationship
with you.
Appendix A: Copying 209
Conveying under any other circumstances is permitted solely under the conditions
stated below. Sublicensing is not allowed; section 10 makes it unnecessary.
medium, is called an "aggregate" if the compilation and its resulting copyright are
not used to limit the access or legal rights of the compilation’s users beyond what the
individual works permit. Inclusion of a covered work in an aggregate does not cause
this License to apply to the other parts of the aggregate.
ticular user or of the way in which the particular user actually uses, or expects or is
expected to use, the product. A product is a consumer product regardless of whether
the product has substantial commercial, industrial or non-consumer uses, unless such
uses represent the only significant mode of use of the product.
"Installation Information" for a User Product means any methods, procedures, autho-
rization keys, or other information required to install and execute modified versions of a
covered work in that User Product from a modified version of its Corresponding Source.
The information must suffice to ensure that the continued functioning of the modified
object code is in no case prevented or interfered with solely because modification has
been made.
If you convey an object code work under this section in, or with, or specifically for
use in, a User Product, and the conveying occurs as part of a transaction in which
the right of possession and use of the User Product is transferred to the recipient in
perpetuity or for a fixed term (regardless of how the transaction is characterized),
the Corresponding Source conveyed under this section must be accompanied by the
Installation Information. But this requirement does not apply if neither you nor any
third party retains the ability to install modified object code on the User Product (for
example, the work has been installed in ROM).
The requirement to provide Installation Information does not include a requirement
to continue to provide support service, warranty, or updates for a work that has been
modified or installed by the recipient, or for the User Product in which it has been
modified or installed. Access to a network may be denied when the modification itself
materially and adversely affects the operation of the network or violates the rules and
protocols for communication across the network.
Corresponding Source conveyed, and Installation Information provided, in accord with
this section must be in a format that is publicly documented (and with an implementa-
tion available to the public in source code form), and must require no special password
or key for unpacking, reading or copying.
7. ADDITIONAL TERMS
"Additional permissions" are terms that supplement the terms of this License by mak-
ing exceptions from one or more of its conditions. Additional permissions that are
applicable to the entire Program shall be treated as though they were included in this
License, to the extent that they are valid under applicable law. If additional permis-
sions apply only to part of the Program, that part may be used separately under those
permissions, but the entire Program remains governed by this License without regard
to the additional permissions.
When you convey a copy of a covered work, you may at your option remove any
additional permissions from that copy, or from any part of it. (Additional permissions
may be written to require their own removal in certain cases when you modify the
work.) You may place additional permissions on material, added by you to a covered
work, for which you have or can give appropriate copyright permission.
Notwithstanding any other provision of this License, for material you add to a covered
work, you may (if authorized by the copyright holders of that material) supplement
the terms of this License with terms:
Appendix A: Copying 212
8. TERMINATION
You may not propagate or modify a covered work except as expressly provided un-
der this License. Any attempt otherwise to propagate or modify it is void, and will
automatically terminate your rights under this License (including any patent licenses
granted under the third paragraph of section 11).
However, if you cease all violation of this License, then your license from a particular
copyright holder is reinstated (a) provisionally, unless and until the copyright holder
explicitly and finally terminates your license, and (b) permanently, if the copyright
holder fails to notify you of the violation by some reasonable means prior to 60 days
after the cessation.
Moreover, your license from a particular copyright holder is reinstated permanently if
the copyright holder notifies you of the violation by some reasonable means, this is the
first time you have received notice of violation of this License (for any work) from that
copyright holder, and you cure the violation prior to 30 days after your receipt of the
notice.
Appendix A: Copying 213
Termination of your rights under this section does not terminate the licenses of parties
who have received copies or rights from you under this License. If your rights have
been terminated and not permanently reinstated, you do not qualify to receive new
licenses for the same material under section 10.
11. PATENTS
A "contributor" is a copyright holder who authorizes use under this License of the
Program or a work on which the Program is based. The work thus licensed is called
the contributor’s "contributor version".
A contributor’s "essential patent claims" are all patent claims owned or controlled by
the contributor, whether already acquired or hereafter acquired, that would be infringed
by some manner, permitted by this License, of making, using, or selling its contributor
version, but do not include claims that would be infringed only as a consequence of
further modification of the contributor version. For purposes of this definition, "con-
trol" includes the right to grant patent sublicenses in a manner consistent with the
requirements of this License.
Appendix A: Copying 214
the Program, the only way you could satisfy both those terms and this License would
be to refrain entirely from conveying the Program.
The GNU General Public License does not permit incorporating your program into
proprietary programs. If your program is a subroutine library, you may consider it more
useful to permit linking proprietary applications with the library. If this is what you want
to do, use the GNU Lesser General Public License instead of this License. But first, please
read <http://www.gnu.org/philosophy/why-not-lgpl.html>.
relationship could be a matter of historical connection with the subject or with related
matters, or of legal, commercial, philosophical, ethical or political position regarding
them.
The “Invariant Sections” are certain Secondary Sections whose titles are designated, as
being those of Invariant Sections, in the notice that says that the Document is released
under this License. If a section does not fit the above definition of Secondary then it is
not allowed to be designated as Invariant. The Document may contain zero Invariant
Sections. If the Document does not identify any Invariant Sections then there are none.
The “Cover Texts” are certain short passages of text that are listed, as Front-Cover
Texts or Back-Cover Texts, in the notice that says that the Document is released under
this License. A Front-Cover Text may be at most 5 words, and a Back-Cover Text may
be at most 25 words.
A “Transparent” copy of the Document means a machine-readable copy, represented
in a format whose specification is available to the general public, that is suitable for
revising the document straightforwardly with generic text editors or (for images com-
posed of pixels) generic paint programs or (for drawings) some widely available drawing
editor, and that is suitable for input to text formatters or for automatic translation to
a variety of formats suitable for input to text formatters. A copy made in an otherwise
Transparent file format whose markup, or absence of markup, has been arranged to
thwart or discourage subsequent modification by readers is not Transparent. An image
format is not Transparent if used for any substantial amount of text. A copy that is
not “Transparent” is called “Opaque”.
Examples of suitable formats for Transparent copies include plain ascii without
markup, Texinfo input format, LaTEX input format, SGML or XML using a publicly
available DTD, and standard-conforming simple HTML, PostScript or PDF designed
for human modification. Examples of transparent image formats include PNG, XCF
and JPG. Opaque formats include proprietary formats that can be read and edited
only by proprietary word processors, SGML or XML for which the DTD and/or
processing tools are not generally available, and the machine-generated HTML,
PostScript or PDF produced by some word processors for output purposes only.
The “Title Page” means, for a printed book, the title page itself, plus such following
pages as are needed to hold, legibly, the material this License requires to appear in the
title page. For works in formats which do not have any title page as such, “Title Page”
means the text near the most prominent appearance of the work’s title, preceding the
beginning of the body of the text.
The “publisher” means any person or entity that distributes copies of the Document
to the public.
A section “Entitled XYZ” means a named subunit of the Document whose title either
is precisely XYZ or contains XYZ in parentheses following text that translates XYZ in
another language. (Here XYZ stands for a specific section name mentioned below, such
as “Acknowledgements”, “Dedications”, “Endorsements”, or “History”.) To “Preserve
the Title” of such a section when you modify the Document means that it remains a
section “Entitled XYZ” according to this definition.
The Document may include Warranty Disclaimers next to the notice which states that
this License applies to the Document. These Warranty Disclaimers are considered to
Appendix A: Copying 219
If the Modified Version includes new front-matter sections or appendices that qualify
as Secondary Sections and contain no material copied from the Document, you may at
your option designate some or all of these sections as invariant. To do this, add their
titles to the list of Invariant Sections in the Modified Version’s license notice. These
titles must be distinct from any other section titles.
You may add a section Entitled “Endorsements”, provided it contains nothing but
endorsements of your Modified Version by various parties—for example, statements of
peer review or that the text has been approved by an organization as the authoritative
definition of a standard.
You may add a passage of up to five words as a Front-Cover Text, and a passage of up
to 25 words as a Back-Cover Text, to the end of the list of Cover Texts in the Modified
Version. Only one passage of Front-Cover Text and one of Back-Cover Text may be
added by (or through arrangements made by) any one entity. If the Document already
includes a cover text for the same cover, previously added by you or by arrangement
made by the same entity you are acting on behalf of, you may not add another; but
you may replace the old one, on explicit permission from the previous publisher that
added the old one.
The author(s) and publisher(s) of the Document do not by this License give permission
to use their names for publicity for or to assert or imply endorsement of any Modified
Version.
5. COMBINING DOCUMENTS
You may combine the Document with other documents released under this License,
under the terms defined in section 4 above for modified versions, provided that you
include in the combination all of the Invariant Sections of all of the original documents,
unmodified, and list them all as Invariant Sections of your combined work in its license
notice, and that you preserve all their Warranty Disclaimers.
The combined work need only contain one copy of this License, and multiple identical
Invariant Sections may be replaced with a single copy. If there are multiple Invariant
Sections with the same name but different contents, make the title of each such section
unique by adding at the end of it, in parentheses, the name of the original author or
publisher of that section if known, or else a unique number. Make the same adjustment
to the section titles in the list of Invariant Sections in the license notice of the combined
work.
In the combination, you must combine any sections Entitled “History” in the vari-
ous original documents, forming one section Entitled “History”; likewise combine any
sections Entitled “Acknowledgements”, and any sections Entitled “Dedications”. You
must delete all sections Entitled “Endorsements.”
6. COLLECTIONS OF DOCUMENTS
You may make a collection consisting of the Document and other documents released
under this License, and replace the individual copies of this License in the various
documents with a single copy that is included in the collection, provided that you
follow the rules of this License for verbatim copying of each of the documents in all
other respects.
You may extract a single document from such a collection, and distribute it individu-
ally under this License, provided you insert a copy of this License into the extracted
Appendix A: Copying 222
document, and follow this License in all other respects regarding verbatim copying of
that document.
7. AGGREGATION WITH INDEPENDENT WORKS
A compilation of the Document or its derivatives with other separate and independent
documents or works, in or on a volume of a storage or distribution medium, is called
an “aggregate” if the copyright resulting from the compilation is not used to limit the
legal rights of the compilation’s users beyond what the individual works permit. When
the Document is included in an aggregate, this License does not apply to the other
works in the aggregate which are not themselves derivative works of the Document.
If the Cover Text requirement of section 3 is applicable to these copies of the Document,
then if the Document is less than one half of the entire aggregate, the Document’s Cover
Texts may be placed on covers that bracket the Document within the aggregate, or the
electronic equivalent of covers if the Document is in electronic form. Otherwise they
must appear on printed covers that bracket the whole aggregate.
8. TRANSLATION
Translation is considered a kind of modification, so you may distribute translations
of the Document under the terms of section 4. Replacing Invariant Sections with
translations requires special permission from their copyright holders, but you may
include translations of some or all Invariant Sections in addition to the original versions
of these Invariant Sections. You may include a translation of this License, and all the
license notices in the Document, and any Warranty Disclaimers, provided that you
also include the original English version of this License and the original versions of
those notices and disclaimers. In case of a disagreement between the translation and
the original version of this License or a notice or disclaimer, the original version will
prevail.
If a section in the Document is Entitled “Acknowledgements”, “Dedications”, or “His-
tory”, the requirement (section 4) to Preserve its Title (section 1) will typically require
changing the actual title.
9. TERMINATION
You may not copy, modify, sublicense, or distribute the Document except as expressly
provided under this License. Any attempt otherwise to copy, modify, sublicense, or
distribute it is void, and will automatically terminate your rights under this License.
However, if you cease all violation of this License, then your license from a particular
copyright holder is reinstated (a) provisionally, unless and until the copyright holder
explicitly and finally terminates your license, and (b) permanently, if the copyright
holder fails to notify you of the violation by some reasonable means prior to 60 days
after the cessation.
Moreover, your license from a particular copyright holder is reinstated permanently if
the copyright holder notifies you of the violation by some reasonable means, this is the
first time you have received notice of violation of this License (for any work) from that
copyright holder, and you cure the violation prior to 30 days after your receipt of the
notice.
Termination of your rights under this section does not terminate the licenses of parties
who have received copies or rights from you under this License. If your rights have
Appendix A: Copying 223
been terminated and not permanently reinstated, receipt of a copy of some or all of the
same material does not give you any rights to use it.
10. FUTURE REVISIONS OF THIS LICENSE
The Free Software Foundation may publish new, revised versions of the GNU Free
Documentation License from time to time. Such new versions will be similar in spirit
to the present version, but may differ in detail to address new problems or concerns.
See http://www.gnu.org/copyleft/.
Each version of the License is given a distinguishing version number. If the Document
specifies that a particular numbered version of this License “or any later version”
applies to it, you have the option of following the terms and conditions either of that
specified version or of any later version that has been published (not as a draft) by
the Free Software Foundation. If the Document does not specify a version number of
this License, you may choose any version ever published (not as a draft) by the Free
Software Foundation. If the Document specifies that a proxy can decide which future
versions of this License can be used, that proxy’s public statement of acceptance of a
version permanently authorizes you to choose that version for the Document.
11. RELICENSING
“Massive Multiauthor Collaboration Site” (or “MMC Site”) means any World Wide
Web server that publishes copyrightable works and also provides prominent facilities
for anybody to edit those works. A public wiki that anybody can edit is an example of
such a server. A “Massive Multiauthor Collaboration” (or “MMC”) contained in the
site means any set of copyrightable works thus published on the MMC site.
“CC-BY-SA” means the Creative Commons Attribution-Share Alike 3.0 license pub-
lished by Creative Commons Corporation, a not-for-profit corporation with a principal
place of business in San Francisco, California, as well as future copyleft versions of that
license published by that same organization.
“Incorporate” means to publish or republish a Document, in whole or in part, as part
of another Document.
An MMC is “eligible for relicensing” if it is licensed under this License, and if all works
that were first published under this License somewhere other than this MMC, and
subsequently incorporated in whole or in part into the MMC, (1) had no cover texts
or invariant sections, and (2) were thus incorporated prior to November 1, 2008.
The operator of an MMC Site may republish an MMC contained in the site under
CC-BY-SA on the same site at any time before August 1, 2009, provided the MMC is
eligible for relicensing.
Appendix A: Copying 224
Concept Index
A D
aa confirm safety . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 data structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
accurate approxlib . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 debugging on a graphical board . . . . . . . . . . . . . . . . 38
accuratelib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 debugging options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
adjacent dragons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Debugging the reading code . . . . . . . . . . . . . . . . . . 121
advance random seed . . . . . . . . . . . . . . . . . . . . . . . . 199 decide-dragon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
all legal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 decide-string. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
amalgamation of worms into dragons . . . . . . . . . . . 51 decrease depths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
analyze eyegraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 defence shapes database . . . . . . . . . . . . . . . . . . . . . . . 77
analyze semeai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 defend . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
analyze semeai after move . . . . . . . . . . . . . . . . . . . 189 defend both . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 depth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
area . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 Depth of reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
ascii description of shapes . . . . . . . . . . . . . . . . . . . . . 77 description of shapes. . . . . . . . . . . . . . . . . . . . . . . . . . . 77
ascii interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 dfa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
ascii mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 dfa.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 dfa.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
attack shapes database . . . . . . . . . . . . . . . . . . . . . . . . 77 disconnect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
attack either . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 distance from liberty to dragon . . . . . . . . . . . . . . . . 49
autohelper actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 does attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
Autohelpers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 does defend . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
automaton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 does surround . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
dragon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
dragon escape route . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
B dragon genus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
black . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 dragon lunch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
block off . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 dragon number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
board state . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 dragon origin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
boardsize . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 dragon safety . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
break in . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 dragon size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
dragon status . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
dragon weakness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
C dragon data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
cache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 dragon status . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
cache-size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 dragon stones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
captures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 dragons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
CGoban . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 draw search area . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
clear board . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 dump stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
clear cache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
color . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
color (dragon) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 E
colored display . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38, 59 echo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
combination attack . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 echo err . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
combination defend . . . . . . . . . . . . . . . . . . . . . . . . . . 191 editing pattern database . . . . . . . . . . . . . . . . . . . . . . 102
command line options . . . . . . . . . . . . . . . . . . . . . . . . . 14 editing patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
connect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 effective size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
connection shapes database . . . . . . . . . . . . . . . . 77, 90 effective size (worm) . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
connections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 eliminate the randomness . . . . . . . . . . . . . . . . . . . . . . 95
connections database . . . . . . . . . . . . . . . . . . . . . . . . . . 90 emacs mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
corner matcher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 escape route . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
countlib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 estimate score . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
cputime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 eval eye . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
cutting stone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 experimental score . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
cutting stone, potential . . . . . . . . . . . . . . . . . . . . . . . . 50 eye shapes database . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Concept Index 226
Functions Index
A E
abortgo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 edge_distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
accuratelib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 endgame_shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
add_eyevalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 estimate_territorial_value . . . . . . . . . . . . . . . . . 45
add_false_eye . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 extended_chainlinks . . . . . . . . . . . . . . . . . . . . . . . . 175
add_stone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 eyevalue_to_string . . . . . . . . . . . . . . . . . . . . . . . . . . 75
adjacent_strings. . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
amalgamate_most_valuable_helper . . . . . . . . . . . 52
analyze_eyegraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 F
approxlib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 far . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
atari_atari . . . . . . . . . . . . . . . . . . . . . . . . . . 26, 44, 127 fastlib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
atari_atari_blunder_size . . . . . . . . . . . . . . . . . . 127 fill_liberty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
atari_atari_confirm_safety . . . . . . . . . . . . . . . . 127 find_common_libs. . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 find_connections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
find_cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50, 92
B find_defense . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
find_eye_dragons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
block_off . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 find_half_and_false_eyes . . . . . . . . . . . . . . . . . . . 74
blunder_size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 find_neighbor_dragons . . . . . . . . . . . . . . . . . . . . . . . 56
break_in . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 find_origin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
find_proper_superstring_liberties . . . . . . . . 170
C find_superstring. . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
find_superstring_liberties . . . . . . . . . . . . . . . . 170
chainlinks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 find_superstring_stones_and_liberties . . . 170
chainlinks2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 findlib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
chainlinks3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 findstones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
change_dragon_status . . . . . . . . . . . . . . . . . . . . . . . 166 followup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
clear_board . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 fuseki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
color_to_string . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
compute_escape . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 G
compute_eyes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 gameinfo_clear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
compute_eyes_pessimistic . . . . . . . . . . . . . . . 74, 125 gameinfo_load_sgfheader . . . . . . . . . . . . . . . . . . . 165
compute_influence . . . . . . . . . . . . . . . . . . . . . . . . . . 177 gameinfo_play_move . . . . . . . . . . . . . . . . . . . . . . . . . 165
compute_surrounding_moyo_sizes . . . . . . . . . . . . . 57 gameinfo_play_sgftree . . . . . . . . . . . . . . . . . . . . . . 165
confirm_safety . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 gameinfo_play_sgftree_rot . . . . . . . . . . . . . . . . . 165
count_common_libs . . . . . . . . . . . . . . . . . . . . . . . . . . 175 gameinfo_print . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
countlib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 get_kom_pos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
countstones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 get_komaster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
cut_connect_callback . . . . . . . . . . . . . . . . . . . . . . . . 92 gfprintf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
gnugo_add_stone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
D gnugo_attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
gnugo_clear_board . . . . . . . . . . . . . . . . . . . . . . . . . . 162
DEBUG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 gnugo_estimate_score . . . . . . . . . . . . . . . . . . . . . . . 163
decrease_depth_values . . . . . . . . . . . . . . . . . . . . . . 168 gnugo_examine_position . . . . . . . . . . . . . . . . . . . . . 164
defend_against . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 gnugo_find_defense . . . . . . . . . . . . . . . . . . . . . . . . . 163
disconnect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 gnugo_genmove . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
does_attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 gnugo_get_board . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
does_capture_something . . . . . . . . . . . . . . . . . . . . . 176 gnugo_get_boardsize . . . . . . . . . . . . . . . . . . . . . . . . 164
does_defend . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 gnugo_get_komi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
double_atari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 gnugo_get_move_number . . . . . . . . . . . . . . . . . . . . . . 164
dragon_eye. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 gnugo_is_legal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
draw_letter_coordinates . . . . . . . . . . . . . . . . . . . 172 gnugo_is_pass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
dump_stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 gnugo_is_suicide. . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
Functions Index 230
H N
has_neighbor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 near . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
hashnode_new_result . . . . . . . . . . . . . . . . . . . . . . . . 113 neighbor_of_string . . . . . . . . . . . . . . . . . . . . . . . . . 176
hashtable_enter_position . . . . . . . . . . . . . . . . . . 113
hashtable_search. . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
have_common_lib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 O
obvious_false_eye. . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
ocap0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
I ocap1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
increase_depth_values . . . . . . . . . . . . . . . . . . . . . . 168 ocap1+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
influence_mark_non_territory . . . . . . . . . . . . . . 177 ocap1- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
init_gnugo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161, 162 ocap2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
is_corner_vertex. . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 ocap2+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
is_edge_vertex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 ocap2- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
is_eye_space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 ocap3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
is_false_eye . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 osafe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
is_halfeye. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 OTHER_COLOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
is_hoshi_point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 ounsafe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
is_illegal_ko_capture . . . . . . . . . . . . . . . . . . . . . . 173 owl_attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
is_ko . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 owl_defend . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
is_ko_point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 owl_reasons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25, 43
is_legal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29, 173
is_marginal_eye_space . . . . . . . . . . . . . . . . . . . . . . . 74
is_pass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 P
is_proper_eye_space . . . . . . . . . . . . . . . . . . . . . . . . . 74 partition_eyespaces . . . . . . . . . . . . . . . . . . . . . . . . . 73
is_self_atari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 play_attack_defend_n . . . . . . . . . . . . . . . . . . . . . . . 167
is_suicide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 play_attack_defend2_n . . . . . . . . . . . . . . . . . . . . . . 167
play_break_through_n . . . . . . . . . . . . . . . . . . . . . . . 166
K play_connect_n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
play_move . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
komaster_trymove. . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 popgo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29, 156
propagate_eye . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
proper_superstring_chainlingks . . . . . . . . . . . 171
L purge_persistent_breakin_cache . . . . . . . . . . . 115
liberty_of_string . . . . . . . . . . . . . . . . . . . . . . . . . . 176 purge_persistent_connection_cache . . . . . . . . 115
location_to_buffer . . . . . . . . . . . . . . . . . . . . . . . . . 172 purge_persistent_owl_cache . . . . . . . . . . . . . . . . 115
location_to_string . . . . . . . . . . . . . . . . . . . . . . . . . 172 purge_persistent_reading_cache . . . . . . . . . . . 115
M R
make_domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50, 73 remove_stone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
mark_string . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 restore_board . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
max_eye_threat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 restore_depth_values . . . . . . . . . . . . . . . . . . . . . . . 168
max_eye_value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 result_to_string. . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
Functions Index 231
revise_semeai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 topological_eye . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
revise_thrashing_dragon . . . . . . . . . . . . . . . . . . . . . 26 tryko . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
trymove . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29, 155
S
safe_move . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 U
safety_to_string. . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 unconditional_life . . . . . . . . . . . . . . . . . . . . . . 50, 169
same_string . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 undo_move . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
search_persistent_reading_cache . . . . . . . . . . 115
second_order_liberty_of_string . . . . . . . . . . . 176
semeai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 V
set_depth_values. . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
set_eyevalue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 value_move_reasons() . . . . . . . . . . . . . . . . . . . . . . . . 44
shape . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
shapes_callback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 W
showboard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 whose_area . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
simple_showboard. . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 whose_moyo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
small_semeai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 whose_territory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
somewhere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 worm_reasons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
start_timer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
status_to_string. . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
stones_on_board . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 X
store_board . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 xcap0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
store_persistent_reading_cache . . . . . . . . . . . 115 xcap1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
string_connect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 xcap1+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
string_to_location . . . . . . . . . . . . . . . . . . . . . . . . . 172 xcap1- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
superstring_chainlinks . . . . . . . . . . . . . . . . . . . . . 170 xcap2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
xcap2+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
xcap2- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
T xcap3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
terri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 xnosuicide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
test_eyeshape . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 xsafe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
test_symmetry_after_move . . . . . . . . . . . . . . . . . . 166 xsuicide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
time_report . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 xunsafe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147