This is gnugo.info, produced by makeinfo version 4.11 from gnugo.texi.
INFO-DIR-SECTION GNU games
* GNU Go: (gnugo). The GNU Go program
File: gnugo.info, Node: Top, Next: Introduction, Up: (dir)
This manual documents `GNU Go', a Go program and its sources. This is
Edition 3.8 of the `GNU Go Program Documentation'
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 (*note GFDL::, version 1.3 or any later version)
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 (*note GPL::, version 3 or any later version)
* Introduction:: What is GNU Go ?
* Installation:: Installing GNU Go
* User Guide:: Using GNU Go
An introduction to the GNU Go engine
* Overview:: Overview of the GNU Go engine
* Analyzing:: Analyzing GNU Go's moves
* Move Generation:: How GNU Go generates moves
* Worms and Dragons:: Dragons and Worms
* Eyes:: Eyes and half eyes
* Patterns:: Pattern database
* Tactical Reading:: Tactical and Connection Reading
* Pattern Based Reading:: Pattern Based Reading: Owl and Combinations
* Influence:: Influence Function
* Monte Carlo Go:: Monte Carlo GNU Go
Infrastructure and Interfaces
* Libboard:: The basic go board library.
* SGF:: Handling SGF trees in memory
* DFA:: The DFA Pattern Matcher
* Utility Functions:: `utils.c' and `printutils.c'
* API:: API to the GNU Go engine
* GTP:: The Go Text Protocol
* Regression:: Regression testing
* Copying:: Software and Documentation Licenses
* Concept Index:: Concept Index
* Functions Index:: Functions Index
File: gnugo.info, Node: Introduction, Next: Installation, Prev: Top, Up: Top
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
<gnugo@gnu.org> if you are interested in helping.
* About:: About GNU Go and this Manual
* Authors:: The Authors of GNU Go
* Thanks:: Acknowledgements
* Development:: Developing GNU Go
File: gnugo.info, Node: About, Next: Copyright, Up: Introduction
1.1 About GNU Go and this Manual
================================
The challenge of Computer Go is not to *beat* the computer, but to
In Computer Chess, strong programs are capable of playing at the
highest level, even challenging such a player as Garry Kasparov. No Go
program exists that plays at the same level as the strongest human
To be sure, existing Go programs are strong enough to be interesting
as opponents, and the hope exists that some day soon a truly strong
program can be written. This is especially true in view of the
successes of Monte Carlo methods, and a general recent improvement of
Before GNU Go, Go programs have always been distributed as binaries
only. The algorithms in these proprietary programs are secret. No-one
but the programmer can examine them to admire or criticise. As a
consequence, anyone who wished to work on a Go program usually had to
start from scratch. This may be one reason that Go programs have not
reached a higher level of play.
Unlike most Go programs, GNU Go is Free Software. Its algorithms and
source code are open and documented. They are free for any one to
inspect or enhance. We hope this freedom will give GNU Go's descendents
a certain competetive advantage.
Here is GNU Go's Manual. There are doubtless inaccuracies. The
ultimate documentation is in the commented source code itself.
The first three chapters of this manual are for the general user.
Chapter 3 is the User's Guide. The rest of the book is for programmers,
or persons curious about how GNU Go works. Chapter 4 is a general
overview of the engine. Chapter 5 introduces various tools for looking
into the GNU Go engine and finding out why it makes a certain move, and
Chapters 6-7 form a general programmer's reference to the GNU Go API.
The remaining chapters are more detailed explorations of different
aspects of GNU Go's internals.
File: gnugo.info, Node: Copyright, Next: Authors, Prev: About, Up: Introduction
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
(*note GPL::, version 3 or any later version), except `gmp.c', `gmp.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 (*note GTP License::).
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.
Documentation files (including this manual) are distributed under
the GNU Free Documentation License (*note GFDL::, version 1.3 or any
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
File: gnugo.info, Node: Authors, Next: Thanks, Prev: Copyright, Up: Introduction
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 Farneba"ck, Nils Lohner,
Jerome Dumonteil, Tommy Thorn, Nicklas 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, Maans 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.
File: gnugo.info, Node: Thanks, Next: Development, Prev: Authors, Up: Introduction
We would like to thank Arthur Britto, David Doshay, Tim Hunt, Matthias
Krings, Piotr 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, Maans Ullerstam, Don Wagner and Yin Zheng for
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 Urvoy and comments by Alan Crossman. The old GNU Go
logo was adapted from Jamal Hannah'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.
File: gnugo.info, Node: Development, Prev: Thanks, Up: Introduction
You can help make GNU Go the best Go program.
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 (*note GPL::). 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
(<bump@sporadic.stanford.edu>) and Gunnar Farneba"ck
(<gunnar@lysator.liu.se>), to get more information and the papers to
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.
File: gnugo.info, Node: Installation, Next: User Guide, Prev: Introduction, Up: Top
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/'.
* GNU/Linux and Unix:: GNU Linux and Unix Installation
* Configure Options:: Configure Options
* Windows and MS-DOS:: Windows Installation
* Macintosh:: Macintosh Installation
File: gnugo.info, Node: GNU/Linux and Unix, Next: Configure Options, Up: Installation
Untar the sources, change to the directory gnugo-3.8. Now do:
Several configure options will be explained in the next section. You
do not need to set these unless you are dissatisfied with GNU Go's
performance or wish to vary the experimental options.
./configure --enable-level=9 --enable-cosmic-gnugo
will make a binary in which the default level is 9, and the experimental
"cosmic"' option is enabled. A list of all configure options can be
obtained by running `./configure --help'. Further information about the
experimental options can be found in the next section (*note Configure
After running configure and make, you have now made a binary called
`interface/gnugo'. Now (running as root) type
to install `gnugo' in `/usr/local/bin'.
There are different methods of using GNU Go. You may run it from the
command line by just typing:
but it is nicer to run it using CGoban 1 (under X Window System),
Quarry, Jago (on any platform with a Java Runtime Environment) or other
client programs offering a GUI.
You can get the most recent version of CGoban 1 from
`http://sourceforge.net/projects/cgoban1/'. The earlier version 1.12 is
available from `http://www.igoweb.org/~wms/comp/cgoban/index.html'.
The CGoban version number MUST be 1.9.1 at least or it won't work.
*Note CGoban::, for instructions on how to run GNU Go from Cgoban, or
*Note Other Clients::, for Jago or other clients.
Quarry is available at `http://home.gna.org/quarry/'.
File: gnugo.info, Node: Configure Options, Next: Windows and MS-DOS, Prev: GNU/Linux and Unix, Up: Installation
There are three options which you should consider configuring,
particularly if you are dissatisfied with GNU Go's performance.
* Default Level:: Default Level
* Other Options:: Other Options
File: gnugo.info, Node: Ram Cache, Next: Default Level, Up: Configure Options
By default, GNU Go makes a cache of about 8 Megabytes in RAM for its
internal use. The cache is used to store intermediate results during
its analysis of the position. More precisely the default cache size is
350000 entries, which translates to 8.01 MB on typical 32 bit platforms
and 10.68 MB on typical 64 bit platforms.
Increasing the cache size will often give a modest speed improvement.
If your system has lots of RAM, consider increasing the cache size. But
if the cache is too large, swapping will occur, causing hard drive
accesses and degrading performance. If your hard drive seems to be
running excessively your cache may be too large. On GNU/Linux systems,
you may detect swapping using the program 'top'. Use the 'f' command to
You may override the size of the default cache at compile time by
./configure --enable-cache-size=n
to set the cache size to `n' megabytes. For example
./configure --enable-cache-size=32
creates a cache of size 32 megabytes. If you omit this, your default
cache size will be 8-11 MB as discussed above. Setting cache size
negative also gives the default size. You must recompile and reinstall
GNU Go after reconfiguring it by running `make' and `make install'.
You may override the compile-time defaults by running `gnugo' with
the option `--cache-size n', where `n' is the size in megabytes of the
cache you want, and `--level' where n is the level desired. We will
discuss setting these parameters next in detail.
File: gnugo.info, Node: Default Level, Next: Other Options, Prev: Ram Cache, Up: Configure Options
GNU Go can play at different levels. Up to level 10 is supported. At
level 10 GNU Go is much more accurate but takes an average of about 1.6
times longer to play than at level 8.
The level can be set at run time using the `--level' option. If you
don't set this, the default level will be used. You can set the default
level with the configure option `--enable-level=n'. For example
./configure --enable-level=9
sets the default level to 9. If you omit this parameter, the compiler
sets the default level to 10. We recommend using level 10 unless you
find it too slow. If you decide you want to change the default you may
rerun configure and recompile the program.
File: gnugo.info, Node: Other Options, Prev: Default Level, Up: Configure Options
Anything new in the engine is generally tested as an experimental option
which can be turned on or off at compile time or run time. Some
"experimental" options such as the break-in code are no longer
experimental but are enabled by default.
This section can be skipped unless you are interested in the
Moreover, some configure options were removed from the stable
release. For example it is known that the owl extension code can cause
crashes, so the configure option -enable-experimental-owl-ext was
The term "default" must be clarified, since there are really two
sets of defaults at hand, runtime defaults specified in `config.h' and
compile time default values for the runtime defaults, contained in
`configure' (which is created by editing `configure.in' then running
`autoconf'. For example we find in `config.h'
/* Center oriented influence. Disabled by default. */
/* Break-in module. Enabled by default. */
This means that the experimental cosmic option, which causes GNU Go
to play a center-oriented game (and makes the engine weaker) is
disabled by default, but that the break-in module is used. These are
defaults which are used when GNU Go is run without command line
options. They can be overridden with the run time options:
gnugo --cosmic-gnugo --without-break-in
Alternatively you can configure GNU Go as follows:
./configure --enable-cosmic-gnugo --disable-experimental-break-in
then recompile GNU Go. This changes the defaults in `config.h', so
that you do not have to pass any command line options to GNU Go at run
time to get the experimental owl extension turned on and the
experimental break-in code turned off.
If you want to find out what experimental options were compiled into
your GNU Go binary you can run `gnugo --options' to find out. Here is a
list of experimental options in GNU Go.
* `experimental-break-in'. Experimental break-in code (*note Break
Ins::). You should not need to configure this because the break in
code is enabled by default in level 10, and is turned off at level
9. If you don't want the breakin code just play at level 9.
* `cosmic-gnugo'. An experimental style which plays a center
oriented game and has a good winning rate against standard GNU Go,
though it makes GNU Go weaker against other opponents.
* `large-scale'. Attempt to make large-scale captures. See:
`http://lists.gnu.org/archive/html/gnugo-devel/2003-07/msg00209.html'
for the philosophy of this option. This option makes the engine
* `metamachine'. Enables the metamachine, which allows you to run
the engine in an experimental mode whereby it forks a new `gnugo'
process which acts as an "oracle." Has no effect unless combined
with the `--metamachine' run-time option.
Other options are not experimental, and can be changed as configure
* `chinese-rules' Use Chinese (area) counting.
* `resignation-allowed' Allow GNU Go to resign games. This is on by
File: gnugo.info, Node: Windows and MS-DOS, Next: Macintosh, Prev: Configure Options, Up: Installation
2.3 Compiling GNU Go on Microsoft platforms
===========================================
2.3.1 Building with older visual studio
---------------------------------------
The distribution directories contain some .dsp and .dsw files with GNU
Go. These have been brought up to date in the sense that they should
work if you have the older VC++ with Visual Studio 6 but the
distributed .dsp and .dsw files will only be of use with older version
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.3.2 Building with Visual Studio project files
-----------------------------------------------
Before you compile the GNU Go source, you need to run CMake first, to
generate the build files you'll give to Visual Studio.
From the cmd.exe command prompt, CD into the GNU Go source directory.
To confirm you're in the right place, you should see the file
'CMakeLists.txt' in the top-level directory of the GNU Go code (as well
as others in lower subdirectories).
Direct CMake to generate the new Visual Studio build files by typing:
Compile the code by invoking the newly-created Solution file:
This will take a few moments, as CMake generates 4 debug/retail
For each of these targets, Visual Studio is generating a version of
interface\debug\gnugo.exe
interface\release\gnugo.exe
interface\minsizerel\gnugo.exe
interface\relwithdebinfo\gnugo.exe
Additionally, there is an 'Install' target available, that will copy
the the gnugo.exe into the %ProgramFiles% directory. To do this, type:
This should result in copying GNU/Go into:
"%ProgramFiles%\GNUGo\bin\gnugo.exe" --options
In addition to command line use, CMake also has a GUI version. Users
of the Visual Studio GUI might prefer to use that.
2.3.3 Building with Nmake makefiles
-----------------------------------
GNU Go will also build using NMake makefiles. Optionally, instead of
Visual Studio project/solution files, you may direct CMake to generate
NMake makefiles. To generate the makefiles:
cmake -G "NMake Makefiles" CMakeLists.txt
The default rule for the makefile is 'all'. Use the 'help' rule to
show a list of available targets.
One sysand 2009 tems, GNU GO may fail to build when using NMake
makefiles. only fails the first time run, run NMake again with the
'clean all' targets, and it will compile the second and subsequent
nmake -f Makefile clean all
Which will successfully generate a gnugo.exe.
interface\gnugo.exe --options
2.3.4 Building with MinGW Makefiles
-----------------------------------
GNU Go can be built on Windows systems using MinGW.
This development environment uses: the GCC compiler (gcc.exe, not
cl.exe), the Microsoft C runtime libraries (MSCRT, not GLibC), the GNU
Make build tool (`mingw32-make.exe', not NMake), all from the Windows
shell (`cmd.exe', not sh/bash).
For CMake to work, in addition to the base MinGW installation, the
C++ compiler (g++.exe) and GNU Make (mingw32-make.exe) need to be
installed. This was tested using GCC v3, not the experimental v4. To
debug, use GDB, as the GCC-generated symbols won't work with
NTSD/Windbg/Visual Studio.
To create the makfiles, run CMake with the MinGW generator option:
cmake -G "MinGW Makefiles" CMakeLists.txt
To build GNU Go, from a cmd.exe shell, run GNU Make (against the
newly-created 'Makefile' and it's default 'all' target):
..\interface\gnugo.exe --options
2.3.5 Building with MSYS makefiles (MinGW)
------------------------------------------
GNU Go can be built on Windows systems using MSYS.
This development environment uses: the GCC compiler (gcc.exe, not
cl.exe), the Microsoft C runtime libraries (MSCRT, not GLibC), the GNU
Make build tool (make, not NMake), all from the GNU Bash (sh.exe, not
To create the makfiles, run CMake with the MSYS generator option:
cmake -G "MSYS Makefiles" CMakeLists.txt
Start MSYS's Bash shell, either clicking on a shortcut on from the
To build GNU Go, from a Bash shell, run GNU Make (against the
newly-created 'Makefile' and it's default 'all' target):
../interface/gnugo.exe --options
To debug, use GDB, as the GCC-generated symbols won't work with
NTSD/Windbg/Visual Studio.
With Cygwin, you should be able to
tar zxvf gnugo-3.8.tar.gz
env CC='gcc -mno-cygwin' ./configure
2.3.7 Testing on Windows:
-------------------------
`regression/regress.cmd' is a simplified cmd.exe-centric port of the
main gnugo Unix shell script regress.sh. It can be used to help verify
that the generated binary might be operational. Read the script's
comment header for more information. For access to the full GNU Go
tests, use Unix, not Windows.
regress.cmd ..\interface\gnugo.exe
File: gnugo.info, Node: Macintosh, Prev: Windows and MS-DOS, Up: Installation
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
File: gnugo.info, Node: User Guide, Next: Overview, Prev: Installation, Up: Top
* Documentation:: Getting Documentation
* CGoban:: Running GNU Go with CGoban
* Other Clients:: Other Clients
* Ascii:: The Ascii Interface
* Emacs:: GNU Go mode in Emacs
* GMP and GTP:: The Go Modem Protocol and Go Text Protocol
* Tournaments:: Computer Tournaments
* SGF Support:: The Smart Game Format
* Invoking GNU Go:: Command line options
File: gnugo.info, Node: Documentation, Next: CGoban, Up: User Guide
3.1 Getting Documentation
=========================
You can obtain a printed copy of the manual by running `make gnugo.pdf'
in the `doc/'directory, then printing the resulting file. The manual
contains a great deal of information about the algorithms of GNU Go.
On platforms supporting info documentation, you can usually install
the manual by executing `make install' (running as root) from the
`doc/' directory. This will create a file called `gnugo.info' (and a
few others) and copy them into a system directory such as
`/usr/local/share/info'. You may then add them to your info directory
tree with the command `install-info --info-file=[path to gnugo.info]
--info-dir=[path to dir]'. The info documentation can be read
conveniently from within Emacs by executing the command `Control-h i'.
Documentation in `doc/' consists of a man page `gnugo.6', the info
files `gnugo.info', `gnugo.info-1', ... and the Texinfo files from
which the info files are built. The Texinfo documentation contains this
User's Guide and extensive information about the algorithms of GNU Go,
If you want a typeset copy of the Texinfo documentation, you can
`make gnugo.dvi', `make gnugo.ps', or `make gnugo.pdf' in the `doc/'
directory. (`make gnugo.pdf' only works after you have converted all
.eps-files in the doc/ directory to .pdf files, e.g. with the utility
You can make an HTML version with the command `makeinfo --html
gnugo.texi'. If you have `texi2html', better HTML documentation may be
obtained by `make gnugo.html' in the `doc/' directory.
User documentation can be obtained by running `gnugo --help' or `man
gnugo' from any terminal, or from the Texinfo documentation.
Documentation for developers is in the Texinfo documentation, and in
comments throughout the source. Contact us at <gnugo@gnu.org> if you are
interested in helping to develop this program.
File: gnugo.info, Node: CGoban, Next: Other Clients, Prev: Documentation, Up: User Guide
3.2 Running GNU Go via CGoban
=============================
There are two different programs called CGoban, both written by William
Shubert. In this documentation, CGoban means CGoban 1.x, the older
program. You should get a copy with version number 1.12 or higher.
CGoban is an extremely nice way to run GNU Go. CGoban provides a
beautiful graphic user interface under X Window System.
Start CGoban. When the CGoban Control panel comes up, select "Go
Modem". You will get the Go Modem Protocol Setup. Choose one (or both)
of the players to be "Program," and fill out the box with the path to
`gnugo'. After clicking OK, you get the Game Setup window. Choose
"Rules Set" to be Japanese (otherwise handicaps won't work). Set the
board size and handicap if you want.
If you want to play with a komi, you should bear in mind that the
GMP does not have any provision for communicating the komi. Because of
this misfeature, unless you set the 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
File: gnugo.info, Node: Other Clients, Next: Ascii, Prev: CGoban, Up: User Guide
In addition to CGoban (*note CGoban::) there are a number of other good
clients that are capable of running GNU Go. Here are the ones that we
are aware of that are Free Software. This list is part of a larger list
of free Go programs that is maintained at
`http://www.gnu.org/software/gnugo/free_go_software.html'.
* Quarry (`http://home.gna.org/quarry/') is a GPL'd client that
supports GTP. Works under GNU/Linux and requires GTK+ 2.x and
librsvg 2.5. Supports GNU Go as well as other engines. Can play
not only Go, but also a few other board games.
* qGo (`http://sourceforge.net/projects/qgo/') is a full featured
Client for playing on the servers, SGF viewing/editing, and GNU Go
client written in C++ for GNU/Linux, Windows and Mac OS X. Can
play One Color Go. Licensed GPL and QPL.
* ccGo (`http://ccdw.org/~cjj/prog/ccgo/') is a GPL'd client written
in C++ capable of playing with GNU Go, or on IGS.
* RubyGo (`http://rubygo.rubyforge.org/') is a GPL'd client by J.-F.
Menon for IGS written in the scripting language Ruby. RubyGo is
capable of playing with GNU Go using the GTP.
* Dingoui (`http://dingoui.sourceforge.net/') is a free GMP client
written in GTK+ which can run GNU Go.
* Jago (`http://www.rene-grothmann.de/jago/') is a GPL'd Java client
which works for both Microsoft Windows and X Window System.
* Sente Software's FreeGoban
(`http://www.sente.ch/software/goban/freegoban.html') is a
well-liked user interface for GNU Go (and potentially other
programs) distributed under the GPL.
(`http://www1.u-netsurf.ne.jp/~future/HTML/macgnugo.html') is a
front end for GNU Go 3.2 with both English and Japanese versions.
* Quickiego (`http://www.geocities.com/secretmojo/QuickieGo/') is a
Mac interface to GNU Go 2.6.
* Gogui (`http://sourceforge.net/projects/gogui/') from Markus
Enzenberger is a Java workbench that allows you to play with a gtp
(`http://www.lysator.liu.se/~gunnar/gtp') engine such as GNU Go.
Licence is GPL. Gogui does not support gmp or play on servers but
is potentially very useful for programmers working on GNU Go or
File: gnugo.info, Node: Ascii, Next: Emacs, Prev: Other Clients, Up: User Guide
Even if you do not have any client program, you can play with GNU Go
using its default Ascii interface. Simply type `gnugo' at the command
line, and GNU Go will draw a board. Typing `help' will give a list of
options. At the end of the game, pass twice, and GNU Go will prompt you
through the counting. You and GNU Go must agree on the dead groups--you
can toggle the status of groups to be removed, and when you are done,
GNU Go will report the score.
You can save the game at any point using the `save FILENAME'
command. You can reload the game from the resulting SGF file with the
command `gnugo -l FILENAME --mode ascii'. Reloading games is not
supported when playing with CGoban. However you can use CGoban to save
a file, then reload it in ascii mode.
You may play games with a time limit against GNU Go in ascii mode.
For this, the Canadian time control system is used. (See
`http://en.wikipedia.org/wiki/Byoyomi' and
`http://senseis.xmp.net/?CanadianByoyomi'.) That is, you have a main
time to be followed by byo-yomi periods. After the main time is
exhausted you have a certain number of moves to be made in a certain
number of seconds. (*note Invoking GNU Go::)
File: gnugo.info, Node: Emacs, Next: GMP and GTP, Prev: Ascii, Up: User Guide
You can run GNU Go from Emacs. This has the advantage that you place
the stones using the cursor arrow keys or with the mouse, and you can
have a nice graphical display of the board within emacs.
You will need the file `interface/gnugo.el'. There is a version of
this distributed with GNU Go but it only works with Emacs 21. Most
Emacsen are Emacs 22 however. Therefore you should get the latest
version of gnugo.el by Thien-Thi Nguyen, which you can find at
`http://www.gnuvola.org/software/j/gnugo/' or
`http://www.emacswiki.org/emacs/gnugo.el'.
You will also need some xpm files for the graphical display. You can
either use those distributed by Thien-Thi Nguyen (at the first URL
above) or those distributed with GNU Go, either the file
`interface/gnugo-xpms.el' or (for high resolution displays)
`interface/gnugo-big-xpms.el'.
Load the file `interface/gnugo.el' and `interface/gnugo-xpms.el'.
You may do this using the Emacs `M-x load-file' command.
When you start a game with `M-x gnugo', you will first see an ascii
board. However typing `i' toggles a graphical board display which is
very nice. This is a pleasant way to play GNU Go. You may get help by
File: gnugo.info, Node: GMP and GTP, Next: Tournaments, Prev: Emacs, Up: User Guide
3.6 The Go Modem Protocol and Go Text Protocol
==============================================
The Go Modem Protocol (GMP) was developed by Bruce Wilcox with input
from David Fotland, Anders Kierulf and others, according to the history
in `http://www.britgo.org/tech/gmp.html'.
Any Go program _should_ support this protocol since it is a
standard. Since CGoban supports this protocol, the user interface for
any Go program can be done entirely through 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 (*note
GTP::) 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.
File: gnugo.info, Node: Tournaments, Next: SGF Support, Prev: GMP and GTP, Up: User Guide
3.7 Computer Go Tournaments
===========================
Computer Tournaments currently use the Go Modem Protocol. The current
method followed in such tournaments is to connect the serial ports of
the two computers by a "null modem" cable. If you are running
GNU/Linux it is convenient to use CGoban. If your program is black,
set it up in the Go Modem Protocol Setup window as usual. For White,
select "Device" and set the device to `/dev/cua0' if your serial port
is COM1 and `/dev/cua1' if the port is COM2.
File: gnugo.info, Node: SGF Support, Next: Invoking GNU Go, Prev: Tournaments, Up: User Guide
The Smart Game Format (SGF), is the standard format for storing Go
games. GNU Go supports both reading and writing SGF files. The SGF
specification (FF[4]) is at: `http://www.red-bean.com/sgf/'
File: gnugo.info, Node: Invoking GNU Go, Prev: SGF Support, Up: User Guide
3.9 Invoking GNU Go: Command line options
=========================================
Print a help message describing the options. This will also
tell you the defaults of various parameters, most importantly
the level and cache size. The default values of these
parameters can be set before compiling by `configure'. If
you forget the defaults you can find out using `--help'.
GNU Go can play with different strengths and speeds. Level 10
is the default. Decreasing the level will make GNU Go faster
but less accurate in its reading.
Don't print copyright and other messages. Messages
specifically requested by other command line options, such as
`--trace', are not supressed.
* `-l', `--infile FILENAME'
Load the named SGF file. GNU Go will generate a move for the
player who is about to move. If you want to override this and
generate a move for the other player you may add the option
`--color <COLOR>' where <COLOR> is `black' or `white'.
Stop loading just before the indicated move is played. MOVE
can be either the move number or location.
* `-o', `--outfile FILENAME'
* `-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.
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.
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.
GNU Go will not resign games.
GNU Go will resign lost games. This is the default.
3.9.2 Monte Carlo Options
-------------------------
GNU Go can play Monte Carlo Go on a 9x9 board. (Not available for
larger boards.) It makes quite a strong engine. Here are the command
Use Monte Carlo move generation (9x9 or smaller).
* `--mc-games-per-level <number>'
Number of Monte Carlo simulations per level. Default 8000.
Thus at level 10, GNU Go simulates 80,000 games in order to
list names of builtin Monte Carlo patterns
Choose a built in Monte Carlo pattern database. The argument
can be `mc_mogo_classic', `mc_montegnu_classic' or
* `--mc-load-patterns <filename>'
read Monte Carlo patterns from file
3.9.3 Other general options
---------------------------
* `-M', `--cache-size MEGS'
Memory in megabytes used for caching of read results. The
default size is 8 unless you configure gnugo with the command
`configure --enable-cache-size=SIZE' before compiling to make
SIZE the default (*note Installation::). GNU Go stores
results of its reading calculations in a hash table (*note
Hashing::). If the hash table is filled, it is emptied and
the reading continues, but some reading may have to be
repeated that was done earlier, so a larger cache size will
make GNU Go run faster, provided the cache is not so large
that swapping occurs. Swapping may be detected on GNU/Linux
machines using the program `top'. However, if you have ample
memory or if performance seems to be a problem you may want
to increase the size of the cache using this option.
Use Chinese rules. This means that the Chinese or Area
Counting is followed. It may affect the score of the game by
one point in even games, more if there is a handicap (since
in Chinese Counting the handicap stones count for Black) or
if either player passes during the game.
Use Japanese Rules. This is the default unless you specify
`--enable-chinese-rules' as a configure option.
These options cause GNU Go to play out moves that are usually
left unplayed after the end of the game. Such moves lose
points under Japanese rules but not Chinese rules. With
`--play-out-aftermath', GNU Go may play inside its territory
in order to reach a position where it considers every group
demonstrably alive or dead. The option `--capture-all-dead'
causes GNU Go to play inside its own territory to remove dead
Do not allow suicide moves (playing a stone so that it ends
up without liberties and is therefore immediately removed).
Allow suicide moves, except single-stone suicide. The latter
would not change the board at all and pass should be used
Allow suicide moves, including single-stone suicide. This is
only interesting in exceptional cases. Normally the
`--allow-suicide' option should be used instead.
Do not allow an immediate recapture of a ko so that the
previous position is recreated. Repetition of earlier
positions than that are allowed. This is default.
Allow all kinds of board repetition.
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
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.
Print which experimental configure options were compiled into
the program (*note Other Options::).
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.
3.9.4 Other options affecting strength and speed
------------------------------------------------
The higher the level, the deeper GNU Go reads. Level 10 is
the default. If GNU Go plays too slowly on your machine, you
This single parameter `--level' is the best way of choosing whether to
play stronger or faster. It controls a host of other parameters which
may themselves be set individually at the command line. The default
values of these parameters may be found by running `gnugo --help'.
Unless you are working on the program you probably don't need the
remaining options in this category. Instead, just adjust the single
variable `--level'. The following options are of use to developers
tuning the program for performance and accuracy. For completeness, here
Deep reading cutoff. When reading beyond this depth (default
16) GNU Go assumes that any string which can obtain 3
liberties is alive. Thus GNU Go can read ladders to an
arbitrary depth, but will miss other types of capturing moves.
* `-B', `--backfill-depth DEPTH'
Deep reading cutoff. Beyond this depth (default 12) GNU Go
will no longer try backfilling moves in its reading.
* `--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
* `-F', `--fourlib-depth DEPTH'
Deep reading cutoff. When reading beyond this depth (default
7) GNU Go assumes that any string which can obtain 4
* `-K', `--ko-depth DEPTH'
Deep reading cutoff. Beyond this depth (default 8) GNU Go no
longer tries very hard to analyze kos.
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.
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
A superstring (*note Superstrings::) is an amalgamation 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
The preceeding options are documented with the reading code (*note
* `--owl-branch' Below this depth Owl only considers one move.
* `--owl-reading' Below this depth Owl assumes the dragon has
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.
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.
Below this limit some owl reading is truncated.
Choose your color ('black' or 'white').
Choose the number of handicap stones (0-9)
For more information about the following clock options see *Note
Number of seconds per (Canadian) byo-yomi period
Number of stones per (Canadian) byo-yomi period
3.9.6 Development options
-------------------------
Replay all moves in a game for either or both colors. If used
with the `-o' option the game record is annotated with move
values. This option requires `-l FILENAME'. The color can be:
* white: replay white moves only
* black: replay black moves only
When the move found by genmove differs from the move in the
sgf file the values of both moves are reported thus:
Move 13 (white): GNU Go plays C6 (20.60) - Game move F4 (20.60)
This option is useful if one wants to confirm that a change
such as a speedup or other optimization has not affected the
behavior of the engine. Note that when several moves have the
same top value (or nearly equal) the move generated is not
deterministic (though it can be made deterministic by
starting with the same random seed). Thus a few deviations
from the move in the sgf file are to be expected. Only if the
two reported values differ should we conclude that the engine
plays differently from the engine which generated the sgf
file. *Note Regression::.
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. (*note Colored Display::)
Print timing information to stderr.
* `-E', `--printeyes': colored display of eye spaces
Use rxvt, xterm or Linux Console. (*note Colored Display::)
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 hexadecimal:
DEBUG_MOVE_REASONS 0x0800
DEBUG_OWL_PERFORMANCE 0x1000
DEBUG_READING_PERFORMANCE 0x8000
DEBUG_ATARI_ATARI 0x040000
DEBUG_READING_CACHE 0x080000
DEBUG_OWL_PERSISTENT_CACHE 0X200000
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'.
Print the list of debug flags
Print more information about worm data.
moyo debugging, show moyo board. The LEVEL is fully
documented elsewhere (*note Influential Display::).
* `-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.
Print statistics (for debugging purposes).
Print debugging information. Use twice for more detail.
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 (*note Tactical Reading:: 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 (*note The Owl Code::) 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
* `--decide-connection LOCATION1/LOCATION2'
Decide whether dragons at LOCATION1 and LOCATION2 can be
connected. Useful 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
* `--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.
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. (*note Eye Local Game Values::.)
* `--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
Calls the function `atari_atari' to decide whether there
exist combinations on the board.
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 "estimate", "finish", or "aftermath".
"finish" and "aftermath" are appropriate when the game is
complete, or nearly so, and both try to supply an accurate
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 written as a comment in the output file. For the
"finish" and "aftermath" scoring algorithms, the selfplayed
moves completing the game are also stored.
Finish the game by selfplaying until two passes,
then determine the status of all stones and compute
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, then uses area (Chinese) scoring.
The option `--capture-all-dead' requires the aftermath code
to finish capturing all dead stones.
3.9.7 Experimental options
--------------------------
Most of these are available as configure options and are described in
Print which experimental configure options were compiled into
Use or do not use the experimental break-in code. This option
has no effect at level 9 or below. The break in code is
enabled by default at level 10, and the only difference
between levels 9 and level 10 is that the break in code is
Use center oriented influence.
Turn off the fuseki database.
Turn off fuseki moves entirely
Turn off the joseki database.
Stop mirroring when N stones are on the board.
File: gnugo.info, Node: Overview, Next: Analyzing, Prev: User Guide, Up: Top
This chapter is an overview of the GNU Go internals. Further
documentation of how any one module or routine works may be found in
later chapters or comments in the source files.
GNU Go starts by trying to understand the current board position as
good as possible. Using the information found in this first phase, and
using additional move generators, a list of candidate moves is
generated. Finally, each of the candidate moves is valued according to
its territorial value (including captures or life-and-death effects),
and possible strategical effects (such as strengthening a weak group).
Note that while GNU Go does, of course, do a lot of reading to
analyze possible captures, life and death of groups etc., it does not
(yet) have a fullboard lookahead.
* Examining the Position:: Gathering Information
* Move Generators:: Selecting Candidate Moves
* Move Valuation:: Selecting the best Move
* Detailed Sequence of Events:: Outline of `genmove()'.
* Roadmap:: Description of the different files.
* Coding Styles:: Coding conventions.
* Navigating the Source:: Navigating the Source.
File: gnugo.info, Node: Examining the Position, Next: Move Generators, Up: Overview
4.1 Gathering Information
=========================
This is by far the most important phase in the move generation.
Misunderstanding life-and-death situations can cause gross mistakes.
Wrong territory estimates will lead to inaccurate move valuations. Bad
judgement of weaknesses of groups make strategic mistakes likely.
This information gathering is done by the function
`examine_position()'. It first calls `make_worms()'.
Its first steps are very simple: it identifies sets of directly
connected stones, called "worms", and notes their sizes and their
Soon after comes the most important step of the worm analysis: the
tactical reading code (*note Tactical Reading::) is called for every
worm. It tries to read out which worms can be captured directly, giving
up as soon as a worm can reach 5 liberties. If a worm can be captured,
the engine of course looks for moves defending against this capture.
Also, a lot of effort is made to find virtually all moves that achieve
the capture or defense of a worm.
After knowing which worms are tactically stable, we can make a first
picture of the balance of power across the board: the *note Influence::
code is called for the first time.
This is to aid the next step, the analysis of dragons. By a "dragon"
we mean a group of stones that cannot be disconnected.
Naturally the first step in the responsible function `make_dragons()'
is to identify these dragons, i.e. determine which worms cannot be
disconnected from each other. This is partly done by patterns, but in
most cases the specialized readconnect code is called. This module does
a minimax search to determine whether two given worms can be connected
with, resp. disconnected from each other.
Then we compute various measures to determine how strong or weak any
* A crude estimate of the number of eyes is made.
* The results of the influence computations is used to see which
dragons are adjacent to own territory or a moyo.
* A guess is made for the potential to escape if the dragon got
For those dragons that are considered weak, a life and death analysis
is made (*note The Owl Code::). If two dragons next to each other are
found that are both not alive, we try to resolve this situation with
For a more detailed reference of the worm and dragon analysis (and
explanations of the data structures used to store the information), see
*Note Worms and Dragons::.
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.
File: gnugo.info, Node: Move Generators, Next: Move Valuation, Prev: Examining the Position, Up: Overview
Once we have found out all about the position it is time to generate
the best move. Moves are proposed by a number of different modules
called "move generators". The move generators themselves do not set the
values of the moves, but enumerate justifications for them, called
"move reasons". The valuation of the moves comes last, after all moves
and their reasons have been generated.
For a list and explanation of move reasons used in GNU Go, and how
they are evaluated, see *Note Move Generation::.
There are a couple of move generators that only extract data found in
the previous phase, examining the position:
Moves that have been found to capture or defend a worm are
The status of every dragon, as it has been determined by the
owl code (*note The Owl Code::) in the previous phase, is
reviewed. If the status is critical, the killing or defending
move gets a corresponding move reason.
* `semeai_move_reasons()'
Similarly as `owl_reasons', this function proposes moves
* `break_in_move_reasons()'
This suggests moves that have been found to break into
opponent's territory by the break-in module.
The following move generators do additional work:
Generate a move in the early fuseki, either in an empty
corner of from the fuseki database.
This is probably the most important move generator. It finds
patterns from `patterns/patterns.db',
`patterns/patterns2.db', `patterns/fuseki.db', and the joseki
files in the current position. Each pattern is matched in
each of the 8 possible orientations obtainable by rotation and
reflection. If the pattern matches, a so called "constraint"
may be tested which makes use of reading to determine if the
pattern should be used in the current situation. Such
constraints can make demands on number of liberties of
strings, life and death status, and reading out ladders, etc.
The patterns may call helper functions, which may be hand
coded (in `patterns/helpers.c') or autogenerated.
The patterns can be of a number of different classes with
different goals. There are e.g. patterns which try to attack
or defend groups, patterns which try to connect or cut
groups, and patterns which simply try to make good shape. (In
addition to the large pattern database called by `shapes()',
pattern matching is used by other modules for different tasks
throughout the program. *Note Patterns::, for a complete
documentation of patterns.)
See if there are any combination threats or atari sequences
and either propose them or defend against them.
* `revise_thrashing_dragon()'
This module does not directly propose move: If we are clearly
ahead, and the last move played by the opponent is part of a
dead dragon, we want to attack that dragon again to be on the
safe side. This is done be setting the status of this
"thrashing dragon" to unkown and repeating the shape move
generation and move valution.
If no move is found with a value greater than 6.0, this
module matches a set of extra patterns which are designed for
the endgame. The endgame patterns can be found in
If no move is found, this module changes the status of
opponent groups involved in a semeai from `DEAD' to
`UNKNOWN'. After this, genmove runs `shapes' and
`endgame_shapes' again to see if a new move turns up.
Fill a common liberty. This is only used at the end of the
game. If necessary a backfilling or backcapturing move is
File: gnugo.info, Node: Move Valuation, Next: Detailed Sequence of Events, Prev: Move Generators, Up: Overview
After the move generation modules have run, each proposed candidate
move goes through a detailed valuation by the function
`review_move_reasons'. This invokes some analysis to try to turn up
other move reasons that may have been missed.
The most important value of a move is its territorial effect. *note
Influence and Territory:: explains in detail how this is determined.
This value is modified for all move reasons that cannot be expressed
directly in terms of territory, such as combination attacks (where it
is not clear which of several strings will 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 *note Valuation::.
File: gnugo.info, Node: Detailed Sequence of Events, Next: Roadmap, Prev: Move Valuation, Up: Overview
4.4 Detailed Sequence of Events
===============================
First comes the sequence of events when `examine_position()' is run
from `genmove()'. This is for reference only.
`purge_persistent_caches()'
`compute_effective_sizes()'
`compute_unconditional_status()'
`find_worm_attacks_and_defenses()':
for each attackable worm:
`change_attack()' to add the attack point
`find_attack_patterns()' to find a few more attacks
for each defensible worm:
`change_defense()' to add the defense point
`find_defense_patterns()' to find a few more defense moves
find additional attacks and defenses by testing all
find higher order liberties (for each worm)
find cutting stones (for each worm)
improve attacks and defenses: if capturing a string defends
another friendly string, or kills an unfriendly one, we
add points of defense or attack. Make repairs if adjacent
strings can both be attacked but not defended.
identify inessential worms (such as nakade stones)
`compute_worm_influence()':
`find_influence_patterns()'
`make_domains()' (determine eyeshapes)
`find_lunches()' (adjacent strings that can be captured)
`find_half_and_false_eyes()'
`eye_computations()': Compute the value of each eye space.
Store its attack and defense point.
`analyze_false_eye_territory()'
for each dragon `compute_dragon_genus()'
for each dragon `compute_escape()' and set escape route data
`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()'
for every semeai, run `owl_analyze_semeai()'
`find_moves_to_make_seki()'
`identify_thrashing_dragons()'
`compute_dragon_influence()':
`break_territories()' (*note Break Ins::)
`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:
`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
`shapes()': match patterns around the board (*note Patterns Overview::)
`combinations()': look for moves with a double meaning and other tricks
if ahead and there is a thrashing dragon, consider it
alive and reconsider the position
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()'
File: gnugo.info, Node: Roadmap, Next: Coding Styles, Prev: Detailed Sequence of Events, Up: Overview
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 this document we will describe some of the individual files
comprising the engine code in `engine/' and `patterns/'. In `interface/'
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.
This contains `main()'. The `gnugo' target is thus built in
the `interface/' directory.
In `engine/' there are the following files:
Contains algorithms which may be called at the end of the
game to generate moves that will generate moves to settle the
position, if necessary playing out a position to determine
exactly the status of every group on the board, which GNU Go
can get wrong, particularly if there is a seki. This module is
the basis for the most accurate scoring algorithm available
This file contains code for the maintenance of the board.
For example it contains the important function `trymove()'
which tries a move on the board, and `popgo()' which removes
it by popping the move stack. At the same time vital
information such as the number of liberties for each string
and their location is updated incrementally.
Code to detect moves which can break into supposed territory
and moves to prevent this.
* `cache.c' and `cache.h'
As a means of speeding up reading, computed results are
cached so that they can be quickly reused if the same
position is encountered through e.g. another move ordering.
This is implemented using a hash table.
* `clock.c' and `clock.h'
Clock code, including code allowing GNU Go to automatically
adjust its level in order to avoid losing on time in
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
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
Code to find certain types of endgame moves.
Code to force filling of dame (backfilling if necessary) at
Generates fuseki (opening) moves from a database. Also
generates moves in empty corners.
This file contains `genmove()' and its supporting routines,
particularly `examine_position()'.
This contains the principal global variables used by GNU Go.
This file contains declarations forming the public interface
Hashing code implementing Zobrist hashing. (*note Hashing::)
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. (*note Influence::)
Header file for the engine. The name "liberty" connotes
freedom (*note Copying::).
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'.
* `move_reasons.c' and `move_reasons.h'
Code for keeping track of move reasons.
Supporting code for lists of moves.
This file contains the code to recognize eye shapes,
documented in *Note Eyes::.
Code to fork off a second GNU Go process which can be used to
simulate reading with top level information (e.g. dragon
This file does life and death reading. Move generation is
pattern based and the code in `optics.c' is used to evaluate
the eyespaces for vital moves and independent life. A dragon
can also live by successfully escaping. Semeai reading along
the same principles is also implemented in this file.
Persistent cache which allows reuse of read results at a
later move or with additional stones outside an active area,
which are those intersections thought to affect the read
* `readconnect.c' and `readconnect.h'
This file contains code to determine whether two strings can
be connected or disconnected.
This file contains code to determine whether any given string
can be attacked or defended. *Note Tactical Reading::, for
This file contains `semeai()', the module which detects
dragons in semeai. To determine the semeai results the semeai
reading in `owl.c' is used.
Code to generate sgf traces for various types of reading.
This file contains `shapes()', the module called by
`genmove()' which tries to find moves which match a pattern
This file contains `showboard()', which draws an ASCII
representation of the board, depicting dragons (stones with
same letter) and status (color). This was the primary
interface in GNU Go 1.2, but is now a debugging aid.
Code to determine whether a dragon is surrounded and to find
moves to surround with or break out with.
An assortment of utilities, described in greater detail below.
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.
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
4.5.2 Files in `patterns/'
--------------------------
The directory `patterns/' contains files related to pattern matching.
Currently there are several types of patterns. A partial list:
* move generation patterns in `patterns.db' and `patterns2.db'
* move generation patterns in files `hoshi.db' etc. which are
automatically build from the files `hoshi.sgf' etc. These comprise
our small Joseki library.
* patterns in `owl_attackpats.db', `owl_defendpats.db' and
`owl_vital_apats.db'. These generate moves for the owl code (*note
* Connection patterns in `conn.db' (*note Connections Database::)
* Influence patterns in `influence.db' and `barriers.db' (*note
* eye patterns in `eyes.db' (*note Eyes::).
The following list contains, in addition to distributed source files
some intermediate automatically generated files such as `patterns.c'.
These are C source files produced by "compiling" various pattern
databases, or in some cases (such as `hoshi.db') themselves
automatically generated pattern databases produced by "compiling"
joseki files in Smart Game Format.
Database of connection patterns.
Automatically generated file, containing connection patterns
in form of struct arrays, compiled by `mkpat' from `conn.db'.
Automatically generated file, containing eyeshape patterns in
form of struct arrays, compiled by `mkpat' from `eyes.db'.
Header file for `eyes.c'.
Database of eyeshape patterns. *Note Eyes::, for details.
These are helper functions to assist in evaluating moves by
Smart Game Format file containing 4-4 point openings
Automatically generated database of 4-4 point opening
patterns, make by compiling `hoshi.sgf'
Joseki compiler, which takes a joseki file in Smart Game
Format, and produces a pattern database.
Smart Game Format file containing 3-4 point openings
Automatically generated database of 3-4 point opening
patterns, make by compiling `komoku.sgf'
Pattern compiler for the eyeshape databases. This program
takes `eyes.db' as input and produces `eyes.c' as output.
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'.
Smart Game Format file containing 5-3 point openings
Pattern database compiled from mokuhadzushi.sgf
Smart Game Format file containing 3-3 point openings
Pattern database compiled from `sansan.sgf'
Smart Game Format file containing 5-4 point openings
Pattern database compiled from takamoku.sgf.
Pattern data, compiled from patterns.db by mkpat.
Header file relating to the pattern databases.
* `patterns.db' and `patterns2.db'
These contain pattern databases in human readable form.
File: gnugo.info, Node: Coding Styles, Next: Navigating the Source, Prev: Roadmap, Up: Overview
4.6 Coding styles and conventions
=================================
Please follow the coding conventions at:
`http://www.gnu.org/prep/standards_toc.html'
Please preface every function with a brief description of its usage.
Please help to keep this Texinfo documentation up-to-date.
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:
Takes two parameters, and displays a formatted board
Trace messages are automatically indented to reflect the
current stack depth, so it is clear during read-ahead when it
puts a move down or takes one back.
As a workaround, `%o' at the beginning of the: format string
suppresses the indentation.
Normally `gprintf()' is wrapped in one of the following:
Print the message if the 'verbose' variable > 0. (verbose is set
by `-t' on the command line)
`DEBUG(flags, fmt, ...)':
While `TRACE' is intended to afford an overview of what GNU Go is
considering, `DEBUG' allows occasional in depth study of a module,
usually needed when something goes wrong. `flags' is one of the
`DEBUG_*' symbols in `engine/gnugo.h'. The `DEBUG' macro tests to
see if that bit is set in the `debug' variable, and prints the
message if it is. The debug variable is set using the `-d'
The variable `verbose' controls the tracing. It can equal 0 (no
trace), 1, 2, 3 or 4 for increasing levels of tracing. You can set the
trace level at the command line by `-t' for `verbose=1', `-t -t' for
`verbose=2', etc. But in practice if you want more verbose tracing than
level 1 it is better to use GDB to reach the point where you want the
tracing; you will often find that the variable `verbose' has been
temporarily set to zero and you can use the GDB command `set var
verbose=1' to turn the tracing back on.
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
`ASSERT()' is a wrapper around the standard C `assert()' function.
In addition to the test, it takes an extra pair of parameters which are
the co-ordinates of a "relevant" board position. If an assertion fails,
the board position is included in the trace output, and `showboard()'
and `popgo()' are called to unwind and display the stack.
We have adopted the convention of putting the word FIXME in comments to
File: gnugo.info, Node: Navigating the Source, Prev: Coding Styles, Up: Overview
4.7 Navigating the Source
=========================
If you are using Emacs, you may find it fast and convenient to use
Emacs' built-in facility for navigating the source. Switch to the root
directory `gnugo-3.6/' and execute the command:
find . -print|grep "\.[ch]$" | xargs etags
This will build a file called `gnugo-3.6/TAGS'. Now to find any GNU
Go function, type `M-.' and enter the command which you wish to find,
or just `RET' if the cursor is at the name of the function sought.
The first time you do this you will be prompted for the location of
the TAGS table. Enter the path to `gnugo-3.6/TAGS', and henceforth you
will be able to find any function with a minimum of keystrokes.
File: gnugo.info, Node: Analyzing, Next: Move Generation, Prev: Overview, Up: Top
5 Analyzing GNU Go's moves
**************************
In this chapter we will discuss methods of finding out how GNU Go
understands a given position. These methods will be of interest to
anyone working on the program, or simply curious about its workings.
In practice, most tuning of GNU Go is done in conjunction with
maintaining the `regression/' directory (*note Regression::).
We assume that you have a game GNU Go played saved as an sgf file,
and you want to know why it made a certain move.
* Traces:: Analyzing traces in GNU Go 3.6
* Output File:: The Output File
* Decide string:: Checking the reading code
* Decide dragon:: Checking the owl code
* GTP and GDB techniques:: GTP and GDB techniques
* view.pike:: Debugging on a Graphic Board
* Scoring:: Finding out the winner of the game
* Colored Display:: Colored Display
File: gnugo.info, Node: Traces, Next: Output File, Up: Analyzing
A quick way to find out roughly the reason for a move is to run
gnugo -l FILENAME -t -L MOVE NUMBER
(You may also want to add `--quiet' to suppress the copyright
message.) In GNU Go 3.6, the moves together with their reasons are
listed, followed by a numerical analysis of the values given to each
If you are tuning (*note Tuning::) you may want to add the `-a'
option. This causes GNU Go to report all patterns matched, even ones
that cannot affect the outcome of the move. The reasons for doing this
is that you may want to modify a pattern already matched instead of
If you use the `-w' option, GNU Go will report the statuses of worms
and dragons around the board. This type of information is available by
different methods, however (*note view.pike::, *note Colored Display::).
File: gnugo.info, Node: Output File, Next: Decide string, Prev: Traces, Up: Analyzing
If GNU Go is invoked with the option `-o filename' it will produce an
output file. This option can be added at the command line in the Go
Modem Protocol Setup Window of CGoban. The output file will show the
locations of the moves considered and their weights. It is worth noting
that by enlarging the CGoban window to its fullest size it can display
3 digit numbers. Dragons with status `DEAD' are labelled with an `X',
and dragons with status `CRITICAL' are labelled with a `!'.
If you have a game file which is not commented this way, or which
was produced by a non-current version of GNU Go you may ask GNU Go to
produce a commented version by running:
gnugo --quiet -l <old file> --replay <color> -o <new file>
Here <color> can be 'black,' 'white' or 'both'. The replay option will
also help you to find out if your current version of GNU Go would play
differently than the program that created the file.
File: gnugo.info, Node: Decide string, Next: Decide dragon, Prev: Output File, Up: Analyzing
5.3 Checking the reading code
=============================
The `--decide-string' option is used to check the tactical reading code
(*note Tactical Reading::). This option takes an argument, which is a
location on the board in the usual algebraic notation (e.g.
`--decide-string C17'). This will tell you 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 variation 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
attack4-B at D12 (variation 6, hash 51180fdf)
defend3 D12: 1 G12 (trivial extension)
This is to be interpreted as follows. The node in question was
generated by the function `attack3()' in `engine/reading.c', which was
called on the string at `D12'. The data in parentheses tell you the
values of `count_variations' and `hashdata.hashval'.
The second value ("hash") you probably will not need to know unless
you are debugging the hash code, and we will not discuss it. But the
first value ("variation") is useful when using the debugger `gdb'. You
can first make an output file using the `-o' option, then walk through
the reading with `gdb', and to coordinate the SGF file with the
debugger, display the value of `count_variations'. Specifically, from
the debugger you can find out where you are as follows:
B:D13 W:E12 B:E13 W:F12 B:F11 (variation 6)
If you place yourself right after the call to `trymove()' which
generated the move in question, then the variation number in the SGF
file should match the variation number displayed by `dump_stack()', and
the move in question will be the last move played (F11 in this example).
This displays the sequence of moves leading up to the variation in
question, and it also prints `count_variations-1'.
The second two lines tell you that from this node, the function
`break_chain()' was called at D12 and returned 0 meaning that no way
was found of rescuing the string by attacking an element of the
surrounding chain, and the function `defend3()' was called also at D12
and returned 1, meaning that the string can be defended, and that G12
is the move that defends it. If you have trouble finding the function
calls which generate these comments, try setting `sgf_dumptree=1' and
setting a breakpoint in `sgf_trace'.
File: gnugo.info, Node: Decide dragon, Next: GTP and GDB techniques, Prev: Decide string, Up: Analyzing
5.4 Checking the Owl Code
=========================
You can similarly debug the Owl code using the option
`--decide-dragon'. Usage is entirely similar to `--decide-string', and
it can be used similarly to produce variation trees. These should be
typically much smaller than the variation trees produced by
File: gnugo.info, Node: GTP and GDB techniques, Next: view.pike, Prev: Decide dragon, Up: Analyzing
5.5 GTP and GDB techniques
==========================
You can use the Go Text Protocol (*note GTP::) to determine the
statuses of dragons and other information needed for debugging. The GTP
command `dragon_data P12' will list the dragon data of the dragon at
`P12' and `worm_data' will list the worm data; other GTP commands may
You can also conveniently get such information from GDB. A
suggested `.gdbinit' file may be found in *Note Debugging::. Assuming
this file is loaded, you can list the dragon data with the command:
Similarly you can get the worm data with `worm P12'.
File: gnugo.info, Node: view.pike, Next: Scoring, Prev: GTP and GDB techniques, Up: Analyzing
5.6 Debugging on a Graphical Board
==================================
The quickest way to analyze most positions is to use the tool
`view.pike' in the `regression' directory. It can be started with a
testcase specified, e.g. `pike view.pike strategy:40' or at a move in
an sgf file, e.g. `pike view.pike mistake.sgf:125'. When started it
shows the position on a grapical board on which it also marks
information like move values, dragon status, and so on. By clicking on
the board further information about the valuation of moves, contents of
various data structures, and other data can be made available.
Specific information on how to use `view.pike' for influence tuning
can be found in *Note Influence Tuning::.
File: gnugo.info, Node: Scoring, Next: Colored Display, Prev: view.pike, Up: Analyzing
GNU Go can score the game. Normally GNU Go will report its opinion about
the score at the end of the game, but if you want this information about
a game stored in a file, use the `--score' option (*note Invoking GNU
File: gnugo.info, Node: Colored Display, Prev: Scoring, Up: Analyzing
Various colored displays of the board may be obtained in a color
`xterm' or `rxvt' window. Xterm will only work if xterm is compiled
with color support. If the colors are not displayed on your xterm, try
`rxvt'. You may also use the Linux console. The colored display will
work best if the background color is black; if this is not the case you
may want to edit your `.Xdefaults' file or add the options `-bg black
-fg white' to `xterm' or `rxvt'. On Mac OS X put `setenv TERM
xterm-color' in your `.tcshrc' file to enable color in the terminal.
You can get a colored ASCII display of the board in which each dragon
is assigned a different letter; and the different `matcher_status'
values (`ALIVE', `DEAD', `UNKNOWN', `CRITICAL') have different colors.
This is very handy for debugging. Actually two diagrams are generated.
The reason for this is concerns the way the matcher status is computed.
The dragon_status (*note Dragons::) is computed first, then for some,
but not all dragons, a more accurate owl status is computed. The
matcher status is the owl status if available; otherwise it is the
dragon_status. Both the dragon_status and the owl_status are displayed.
The color scheme is as follows:
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
Other useful colored displays may be obtained by using instead:
Instead of `-T', try this with `-E'. This gives a colored display of
the eyespaces, with marginal eye spaces marked `!' (*note Eyes::).
File: gnugo.info, Node: Move Generation, Next: Worms and Dragons, Prev: Analyzing, Up: Top
* Move generation Intro:: Introduction.
* Move Reasons:: Generation of move reasons.
* Move Reason Details:: Detailed Descriptions of Move Reasons
* Valuation:: Valuating the moves
* End Game:: Endgame move generation
File: gnugo.info, Node: Move generation Intro, Next: Move Reasons, Up: Move Generation
GNU Go 3.0 introduced a move generation scheme substantially different
from earlier versions. 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
* 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
* The move reasons are objective, in contrast to the move values in
the old scheme. Anyone can verify whether a suggested move reason
* 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.
File: gnugo.info, Node: Move Reasons, Next: Move Reason Details, Prev: Move generation Intro, Up: Move Generation
6.2 Generation of move reasons
==============================
Each move generator suggests a number of moves. It justifies each move
suggestion with one or move "move reasons". These move reasons are
collected at each intersection where the moves are suggested for later
valuation. Here is a partial list of of move reasons considered by GNU
Go. (The complete list may be found in `move_reasons.h'.)
Threaten to attack or defend a worm.
A move that either achieves one goal or another (at the moment
this only used for attacks on worms).
At the moment this is used for a move that defends two worms
threatened by a double attack.
Connect or cut two worms.
Declare an antisuji or forbidden move.
Win or threaten to win a semeai.
Move expanding our territory/moyo. These reasons are at the moment
A vital point for life and death.
Moves added by 'a' and 'd' class patterns (*note Pattern
Classification::) which (perhaps intangibly) attack or defend a
An owl attack or defense move.
A threat to owl attack or defend a group.
A move to remove an owl threat.
An uncertain owl attack or defense. This means that the owl code
could not decide the outcome, because the owl node limit was
A move that starts a chain of ataris, eventually leading to a
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
The attack and defend move types can have a suffix to denote moves
whose result 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 *note Ko::. See `engine/move_reasons.h' for the full of
*NOTICE:* Some of these are reasons for *not* playing a move.
More detailed discussion of these move reasons will be found in the
File: gnugo.info, Node: Move Reason Details, Next: Valuation, Prev: Move Reasons, Up: Move Generation
6.3 Detailed Descriptions of various Move Reasons
=================================================
* Attack and Defense:: Worm Attack and Defense
* Threats to Attack or Defend:: Worm Threats
* Multi Attack or Defense:: Combined Attacks and Defenses
* Cutting and Connecting:: Cutting and Connecting moves
* Semeai:: Semeai winning moves
* Making eyes:: Vital eye moves
* Antisuji moves:: Never play these!
* Territorial moves:: Block or expand territory
* Owl attack and defense:: Owl Attack and Defense
* Combination Attacks:: Coordinated threats such as double ataris
File: gnugo.info, Node: Attack and Defense, Next: Threats to Attack or Defend, Up: Move Reason Details
6.3.1 Attacking and defending moves
-----------------------------------
A move which tactically captures a worm is called an "attack move" and a
move which saves a worm from being tactically captured is called a
"defense move". It is understood that a defense move can only exist if
the worm can be captured, and that a worm without defense only is
attacked by moves that decrease the liberty count or perform necessary
It is important that all moves which attack or defend a certain
string are found, so that the move generation can make an informed
choice about how to perform a capture, or find moves which capture
and/or defend several worms.
Attacking and defending moves are first found in `make_worms' while
it evaluates the tactical status of all worms, although this step only
gives one attack and defense (if any) move per worm. Immediately after,
still in `make_worms', all liberties of the attacked worms are tested
for additional attack and defense moves. More indirect moves are found
by `find_attack_patterns' and `find_defense_patterns', which match the
A (attack) and D (defense) class patterns in `patterns/attack.db' and
`patterns/defense.db' As a final step, all moves which fill some
purpose at all are tested whether they additionally attacks or defends
some worm. (Only unstable worms are analyzed.)
File: gnugo.info, Node: Threats to Attack or Defend, Next: Multi Attack or Defense, Prev: Attack and Defense, Up: Move Reason Details
6.3.2 Threats to Attack or Defend
---------------------------------
A threat to attack a worm, but where the worm can be defended is used as
a secondary move reason. This move reason can enhance the value of a
move so that it becomes sente. A threatening move without any other
justification can also be used as a ko threat. The same is true for a
move that threatens defense of a worm, but where the worm can still be
captured if the attacker doesn't tenuki.
Threats found by the owl code are called *owl threats* and they have
File: gnugo.info, Node: Multi Attack or Defense, Next: Cutting and Connecting, Prev: Threats to Attack or Defend, Up: Move Reason Details
6.3.3 Multiple attack or defense moves
--------------------------------------
Sometimes a move attacks at least one of a number of worms or
simultaneously defends all of several worms. These moves are noted by
File: gnugo.info, Node: Cutting and Connecting, Next: Semeai, Prev: Multi Attack or Defense, Up: Move Reason Details
6.3.4 Cutting and connecting moves
----------------------------------
Moves which connect two distinct dragons are called `connecting moves'.
Moves which prevent such connections are called "cutting moves". Cutting
and connecting moves are primarily found by pattern matching, the `C'
A second source of cutting and connecting moves comes from the attack
and defense of cutting stones. A move which attacks a worm
automatically counts as a connecting move if there are multiple dragons
adjacent to the attacked worm. Similarly a defending move counts as a
cutting move. The action taken when a pattern of this type is found is
to induce a connect or cut move reason.
When a cut or connect move reason is registered, the involved dragons
are of course stored. Thus the same move may cut and/or connect several
File: gnugo.info, Node: Semeai, Next: Making eyes, Prev: Cutting and Connecting, Up: Move Reason Details
6.3.5 Semeai winning moves
--------------------------
A move which is necessary to win a capturing race is called a "semeai
move". These are similar to attacking moves, except that they involve
the simultaneous attack of one worm and the defense of another. As for
attack and defense moves, it's important that all moves which win a
semeai are found, so an informed choice can be made between them.
Semeai move reasons should be set by the semeai module. However this
has not been implemented yet. One might also wish to list moves which
increase the lead in a semeai race (removes ko threats) for use as
secondary move reasons. Analogously if we are behind in the race.
File: gnugo.info, Node: Making eyes, Next: Antisuji moves, Prev: Semeai, Up: Move Reason Details
6.3.6 Making or destroying eyes
-------------------------------
A move which makes a difference in the number of eyes produced from an
eye space is called an "eye move". It's not necessary that the eye is
critical for the life and death of the dragon in question, although it
will be valued substantially higher if this is the case. As usual it's
important to find all moves that change the eye count.
(This is part of what eye_finder was doing. Currently it only finds
one vital point for each unstable eye space.)
File: gnugo.info, Node: Antisuji moves, Next: Territorial moves, Prev: Making eyes, Up: Move Reason Details
Moves which are locally inferior or for some other reason must not be
played are called "antisuji moves". These moves are generated by pattern
matching. Care must be taken with this move reason as the move under no
circumstances will be played.
File: gnugo.info, Node: Territorial moves, Next: Owl attack and defense, Prev: Antisuji moves, Up: Move Reason Details
Any move that increases territory gets a move reason. This is the expand
territory move reason. That move reason is added by the `e' patterns in
`patterns/patterns.db'. Similarly the `E' patterns attempt to generate
or mitigate a moyo, which is a region of influence not yet secure
territory, yet valuable. Such a pattern sets the "expand moyo" move
File: gnugo.info, Node: Owl attack and defense, Next: Combination Attacks, Prev: Territorial moves, Up: Move Reason Details
6.3.9 Attacking and Defending Dragons
-------------------------------------
Just as the tactical reading code tries to determine when a worm can be
attacked or defended, the owl code tries to determine when a dragon can
get two eyes and live. The function `owl_reasons()' generates the
corresponding move reasons.
The owl attack and owl defense move reasons are self explanatory.
The owl attack threat reason is generated if owl attack on an
opponent's dragon fails but the owl code determines that the dragon can
be killed with two consecutive moves. The killing moves are stored in
`dragon[pos].owl_attack_point' and
`dragon[pos].owl_second_attack_point'.
Similarly if a friendly dragon is dead but two moves can revive it,
an owl defense threat move reason is generated.
The prevent threat reasons are similar but with the colors reversed:
if the opponent has an attack threat move then a move which removes the
threat gets a prevent threat move reason.
The owl uncertain move reasons are generated when the owl code runs
out of nodes. In order to prevent the owl code from running too long, a
cap is put on the number of 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.
File: gnugo.info, Node: Combination Attacks, Prev: Owl attack and defense, Up: Move Reason Details
6.3.10 Combination Attacks
--------------------------
The function `atari_atari' tries to find a sequence of ataris
culminating in an unexpected change of status of any opponent string,
from `ALIVE' to `CRITICAL'. Once such a sequence of ataris is found, it
tries to shorten it by rejecting irrelevant moves.
File: gnugo.info, Node: Valuation, Next: End Game, Prev: Move Reason Details, Up: Move Generation
6.4 Valuation of suggested moves
================================
At the end of the move generation process, the function
`value_move_reasons()' tries to assign values to the moves for the
purpose of selecting the best move. The single purpose of the move
valuation is to try to rank the moves so that the best move gets the
highest score. In principle these values could be arbitrary, but in
order to make it easier to evaluate how well the valuation performs,
not to mention simplify the tuning, we try to assign values which are
consistent with the usual methods of counting used by human Go players,
as explained for example in _The Endgame_ by Ogawa and Davies.
Moves are valued with respect to four different criteria. These are
All of these are floats and should be measured in terms of actual
The territorial value is the total change of expected territory
caused by this move. This includes changes in the status of groups if
the move is an attack or a defense move.
Beginning with GNU Go 3.0, the influence function plays an important
role in estimating territory (*note Influence and Territory::). It is
used to make a guess at each intersection how likely it is that it will
become black or white territory. The territorial value sums up the
changes in these valuations.
Strategical value is a measure of the effect the move has on the
safety of all groups on the board. Typically cutting and connecting
moves have their main value here. Also edge extensions, enclosing moves
and moves towards the center have high strategical value. The
strategical value should be the sum of a fraction of the territorial
value of the involved dragons. The fraction is determined by the change
Shape value is a purely local shape analysis. An important role of
this measure is to offset mistakes made by the estimation of
territorial values. In open positions it's often worth sacrificing a
few points of (apparent) immediate profit to make good shape. Shape
value is implemented by pattern matching, the Shape patterns.
Secondary value is given for move reasons which by themselves are not
sufficient to play the move. One example is to reduce the number of
eyes for a dragon that has several or to attack a defenseless worm.
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.
* Territorial value:: How much territory does a move gain
* Strategical value:: Strategical gains from a move
* Shape factor:: Local shape
* Minimum Value:: Minimum value
* Secondary Value:: Other, more indirect, gains from a move
* Threats and Followup Value:: Valuation of attack and defense threats
File: gnugo.info, Node: Territorial value, Next: Strategical value, Up: Valuation
The algorithm for computing territorial value is in the function
`estimate_territorial_value'. As the name suggests, it seeks to
estimate the change in territory.
It considers all groups that are changed from alive to death or
vice-versa due to this move. Also, it makes an assumption whether the
move should be considered safe. If so, the influence module is called:
The function `influence_delta_territory' estimates the territorial
effect of both the stone played and of the changes of group status'.
The result returned by the influence module is subject to a number of
corrections. This is because some move reasons cannot be evaluated by a
single call to the influence function, such as moves depending on a ko.
File: gnugo.info, Node: Strategical value, Next: Shape factor, Prev: Territorial value, Up: Valuation
Strategical defense or attack reasons are assigned to any move which
matches a pattern of type `a' or `d'. These are moves which in some
(often intangible) way tend to help strengthen or weaken a dragon. Of
course strengthening a dragon which is already alive should not be
given much value, but when the move reason is generated it is not
necessary to check its status or safety. This is done later, during the
File: gnugo.info, Node: Shape factor, Next: Minimum Value, Prev: Strategical value, Up: Valuation
In the value field of a pattern (*note Pattern Values::) one may
This is used to compute the shape factor, which multiplies the score
of a move. We take the largest positive contribution to shape and add 1
for each additional positive contribution found. Then we take the
largest negative contribution to shape, and add 1 for each additional
negative contribution. The resulting number is raised to the power 1.05
to obtain the shape factor.
The rationale behind this complicated scheme is that every shape
point is very significant. If two shape contributions with values (say)
5 and 3 are found, the second contribution should be devalued to 1.
Otherwise the engine is too difficult to tune since finding multiple
contributions to shape can cause significant overvaluing of a move.
File: gnugo.info, Node: Minimum Value, Next: Secondary Value, Prev: Shape factor, Up: Valuation
A pattern may assign a minimum (and sometimes also a maximum) value.
For example the Joseki patterns have values which are prescribed in
this way, or ones with a `value' field. One prefers not to use this
approach but in practice it is sometimes needed.
In the fuseki, there are often several moves with identical minimum
value. GNU Go chooses randomly between such moves, which ensures some
indeterminacy of GNU Go's play. Later in the game, GNU Go's genuine
valuation of such a move is used as a secondary criterion.
File: gnugo.info, Node: Secondary Value, Next: Threats and Followup Value, Prev: Minimum Value, Up: Valuation
Secondary move reasons are weighed very slightly. Such a move can tip
the scales if all other factors are equal.
File: gnugo.info, Node: Threats and Followup Value, Prev: Secondary Value, Up: Valuation
6.4.6 Threats and Followup Value
--------------------------------
Followup value refers to value which may acrue if we get two moves in a
row in a local area. It is assigned for moves that threaten to attack
or defend a worm or dragon. Also, since GNU Go 3.2 the influence module
makes an assessment of the possible purely territorial followup moves.
In cases where these two heuristics are not sufficient we add patterns
with a `followup_value' autohelper macro.
Usually, the followup value gives only a small contribution; e.g. if
it the followup value is very large, then GNU Go treats the move as
sente by doubling its value. However, if the largest move on the board
is a ko which we cannot legally take, then such a move becomes
attractive as a ko threat and the full followup value is taken into
File: gnugo.info, Node: End Game, Prev: Valuation, Up: Move Generation
Endgame moves are generated just like any other move by GNU Go. In fact,
the concept of endgame does not exist explicitly, but if the largest
move initially found is worth 6 points or less, an extra set of patterns
in `endgame.db' is matched and the move valuation is redone.
File: gnugo.info, Node: Worms and Dragons, Next: Eyes, Prev: Move Generation, Up: Top
* Amalgamation:: How two Worms are amalgamated.
* Connection:: Connections.
* Half Eyes:: Half Eyes and False Eyes.
* Dragons:: Union of WORMS.
* Dragons in Color:: Colored display of DRAGONS.
Before considering its move, GNU Go collects some data in several
arrays. Two of these arrays, called `worm' and `dragon', are discussed
in this document. Others are discussed in *Note Eyes::.
This information is intended to help evaluate the connectedness, eye
shape, escape potential and life status of each group.
Later routines called by `genmove()' will then have access to this
information. This document attempts to explain the philosophy and
algorithms of this preliminary analysis, which is carried out by the
two routines `make_worm()' and `make_dragon()' in `dragon.c'.
A "worm" is a maximal set of stones on the board which are connected
along the horizontal and vertical lines, and are of the same color. We
often say "string" instead of worm.
A "dragon" is a union of strings of the same color which will be
treated as a unit. The dragons are generated anew at each move. If two
strings are in the dragon, it is the computer's working hypothesis that
they will live or die together and are effectively connected.
The purpose of the dragon code is to allow the computer to formulate
meaningful statements about life and death. To give one example,
consider the following situation:
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.
File: gnugo.info, Node: Worms, Next: Amalgamation, Up: Worms and Dragons
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
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];
This field contains the cardinality of the worm.
This is the number of stones in a worm plus the number of
empty intersections 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.
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:
For a nonempty worm the field liberties is the number of
liberties of the string. This is supplemented by
`LIBERTIES2', `LIBERTIES3' and `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:
.XX... We label the .XX.4.
XO.... liberties of XO1234
XO.... order < 5 of XO1234
...... the O group: .12.4.
The convention that liberties of order >1 may not touch a
group of the opposite 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
We say that n is the "distance" of the liberty of order n
If nonzero, `lunch' points to a boundary worm which can be
easily captured. (It does not matter whether or not the
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.
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 adjacent to two enemy
strings, which do not have a liberty in common. The most
common type of cutting string is in this situation:
A "potential cutting stone" is adjacent to two enemy strings
which do share a liberty. For example, X in:
For cutting strings we set `worm[].cutstone=2'. For potential
cutting strings we set `worm[].cutstone=1'.
Cutting points are identified by the patterns in the
connections database. Proper cuts are handled by the fact
that attacking and defending moves also count as moves
cutting or connecting the surrounding dragons. The
`cutstone2' field is set during `find_cuts()', called from
There are two separate notions of "genus" for worms and
dragons. The dragon notion is more important, so
`dragon[pos].genus' is a far more useful field than
`worm[pos].genus'. Both fields are intended as approximations
to the number of eyes. The "genus" of a string is the number
of connected components of its complement, minus one. It is
an approximation to the number of eyes of the string.
An "inessential" string is one which meets a criterion
designed to guarantee that it has no life potential unless a
particular surrounding string of the opposite color can be
killed. More precisely an "inessential string" is a string S
of genus zero, not adjacent to any opponent string which can
be easily captured, and which has no edge liberties or second
order liberties, and which satisfies the following further
property: If the string is removed from the board, then the
remaining cavity only borders worms of the opposite color.
An "invincible" worm is one which GNU Go thinks cannot be
captured. Invincible worms are computed by the function
`unconditional_life()' which tries to find those worms of the
given color that can never be captured, even if the opponent
is allowed an arbitrary number of consecutive moves.
Unconditional status is also set by the function
`unconditional_life'. This is set `ALIVE' for stones which are
invincible. Stones which can not be turned invincible even if
the defender is allowed an arbitrary number of consecutive
moves are given an unconditional status of `DEAD'. Empty
points where the opponent cannot form an invincible worm are
called unconditional territory. The unconditional status is
set to `WHITE_TERRITORY' or `BLACK_TERRITORY' depending on
who owns the territory. Finally, if a stone can be captured
but is adjacent to unconditional territory of its own color,
it is also given the unconditional status `ALIVE'. In all
other cases the unconditional status is `UNKNOWN'.
To make sense of these definitions it is important to notice
that any stone which is alive in the ordinary sense (even if
only in seki) can be transformed into an invincible group by
some number of consecutive moves. Well, this is not entirely
true because there is a rare class of seki groups not
satisfying this condition. Exactly which these are is left as
an exercise for the reader. Currently `unconditional_life',
which strictly follows the definitions above, calls such seki
groups unconditionally dead, which of course is a misfeature.
It is possible to avoid this problem by making the algorithm
slightly more complex, but this is left for a later revision.
* `int attack_points[MAX_TACTICAL_POINTS]'
* `attack_codes[MAX_TACTICAL_POINTS]'
* `int defense_points[MAX_TACTICAL_POINTS];'
* `int defend_codes[MAX_TACTICAL_POINTS];'
If the tactical reading code (*note Tactical Reading::) finds
that the worm can be attacked, `attack_points[0]' is a point
of attack, and `attack_codes[0]' is the attack code, `WIN',
`KO_A' or `KO_B'. If multiple attacks are known,
`attack_points[k]' and `attack_codes[k]' are used. Similarly
with the defense codes and defense 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];'
These are points that threaten to attack or defend a worm.
The function `makeworms()' will generate data for all worms.
File: gnugo.info, Node: Amalgamation, Next: Connection, Prev: Worms, Up: Worms and Dragons
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
Amalgamation of worms in GNU Go proceeds as follows. First we
amalgamate all boundary components of an eyeshape. Thus in the
.OOOO. The four X strings are amalgamated into a
OOXXO. single dragon because they are the boundary
OX..XO components of a blackbordered cave. The
OX..XO cave could contain an inessential string
OOXXO. with no effect on this amalgamation.
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.
A database of connection patterns may be found in `patterns/conn.db'.
File: gnugo.info, Node: Connection, Next: Half Eyes, Prev: Amalgamation, Up: Worms and Dragons
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
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
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':
?xxx? straight extension to connect
;xcut(a) && odefend_against(b,a)
where we verify that a move at `*' would stop the enemy from safely
playing at the cutting point, thus defending against the cut.
File: gnugo.info, Node: Half Eyes, Next: Dragons, Prev: Connection, Up: Worms and Dragons
7.4 Half Eyes and False Eyes
============================
A "half eye" is a place where, if the defender plays first, an eye will
materialize, but where if the attacker plays first, no eye will
materialize. A "false eye" is a vertex which is surrounded by a dragon
yet is not an eye. Here is a half eye:
The "topological" algorithm for determining half and false eyes is
described elsewhere (*note Eye Topology::).
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.
struct half_eye_data half_eye[MAX_BOARD];
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 */
The array `struct half_eye_data half_eye[MAX_BOARD]' contains
information about half and false eyes. If the type is `HALF_EYE' then
up to four moves are recorded which can either attack or defend the
eye. In rare cases the attack points could be different from the
File: gnugo.info, Node: Dragons, Next: Dragons in Color, Prev: Half Eyes, Up: Worms and Dragons
The array `struct dragon_data dragon[MAX_BOARD]' collects information
about the dragons. We will give definitions of the various fields. Each
field has constant value at each vertex of the dragon. (Fields will be
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 */
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 */
extern struct dragon_data dragon[BOARDMAX];
Other fields attached to the dragon are contained in the
`dragon_data2' struct array. (Fields will be discussed below.)
int adjacent[MAX_NEIGHBOR_DRAGONS];
float moyo_territorial_value;
int semeai_margin_of_safety;
int semeai_defense_point;
int semeai_defense_certain;
int semeai_attack_certain;
int owl_second_attack_point;
int owl_second_defense_point;
extern struct dragon_data2 *dragon2;
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;
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.
The dragon number, used as a key into the `dragon2' array.
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 amalgamation the worm origins are
copied to the dragon origins. Amalgamation of two dragons
amounts to changing the origin of one.
The number of stones in the dragon.
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.
(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
The dragon status is the best measure of the dragon's health.
It is computed 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.
The origin field is duplicated here.
* `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.
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.
The number of neighbor dragons.
The number of neighbor dragons of the opposite color.
* float moyo_territorial_value
The function `compute_surrounding_moyo_sizes()' assigns a
size and a territorial value to the moyo around each dragon
(*note Territory and Moyo::). This is the moyo size. They are
recorded in these fields.
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
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
A measure of the dragon's potential to escape towards safety,
in case it cannot make two eyes locally. Documentation may be
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:
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 */
Location of a half eye attached to the dragon.
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.
In estimating the safety of a dragon it is useful to know if
it is "surrounded". See *note Surrounded Dragons:: and the
comments in `surround.c' for more information about the
algorithm. Used in computing the escape_route, and also
callable from patterns (currently used by CB258).
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
determine 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' attempts 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 attacker 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
This is a classification similar to `dragon.crude_status', but
based on the life and death reading in `owl.c'. The owl code
(*note The Owl Code::) 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'.
If the dragon can be attacked this is the point to attack the
The owl attack code, It can be WIN, KO_A, KO_B or 0 (*note
The owl reading is able to finish analyzing the attack
without running out of nodes.
* owl_second_attack_point
If the dragon can be defended, this is the place to play.
The owl defense code, It can be WIN, KO_A, KO_B or 0 (*note
The owl code is able to finish analyzing the defense without
* owl_second_defense_point
A second owl defense point.
File: gnugo.info, Node: Dragons in Color, Prev: Dragons, Up: Worms and Dragons
7.6 Colored Dragon Display
==========================
You can get a colored ASCII display of the board in which each dragon
is assigned a different letter; and the different values of
`dragon.status' values (`ALIVE', `DEAD', `UNKNOWN', `CRITICAL') have
different colors. This is very handy for debugging. A second diagram
shows the values of `owl.status'. If this is `UNCHECKED' the dragon is
Save a game in sgf format using CGoban, or using the `-o' option with
Open an `xterm' or `rxvt' window. You may also use the Linux
console. Using the console, you may need to use "SHIFT-PAGE UP" to see
the first diagram. Xterm will only work if it is compiled with color
support--if you do not see the colors try `rxvt'. Make the background
color black and the foreground color white.
`gnugo -l [filename] -L [movenum] -T' to get the colored display.
The color scheme: Green = `ALIVE'; Yellow = `UNKNOWN'; Cyan = `DEAD'
and Red = `CRITICAL'. Worms which have been amalgamated into the same
dragon are labelled with the same letter.
Other useful colored displays may be obtained by using instead:
* the option -E to display eye spaces (*note Eyes::).
* the option -m 0x0180 to display territory, moyo and area (*note
The colored displays are documented elsewhere (*note Colored
File: gnugo.info, Node: Eyes, Next: Patterns, Prev: Worms and Dragons, Up: Top
The purpose of this Chapter is to describe the algorithm used in GNU Go
* Local Games:: Local games
* Eye Space as Local Game:: Eye space as local game
* Eye Example:: An example
* Graphs:: Underlying graphs
* Eye Shape:: Pattern matching
* Eye Local Game Values:: Pattern matching
* Eye Topology:: False eyes and half eyes
* Eye Topology with Ko:: False eyes and half eyes with ko
* False Margins:: False margins
* Eye Functions:: Functions in `optics.c'
File: gnugo.info, Node: Local Games, Next: Eye Space, Up: Eyes
The fundamental paradigm of combinatorial game theory is that games can
be added and in fact form a group. If `G' and `H' are games, then `G+H'
is a game in which each player on his turn has the option of playing in
either move. We say that the game `G+H' is the sum of the local games
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.
Here is an example of a chimera:
File: gnugo.info, Node: Eye Space, Next: Eye Space as Local Game, Prev: Local Games, Up: Eyes
In order that each eyespace be assignable to a dragon, it is necessary
that all the dragons surrounding it be amalgamated (*note
Amalgamation::). This is the function of `dragon_eye()'.
An EYE SPACE for a black dragon is a collection of vertices adjacent
to a dragon which may not yet be completely closed off, but which can
potentially become eyespace. If an open eye space is sufficiently
large, it will yield two eyes. Vertices at the edge of the eye space
(adjacent to empty vertices outside the eye space) are called MARGINAL.
Here is an example from a game:
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
the shape in question has the form:
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'.
File: gnugo.info, Node: Eye Space as Local Game, Next: Eye Example, Prev: Eye Space, Up: Eyes
8.3 The eyespace as local game
==============================
In the abstraction, an eyespace consists of a set of vertices labelled:
Tables of many eyespaces are found in the database
`patterns/eyes.db'. Each of these may be thought of as a local game.
The result of this game is listed after the eyespace in the form
`:max,min', where `max' is the number of eyes the pattern yields if `O'
moves first, while `min' is the number of eyes the pattern yields if
`X' moves first. The player who owns the eye space is denoted `O'
throughout this discussion. Since three eyes are no better than two,
there is no attempt to decide whether the space yields two eyes or
three, so max never exceeds 2. Patterns with min>1 are omitted from the
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
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
However if `X' moves he may remove the `!' and the `.'s adjacent to
the `!' become `!' themselves. Thus if `X' moves first he may transform
NOTE: A nuance which is that after the `X:1', `O:2' exchange below,
`O' is threatening 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.
We will not attempt to characterize the terminal states of the local
game (some of which could be seki) or the scoring.
File: gnugo.info, Node: Eye Example, Next: Graphs, Prev: Eye Space as Local Game, Up: Eyes
Here is a local game which yields exactly one eye, no matter who moves
Here are some variations, assuming `O' moves first.
Here is another variation:
File: gnugo.info, Node: Graphs, Next: Eye Shape, Prev: Eye Example, Up: Eyes
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
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 (*note Eye Topology::).
A half eye is isomorphic to the pattern `(!.)' . To see this,
consider the following two eye shapes:
These are equivalent eyeshapes, with isomorphic local games {2|1}.
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 (*note Eye
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:
This is equivalent to the two previous eyeshapes, with an isomorphic
This eyeshape has a false eye at `a'. This is also found by the
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.
File: gnugo.info, Node: Eye Shape, Next: Eye Local Game Values, Prev: Graphs, Up: Eyes
The patterns in `patterns/eyes.db' are compiled into graphs represented
essentially by arrays in `patterns/eyes.c'.
Each actual eye space as it occurs on the board is also compiled
into a graph. Half eyes are handled as follows. Referring to the
repeated from the preceding discussion, the vertex at `b' is added to
the eyespace as a marginal vertex. The adjacency condition in the graph
is a macro (in `optics.c'): two vertices are adjacent if they are
physically adjacent, or if one is a half eye and the other is its key
In `recognize_eyes()', each such graph arising from an actual
eyespace is matched against the graphs in `eyes.c'. If a match is
found, the result of the local game is known. If a graph cannot be
matched, its local game is assumed to be {2|2}.
File: gnugo.info, Node: Eye Local Game Values, Next: Eye Topology, Prev: Eye Shape, Up: Eyes
8.7 Eye Local Game Values
=========================
The game values in `eyes.db' are given in a simplified scheme which is
flexible enough to represent most possibilities in a useful way.
The colon line below the pattern gives the eye value of the matched
eye shape. This consists of four digits, each of which is the number of
eyes obtained during the following conditions:
1. The attacker moves first and is allowed yet another move because
the defender plays tenuki.
2. The attacker moves first and the defender responds locally.
3. The defender moves first and the attacker responds locally.
4. The defender moves first and is allowed yet another move because
the attacker plays tenuki.
The first case does *not* necessarily mean that the attacker is
allowed two consecutive moves. This is explained with an example later.
Also, since two eyes suffice to live, all higher numbers also count
The following 15 cases are of interest:
* 0001 0 eyes, but the defender can threaten to make one eye.
* 0002 0 eyes, but the defender can threaten to make two eyes.
* 0011 1/2 eye, 1 eye if defender moves first, 0 eyes if attacker
* 0012 3/4 eyes, 3/2 eyes if defender moves first, 0 eyes if
* 0022 1* eye, 2 eyes if defender moves first, 0 eyes if attacker
* 0111 1 eye, attacker can threaten to destroy the eye.
* 0112 1 eye, attacker can threaten to destroy the eye, defender can
threaten to make another eye.
* 0122 5/4 eyes, 2 eyes if defender moves first, 1/2 eye if attacker
* 0222 2 eyes, attacker can threaten to destroy both.
* 1112 1 eye, defender can threaten to make another eye.
* 1122 3/2 eyes, 2 eyes if defender moves first, 1 eye if attacker
* 1222 2 eyes, attacker can threaten to destroy one eye.
The 3/4, 5/4, and 1* eye values are the same as in Howard Landman's
paper Eyespace Values in Go. Attack and defense points are only marked
in the patterns when they have definite effects on the eye value, i.e.
pure threats are not marked.
Examples of all different cases can be found among the patterns in
this file. Some of them might be slightly counterintuitive, so we
explain one important case here. Consider
which e.g. matches in this position:
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:
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.
We always assume suicide to be allowed in this database. It is easy
enough to sort out such moves at a higher level when suicide is
File: gnugo.info, Node: Eye Topology, Next: Eye Topology with Ko, Prev: Eye Local Game Values, Up: Eyes
8.8 Topology of Half Eyes and False Eyes
========================================
A HALF EYE is a pattern where an eye may or may not materialize,
depending on who moves first. Here is a half eye for `O':
A FALSE EYE is an eye vertex which cannot become a proper eye. Here
are two examples of false eyes for `O':
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
* 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:
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.
File: gnugo.info, Node: Eye Topology with Ko, Next: False Margins, Prev: Eye Topology, Up: Eyes
This section extends the topological eye analysis to handle ko. We
distinguish between a ko in favor of `O' and one in favor of `X':
Preliminarily we give the former the symbolic diagonal value `a' and
the latter the diagonal value `b'. We should clearly have `0 < a < 1 <
b < 2'. Letting `e' be the topological eye value (still the sum of the
four diagonal values), we want to have the following properties:
2 < e < 3 - worse than proper eye, better than half eye
3 < e < 4 - worse than half eye, better than false eye
In order to determine the appropriate values of `a' and `b' we
analyze the typical cases of ko contingent topological eyes:
.X.. (slightly) better than proper eye
.X.. better than half eye, worse than proper eye
.X.. better than half eye, worse than proper eye
.X.. better than false eye, worse than half eye
XOX. (slightly) better than proper eye
XOX. proper eye, some aji
X.X. better than half eye, worse than proper eye
XOX.. better than half eye, worse than proper eye
X.X.. better than false eye, worse than half eye
XOX.. better than false eye, worse than half eye
XOX.. false eye, some aji
X.X.. (slightly) worse than false eye
It may seem obvious that we should use
but this turns out to have some drawbacks. These can be solved by
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
value b=3/2 b=4/3 b=5/4 b=6/5 interval
(a) 1+a 1.5 1.67 1.75 1.8 e < 2
(a') 1+b 2.5 2.33 2.25 2.2 2 < e < 3
(b) 2+a 2.5 2.67 2.75 2.8 2 < e < 3
(b') 2+b 3.5 3.33 3.25 3.2 3 < e < 4
(c) 2a 1 1.33 1.5 1.6 e < 2
(c'') 2b 3 2.67 2.5 2.4 2 < e < 3
(d) 1+2a 2 2.33 2.5 2.6 2 < e < 3
(d'') 1+2b 4 3.67 3.5 3.4 3 < e < 4
(e) 2+2a 3 3.33 3.5 3.6 3 < e < 4
(e'') 2+2b 5 4.67 4.5 4.4 4 < e
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.
File: gnugo.info, Node: False Margins, Next: Eye Functions, Prev: Eye Topology with Ko, Up: Eyes
The following situation is rare but special enough to warrant separate
Here `a' may be characterized by the fact that it is adjacent to O's
eyespace, and it is also adjacent to an X group which cannot be
attacked, but that an X move at 'a' results in a string with only one
liberty. We call this a "false margin".
For the purpose of the eye code, O's eyespace should be parsed as
File: gnugo.info, Node: Eye Functions, Prev: False Margins, Up: Eyes
8.11 Functions in `optics.c'
============================
The public function `make_domains()' calls the function
`make_primary_domains()' which is static in `optics.c'. It's purpose is
to compute the domains of influence of each color, used in determining
eye shapes. *Note*: the term influence as used here is distinct from the
influence in influence.c.
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
The constraint that the two adjoining vertices not lie on the first
line prevents influence 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.
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
* `void partition_eyespaces(struct eye_data eye[BOARDMAX], int
Find connected eyespace components and compute relevant
* `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.
* `void compute_eyes(int pos, struct eyevalue *value, int
*attack_point, int *defense_point, struct eye_data eye[BOARDMAX],
struct half_eye_data heye[BOARDMAX], int add_moves)'
Given an eyespace with origin `pos', this function computes
the minimum and maximum numbers of eyes the space can yield.
If max and min are different, then vital points of attack and
defense are also generated. If `add_moves == 1', this
function may add a move_reason for `color' at a vital point
which is found by the function. If `add_moves == 0', set
* `void compute_eyes_pessimistic(int pos, struct eyevalue *value,
int *pessimistic_min, int *attack_point, int *defense_point,
struct eye_data eye[BOARDMAX], struct half_eye_data
This function works like `compute_eyes()', except that it
also gives a pessimistic view of the chances to make eyes.
Since it is intended to be used from the owl code, the option
to add move reasons has been removed.
* `void add_false_eye(int pos, struct eye_data eye[BOARDMAX], struct
half_eye_data heye[BOARDMAX])'
turns a proper eyespace into a margin.
* `int is_eye_space(int pos)'
* `int is_proper_eye_space(int pos)'
These functions are used from constraints to identify eye
spaces, primarily for late endgame moves.
* `int max_eye_value(int pos)'
Return the maximum number of eyes that can be obtained from
the eyespace at `(i, j)'. This is most useful in order to
determine whether the eyespace can be assumed to produce any
* `int is_marginal_eye_space(int pos)'
* `int is_halfeye(struct half_eye_data heye[BOARDMAX], int pos)'
* `int is_false_eye(struct half_eye_data heye[BOARDMAX], int pos)'
These functions simply return information about an eyeshape
that has already been analyzed. (They do no real work.)
* `void find_half_and_false_eyes(int color, struct eye_data
eye[BOARDMAX], struct half_eye_data heye[BOARDMAX], int
Find topological half eyes and false eyes by analyzing the
diagonal intersections, as described in the Texinfo
documentation (Eyes/Eye Topology).
* `float topological_eye(int pos, int color, struct eye_data
my_eye[BOARDMAX],struct half_eye_data heye[BOARDMAX])'
See Texinfo documentation (Eyes:Eye Topology). Returns:
* 2 or less if `pos' is a proper eye for `color';
* between 2 and 3 if the eye can be made false only by ko
* 3 if `pos' is a half eye;
* between 3 and 4 if the eye can be made real only by ko
* 4 or more if `pos' is a false eye.
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 algorithm 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
* `void set_eyevalue(struct eyevalue *e, int a, int b, int c, int d)'
set parameters into the `struct eyevalue' as follows: (*note
Eye Local Game Values::):
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
* `int max_eyes(struct eyevalue *e)'
Number of eyes if defender plays first followed by
* `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,
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
is encoded as `OO!%O.X%!...'. (The encoding is needed for the
GTP interface 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)
If the eye graph cannot be realized, 0 is returned, 1
File: gnugo.info, Node: Patterns, Next: Tactical Reading, Prev: Eyes, Up: Top
* Patterns Overview:: Overview of the pattern database.
* Pattern Classification:: The classification field
* Pattern Values:: The value field
* Helper Functions:: Helper Functions
* Autohelpers and Constraints:: Automatic generation of helper functions.
* Autohelper Actions:: Autohelper Actions
* Autohelper Functions:: Autohelper Functions
* Attack and Defense DB:: The Attack and defense moves database.
* Connections Database:: The connection database.
* Connection Functions:: Functions in `connections.c'
* Tuning:: Tuning the pattern database.
* PM Implementation:: Implementation.
* Symmetry & transformations:: Symmetry and transformations.
* Details:: Details of implementation.
* Grid optimization:: The ``grid'' optimization.
* Joseki Compiler:: The joseki compiler.
* Ladders in Joseki:: Example: ladders in joseki.
* Corner Matcher:: A special matcher for joseki patterns.
* Editing Patterns:: Emacs major mode for pattern files.
File: gnugo.info, Node: Patterns Overview, Next: Pattern Classification, Up: Patterns
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' (*note Joseki Compiler::). 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
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 (*note Eyes::).
The patterns described in the databases are ascii representations, of
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
The line beginning `:' describes various attributes of the pattern,
such as its symmetry 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
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
After the pattern, there is some supplementary information in the
:trfno, classification, [values], helper_function
Here trfno represents the number of transformations of the pattern to
consider, usually `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:
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'.
File: gnugo.info, Node: Pattern Classification, Next: Pattern Values, Prev: Patterns Overview, Up: Patterns
The attribute field in the `:' line of a pattern consists of a sequence
of zero or more of the following characters, each with a different
meaning. The attributes may be roughly classified as "constraints",
which determine whether or not the pattern is matched, and "actions",
which describe what is to be done when the pattern is matched, typically
9.2.1 Constraint Pattern Attributes
-----------------------------------
Safety of the move is not checked. This is appropriate for
sacrifice patterns. If this classification is omitted, the
matcher requires that the stone played cannot be trivially
captured. Even with s classification, a check for legality is
In addition to usual check that the stone played cannot be
trivially captured, it is also confirmed that an opponent
move here could not be captured.
It is checked that every friendly (`O') stone of the pattern
belongs to a dragon which has status (*note Dragons::)
`ALIVE' or `UNKNOWN'. The `CRITICAL' matcher status is
excluded. It is possible for a string to have `ALIVE' status
and still be tactically critical, since it might be
amalgamated into an ALIVE dragon, and the matcher status is
constant on the dragon. Therefore, an additional test is
performed: if the pattern contains a string which is
tactically critical, and if `*' does not rescue it, the
It is checked that every friendly (`O') stone of the pattern
belongs to a dragon which is classified as `DEAD' or
It is checked that every opponent (`X') stone of the pattern
belongs to a dragon with status `ALIVE', `UNKNOWN' or
`CRITICAL'. Note that there is an asymmetry with `O'
patterns, where `CRITICAL' dragons are rejected.
It is checked that every opponent (`X') stone of the pattern
belongs to a dragon which is classified as `DEAD' or `UNKNOWN'
If two or more distinct O dragons occur in the pattern, the
move is given the move reasons that it connects each pair of
dragons. An exception is made for dragons where the underlying
worm can be tactically captured and is not defended by the
Add strategical defense move reason for all our dragons and a
small shape bonus. This classification is appropriate for
weak connection patterns.
If two or more distinct `X' dragons occur in the pattern, the
move is given the move reasons that it cuts each pair of
The move makes or secures territory.
The move attempts increase influence and create/expand a moyo.
The move strategically defends all O dragons in the pattern,
except those that can be tactically captured and are not
tactically defended by this move. If any O dragon should
happen to be perfectly safe already, this only reflects in
the move reason being valued to zero.
The move strategically attacks all `X' dragons in the pattern.
Standard joseki move. Unless there is an urgent move on the
board these moves are made as soon as they can be. This is
equivalent to adding the `d' and `a' classifications together
with a minimum accepted value of 27.
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.
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
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).
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.
File: gnugo.info, Node: Pattern Values, Next: Helper Functions, Prev: Pattern Classification, Up: Patterns
The second and following fields in the `:' line of a pattern are
optional and of the form `value1(x),value2(y),...'. The available set
of values are as follows.
Forces the territorial value of the move to be at least x.
Forces the territorial value of the move to be at least x.
Forces the territorial value of the move to be at most x.
Forces the final value of the move to be at least x.
* `minvalue(x)', `maxvalue(x)'
Forces the final value of the move to be at least/most x.
Adds x to the move's shape value.
Adds x to the move's followup value.
The meaning of these values is documented in *Note Move Generation::.
File: gnugo.info, Node: Helper Functions, Next: Autohelpers and Constraints, Prev: Pattern Values, Up: Patterns
Helper functions can be provided to assist the matcher in deciding
whether to accept a pattern, register move reasons, and setting various
move values. The helper is supplied with the compiled pattern entry in
the table, and the (absolute) position on the board of the `*' point.
One difficulty is that the helper must be able to cope with all the
possible transformations of the pattern. To help with this, the OFFSET
macro is used to transform relative pattern coordinates to absolute
The actual helper functions are in `helpers.c'. They are declared in
As an example to show how to write a helper function, we consider a
hypothetical helper called `wedge_helper'. Such a helper used to exist,
but has been replaced by a constraint. Due to its simplicity it's still
a good example. The helper begins with a comment:
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 other = OTHER_COLOR(color);
if (TRYMOVE(move, color)) {
if (TRYMOVE(apos, other)) {
if (board[apos] == EMPTY || attack(apos, NULL))
else if (TRYMOVE(bpos, color)) {
if (!safe_move(cpos, other))
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
File: gnugo.info, Node: Autohelpers and Constraints, Next: Autohelper Actions, Prev: Helper Functions, Up: Patterns
9.5 Autohelpers and Constraints
===============================
In addition to the hand-written helper functions in `helpers.c', GNU Go
can automatically generate helper functions from a diagram with labels
and an expression describing a constraint. The constraint diagram,
specifying the labels, is placed below the `:' line and the constraint
expression is placed below the diagram on line starting with a `;'.
Constraints can only be used to accept or reject a pattern. If the
constraint evaluates to zero (false) the pattern is rejected, otherwise
it's accepted (still conditioned on passing all other tests of course).
To give a simple example we consider a connection pattern.
;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 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
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
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.
File: gnugo.info, Node: Autohelper Actions, Next: Autohelper Functions, Prev: Autohelpers and Constraints, Up: Patterns
As a complement to the constraints, which only can accept or reject a
pattern, one can also specify an action to perform when the pattern has
passed all tests and finally has been accepted.
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 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
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
Mark `a' as an antisuji, that is, a move that must never be
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'.
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 to the move reasons that the move at `*' threatens to cut
File: gnugo.info, Node: Autohelper Functions, Next: Attack and Defense DB, Prev: Autohelper Actions, Up: Patterns
The autohelper functions are translated into C code by the program in
`mkpat.c'. To see exactly how the functions are implemented, consult
the autohelper function definitions in that file. Autohelper functions
can be used in both constraint and action lines.
Number of first, second, third, and fourth order liberties of a worm
respectively. *Note Worms and Dragons::, the documentation on worms for
The number of liberties that an enemy or own stone, respectively,
would obtain if played at the empty intersection `x'.
Calls `cut_possible' (*note General Utilities::) to determine
whether `X' or `O' can cut at the empty intersection `x'.
True if `x' is either a stone or an empty point involved in a ko
The matcher status of a dragon. status(x) returns an integer that
can have the values `ALIVE', `UNKNOWN', `CRITICAL', or `DEAD' (*note
Each function true if the dragon has the corresponding matcher
status and false otherwise (*note Worms and Dragons::).
Returns the status of the dragon at `x' (*note Worms and Dragons::).
The number of eyes of a dragon. It is only meaningful to compare this
value against 0, 1, or 2.
These functions call `whose_territory()', `whose_moyo()' and
`whose_area()' (*note Territory and Moyo::). For example `xarea(x)'
evaluates to true if `x' is either a living enemy stone or an empty
point within the opponent's "area". The function `oarea(x)' is
analogous but with respect to our stones and area. The main difference
between area, moyo, and terri is that area is a very far reaching kind
of influence, moyo gives a more realistic estimate of what may turn in
to territory, and terri gives the points that already are believed to
True for a dragon that is perceived as weak.
Results of tactical reading. `attack(x)' is true if the worm can be
captured, `defend(x)' is true if there also is a defending move. Please
notice that `defend(x)' will return false if there is no attack on the
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.
True if an enemy or friendly stone, respectively, can legally be
True if O (respectively X) has a stone at one of the labelled
vertices. In the diagram, these vertices should be marked with a `?'.
True if an own stone at `x' would stop the enemy from safely playing
at `y', and conversely for the second function.
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
`xplay_defend(a,b,c,...,z)'
`oplay_defend(a,b,c,...,z)'
`xplay_attack(a,b,c,...,z)'
`oplay_attack(a,b,c,...,z)'
These functions make it possible to do more complex reading
experiments in the constraints. All of them work so that first the
sequence of moves `a',`b',`c',... is played through with alternating
colors, starting with `X' or `O' as indicated by the name. Then it is
tested whether the worm at `z' can be attacked or defended,
respectively. It doesn't matter who would be in turn to move, a worm of
either color may be attacked or defended. For attacks the opposite
color of the string being attacked starts moving and for defense 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
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_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
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)'
The function `xplay_connect(a,b,c,...,y,z)' begins with an `X' move
at `a', then an `O' move at `b', and so forth, then finally calls
`string_connect()' to determine whether `x' and `y' can be connected.
The other functions are similar (*note Connection Reading::).
`xplay_break_through(a,b,c,...,x,y,z)'
`oplay_break_through(a,b,c,...,x,y,z)'
These functions are used to set up a position like
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.
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
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
Returns the number of stones in the area around `x'.
Returns the amount of space in the area around `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,
Tell the move generation that `x' is a substandard move that never
Return true if `x' and `y' are the same dragon or worm respectively.
Number of stones in the indicated dragon or worm.
`add_attack_either_move(x,y)'
`add_defend_both_move(x,y)'
Explicitly notify the move generation about move reasons for the move
Returns true if the empty intersection at `x' is a half eye.
Inform the tactical reading that a supposed attack does in fact not
True if `cutstone2' field from worm data is larger than one. This
indicates that saving the worm would introduce at least two new cutting
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:
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
Amalgamate (join) the dragons at `x' and `y' (*note Worms and
`amalgamate_most_valuable(x,y,z)'
Called when `x', `y', `z' point to three (preferably distinct)
dragons, in situations such as this:
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.
This autohelper should be called when `x' is an eyespace which is
misidentified as marginal. It is reclassified as a proper eyespace
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
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. Returns the sum of the
values of the diagonal intersections, relative to `x', as explained in
*Note Eye Topology::, 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.
Returns the escape value at `x'. This is only useful in owl attack
File: gnugo.info, Node: Attack and Defense DB, Next: Connections Database, Prev: Autohelper Functions, Up: Patterns
9.8 Attack and Defense Database
===============================
The patterns in `attack.db' and `defense.db' are used to assist the
tactical reading in finding moves that attacks or defends worms. The
matching is performed during `make_worms()', at the time when the
tactical status of all worms is decided. None of the classes described
above are useful in these databases, instead we have two other classes.
For each `O' worm in the pattern that can be tactically captured
(`worm[m][n].attack_code != 0'), the move at `*' is tried. If it
is found to defend the stone, this is registered as a reason for
the move `*' and the defense point of the worm is set to `*'.
For each `X' worm in the pattern, it's tested whether the move at
`*' captures the worm. If that is the case, this is registered as
a reason for the move at `*'. The attack point of the worm is set
to `*' and if it wasn't attacked before, a defense is searched for.
Furthermore, `A' patterns can only be used in `attack.db' and `D'
patterns only in `defense.db'. Unclassified patterns may appear in
these databases, but then they must work through actions to be
File: gnugo.info, Node: Connections Database, Next: Connection Functions, Prev: Attack and Defense DB, Up: Patterns
9.9 The Connections Database
============================
The patterns in `conn.db' are used for helping `make_dragons()'
amalgamate worms into dragons and to some extent for modifying eye
spaces. The patterns in this database use the classifications `B',
`C', and `e'. `B' patterns are used for finding cutting points, where
amalgamation should not be performed, `C' patterns are used for finding
existing connections, over which amalgamation is to be done, and `e'
patterns are used for modifying eye spaces and reevaluating lunches.
There are also some patterns without classification, which use action
lines to have an impact. These are matched together with the `C'
patterns. Further details and examples can be found in *Note Worms and
We will illustrate these databases by example. In this situation:
`X' cannot play safely at the cutting point, so the `O' dragons are
to be amalgamated. Two patterns are matched here:
;!safe_xmove(A) && !ko(A) && !xcut(A)
;attack(A) || (!safe_xmove(B) && !ko(B) && !xcut(B))
The constraints are mostly clear. For example the second pattern
should not be matched if the `X' stone cannot be attacked and `X' can
play safely at `B', or if `B' is a ko. The constraint `!xcut(B)' means
that connection has not previously been inhibited by `find_cuts'. For
example consider this situation:
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:
; !attack(A) && !attack(B) && !xplay_attack(*,a,b,*) && !xplay_attack(*,b,a,*)
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
File: gnugo.info, Node: Connection Functions, Next: Tuning, Prev: Connections Database, Up: Patterns
9.10 Connections Functions
==========================
Here are the public functions in `connections.c'.
* `static void cut_connect_callback(int m, int n, int color,
struct pattern *pattern, int ll, void *data)'
Try to match all (permutations of) connection patterns at
`(m,n)'. For each match, if it is a B pattern, set cutting
point in worm data structure and make eye space marginal for
the connection inhibiting entries of the pattern. If it is a
`C' pattern, amalgamate the dragons in the pattern.
Find cutting points which should inhibit amalgamations and
sever the adjacent eye space. This goes through the
connection database consulting only patterns of type B. When
such a function is found, the function `cut_connect_callback'
* `void find_connections(void)'
Find explicit connection patterns and amalgamate the involved
dragons. This goes through the connection database
consulting patterns except those of type B, E or e. When such
a function is found, the function `cut_connect_callback' is
* void modify_eye_spaces1(void)
Find explicit connection patterns and amalgamate the involved
dragons. This goes through the connection database
consulting only patterns of type E (*note Connections
Database::). When such a function is found, the function
`cut_connect_callback' is invoked.
* void modify_eye_spaces1(void)
Find explicit connection patterns and amalgamate the involved
dragons. This goes through the connection database
consulting only patterns of type e (*note Connections
Database::). When such a function is found, the function
`cut_connect_callback' is invoked.
File: gnugo.info, Node: Tuning, Next: PM Implementation, Prev: Connection Functions, Up: Patterns
9.11 Tuning the Pattern databases
=================================
Since the pattern databases, together with the valuation of move
reasons, decide GNU Go's personality, much time can be devoted to
"tuning" them. Here are some suggestions.
If you want to experiment with modifying the pattern database, invoke
with the `-a' option. This will cause every pattern to be evaluated,
even when some of them may be skipped due to various optimizations.
You can obtain a Smart Game Format (SGF) record of your game in at
least two different ways. One is to use CGoban to record the game. You
can also have GNU Go record the game in Smart Game Format, using the
`-o' option. It is best to combine this with `-a'. Do not try to read
the SGF file until the game is finished and you have closed the 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
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:
gnugo -l [filename] -L [move number] -t -a -w
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
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 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 connected, 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
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.
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
Blue: GNU Go thinks the dragon is dead
Red: Status critical (1.5 eyes) or weak by the algorithm
If you want to get the same game over and over again, you can
eliminate the randomness in GNU Go's play by providing a fixed random
seed with the `-r' option.
File: gnugo.info, Node: PM Implementation, Next: Symmetry & transformations, Prev: Tuning, Up: Patterns
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 (notionally) 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)
File: gnugo.info, Node: Symmetry & transformations, Next: Details, Prev: PM Implementation, Up: Patterns
9.13 Symmetry and transformations
=================================
In general, each pattern must be tried in each of 8 different
permutations, to reflect the symmetry of the board. But some patterns
have symmetries which mean that it is unnecessary (and therefore
inefficient) to try all eight. The first character after the `:' can be
one of `8',`|',`\',`/', `X', `-', `+', representing the axes of
symmetry. It can also be `O', representing symmetry under 180 degrees
transformation I - | . \ l r /
ABC GHI CBA IHG ADG CFI GDA IFC
DEF DEF FED FED BEH BEH HEB HEB
GHI ABC IHG CBA CFI ADG IFC GDA
Then if the pattern has the following symmetries, the following are
We can choose to use transformations a,d,f,g as the unique
transformations for patterns 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 `\'.
File: gnugo.info, Node: Details, Next: Grid optimization, Prev: Symmetry & transformations, Up: Patterns
9.14 Implementation Details
===========================
1. An entry in the pattern header states whether the anchor is an `X'
or an `O'. This helps performance, since all transformations can be
rejected at once if the anchor stone does not match. (Ideally, we
could just define that the anchor is always `O' or always `X', but
some patterns contain no `O' and some contain no `X'.)
2. The pattern header contains the size of the pattern (ie the
co-ordinates of the top left and bottom right elements) relative to
the anchor. This allows the pattern can be rejected quickly if
there is not room for the pattern to fit around the anchor stone
in a given orientation (ie it is too near the edge of the board).
The bounding box information must first be transformed like the
elements before it can be tested, and after transforming, we need
to work out where the top-left and bottom-right corners are.
3. The edge constraints are implemented by notionally padding the
pattern with rows or columns of `?' until it is exactly 19 (or
whatever the current board size is) elements wide or high. Then the
pattern is quickly rejected by (ii) above if it is not at the
edge. So the example pattern above is compiled as if it was written
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 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
File: gnugo.info, Node: Grid optimization, Next: Joseki Compiler, Prev: Details, Up: Patterns
9.15 The "Grid" Optimization
============================
The comparisons between pattern and board are performed as 2-bit
bitwise operations. Therefore they can be performed in parallel,
16-at-a-time on a 32-bit machine.
Suppose the board is layed out as follows :
which is internally stored internally in a 2d array (binary)
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 :
???????? ???????? ???????? ...
??001000 00100001 10000100
??101010 10101010 10101001
??001000 00100000 10000001
Where '??' is off the board.
We can store these 32-bit composites in a 2d merged-board array,
substituting the illegal value %11 for '??'.
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
File: gnugo.info, Node: Joseki Compiler, Next: Ladders in Joseki, Prev: Grid optimization, Up: Patterns
GNU Go includes a joseki compiler in `patterns/joseki.c'. This processes
an SGF file (with variations) and produces a sequence of patterns which
can then be fed back into mkpat. The joseki database is currently in
files in `patterns/' called `hoshi.sgf', `komoku.sgf', `sansan.sgf',
`mokuhazushi.sgf' and `takamoku.sgf'. This division can be revised
The SGF files are transformed into the pattern database `.db' format
by the program in `joseki.c'. These files are in turn transformed into C
code by the program in `mkpat.c' and the C files are compiled and linked
Not every node in the SGF file contributes a pattern. The nodes which
contribute patterns have the joseki in the upper right corner, with the
boundary marked with a square mark and other information to determine
the resulting pattern marked in the comments.
The intention is that the move valuation should be able to choose
between the available variations by normal valuation. When this fails
the primary workaround is to use shape values to increase or decrease
the value. It is also possible to add antisuji variations to forbid
popular suboptimal moves. As usual constraints can be used, e.g. to
condition a variation on a working ladder.
The joseki format has the following components for each SGF node:
* A square mark (`SQ' or `MA' property) to decide how large part of
the board should be included in the pattern.
* A move (`W' or `B' property) with the natural interpretation. If
the square mark is missing or the move is a pass, no pattern is
* Optional labels (`LB' property), which must be a single letter
each. If there is at least one label, a constraint diagram will be
produced with these labels.
* A comment (`C' property). As the first character it should have
one of the following characters to decide its classification:
- `S' or `J' - standard move
- `s' or `j' - lesser joseki
- `t' - minor joseki move (tenuki OK)
- `0' - antisuji (`A' can also be used)
The rest of the line is ignored, as is the case of the letter. If
neither of these is found, it's assumed to be a standard joseki
In addition to this, rows starting with the following characters
- `#' - Comments. These are copied into the patterns file,
- `;' - Constraints. These are copied into the patterns file,
below the constraint diagram.
- `>' - Actions. These are copied into the patterns file, below
- `:' - 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 pattern 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
the generated pattern will have a colon line
File: gnugo.info, Node: Ladders in Joseki, Next: Corner Matcher, Prev: Joseki Compiler, Up: Patterns
As an example of how to use autohelpers with the Joseki compiler, we
consider an example where a Joseki is bad if a ladder fails. Assume we
have the taisha and are considering connecting on the outside with the
But this is bad unless we have a ladder in our favor. To check this
we add a constraint which may look like
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 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
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:
The appropriate constraint (autohelper macro) will then be added to
File: gnugo.info, Node: Corner Matcher, Next: Editing Patterns, Prev: Ladders in Joseki, Up: Patterns
GNU Go uses a special matcher for joseki patterns. It has certain
constraints on the patterns it can match, but is much faster and takes
far less space to store patterns than the standard matcher.
Patterns used with corner matcher have to qualify the following
* They must be matchable only at a corner of the board (hence the
* They can consist only of `O', `X' and `.' elements.
* Of all pattern values (*note Pattern Values::), corner matcher only
support `shape(x)'. This is not because the matcher cannot handle
other values in principle, just they are currently not used in
Corner matcher was specifically designed for joseki patterns and
they of course satisfy all the conditions above. With some
modifications corner matcher could be used for fuseki patterns as well,
but fullboard matcher does its work just fine.
The main idea of the matcher is very same to the one of DFA matcher
(*note Pattern matching with DFA::): check all available patterns at
once, not a single pattern at a time. A modified version of DFA
matcher could be used for joseki pattern matching, but its database
would be very large. Corner matcher capitalizes on the fact that there
are relatively few stones in each such pattern.
Corner pattern database is organized into a tree. Nodes of the tree
are called "variations". Variations represent certain sets of stones
in a corner of the board. Root variation corresponds to an empty
corner and a step down the tree is equivalent to adding a stone to the
corner. Each variation has several properties:
- stone position relative to the corner,
- a flag determining whether the stone color must be equal to the
first matched stone color,
- number of stones in the corner area (see below) of the variation
By corner area we define a rectangle which corners are the current
corner of the board and the position of the stone (inclusive). For
instance, if the current board corner is A19 then corner area of a
stone at C18 consists of A18, A19, B18, B19, C18 and C19.
Variation which is a direct child of the root variation matches if
there is any stone at the variation position and the stone is alone in
Variation at a deeper level of the tree matches if there is a stone
of specified color in variation position and the number of stones in its
corner area is equal to the number specified in variation structure.
When a certain variation matches, all its children has to be checked
All leaf variations and some inner ones have patterns attached to
them. For a pattern to match, it is required that its _parent_
variation matches. In addition, it is checked that pattern is being
matched for the appropriate color (using its variation "stone color"
field) and that the number of stones in the area where the pattern is
being matched is indeed equal to the number of stones in the pattern.
The "stone position" property of the pattern variation determines the
move suggested by the pattern.
Consider this joseki pattern which has four stones:
To encode it for the corner matcher, we have to use five variations,
each next being a child of previous:
Tree level Position Color Number of stones
The fifth variation should have an attached pattern. Note that the
stone color for the fifth variation is "same" because the first matched
stone for this pattern is `O' which stands for the stones of the player
to whom moves are being suggested with `*'.
The tree consists of all variations for all patterns combined
together. Variations for each patterns are sorted to allow very quick
tree branch rejection and at the same time keep the database small
enough. More details can be found in comments in file `mkpat.c'
Corner matcher resides in `matchpat.c' in two functions:
`corner_matchpat()' and `do_corner_matchpat()'. The former computes
`num_stones[]' array which holds number of 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 responsible 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 generator consists of several functions, most
important are: `corner_best_element()', `corner_variation_new()',
`corner_follow_variation()' and `corner_add_pattern()'.
File: gnugo.info, Node: Editing Patterns, Prev: Corner Matcher, Up: Patterns
9.19 Emacs Mode for Editing Patterns
====================================
If you use GNU Emacs (XEmacs might work too), you can try a special
mode for editing GNU Go pattern databases. The mode resides in
Copy the file to `emacs/site-lisp' directory. You can then load the
mode with `(require 'gnugo-db)'. It makes sense to put this line into
your configuration file (`~/.emacs'). You can either use
`gnugo-db-mode' command to switch to pattern editing mode, or use the
following code snippet to make Emacs do this automatically upon opening
a file with `.db' suffix:
'(("\\.db\\'" . gnugo-db-mode))))
Pattern editing mode provides the following features:
- highlighting of keywords (`Pattern', `goal_elements' and
`callback_data') and comments,
- making paragraphs equal to patterns (`M-h', `M-{', `M-}' and
others operate on patterns),
- commands for pattern creation with automatic name selection (`C-c
C-p') and copying main diagram to constraint diagram (`C-c C-c'),
- automated indentation of constraints and side comments (pattern
File: gnugo.info, Node: DFA, Next: Utility Functions, Prev: SGF, Up: Top
10 The DFA pattern matcher
**************************
In this chapter, we describe the principles of the GNU Go DFA pattern
matcher. The aim of this system is to permit a fast pattern matching
when it becomes time critical like in owl module (*note The Owl
Code::). Since GNU Go 3.2, this is enabled by default. You can still
get back the traditional pattern matcher by running `configure
--disable-dfa' and then recompiling GNU Go.
Otherwise, a finite state machine called a Deterministic Finite
State Automaton (*note What is a DFA::) will be built off line from the
pattern database. This is used at runtime to speedup pattern matching
(*note Pattern matching with DFA:: and *note Incremental Algorithm::).
The runtime speedup is at the cost of an increase in memory use and
* Introduction to the DFA:: Scanning the board along a path
* What is a DFA:: A recall of language theory.
* Pattern matching with DFA:: How to retrieve go patterns with a DFA?
* Building the DFA:: Playing with explosives.
* Incremental Algorithm:: The joy of determinism.
* DFA Optimizations:: Some possible optimizations.
File: gnugo.info, Node: Introduction to the DFA, Next: What is a DFA, Up: DFA
10.1 Introduction to the DFA
============================
The general idea is as follows:
For each intersection of the board, its neighbourhood is scanned
following a predefined path. The actual path used does not matter very
much; GNU Go uses a spiral as shown below.
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 (*note What is a DFA::).
Reading the board following a predefined path reduces the two
dimentional pattern matching to a linear text searching problem. For
scanned following the path
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.
File: gnugo.info, Node: What is a DFA, Next: Pattern matching with DFA, Prev: Introduction to the DFA, Up: DFA
The acronym DFA means Deterministic Finite state Automaton (See
`http://www.eti.pg.gda.pl/~jandac/thesis/node12.html' or `Hopcroft &
Ullman "Introduction to Language Theory"' for more details). DFA are
common tools in compilers design (Read `Aho, Ravi Sethi, Ullman
"COMPILERS: Principles, Techniques and Tools"' for a complete
introduction), a lot of powerfull text searching algorithm like
`Knuth-Morris-Pratt' or `Boyer-Moore' algorithms are based on DFA's
(See `http://www-igm.univ-mlv.fr/~lecroq/string/' for a bibliography of
pattern matching algorithms).
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
The best way to represent a DFA is to draw its transition graph: the
pattern "????..X" is recognized by the following DFA:
.,X,O .,X,O .,X,O .,X,O . . X
[1]------>[2]----->[3]----->[4]----->[5]--->[6]--->[7]--->[8 OK!]
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"
Adding a pattern like "XXo" ('o' is a wildcard for not 'X') will
transform directly the automaton by synchronization product (*note
Building the DFA::). Consider the following DFA:
Start .,O .,X,O .,O,X .,X,O . . X
[1]---->[2]----->[3]----->[4]------>[5]--->[6]---->[7]--->[8 OK!]
--------->[9]------>[A]--->[B OK!]-
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 (*note Building the DFA::) is only possible on
Start .,O .,X,O .,O,X .,X,O . . X
[1]---->[2]----->[3]----->[4]------>[5]--->[6]---->[7]--->[8 OK!]
| | X | | |X,O | .,O |X,.,O
| X | X | O,. | \ / \ / \ /
--------->[9]------>[A]--->[B OK!]- [0 Error state !]
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
----------------------------------------------------
8 | 0 | 0 | 0 | 0 | Found pattern "????..X"
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:
int next[4]; /* transitions for EMPTY, BLACK, WHITE and OUT_BOARD */
attrib_t *indexes; /* Array of pattern indexes */
state_t *states; /* Array of states */
File: gnugo.info, Node: Pattern matching with DFA, Next: Building the DFA, Prev: What is a DFA, Up: DFA
10.3 Pattern matching with DFA
==============================
Recognizing with a DFA is very simple and thus very fast (See
'`scan_for_pattern()'' in the '`engine/matchpat.c'' file).
Starting from the start state, we only need to read the board
following the spiral path, jump from states to states following the
transitions labelled by the values read on the board and collect the
patterns indexes on the way. If we reach the error state (zero), it
means that no more patterns will be matched. The worst case complexity
of this algorithm is o(m) where m is the size of the biggest pattern.
Here is an example of scan:
First we build a minimal DFA recognizing these patterns: "X..X",
"X???", "X.OX" and "X?oX". Note that wildcards like '?','o', or 'x'
give multiple out-transitions.
----------------------------------------------------
state | . | O | X | # | att
----------------------------------------------------
6 | 0 | 0 | 0 | 0 | 4 2 1
8 | 0 | 0 | 0 | 0 | 4 2 3
----------------------------------------------------
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....
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.
File: gnugo.info, Node: Building the DFA, Next: Incremental Algorithm, Prev: Pattern matching with DFA, Up: DFA
The most flavouring point is the building of the minimal DFA
recognizing a given set of patterns. To perform the insertion of a new
pattern into an already existing DFA one must completly rebuild the
DFA: the principle is to build the minimal CDFA recognizing the new
pattern to replace the original CDFA with its "synchronised product" by
We first give a formal definition: Let L be the left CDFA and R be
the right one. Let B be the "synchronised product" of L by R. Its
states are the couples (l,r) where l is a state of L and r is a state
of R. The state (0,0) is the error state of B and the state (1,1) is
its initial state. To each couple (l,r) we associate the union of
patterns recognized in both l and r. The transitions set of B is the
set of transitions (l1,r1)--a-->(l2,r2) for each symbol 'a' such that
both l1--a-->l2 in L and r1--a-->r2 in R.
The maximal number of states of B is the product of the number of
states of L and R but almost all this states are non reachable from the
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
It is possible to construct a special pattern database that
generates an "explosive" automaton: the size of the DFA is in the worst
case exponential in the number of patterns it recognizes. But it
doesn't occur in pratical situations: the DFA size tends to be
"stable". By "stable" we mean that if we add a pattern which greatly
increases the size of the DFA it also increases the chance that the
next added pattern does not increase its size at all. Nevertheless
there are many ways to reduce the size of the DFA. Good compression
methods are explained in `Aho, Ravi Sethi, Ullman "COMPILERS:
Principles, Techniques and Tools" chapter Optimization of DFA-based
File: gnugo.info, Node: Incremental Algorithm, Next: DFA Optimizations, Prev: Building the DFA, Up: DFA
10.5 Incremental Algorithm
==========================
The incremental version of the DFA pattern matcher is not yet
implemented in GNU Go but we explain here how it will work. By
definition of a deterministic automaton, scanning the same string will
reach the same states every time.
Each reached state during pattern matching is stored in a stack
`top_stack[i][j]' and `state_stack[i][j][stack_idx]' We use one stack
by intersection `(i,j)'. A precomputed reverse path list allows to
know for each couple of board intersections `(x,y)' its position
`reverse(x,y)' in the spiral scan path starting from `(0,0)'.
When a new stone is put on the board at `(lx,ly)', the only work of
for(each stone on the board at (i,j))
if(reverse(lx-i,ly-j) < top_stack[i][j])
begin the dfa scan from the state
state_stack[i][j][reverse(lx-i,ly-j)];
In most situations reverse(lx-i,ly-j) will be inferior to
top_stack[i][j]. This should speedup a lot pattern matching.
File: gnugo.info, Node: DFA Optimizations, Prev: Incremental Algorithm, Up: DFA
10.6 Some DFA Optimizations
===========================
The DFA is constructed to minimize jumps in memory making some
assumptions about the frequencies of the values: the EMPTY value is
supposed to appear often on the board, so the the '.' transition are
almost always successors in memory. The OUT_BOARD are supposed to be
rare, so '#' transitions will almost always imply a big jump.
File: gnugo.info, Node: Tactical Reading, Next: Pattern Based Reading, Prev: Patterns, Up: Top
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'.
* Reading Basics:: Reading Basics
* Hashing:: Hashing of positions
* Persistent Cache:: Persistent Reading Cache
* A Ko Example:: A Ko Example
* Another Ko Example:: Another Ko Example
* Alternate Komaster Schemes:: Alternate Komaster Schemes
* Superstrings:: Superstrings
* Debugging:: Debugging the reading code
* Connection Reading:: Connection Reading
File: gnugo.info, Node: Reading Basics, Next: Hashing, Up: Tactical Reading
What we call _Tactical Reading_ is the analysis whether there is a
direct capture of a single string, or whether there is a move to prevent
If the reading module finds out that the string can get captured,
this answer should (usually) be trusted. However, if it says it can be
defended, this does not say as much. It is often the case that such a
string has no chance to make a life, but that it cannot be captured
within the horizon (and the cutoff heuristics) of the tactical reading.
The tactical reading is done by the functions in `engine/reading.c'.
It is a minimax search that declares win for the attacker once he can
physically take the string off board, whereas the defense is considered
successful when the string has sufficiently many liberties. A string
with five liberties is always considered alive. At higher depth within
the search tree even fewer liberties cause GNU Go to give up the attack,
The reading code makes use of a stack onto which board positions can
be pushed. The parameter `stackp' is zero if GNU Go is examining the
true board position; if it is higher than zero, then GNU Go is
examining a hypothetical position obtained by playing several moves.
The most important public reading functions are `attack' and
`find_defense'. These are wrappers for functions `do_attack' and
`do_find_defense' which are declared statically in `reading.c'. The
functions `do_attack' and `do_find_defense' call each other recursively.
11.1.1 Organization of the reading code
---------------------------------------
The function `do_attack' and `do_find_defense' are wrappers themselves
and call `attack1', `attack2', `attack3' or `attack4' resp. `defend1',
`defend1', `defend1' or `defend1' depending on the number of liberties.
These are fine-tuned to generate and try out the moves in an
efficient order. They generate a few moves themselves (mostly direct
liberties of the string), and then call helper functions called
`..._moves' which suggest less obvious moves. Which of these functions
get called depends on the number of liberties and of the current search
The return codes of the reading (and owl) functions and owl can be `0',
`KO_B', `KO_A' or `WIN'. Each reading function determines whether a
particular player (assumed to have the move) can solve a specific
problem, typically attacking or defending a string.
A return code of `WIN' means success, 0 failure, while `KO_A' and
`KO_B' are success conditioned on ko. A function returns `KO_A' if the
position results in ko and that the player to move will get the first
ko capture (so the opponent has to make the first ko threat). A return
code of `KO_B' means that the player to move will have to make the
If GNU Go is compiled with the configure option
`--enable-experimental-owl-ext' then the owl functions also have
possible return codes of `GAIN' and `LOSS'. A code of `GAIN' means that
the attack (or defense) does not succeed, but that in the process of
trying to attack or defend, an opponent's worm is captured. A code of
`LOSS' means that the attack or defense succeeds, but that another
friendly worm dies during the attack or defense.
11.1.3 Reading cutoff and depth parameters
------------------------------------------
Depth of reading is controlled by the parameters `depth' and
`branch_depth'. The `depth' has a default value `DEPTH' (in
`liberty.h'), which is set to 16 in the distribution, but it may also
be set at the command line using the `-D' or `--depth' option. If
`depth' is increased, GNU Go will be stronger and slower. GNU Go will
read moves past depth, but in doing so it makes simplifying assumptions
that can cause it to miss moves.
Specifically, when `stackp > depth', GNU Go assumes that as soon as
the string can get 3 liberties it is alive. This assumption is
sufficient for reading ladders.
The `branch_depth' is typically set a little below `depth'. Between
`branch_depth' and `depth', attacks on strings with 3 liberties are
considered, but branching is inhibited, so fewer variations are
%%Currently the reading code does not try to defend a string by
%attacking a boundary string with more than two liberties. Because %of
this restriction, it can make oversights. A symptom of this is %two
adjacent strings, each having three or four liberties, each %classified
as `DEAD'. To resolve such situations, a function %`small_semeai()' (in
`engine/semeai.c') looks for such %pairs of strings and corrects their
The `backfill_depth' is a similar variable with a default 12. Below
this depth, GNU Go will try "backfilling" to capture stones. For
example in this situation:
.OOOOOO. on the edge of the board, O can capture X but
OOXXXXXO in order to do so he has to first play at a in
.aObX.XO preparation for making the atari at b. This is
-------- called backfilling.
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
* `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 *note Return
* `find_defense(int str, int *move)'
Attempts to find a move that will save the string at `str'. It
returns true if such a move is found, with `*move' the
location of the saving move (unless `*move' is a null
pointer). It is not checked that tenuki defends, so this may
give an erroneous answer if `!attack(str)'. Returns `KO_A'
or `KO_B' if the result depends on ko *Note Return Codes::.
* `safe_move(int str, int color)' :
The function `safe_move(str, color)' checks whether a move at
`str' is illegal or can immediately be captured. If
`stackp==0' the result is cached. If the move only can be
captured by a ko, it's considered safe. This may or may not
File: gnugo.info, Node: Hashing, Next: Persistent Cache, Prev: Reading Basics, Up: Tactical Reading
11.2 Hashing of Positions
=========================
To speed up the reading process, we note that a position can be reached
in several different ways. In fact, it is a very common occurrence
that a previously checked position is rechecked, often within the same
search but from a different branch in the recursion tree.
This wastes a lot of computing resources, so in a number of places,
we store away the current position, the function we are in, and which
worm is under attack or to be defended. When the search for this
position is finished, we also store away the result of the search and
which move made the attack or defense succeed.
All this data is stored in a hash table, sometimes also called a
transposition table, where Go positions are the key and results of the
reading for certain functions and groups are the data. You can increase
the size of the Hash table using the `-M' or `--memory' option *note
The hash table is created once and for all at the beginning of the
game by the function `hashtable_new()'. Although hash memory is thus
allocated only once in the game, the table is reinitialized at the
beginning of each move by a call to `hashtable_clear()' from
* Hash Calculation:: Calculation of the hash value
* Hash Organization:: Organization of the hash table
* Hash Structures:: Structures in `hash.h'
File: gnugo.info, Node: Hash Calculation, Next: Hash Organization, Up: Hashing
11.2.1 Calculation of the hash value
------------------------------------
The hash algorithm is called Zobrist hashing, and is a standard
technique for go and chess programming. The algorithm as used by us
1. First we define a "go position". This positions consists of
* the actual board, i.e. the locations and colors of the stones
* A "ko point", if a ko is going on. The ko point is defined as
the empty point where the last single stone was situated
It is not necessary to specify the color to move (white or black)
as part of the position. The reason for this is that read results
are stored separately for the various reading functions such as
`attack3', and it is implicit in the calling function which player
2. For each location on the board we generate random numbers:
* A number which is used if there is a white stone on this
* A number which is used if there is a black stone on this
* A number which is used if there is a ko on this location
These random numbers are generated once at initialization time and
then used throughout the life time of the hash table.
3. The hash key for a position is the XOR of all the random numbers
which are applicable for the position (white stones, black stones,
File: gnugo.info, Node: Hash Organization, Next: Hash Structures, Prev: Hash Calculation, Up: Hashing
11.2.2 Organization of the hash table
-------------------------------------
The hash table consists of 3 parts:
* An area which contains so called "Hash Nodes". Each hash node
- A go position as defined above.
- A computed hash value for the position
- A pointer to Read Results (see below)
- A pointer to another hash node.
* An area with so called Read Results. These are used to store
which function was called in the go position, which string was
under attack or to be defended, and the result of the reading.
Each Read Result contains:
- the function ID (an int between 0 and 255), the position of
the string under attack and a depth value, which is used to
determine how deep the search was when it was made, packed
- The result of the search (a numeric value) and a position to
play to get the result packed into one 32 bit integer.
- A pointer to another Read Result.
* An array of pointers to hash nodes. This is the hash table proper.
When the hash table is created, these 3 areas are allocated using
`malloc()'. When the hash table is populated, all contents are taken
from the Hash nodes and the Read results. No further allocation is done
and when all nodes or results are used, the hash table is full.
Nothing is deleted from the hash table except when it is totally
emptied, at which point it can be used again as if newly initialized.
When a function wants to use the hash table, it looks up the current
position using `hashtable_search()'. If the position doesn't already
exist there, it can be entered using
`hashtable_enter_position()'.
Once the function has a pointer to the hash node containing a
function, it can search for a result of a previous search using
`hashnode_search()'. If a result is found, it can be used, and if not,
a new result can be entered after a search using `hashnode_new_result()'.
Hash nodes which hash to the same position in the hash table
(collisions) form a simple linked list. Read results for the same
position, created by different functions and different attacked or
defended strings also form a linked list.
This is deemed sufficiently efficient for now, but the representation
of collisions could be changed in the future. It is also not
determined what the optimum sizes for the hash table, the number of
positions and the number of results are.
File: gnugo.info, Node: Hash Structures, Prev: Hash Organization, Up: Hashing
The basic hash structures are declared in `engine/hash.h' and
typedef struct hashposition_t {
Compacttype board[COMPACT_BOARD_SIZE];
Represents the board and optionally the location of a ko, which is
an illegal move. The player whose move is next is not recorded.
Represents the return value of a function (`hashval') and the board
typedef struct read_result_t {
struct read_result_t *next;
The data1 field packs into 32 bits the following fields:
komaster: 2 bits (EMPTY, BLACK, WHITE, or GRAY)
kom_pos : 10 bits (allows MAX_BOARD up to 31)
routine : 4 bits (currently 10 different choices)
The data2 field packs into 32 bits the following fields:
status : 2 bits (0 free, 1 open, 2 closed)
The `komaster' and `(kom_pos)' field are documented in *Note Ko::.
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
typedef struct hashnode_t {
struct hashnode_t * next;
The hash table consists of hash nodes. Each hash node consists of
The hash value for the position it holds, the position itself and the
actual information which is purpose of the table from the start.
There is also a pointer to another hash node which is used when the
nodes are sorted into hash buckets (see below).
typedef struct hashtable {
size_t hashtablesize; /* Number of hash buckets */
Hashnode ** hashtable; /* Pointer to array of hashnode lists */
int num_nodes; /* Total number of hash nodes */
Hashnode * all_nodes; /* Pointer to all allocated hash nodes. */
int free_node; /* Index to next free node. */
int num_results; /* Total number of results */
Read_result * all_results; /* Pointer to all allocated results. */
int free_result; /* Index to next free result. */
The hash table consists of three parts:
* The hash table proper: a number of hash buckets with collisions
being handled by a linked list.
* The hash nodes. These are allocated at creation time and are
never removed or reallocated in the current implementation.
* The results of the searches. Since many different searches can be
done in the same position, there should be more of these than hash
File: gnugo.info, Node: Persistent Cache, Next: Ko, Prev: Hashing, Up: Tactical Reading
11.3 Persistent Reading Cache
=============================
Some calculations can be safely saved from move to move. If the
opponent's move is not close to our worm or dragon, we do not have to
reconsider the life or death of that group on the next move. So the
result is saved in a persistent cache. Persistent caches are used for
are used in the engine for several types of read results.
In this section we will discuss the persistent caching of tactical
reading but the same principles apply to the other persistent caches.
Persistent caching is an important performance feature. However it
can lead to mistakes and debugging problems--situations where GNU Go
generates the right move during debugging but plays a wrong move during
a game. If you suspect a persistent cache effect you may try loading
the sgf file with the `--replay' option and see if the mistake is
repeated (*note Invoking GNU Go::).
The function `store_persistent_cache()' is called only by `attack'
and `find_defense', never from their static recursive counterparts
`do_attack' and `do_defend'. The function
`store_persistent_reading_cache()' attempts to cache the most expensive
reading results. The function `search_persistent_reading_cache'
attempts to retrieve a result from the cache.
If all cache entries are occupied, we try to replace the least useful
one. This is indicated by the score field, which is initially the
number of nodes expended by this particular reading, and later
multiplied by the number of times it has been retrieved from the cache.
Once a (permanent) move is made, a number of cache entries
immediately become invalid. These are cleaned away by the function
`purge_persistent_reading_cache().' To have a criterion for when a
result may be purged, the function `store_persistent_cache()' computes
the "reading shadow" and "active area". If a permanent move is
subsequently played in the active area, the cached result is
invalidated. We now explain this algorithm in detail.
The "reading shadow" is the concatenation of all moves in all
variations, as well as locations where an illegal move has been tried.
Once the read is finished, the reading shadow is expanded to the
"active area" which may be cached. The intention is that as long as no
stones are played in the active area, the cached value may safely be
Here is the algorithm used to compute the active area. This
algorithm is in the function `store_persistent_reading_cache()'. The
most expensive readings so far are stored in the persistent cache.
* The reading shadow and the string under attack are marked with the
character `1'. We also include the successful move, which is most
often a part of the reading shadow, but sometimes not, for example
with the function `attack1()'.
* Next the reading shadow is expanded by marking strings and empty
vertices adjacent to the area marked `1' with the character `2'.
* Next vertices adjacent to empty vertices marked `2' are labelled
* Next all vertices adjacent to previously marked vertices. These are
marked `-1' instead of the more logical `4' because it is slightly
* If the stack pointer is >0 we add the moves already played from the
File: gnugo.info, Node: Ko, Next: A Ko Example, Prev: Persistent Cache, Up: Tactical Reading
The principles of ko handling are the same for tactical reading and owl
We have already mentioned (*note Reading Basics::) 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'. 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:
Here if `m' is the location of `kom_pos', then the move at `*' is
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
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.
- 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
- 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.
- 2a) Only nested ko captures are allowed. Kom_pos is moved to
- 2b) If komaster fills the ko at kom_pos then komaster reverts
Play at kom_pos is not allowed. Any other ko capture is
allowed. If O takes another ko, komaster becomes GRAY_X.
* 4. Komaster is GRAY_O or GRAY_X:
Ko captures are not allowed. If the ko at kom_pos is filled
then the komaster reverts to EMPTY.
* 5. Komaster is WEAK_KO:
- 5a) After a non-ko move komaster reverts to EMPTY.
- 5b) Unconditional ko capture is only allowed if it is nested
Komaster is changed to WEAK_X and kom_pos to the old
- 5c) Conditional ko capture is allowed according to the rules
File: gnugo.info, Node: A Ko Example, Next: Another Ko Example, Prev: Ko, Up: Tactical Reading
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
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
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
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
8 . . . . . . . . komaster: BLACK
7 . . O . . . . . kom_pos: A2
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
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
File: gnugo.info, Node: Another Ko Example, Next: Alternate Komaster Schemes, Prev: A Ko Example, Up: Tactical Reading
We now consider an example to show why the komaster is reset to `EMPTY'
if the ko is resolved in the komaster's favor. This means that the ko
is filled, or else that is becomes no longer a ko and it is illegal for
the komaster's opponent to play there.
The position resulting under consideration is in the file
`regressions/games/ko5.sgf'. This is the position:
We recommend studying this example by examining the variation file
gnugo -l ko5.sgf --quiet --decide-string L1 -o vars.sgf
The correct resolution is that H1 attacks L1 unconditionally while K2
defends it with ko (code `KO_A').
After Black (X) takes the ko at K3, white can do nothing but retake
the ko conditionally, becoming komaster. B cannot do much, but in one
variation he plays at K4 and W takes at H1. The following position
Now it is important the `O' is no longer komaster. Were `O' still
komaster, he could capture the ko at N3 and there would be no way to
File: gnugo.info, Node: Alternate Komaster Schemes, Next: Superstrings, Prev: Another Ko Example, Up: Tactical Reading
11.7 Alternate Komaster Schemes
===============================
The following alternate schemes have been proposed. It is assumed that
`O' is the player about to move.
11.7.1 Essentially the 2.7.232 scheme.
--------------------------------------
- Unconditional ko capture is allowed. Komaster remains EMPTY.
- Conditional ko capture is allowed. Komaster is set to O and
`kom_pos' to the location of the ko, where a stone was just
- Conditional ko capture is not allowed.
- Unconditional ko capture is allowed. Komaster parameters
- Conditional ko capture is not allowed.
- Unconditional ko capture is allowed except for a move at
`kom_pos'. Komaster parameters unchanged.
11.7.2 Revised 2.7.232 version
------------------------------
- Unconditional ko capture is allowed. Komaster remains EMPTY.
- Conditional ko capture is allowed. Komaster is set to `O' and
`kom_pos' to the location of the ko, where a stone was just
- Ko capture (both kinds) is allowed only if after playing the
move, `is_ko(kom_pos, X)' returns false. In that case,
`kom_pos' is updated to the new ko position, i.e. the stone
- Conditional ko capture is not allowed.
- Unconditional ko capture is allowed except for a move at
`kom_pos'. Komaster parameters unchanged.
File: gnugo.info, Node: Superstrings, Next: Debugging, Prev: Alternate Komaster Schemes, Up: Tactical Reading
A _superstring_ is an extended string, where the extensions are through
the following kinds of connections:
1. Solid connections (just like ordinary string).
2. Diagonal connection or one space jump through an intersection
where an opponent move would be suicide or self-atari.
4. Diagonal connection where both adjacent intersections are empty.
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
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 encountered 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.
File: gnugo.info, Node: Debugging, Next: Connection Reading, Prev: Superstrings, Up: Tactical Reading
11.9 Debugging the reading code
===============================
The reading code searches for a path through the move tree to determine
whether a string can be captured. We have a tool for investigating this
with the `--decidestring' option. This may be run with or without an
`gnugo -t -l [input file name] -L [movenumber] --decidestring [location]'
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 of the number of
variations read. The `-t' is necessary, or else GNU Go will not report
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
If you are using GDB to debug GNU Go you may find it less confusing
to compile without optimization. The optimization sometimes changes the
order in which program 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
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) set args -l [filename] -L [move number] --decidestring [location]
will then jump to the location in question.
Actually the attack variations and defense variations are numbered
separately. (But `find_defense()' is only run if `attack()' succeeds,
so the defense variations may or may not exist.) It is redundant to
have to tbreak main each time. So there are two macros avar and dvar.
restarts the program, and jumps to the 17-th attack variation.
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:
`dump' will print the move stack.
`nv' moves to the next variation
`ascii i j' converts (i,j) to ascii
#######################################################
############### .gdbinit file ###############
#######################################################
# this command displays the stack
# display the name of the move in ascii
set gprintf("%o%m\n",$arg0,$arg1)
# display the all information about a dragon
set ascii_report_dragon("$arg0")
set ascii_report_worm("$arg0")
# move to the next variation
# move forward to a particular variation
while (count_variations < $arg0)
# restart, jump to a particular attack variation
tbreak sgffile_decidestring
# restart, jump to a particular defense variation
tbreak sgffile_decidestring
File: gnugo.info, Node: Connection Reading, Prev: Debugging, Up: Tactical Reading
GNU Go does reading to determine if strings can be connected. The
algorithms for this are in `readconnect.c'. As with the reading code,
the connection code is not pattern based.
The connection code is invoked by the engine through the functions:
* `int string_connect(int str1, int str2, int *move)'
Returns `WIN' if `str1' and `str2' can be connected.
* `int disconnect(int str1, int str2, int *move)'
Returns `WIN' if `str1' and `str2' can be disconnected.
To see the connection code in action, you may try the following
gnugo --quiet -l connection3.sgf --decide-connection M3/N7 -o vars.sgf
(The file `connection3.sgf' is in `regression/games'.) Examine the
sgf file produced by this to see what kind of reading is done by the
functions `string_connect()' and `string_disconnect()', which are
called by the function `decide_connection'.
One use of the connection code is used is through the autohelper
macros `oplay_connect', `xplay_connect', `oplay_disconnect' and
`xplay_disconnect' which are used in the connection databases.
File: gnugo.info, Node: Pattern Based Reading, Next: Influence, Prev: Tactical Reading, Up: Top
In the tactical reading code in `reading.c', the code generating the
moves which are tried are all hand coded in C, for efficiency. There is
much to be said for another type of reading, in which the moves to be
tried are generated from a pattern database.
GNU Go does three main types of pattern based reading. First, there
is the OWL code (Optics with Limit Negotiation) which attempts to read
out to a point where the code in `engine/optics.c' (*note Eyes::) can
be used to evaluate it. Like the tactical reading code, a persistent
cache is employed to maintain some of the owl data from move to move.
This is an essential speedup without which GNU Go would play too slowly.
Secondly, there is the `engine/combination.c' which attempts to find
combinations--situations where a series of threats eventually
culminates in one that cannot be parried.
Finally there is the semeai module. A *semeai* is a capturing race
between two adjacent DEAD or CRITICAL dragons of opposite colors. The
principal function, `owl_analyze_semeai()' is contained in `owl.c'.
Due to the complex nature of semeais, the results of this function are
more frequently wrong than the usual owl code.
* The Owl Code:: Life and death reading
* Combinations:: Combinations
projects / sgk-go / blob