GNU Go Documentation

GNU GO

This manual documents GNU Go, a Go program and its sources. This is Edition 3.6 of the GNU Go Program Documentation

Copyright 1999, 2000, 2001, 2002, 2003, 2004 and 2005, The Free Software Foundation, Inc. Permission is granted to make and distribute verbatim or modified copies of this manual is given provided that the terms of the GNU Free Documentation License (see section A.2 GNU FREE DOCUMENTATION LICENSE) are respected.

Permission is granted to make and distribute verbatim or modified copies of the program GNU Go is given provided the terms of the GNU General Public License (see section A.1 GNU GENERAL PUBLIC LICENSE) are respected.

1. Introduction

This is GNU Go 3.6, 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.

1.1 About GNU Go and this Manual

The challenge of Computer Go is not to beat the computer, but to program the computer.

In Computer Chess, strong programs are capable of playing at the highest level, even challenging such a player as Garry Kasparov. No Go program even as strong as amateur shodan exists. The challenge is to write such a program.

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.

GNU Go is getting stronger. GNU Go 3.6 plays at about the level of 9 kyu.

Until now, 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.

1.2 Copyrights

Copyright 1999, 2000, 2001, 2002, 2003, 2004 and 2005 by the Free Software Foundation except as noted below.

All files are under the GNU General Public License (see section A.1 GNU GENERAL PUBLIC LICENSE), except `gmp.c', `gmp.h', `gtp.c', `gtp.h', the files `interface/html/*' and `win/makefile.win'.

The files `gtp.c' and `gtp.h' are copyright the Free Software Foundation. In the interests of promoting the Go Text Protocol these two files are licensed under a less restrictive license than the GPL and are free for unrestricted use (see section A.3 The Go Text Protocol 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.

The files `interface/html/*' are not part of GNU Go but are a separate program and are included in the distribution for the convenience of anyone looking for a CGI interface to GNU Go. They were placed in the public domain by their author, Douglas Ridgway, and are free for unrestricted use.

The files `regression/games/golois/*sgf' are copyright Tristan Cazenave and are included with his permission.

The SGF files in `regression/games/handtalk/' are copyright Jessie Annala and are used with permission.

The SGF files in `regression/games/mertin13x13/' are copyright Stefan Mertin and are used with permission.

The remaining SGF files are either copyright by the FSF or are in the public domain.

1.3 Authors

GNU Go maintainers are Daniel Bump, Gunnar Farneback and Arend Bayer. GNU Go authors (in chronological order of contribution) are Man Li, Wayne Iba, Daniel Bump, David Denholm, Gunnar Farneb@"ack, 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, Måns Ullerstam, Arend Bayer, Trevor Morris, Evan Berggren Daniel, Fernando Portela, Paul Pogonyshev, S.P. Lee and Stephane Nicolet and Martin Holters.

1.4 Thanks

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, Måns Ullerstam, Don Wagner and Yin Zheng for help with Visual C++.

Thanks to Alan Crossman, Stephan Somogyi, Pierce Wetter and Mathias Wagner for help with Macintosh. And thanks to Marco Scheurer and Shigeru Mabuchi for helping us find various problems.

Thanks to Jessie Annala for the Handtalk games.

Special thanks to Ebba Berggren for creating our logo, based on a design by Tanguy 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.

1.5 The GNU Go Task List

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 (see section A.1 GNU GENERAL PUBLIC LICENSE). 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 Farneb@"ack (gunnar@lysator.liu.se), to get more information and the papers to sign.

Below is a list of things YOU could work on. We are already working on some of these tasks, but don't let that stop you. Please contact us or the person assigned to task for further discussion.

1.5.1 General

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

1.5.2 Smaller projects

These issues are of tactical nature, i.e. they concern some specific feature or the infrastructure of the engine. Some of these are quiet small, maybe doable in a day for an experienced GNU Go programmer. They might also be useful project to start with for a new project member. Some of them are bigger and demand a deeper knowledge of the engine internals. The issues are presented here in an approximate order of perceived difficulty.

• Add more checks in `patterns/mkpat.c' testing whether the main diagram and the constraint diagram are consistent.
• Break out handling of movelists into its own file and generalize it. This is started in 3.1.16. Move lists are used, among other places, in worms.c where it is used to store moves that capture, save, threaten to capture and threaten to save the worm.
• Implement move lists storing important moves for dragons and eyes in the same way as it is used for worms. Half eyes are already halfway done. The moves are stored, but not the attack and defend codes (LOSE, KO_A, KO_B and WIN).
• Make the cache not waste storage on 64 bit systems.
• Implement detection of superko violation in the board code. We probably only want this optionally in play_move() and in a variant of is_legal().
• The dragon data is split into two arrays, dragon[] and dragon2[]. The dragon2 array only have one entry per dragon, in contrast to the dragon array where all the data is stored once for every intersection of the board. Complete the conversion of eye_data, half_eye_data, worm and dragon to use the same structure as the dragon2 array.
• Support for ko in eyes.db and optics.c.
• Integrate the time handling code in play_gtp.c with the autolevel code in `clock.c'. Alternatively, replace them both with something better. Basing it on some solid system identification theory and/or control theory wouldn't hurt.
• Write a script which plays through the joseki databases and checks that the engine really generates a joseki move for all positions in the databases. This would also be interesting to run with the `--nojosekidb' option.

1.5.3 Long term issues

These issues are strategic in nature. They will help us to improve the playing strength of the program and/or enhance certain aspects of it.

• Extend the regression test suites.

  See the texinfo manual in the doc directory for a description of how to do this. In particular it would be useful with test suites for common life and death problems. Currently second line groups, L groups and the tripod shape are reasonably well covered, but there is for example almost nothing on comb formations, carpenter's square, and so on. Other areas where test suites would be most welcome are fuseki, tesuji, and endgame.

• Tuning the pattern databases.

  These are under constant revision. Tuning them is a sort of art. It is not necessary to do any programming to do this since most of the patterns do not require helpers. We would like it if a few more Dan level players would learn this skill.

• Extend and tune the Joseki database.

  It might be very useful to implement a semi-automatic way of doing this. The current method based on sgf files become difficult to maintain with existing tools.

• The semeai module is still in need of improvement. (This is underway.)
• GNU Go does not have a move generator that tries explicitly to build moyos, or reduce/invade opponent's moyos. Such a move generator could be built using the same type of code that is used in the owl life and death reader, or the connection reader mentioned in point 5 above.
• A much improved combination module.

  The combination module of today only finds combinations of threats to capture enemy groups. A more useful combination module would e.g. find combinations of threats to capture a group or enter opponent territory. It would also be strong enough to find combinations of strategic moves and more indirect threats (a threat to a threat). Possibly it could combine threats in AND-OR trees (DAGs?) that could be searched using ordinary tree search algorithms. (Revision of `combination.c' is underway.)

• Speed up the tactical reading.

  GNU Go is reasonably accurate when it comes to tactical reading, but not always very fast. The main problem is that too many ineffective moves are tested, leading to strange variations that shouldn't need consideration. To improve one could refine the move generation heuristics in the reading. Also, one should implement some more of the standard tree search optimizations used in alpha-beta readers.

• Improve the heuristics for assessment of the safety of a group.

  This might take into account number of eyes / half eyes, moyo in corners, moyo along the edge, moyo in the center, proximity to living friendly groups, weak opponent groups etc. It is of particular interest to be able to accurately determine how a move affects the safety of all groups on the board.

1.5.4 Ideas

These are some ideas that have been floated on the mailing list. Some of them are down-to-earth, and some are just blue sky ramblings. They are presented here for inspiration.

• A good GUI.

  A start is being made with GoThic, a goban widget based on the QT toolkit. This is linked from the GNU Go development web page on gnu.org. Other starts have been made based on GTK, but so far nothing more than a start has been attempted.

• A graphical pattern editor.

  This would make it much easier for non-programmers to improve the strength of GNU Go. It could also be used as a debugging tool for the programmers. This project has the GUI as a prerequisite. The challenge here is not to make a tool which makes it easier to create patterns but to make it easier to overview and maintain the database.

• Make the engine thread safe and use multiple CPUs on an SMP machine.
• Making the engine use many machines loosely connected on the internet or in a cluster.
• Think on the opponent's time.
• A global alpha-beta reader.

  This would probably be very slow and could only read 2 or 3 moves ahead. Still it could find fatal errors and improve the moves that GNU Go makes.

• A strategic module that identifies high-level goals and then gives these goals to the rest of the engine. It should be able to identify if we are ahead in territory or thickness, if we should play safe or if we should play daringly (e.g. if behind). It should also identify weak areas where we can attack or where we should defend. Maybe this module doesn't have to be written in C. Maybe PROLOG, LISP or some other AI language would be better.

• A parameter that makes GNU Go play different styles.

  Such styles could be 'play for territory', 'play aggressively', 'play tricky moves (hamete)', and so on. It could be used to present human users with different kinds of opponents or to tell GNU Go how to play certain computer opponents in tournaments.

• Generalize representation and handling of threats so that we have a graph representation of threats that can be searched to see how different threats interact.
• An endgame module based on ideas from combinatorial game theory.

  To be really useful this would have to deal with early endgame positions.

• Automated fuseki tuning

  Fuseki tuning by hand is difficult. I'd like to encourage people who are interested in doing machine learning experiments with GNU Go work with the fuseki. This may be one of the areas with most potential for substantial and reasonably quick improvements.

• More elaborate classification of ko

  Create a paradigm for handling other types of ko (approach move ko, multi-step ko, etc) and then write code that handles them.

2. Installation

You can get the most recent version of GNU Go ftp.gnu.org or a mirror (see http://www.gnu.org/order/ftp.html for a list). You can read about newer versions and get other information at http://www.gnu.org/software/gnugo/.

2.1 GNU/Linux and Unix

Untar the sources, change to the directory gnugo-3.6. Now do:

   ./configure [OPTIONS]
   make

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.

As an example,

   ./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 (see section 2.2 Configure Options).

After running configure and make, you have now made a binary called `interface/gnugo'. Now (running as root) type

   make install

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:

   gnugo

but it is nicer to run it using CGoban 1 (under X-Windows), 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. CGoban 2 will not work.

See section 3.2 Running GNU Go via CGoban, for instructions on how to run GNU Go from Cgoban, or See section 3.3 Other Clients, for Jago or other clients.

2.2 Configure Options

There are three options which you should consider configuring, particularly if you are dissatisfied with GNU Go's performance.

2.2.1 Ram Cache

By default, GNU Go makes a cache of 8 Megabytes in RAM for its internal use. The cache is used to store intermediate results during its analysis of the position.

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 toggle SWAP display.

You may override the size of the default cache at compile time by running one of:

   ./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 MB. 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.

2.2.2 Default Level

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.

2.2.3 Other 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 experimental options.

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 disabled for 3.6.

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. */
#define COSMIC_GNUGO 0

/* Break-in module. Enabled by default. */
#define USE_BREAK_IN 1

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 (see section 13.10 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 slower.
• 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 or runtime options.

• chinese-rules Use Chinese (area) counting.
• resignation-allowed Allow GNU Go to resign games. This is on by default.

2.3 Compiling GNU Go on Microsoft platforms

GNU Go is being developed on Unix variants. GNU Go is easy to build and install on those platforms. GNU Go 3.6 has support for building on MS-DOS, Windows 3.x, Windows NT/2000 and Windows 95/98.

There are two approaches to building GNU Go on Microsoft platforms.

1. The first approach is to install a Unix-like environment based on ports of GCC to Microsoft platforms. This approach is fully supported by the GNU Go developers and works well. Several high quality free Unix-environments for Microsoft platforms are available.

   One benefit of this approach is that it is easier to participate in GNU Go's development. These unix environments come for instance with the `diff' and `patch' programs necessary to generate and apply patches.

   Another benefit of the unix environments is that development versions (which may be stronger than the latest stable version) can be built too. The supporting files for VC are not always actively worked on and consequently are often out of sync for development versions, so that VC will not build cleanly.

2. The second approach is to use compilers such as Visual C developed specially for the Microsoft platform. GNU Go 2.6 and later support Visual C. Presently we support Visual C through the project files which are supplied with the distribution.

The rest of this section gives more details on the various ways to compile GNU go for Microsoft platforms.

2.3.1 Windows 95/98, MS-DOS and Windows 3.x using DJGPP

On these platforms DJGPP can be used. GNU Go installation has been tested in a DOS-Box with long filenames on Windows 95/98. GNU Go compiles out-of-the box with the DJGPP port of GCC using the standard Unix build and install procedure.

Some URLs for DJGPP:

DJGPP home page: http://www.delorie.com/djgpp/

DJGPP ftp archive on simtel:

ftp://ftp.simtel.net/pub/simtelnet/gnu/djgpp/v2/

ftp://ftp.simtel.net/pub/simtelnet/gnu/djgpp/v2gnu/

Once you have a working DJGPP environment and you have downloaded the GNU Go source available as gnugo-3.6.tar.gz you can build the executable as follows:

       tar zxvf gnugo-3.6.tar.gz
       cd gnugo-3.6
       ./configure
       make

Optionally you can download glib for DJGPP to get a working version of snprintf.

2.3.2 Windows NT, 2000, XP, 95/98/ME using Cygwin

Cygwin is a full fledged and rapidly maturing unix environment on top of windows. Cygwin installs very easily with the interactive setup program available from the cygwin homepage at http://sources.redhat.com/cygwin/. In fact precompiled versions of stable GNU go releases as well as of the cgoban X11 GUI can be downloaded through Cygwin's setup. Cygwin's setup also provides precompiled packages of most of the unix tools necessary to participate in development.

If you want to build GNU Go yourself make sure to download the ncurses packages prior to building GNU go. GNU Go compiles out-of-the box using the standard Unix build procedure on the Cygwin environment. After installation of cygwin and fetching `gnugo-3.6.tar.gz' you can type:

  tar zxvf gnugo-3.6.tar.gz
  cd gnugo-3.6
  ./configure
  make

The generated executable is not a stand-alone executable: it needs cygwin1.dll that comes with the Cygwin environment. cygwin1.dll contains the emulation layer for Unix.

2.3.3 Windows NT, 2000, XP, 95/98/ME using MinGW32

The Cygwin environment also comes with MinGW32. The mingw32 platform generates an executable that relies only on Microsoft DLLs. This executable is thus completely comparable to a Visual C executable and easier to distribute than the Cygwin executable. To build on cygwin an executable suitable for the win32 platform type the following at your cygwin prompt:

  tar zxvf gnugo-3.6.tar.gz
  cd gnugo-3.6
  env CC='gcc -mno-cygwin' ./configure
  make

The generated executable can be reduced in size significantly by using the upx compression program that is available through Cygwin's setup program.

2.3.4 Windows NT, Windows 95/98 using Visual C and project files

We assume that you do not want to change any configure options. If you do, you should edit the file `config.vc'. Note that when configure is run, this file is overwritten with the contents of `config.vcin', so you may also want to edit `config.vcin', though the instructions below do not have you running configure.

1. Open the VC++ 6 workspace file gnugo.dsw
2. Set the gnugo project as the active project (right-click on it, and select "Set as Active Project". Select 'Build' from the main menu, then select 'Build gnugo.exe', this will make all of the runtime subprojects.

Notes:

• a) The build can also be done from the command line:

  msdev gnugo.dsw /make "gnugo - Win32 Release"

• b) The default configuration is 'Debug', build the optimized version by selecting 'Build' from the main menu , then select 'Set active Configuration' and click on 'gnugo - Win32 Release'. See the Visual Studio help for more on project configurations.
• c) A custom build step in the first dependent subproject (utils) copys config.vc to config.h in the root directory. If you want to modify config.h, copy any changes to config.vc. In particular if you want to change the default level or default cache size, whose significance is discussed in See section 2.1 GNU/Linux and Unix, you must edit this file.
• d) This project was built and tested using VC version 6.0. It has not been tested, and will most likely not work with earlier versions of VC.

2.3.5 Running GNU Go on Windows NT and Windows 95/98

GNU Go does not come with its own graphical user interface. The Java client jago can be used.

To run Jago you need a Java Runtime Environment (JRE). This can be obtained from http://www.javasoft.com/. This is the runtime part of the Java Development Kit (JDK) and consists of the Java virtual machine, Java platform core classes, and supporting files. The Java virtual machine that comes with I.E. 5.0 works also.

Jago: http://www.rene-grothmann.de/jago/

1. Invoke GNU Go with gnugo --quiet --mode gmp
2. Run gnugo --help from a cygwin or DOS window for a list of options
3. optionally specify --level <level> to make the game faster

Jago works well with both the Cygwin and MinGW32 executables. The DJGPP executable also works, but has some problems in the interaction with jago after the game has been finished and scored.

2.4 Macintosh

If you have Mac OS X you can build GNU Go using Apple's compiler, which is derived from GCC.

3. Using GNU Go

3.1 Getting Documentation

You can obtain a printed copy of the manual by running make gnugo.ps in the `doc/'directory, then printing the resulting postscript 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. 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, for developers.

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 epstopdf.)

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.

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

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

3.3 Other Clients

In addition to CGoban (see section 3.2 Running GNU Go via 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.

• 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.
• glGo (http://ggo.sourceforge.net/) is a C++ client by Peter Strempel, capable of playing against GNU Go or on IGS. Source code is available under the GPL.
• 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.
• Mac GNU Go (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. License is GPL.
• 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. Source code is in the CVS (http://sourceforge.net/cvs/?group_id=59117). Licence is GPL. Gogui does not yet support gmp or play on servers but is potentially very useful for programmers working on GNU Go or other engines.
• gGo is a Java program which was originally known as qGo for Java. Although the public source of the program is no longer maintained, it is still useful may be found at sourceforge here (http://prdownloads.sourceforge.net/ggo/) or here (ftp://download.sourceforge.net/pub/sourceforge/g/gg/ggo/). GGo can function as a client or sgf editor and supports the GTP, so you can play on the servers or with GNU Go. Licence is GPL.
• 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.
• Goben (http://www.waz.easynet.co.uk/software.html), a GTP capable front end for GNU Go using GTK libraries from Wayne Myers. Licensed GPL.

3.4 Ascii Interface

Even if you do not have CGoban installed 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.

3.5 GNU Go mode in Emacs

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 (provided you have Emacs version 21 or later) you can have a nice graphical display of the board within emacs.

Load the file `interface/gnugo.el' and (if you want the graphical board) `interface/gnugo-xpms.el'. You may do this using the Emacs M-x load-file command.

In detail: Emacs uses Control and Meta keys. The "Meta" key is the Alt key on the PC keyboard. The Control and Meta keys are denoted C- and M-. Thus the M-x is obtained by holding the Alt key and typing `x'. In Emacs, this prompts you for another command. You can then type load-file, hit the Enter key, then type the path to `gnugo.el' and hit Enter again. Then repeat the process for `gnugo-xpms.el'.

To have the files `gnugo.el' and `gnugo-xpms.el' loaded automatically each time you run emacs, copy the files into your `site-lisp' directory (often `/usr/share/emacs/site-lisp') and add lines

(autoload 'gnugo "gnugo" "GNU Go" t)
(autoload 'gnugo-xpms "gnugo-xpms" "GNU Go" t)

in your `.emacs' file.

The `.xpm' bitmaps for the default size Go stones are 30 pixels. For a larger board, alternative 36 pixel stones may be found in `gnugo-big-xpms.el'.

You may start GNU Go by M-x gnugo. You will be prompted for command line options (see section 3.9 Invoking GNU Go: Command line options). Using these, you may set the handicap, board size, color and komi. For example if you want to play white and give a nine-stone handicap, use the options `--handicap 9 --color white'.

By default, Emacs gives you a graphical Go board. You can toggle an alternative ascii board (for example, if you want to paste a diagram into an email) with gnugo-toggle-image-display, which is bound to `i'. If you want a grid, `g' toggles the grid display on or off. The grid is not displayed by default.

You play a move either by moving to the location with the arrow keys, then hitting the SPACE key, or by clicking on an empty location with the mouse. You can save or load a game, and undo moves.

You can get help at any time by typing `?'. This will give a description of the default keybindings. If you want to find out what a particular function does, you can use `C-h f <function-name>' to get documentation on it. For example, after examining the default keybindings with `?' we learn that `v' is bound to gnugo-view-regression. To find out more information about this function we type `C-h f gnugo-view-regression' to view the help string for the function.

You may save the game you are playing as an sgf file with gnugo-write-sgf-file, which is bound to `s'. You may also restore a saved game with gnugo-read-sgf-file, bound to `l'. When the sgf file is loaded, it is assumed to be your move, since typically the game is saved on your move. You may resume play by entering a move.

At the end of the game, after both players pass, GNU Go will run gnugo-venerate to render all dead stones as ghostly shades. You can then type `F' to run gnugo-display-final-score, which will tell you the score. (You may get a score estimate at any time before the end of the game with gnugo-estimate-score, bound to `!'.

You may undo your move with gnugo-undo-two-moves, which is bound to `u'. This takes back your move, and also the last computer move, so it goes back to the position two moves ago. If you undo one or many moves, you may redo them with gnugo-redo-two-moves, which is bound to `r'.

Although if you are playing a game it is most natural to undo or redo two moves at a time, since this does not change the color of the player to move, you may also undo or redo a single move with gnugo-undo and gnugo-redo, bound to `b' and `f'. This is convenient for scrolling forward or backward in a game to review the moves. Note that if you undo once, then play a move (by clicking on the board, or by hitting the space or enter key), you have changed the color of the player to move. GNU Go will begin to generate moves as soon as you play.

You may also use gnugo-jump-to-move, bound to `j' to jump to a particular move in the game. You will be prompted for the game move. After you type the number of the move, Emacs will undo back to that move number. You may then redo or further undo using `f' and `f'. You may also jump to the beginning or end of the game with `<' and `>'.

Another way to undo back to a given move is to move the cursor to a stone (which must be one of your own), then execute gnugo-magic-undo, bound to `U'.

As we have noted, GNU Go normally answers each move that you play by generating a move of its own. If you want to suppress GNU Go's automatic generation of moves, you may toggle an `editing mode' with gnugo-toggle-edit-mode. In the editing mode, GNU Go does not automatically answer each move that you play. For example, you can use the editing mode to write an sgf file from scratch. If you are playing a game, you can turn off GNU Go's automatic responses, play a few moves in editing mode to see what the board position will look like, then back up to the last move, toggle the editing mode off, then resume the game.

You may view a GNU Go regression test with gnugo-view-regression, which will prompt you for the name of a test. You may type (for example) strategy:6. The first time you do this you will be prompted for the path to the `regression/' directory. (Once Emacs knows this path, you will not be prompted again.) This command takes a while to execute since GNU Go will run the regression. When it is completed, Emacs will display the board position (with the grid) and a message below the board such as:

 loadsgf games/incident104.sgf 63
 strategy:6 reg_genmove white
 #? [E10]*
 =6 J13

You may also ask GNU Go to identify a dragon on the board. Click on one stone to move the cursor to that location. Then type `d'. The dragon in question will then be marked flashing. You may also type `D', which will report the dragon data. You may run other gtp commands with gnugo-command, which is bound to `:'.

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 (see section 19. The Go Text Protocol) 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.

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.

3.8 Smart Game Format

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/

3.9 Invoking GNU Go: Command line options

3.9.1 Some basic options

• `--help', `-h'

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

• `--boardsize size'

  Set the board size

• `--komi num'

  Set the komi

• `--level level'

  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.

• `--quiet', `--silent'

  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.

• `-L', `--until move'

  Stop loading just before the indicated move is played. move can be either the move number or location.

• `-o', `--outfile filename'

  Write sgf output to file

• `-O', `--output-flags flags'

  Add useful information to the sgf file. Flags can be 'd', 'v' or both (i.e. 'dv'). If 'd' is specified, dead and critical dragons are marked in the sgf file. If 'v' is specified, move valuations around the board are indicated.

• `--mode mode'

  Force the playing mode ('ascii', 'emacs,' 'gmp' or 'gtp'). The default is ASCII, but if no terminal is detected GMP (Go Modem Protocol) will be assumed. In practice this is usually what you want, so you may never need this option.

• `--resign-allowed'

  GNU Go will resign games if this option is enabled. This is the default unless you build the engine with the configure option `--disable-resignation-allowed'. Unfortunately the Go Modem Protocol has no provision for passing a resignation, so this option has no effect in GMP mode.

• `--never-resign'

  GNU Go will not resign games.

3.9.2 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 (see section 2. Installation). GNU Go stores results of its reading calculations in a Hash table (see section 11.2 Hashing of Positions). 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.

• `--chinese-rules'

  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.

• `--japanese-rules'

  Use Japanese Rules. This is the default unless you specify `--enable-chinese-rules' as a configure option.

• `--copyright': Display the copyright notice
• `--version' or `-v': Print the version number
• `--printsgf filename':

  Create an SGF file containing a diagram of the board. Useful with `-l' and `-L' to create a diagram of the board from another sgf file. Illegal moves are indicated with the private IL property. This property is not used in the FF4 SGF specification, so we are free to preempt it. This feature is used in the CGI interface in `interface/html/gg.cgi'.

• `--options'

  Print which experimental configure options were compiled into the program (see section 2.2.3 Other Options).

• `--orientation n'

  Combine with `-l'. The Go board can be oriented in 8 different ways, counting reflections and rotations of the position; this option selects an orientation (default 0). The parameter `n' is an integer between 0 and 7.

3.9.3 Other options affecting strength and speed

• `--level amount'

  The higher the level, the deeper GNU Go reads. Level 10 is the default. If GNU Go plays too slowly on your machine, you may want to decrease it.

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 these options. Instead, just adjust the single variable `--level'. The remaining options are of use to developers tuning the program for performance and accuracy. For completeness, here they are.

• `-D', `--depth depth'

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

• `-F', `--fourlib-depth depth'

  Deep reading cutoff. When reading beyond this depth (default 7) GNU Go assumes that any string which can obtain 4 liberties is alive.

• `-K', `--ko-depth depth'

  Deep reading cutoff. Beyond this depth (default 8) GNU Go no longer tries very hard to analyze kos.

• `--branch-depth depth'

  This sets the branch_depth, typically a little below the depth. Between branch_depth and depth, attacks on strings with 3 liberties are considered but branching is inhibited, so fewer variations are considered. Below this depth (default 13), GNU Go still tries to attack strings with only 3 liberties, but only tries one move at each node.

• `--break_chain-cutoff depth'

  Set the break_chain_depth. Beyond this depth, GNU Go abandons some attempts to defend groups by trying to capture part of the surrounding chain.

• `--aa-depth depth'

  The reading function atari_atari looks for combinations beginning with a series of ataris, and culminating with some string having an unexpected change in status (e.g. alive to dead or critical). This command line optio sets the parameter aa_depth which determines how deeply this function looks for combinations.

• `--superstring-depth'

  A superstring (see section 11.8 Superstrings) 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 parameter to be set.

The preceeding options are documented with the reading code (see section 11.1 Reading Basics).

• `--owl-branch' Below this depth Owl only considers one move. Default 8.
• `--owl-reading' Below this depth Owl assumes the dragon has escaped. Default 20.
• `--owl-node-limit'

  If the number of variations exceeds this limit, Owl assumes the dragon can make life. Default 1000. We caution the user that increasing owl_node_limit does not necessarily increase the strength of the program.

• `--owl-node-limit n'

  If the number of variations exceeds this limit, Owl assumes the dragon can make life. Default 1000. We caution the user that increasing owl_node_limit does not necessarily increase the strength of the program.

• `--owl-distrust n'

  Below this limit some owl reading is truncated.

3.9.4 Ascii mode options

• `--color color'

  Choose your color ('black' or 'white').

• `--handicap number'

  Choose the number of handicap stones (0--9)

3.9.5 Development options

• `--replay color'

  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
  • both: replay all moves

  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. See section 20. Regression testing.

• `-a', `--allpats'

  Test all patterns, even those smaller in value than the largest move found so far. This should never affect GNU Go's final move, and it will make it run slower. However this can be very useful when "tuning" GNU Go. It causes both the traces and the output file (`-o') to be more informative.

• `-T', `--printboard': colored display of dragons.

  Use rxvt, xterm or Linux Console. (see section 5.8 Colored Display)

• `--showtime'

  Print timing information to stderr.

• `-E', `--printeyes': colored display of eye spaces

  Use rxvt, xterm or Linux Console. (see section 5.8 Colored Display)

• `-d', `--debug level'

  Produce debugging output. The debug level is given in hexadecimal, using the bits defined in the following table from `engine/gnugo.h'. A list of these may be produced using `--debug-flags'. Here they are in hexadecimal:

  DEBUG_INFLUENCE 0x0001 DEBUG_EYES 0x0002 DEBUG_OWL 0x0004 DEBUG_ESCAPE 0x0008 DEBUG_MATCHER 0x0010 DEBUG_DRAGONS 0x0020 DEBUG_SEMEAI 0x0040 DEBUG_LOADSGF 0x0080 DEBUG_HELPER 0x0100 DEBUG_READING 0x0200 DEBUG_WORMS 0x0400 DEBUG_MOVE_REASONS 0x0800 DEBUG_OWL_PERFORMANCE 0x1000 DEBUG_LIFE 0x2000 DEBUG_FILLLIB 0x4000 DEBUG_READING_PERFORMANCE 0x8000 DEBUG_SCORING 0x010000 DEBUG_AFTERMATH 0x020000 DEBUG_ATARI_ATARI 0x040000 DEBUG_READING_CACHE 0x080000 DEBUG_TERRITORY 0x100000 DEBUG_OWL_PERSISTENT_CACHE 0X200000 DEBUG_TOP_MOVES 0x400000 DEBUG_MISCELLANEOUS 0x800000 DEBUG_ORACLE_STREAM 0x1000000

  These debug flags are additive. If you want to turn on both dragon and worm debugging you can use `-d0x420'.

• `--debug-flags'

  Print the list of debug flags

• `-H', `--hash level'

  hash (see `engine/gnugo.h' for bits).

• `-w', `--worms'

  Print more information about worm data.

• `-m', `--moyo level'

  moyo debugging, show moyo board. The level is fully documented elsewhere (see section 13.13 Colored display and debugging of influence).

• `-b', `--benchmark number'

  benchmarking mode - can be used with `-l'. Causes GNU Go to play itself repeatedly, seeding the start of the game with a few random moves. This method of testing the program is largely superceded by use of the twogtp program.

• `-S', `--statistics'

  Print statistics (for debugging purposes).

• `-t', `--trace'

  Print debugging information. Use twice for more detail.

• `-r', `--seed seed'

  Set random number seed. This can be used to guarantee that GNU Go will make the same decisions on multiple runs through the same game. If seed is zero, GNU Go will play a different game each time.

• `--decide-string location'

  Invoke the tactical reading code (see section 11. 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 (see section 12.1 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 tree in SGF.

• `--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 location.

• `--decide-semeai location1/location2'

  At location1 and location2 are adjacent dragons of the opposite color. Neither is aliveby itself, and their fate (alive, dead or seki) depends on the outcome of a semeai (capturing race). Decide what happens. Useful in connection with `-o' to write the variations to an SGF file.

• `--decide-tactical-semeai location1/location2'

  Similar to `--decide-semeai', except that moves proposed by the owl code are not considered.

• `--decide-position'

  Try to attack and defend every dragon with dragon.escape<6. If used with `-o', writes the variations to an sgf file.

• `--decide-eye location'

  Evaluates the eyespace at location and prints a report. You can get more information by adding `-d0x02' to the command line. (see section 8.7 Eye Local Game Values.)

• `--decide-surrounded location'

  A dragon is surrounded if it is contained in the convex hull of its unfriendly neighbor dragons. This does not mean that it cannot escape, but it is often a good indicator that the dragon is under attack. This option draws the convex hull of the neighbor dragons and decides whether the dragon at location is surrounded.

• `--decide-combination'

  Calls the function atari_atari to decide whether there exist combinations on the board.

• `--score method'

  Requires `-l' to specify which game to score and `-L' if you want to score anywhere else than at the end of the game record. method can be "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.

  • estimate

    Examine the status of all groups on the board, then give a quick estimate of the score using the Bouzy 5/21 algorithm (see section 14. Another approach to Moyos : Bouzy's 5/21 algorithm).

  • finish

    Finish the game by selfplaying until two passes, then determine the status of all stones and estimate territory using the Bouzy 5/21 algorithm (see section 14. Another approach to Moyos : Bouzy's 5/21 algorithm).

  • aftermath

    Finish the game by selfplaying until two passes, then accurately determine status of all stones by playing out the "aftermath", i.e. playing on until all stones except ones involved in seki have become either unconditionally (in the strongest sense) alive or unconditionally dead (or captured). Slower than `--score finish', and while these algorithms usually agree, if they differ, `--score aftermath' is most likely to be correct.

• --score aftermath --capture-all-dead --chinese-rules

  This combination mandates Tromp-Taylor scoring. The Tromp-Taylor ruleset requires the game to be played out until all dead stones are removed, then uses area (Chinese) scoring. The option `--capture-all-dead' requires the aftermath code to finish capturing all dead stones.

3.9.6 Experimental options

Most of these are available as configure options and are described in 2.2.3 Other Options.

• `--options'

  Print which experimental configure options were compiled into the program.

• `--with-break-in'
• `--without-break-in'

  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 disabled at level 9.

• `--cosmic-gnugo'

  Use center oriented influence.

• `--nofusekidb'

  Turn off the fuseki database.

• `--nofuseki'

  Turn off fuseki moves entirely

• `--nojosekidb'

  Turn off the joseki database.

• `--mirror'

  Try to play mirror go.

• `--mirror-limit n'

  Stop mirroring when n stones are on the board.

4. GNU Go engine overview

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.

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 number of liberties.

Soon after comes the most important step of the worm analysis: the tactical reading code (see section 11. 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 13. Influence Function 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 given dragon is:

• 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 under attack.

For those dragons that are considered weak, a life and death analysis is made (see section 12.1 The Owl Code). If two dragons next to each other are found that are both not alive, we try to resolve this situation with the semeai module.

For a more detailed reference of the worm and dragon analysis (and explanations of the data structures used to store the information), see See section 7. 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.

4.2 Move Generators

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 See section 6. Move generation.

There are a couple of move generators that only extract data found in the previous phase, examining the position:

• worm_reasons()

  Moves that have been found to capture or defend a worm are proposed as candidates.

• owl_reasons()

  The status of every dragon, as it has been determined by the owl code (see section 12.1 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 relevant for semeais.

• 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:

• fuseki()

  Generate a move in the early fuseki, either in an empty corner of from the fuseki database.

• shapes()

  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. See section 9. The Pattern Code, for a complete documentation of patterns.)

• combinations()

  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.

• endgame_shapes()

  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 `patterns/endgame.db'.

• revise_semeai()

  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_liberty()

  Fill a common liberty. This is only used at the end of the game. If necessary a backfilling or backcapturing move is generated.

4.3 Move Valuation

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. see section 13.4 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 6.4 Valuation of suggested moves.

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()
make_worms():
  compute_effective_sizes()
  compute_unconditional_status()
  find_worm_attacks_and_defenses():      
    for each attackable worm:
      set worm.attack
      change_attack() to add the attack point
    find_attack_patterns() to find a few more attacks
    for each defensible worm:
      set worm.attack
      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
      immediate liberties
  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.
  find worm lunches
  find worm threats
  identify inessential worms (such as nakade stones)
compute_worm_influence():
  find_influence_patterns()
  value_influence()
  segment_influence()
make_dragons():
  find_cuts()
  find_connections()
  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()
  semeai():
    for every semeai, run owl_analyze_semeai()
    find_moves_to_make_seki()
  identify_thrashing_dragons()
  compute_dragon_influence():
    compute_influence()
    break_territories() (see section 13.10 Break Ins)
  compute_refined_dragon_weaknesses()

Now a summary of the sequence of events during the move generation and selection phases of genmove(), which take place after the information gathering phase has been completed:

estimate_score()
choose_strategy()
collect_move_reasons():
  worm_reasons(): for each attack and defense point add a move reason
  semeai_reasons(): for each dragon2.semeai point add a move reason
  owl_reasons(): for each owl attack and defense point add a move reason
  break_in_reasons(): for each breakin found add a move reason
fuseki()
break_mirror_go()
shapes(): match patterns around the board (see section 9.1 Overview)
combinations(): look for moves with a double meaning and other tricks
  find_double_threats()
  atari_atari()
review_move_reasons()
if ahead and there is a thrashing dragon, consider it 
  alive and reconsider the position
endgame_shapes()
endgame()
if no move found yet, revisit any semeai, change status of dead opponent
  to alive, then run shapes() and endgame_shapes() again
if no move found yet, run fill_liberty()

4.5 Roadmap

The GNU Go engine is contained in two directories, `engine/' and `patterns/'. Code related to the user interface, reading and writing of Smart Game Format files, and testing are found in the directories `interface/', `sgf/', and `regression/'. Code borrowed from other GNU programs is contained in `utils/'. That directory also includes some code developed within GNU Go which is not go specific. Documentation is in `doc/'.

In this document we will describe some of the individual files comprising the engine code in `engine/' and `patterns/'. In `interface/' we mention two files:

• `gmp.c'

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

• `main.c'

  This contains main(). The `gnugo' target is thus built in the `interface/' directory.

4.5.1 Files in `engine/'

In `engine/' there are the following files:

• `aftermath.c'

  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 in GNU Go.

• `board.c'

  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.

• `breakin.c'

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

• `combination.c'

  When something can (only) be captured through a series of ataris or other threats we call this a combination attack. This file contains code to find such attacks and moves to prevent them.

• `dragon.c'

  This contains make_dragons(). This function is executed before the move-generating modules shapes() semeai() and the other move generators but after make_worms(). It tries to connect worms into dragons and collect important information about them, such as how many liberties each has, whether (in GNU Go's opinion) the dragon can be captured, if it lives, etc.

• `endgame.c'

  Code to find certain types of endgame moves.

• `filllib.c'

  Code to force filling of dame (backfilling if necessary) at the end of the game.

• `fuseki.c'

  Generates fuseki (opening) moves from a database. Also generates moves in empty corners.

• `genmove.c'

  This file contains genmove() and its supporting routines, particularly examine_position().

• `globals.c'

  This contains the principal global variables used by GNU Go.

• `gnugo.h'

  This file contains declarations forming the public interface to the engine.

• `hash.c' and `hash.h'

  Hashing code implementing Zobrist hashing. (see section 11.2 Hashing of Positions) The code in `hash.c' provides a way to hash board positions into compact descriptions which can be efficiently compared. The caching code in `cache.c' makes use of the board hashes when storing and retrieving read results.

• `influence.c' and `influence.h'.

  This code determines which regions of the board are under the influence of either player. (see section 13. Influence Function)

• `liberty.h'

  Header file for the engine. The name "liberty" connotes freedom (see section A. Copying).

• `matchpat.c'

  This file contains the pattern matcher matchpat(), which looks for patterns at a particular board location. The actual patterns are in the `patterns/' directory. The function matchpat() is called by every module which does pattern matching, notably shapes.

• `move_reasons.c' and `move_reasons.h'

  Code for keeping track of move reasons.

• `movelist.c'

  Supporting code for lists of moves.

• `optics.c'

  This file contains the code to recognize eye shapes, documented in See section 8. Eyes and Half Eyes.

• `oracle.c'

  Code to fork off a second GNU Go process which can be used to simulate reading with top level information (e.g. dragon partitioning) available.

• `owl.c'

  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.c'

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

• `printutils.c'

  Print utilities.

• `readconnect.c' and `readconnect.h'

  This file contains code to determine whether two strings can be connected or disconnected.

• `reading.c'

  This file contains code to determine whether any given string can be attacked or defended. See section 11. Tactical reading, for details.

• `score.c'

  Implements the Bouzy algorithms (see section 14. Another approach to Moyos : Bouzy's 5/21 algorithm) and contains code for scoring the game.

• `semeai.c'

  This file contains semeai(), the module which detects dragons in semeai. To determine the semeai results the semeai reading in `owl.c' is used.

• `sgfdecide.c'

  Code to generate sgf traces for various types of reading.

• `shapes.c'

  This file contains shapes(), the module called by genmove() which tries to find moves which match a pattern (see section 9. The Pattern Code).

• `showbord.c'

  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.

• `surround.c'

  Code to determine whether a dragon is surrounded and to find moves to surround with or break out with.

• `utils.c'

  An assortment of utilities, described in greater detail below.

• `value_moves.c'

  This file contains the code which assigns values to every move after all the move reasons are generated. It also tries to generate certain kinds of additional move reasons.

• `worm.c'

  This file contains make_worms(), code which is run at the beginning of each move cycle, before the code in `dragon.c', to determine the attributes of every string. These attributes are things like liberties, wether the string can be captured (and how), etc

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 (see section 12.1 The Owl Code).
• Connection patterns in `conn.db' (see section 9.9 The Connections Database)
• Influence patterns in `influence.db' and `barriers.db' (see section 13. Influence Function)
• eye patterns in `eyes.db' (see section 8. Eyes and Half 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.

• `conn.db'

  Database of connection patterns.

• `conn.c'

  Automatically generated file, containing connection patterns in form of struct arrays, compiled by mkpat from `conn.db'.

• `eyes.c'

  Automatically generated file, containing eyeshape patterns in form of struct arrays, compiled by mkpat from `eyes.db'.

• `eyes.h'

  Header file for `eyes.c'.

• `eyes.db'

  Database of eyeshape patterns. See section 8. Eyes and Half Eyes, for details.

• `helpers.c'

  These are helper functions to assist in evaluating moves by matchpat.

• `hoshi.sgf'

  Smart Game Format file containing 4-4 point openings

• `hoshi.db'

  Automatically generated database of 4-4 point opening patterns, make by compiling `hoshi.sgf'

• `joseki.c'

  Joseki compiler, which takes a joseki file in Smart Game Format, and produces a pattern database.

• `komoku.sgf'

  Smart Game Format file containing 3-4 point openings

• `komoku.db'

  Automatically generated database of 3-4 point opening patterns, make by compiling `komoku.sgf'

• `mkeyes.c'

  Pattern compiler for the eyeshape databases. This program takes `eyes.db' as input and produces `eyes.c' as output.

• `mkpat.c'

  Pattern compiler for the move generation and connection databases. Takes the file `patterns.db' together with the autogenerated Joseki pattern files `hoshi.db', `komoku.db', `sansan.db', `mokuhadzushi.db', `takamoku.db' and produces `patterns.c', or takes `conn.db' and produces `conn.c'.

• `mokuhazushi.sgf'

  Smart Game Format file containing 5-3 point openings

• `mokuhazushi.db'

  Pattern database compiled from mokuhadzushi.sgf

• `sansan.sgf'

  Smart Game Format file containing 3-3 point openings

• `sansan.db'

  Pattern database compiled from `sansan.sgf'

• `takamoku.sgf'

  Smart Game Format file containing 5-4 point openings

• `takamoku.db'

  Pattern database compiled from takamoku.sgf.

• `patterns.c'

  Pattern data, compiled from patterns.db by mkpat.

• `patterns.h'

  Header file relating to the pattern databases.

• `patterns.db' and `patterns2.db'

  These contain pattern databases in human readable form.

4.6 Coding styles and conventions

4.6.1 Coding 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.

4.6.2 Tracing

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

• %m

  Takes two parameters, and displays a formatted board co-ordinate.

• indentation

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

• "outdent"

  format string suppresses the indentation.

Normally gprintf() is wrapped in one of the following:

TRACE(fmt, ...):

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 command-line option.

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.

4.6.3 Assertions

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

ASSERT() is a wrapper around the standard C assert() function. In addition to the test, it takes an extra pair of parameters which are the co-ordinates of a "relevant" board position. If an assertion fails, the board position is included in the trace output, and showboard() and popgo() are called to unwind and display the stack.

4.6.4 FIXME

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

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.

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 (see section 20. Regression testing).

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.

5.1 Interpreting Traces

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

If you are tuning (see section 9.11 Tuning the Pattern databases) 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 introducing a new one.

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 (see section 5.6 Debugging on a Graphical Board, see section 5.8 Colored Display).

5.2 The Output File

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.

5.3 Checking the reading code

The `--decide-string' option is used to check the tactical reading code (see section 11. 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 may find a comment:

attack4-B at D12 (variation 6, hash 51180fdf)
break_chain D12: 0
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:

(gdb) set dump_stack()
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.

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 `--decide-string'.

5.5 GTP and GDB techniques

You can use the Go Text Protocol (see section 19. The Go Text Protocol) 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 be useful as well.

You can also conveniently get such information from GDB. A suggested `.gdbinit' file may be found in See section 11.9 Debugging the reading code. Assuming this file is loaded, you can list the dragon data with the command:

(gdb) dragon P12

Similarly you can get the worm data with worm P12.

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 See section 13.14 Influence Tuning with view.pike.

5.7 Scoring the game

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 (see section 3.9 Invoking GNU Go: Command line options).

5.8 Colored Display

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.

5.8.1 Dragon Display

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 (see section 7.5 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:

green = alive
cyan = dead
red = critical
yellow = unknown
magenta = unchecked

To get the colored display, save a game in sgf format using CGoban, or using the `-o' option with GNU Go itself.

Open an xterm or rxvt window.

Execute gnugo -l [filename] -L [movenum] -T to get the colored display.

Other useful colored displays may be obtained by using instead:

5.8.2 Eye Space Display

Instead of `-T', try this with `-E'. This gives a colored display of the eyespaces, with marginal eye spaces marked `!' (see section 8. Eyes and Half Eyes).

5.8.3 Moyo Display

The option `-m level' can give colored displays of the various quantities which are computed in `engine/moyo.c'.

GNU Go contains two distinct implementations of the concepts of Territory, Moyo and Area (see section 13.2 Territory, Moyo and Area). Primarily GNU Go computes Territory, Moyo and Area using the influence code, and reports them with the functions whose_territory(), whose_moyo() and whose_area(). To get a colored display of the influence regions found by this module, use `-m 0x18' to see the initial influence, and e.g. `-m 0x10 --debug-influence D5' to see the influence after having made the move D5. There are various other options available for numerical displays influence; for a detailed description see 13.13 Colored display and debugging of influence.

The regions found by Bouzy's algorithm (see section 14. Another approach to Moyos : Bouzy's 5/21 algorithm) are used only in the function estimate_score(). These can be displayed with the following options:

`-m level'
 use or (hexadecimal)   cumulative values for printing these reports :
    1       0x01         ascii printing of territorial evaluation (5/21)
    2       0x02         ascii printing of moyo evaluation (5/10)
    4       0x04         ascii printing of area (4/0)

The `-m' options can be combined by adding the levels.

6. Move generation

6.1 Introduction

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 several attacking moves.

• The absolute move values were increasingly becoming harder to tune with the increasing number of patterns. They were also fairly subjective and the tuning could easily break in unexpected ways when something changed, e.g. the worm valuation.

The basic idea of the new move generation scheme is that the various move generators suggest reasons for moves, e.g. that a move captures something or connects two strings, and so on. When all reasons for the different moves have been found, the valuation starts. The primary advantages are

• The move reasons are objective, in contrast to the move values in the old scheme. Anyone can verify whether a suggested move reason is correct.

• The centralized move valuation makes tuning easier. It also allows for style dependent tuning, e.g. how much to value influence compared to territory. Another possibility is to increase the value of safe moves in a winning position.

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'.)

ATTACK_MOVE

DEFEND_MOVE

Attack or defend a worm.

ATTACK_THREAT_MOVE

DEFEND_THREAT_MOVE

Threaten to attack or defend a worm.

EITHER_MOVE

A move that either achieves one goal or another (at the moment this only used for attacks on worms).

ALL_MOVE

At the moment this is used for a move that defends two worms threatened by a double attack.

CONNECT_MOVE

CUT_MOVE

Connect or cut two worms.

ANTISUJI_MOVE

Declare an antisuji or forbidden move.

SEMEAI_MOVE

SEMEAI_THREAT

Win or threaten to win a semeai.

EXPAND_TERRITORY_MOVE

EXPAND_MOYO_MOVE

Move expanding our territory/moyo. These reasons are at the moment treated identically.

VITAL_EYE_MOVE

A vital point for life and death.

STRATEGIC_ATTACK_MOVE

STRATEGIC_DEFEND_MOVE

Moves added by 'a' and 'd' class patterns (see section 9.2 Pattern Attributes) which (perhaps intangibly) attack or defend a dragon.

OWL_ATTACK_MOVE

OWL_DEFEND_MOVE

An owl attack or defense move.

OWL_ATTACK_THREAT

OWL_DEFEND_THREAT

A threat to owl attack or defend a group.

OWL_PREVENT_THREAT

A move to remove an owl threat.

UNCERTAIN_OWL_ATTACK

UNCERTAIN_OWL_DEFENSE

An uncertain owl attack or defense. This means that the owl code could not decide the outcome, because the owl node limit was reached.

MY_ATARI_ATARI_MOVE

A move that starts a chain of ataris, eventually leading to a capture.

YOUR_ATARI_ATARI_MOVE

A move that if played by the opponent starts a chain of ataris for the opponent, leading to capture, which is also a safe move for us. Preemptively playing such a move almost always defends the threat.

The attack and defend move types can have a suffix to denote moves whose 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 11.4 Ko Handling. See `engine/move_reasons.h' for the full of move reasons.

NOTE: Some of these are reasons for not playing a move.

More detailed discussion of these move reasons will be found in the next section.

6.3 Detailed Descriptions of various Move Reasons

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

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

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 their own owl reasons.

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 their own move reasons.

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 and B class patterns.

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 pairs of dragons.

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.

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

6.3.7 Antisuji moves

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.

6.3.8 Territorial moves

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

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.

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.

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

• territorial value
• strategical value
• shape value,
• secondary value.

All of these are floats and should be measured in terms of actual points.

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 (see section 13.4 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 in safety of the dragon.

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.

6.4.1 Territorial Value

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.

6.4.2 Strategical Value

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 valuation phase.

6.4.3 Shape Factor

In the value field of a pattern (see section 9.3 Pattern Attributes) one may specify a shape value.

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.

6.4.4 Minimum Value

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.

6.4.5 Secondary Value

Secondary move reasons are weighed very slightly. Such a move can tip the scales if all other factors are equal.

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

6.5 End Game

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.

7. Worms and 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 See section 8. Eyes and Half Eyes.

This information is intended to help evaluate the connectedness, eye shape, escape potential and life status of each group.

Later routines called by genmove() will then have access to this information. This document attempts to explain the philosophy and algorithms of this preliminary analysis, which is carried out by the two routines make_worm() and make_dragon() in `dragon.c'.

A worm is a maximal set of 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:

      OOOOO
     OOXXXOO
     OX...XO
     OXXXXXO
      OOOOO

The X's here should be considered a single group with one three-space eye, but they consist of two separate strings. Thus we must amalgamate these two strings into a single dragon. Then the assertion makes sense, that playing at the center will kill or save the dragon, and is a vital point for both players. It would be difficult to formulate this statement if the X's are not perceived as a unit.

The present implementation of the dragon code involves simplifying assumptions which can be refined in later implementations.

7.1 Worms

The array struct worm_data worm[MAX_BOARD] collects information about the worms. We will give definitions of the various fields. Each field has constant value at each vertex of the worm. We will define each field.

struct worm_data {
  int color;
  int size;
  float effective_size;
  int origin;
  int liberties;
  int liberties2;
  int liberties3;
  int liberties4;
  int lunch;
  int cutstone;
  int cutstone2;
  int genus;
  int inessential;
  int invincible;
  int unconditional_status;
  int attack_points[MAX_TACTICAL_POINTS];
  int attack_codes[MAX_TACTICAL_POINTS];
  int defense_points[MAX_TACTICAL_POINTS];
  int defend_codes[MAX_TACTICAL_POINTS];
  int attack_threat_points[MAX_TACTICAL_POINTS];
  int attack_threat_codes[MAX_TACTICAL_POINTS]; 
  int defense_threat_points[MAX_TACTICAL_POINTS];
  int defense_threat_codes[MAX_TACTICAL_POINTS];
};

• color

  The color of the worm.

• size

  This field contains the cardinality of the worm.

• effective_size

  This is the number of stones in a worm plus the number of empty 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.

• origin

  Each worm has a distinguished member, called its origin. The purpose of this field is to make it easy to determine when two vertices lie in the same worm: we compare their origin. Also if we wish to perform some test once for each worm, we simply perform it at the origin and ignore the other vertices. The origin is characterized by the test:

  worm[pos].origin == pos.

• liberties
• liberties2
• liberties3
• liberties4

  For a nonempty worm the field liberties is the number of liberties of the string. This is supplemented by LIBERTIES2, LIBERTIES3 and 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. .X.X.. .X.X..

  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 situation:

  X. .O X.

  We say that n is the distance of the liberty of order n from the dragon.

• lunch

  If nonzero, lunch points to a boundary worm which can be easily captured. (It does not matter whether or not the string can be defended.)

We have two distinct notions of cutting stone, which we keep track of in the separate fields worm.cutstone and worm.cutstone2. We use currently use both concepts in parallel.

• cutstone

  This field is equal to 2 for cutting stones, 1 for potential cutting stones. Otherwise it is zero. Definitions for this field: a cutting stone is one adjacent to two enemy strings, which do not have a liberty in common. The most common type of cutting string is in this situation:

  XO OX

  A potential cutting stone is adjacent to two enemy strings which do share a liberty. For example, X in:

  XO O.

  For cutting strings we set worm[].cutstone=2. For potential cutting strings we set worm[].cutstone=1.

• cutstone2

  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 make_domains().

• genus

  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.

• inessential

  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.

• invincible

  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

  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 (see section 11. 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.

7.2 Amalgamation

A dragon, we have said, is a group of stones which are treated as a unit. It is a working hypothesis that these stones will live or die together. Thus the program will not expect to disconnect an opponent's strings if they have been amalgamated into a single dragon.

The function make_dragons() will amalgamate worms into dragons by maintaining separate arrays worm[] and dragon[] containing similar data. Each dragon is a union of worms. Just as the data maintained in worm[] is constant on each worm, the data in dragon[] is constant on each dragon.

Amalgamation of worms in GNU Go proceeds as follows. First we amalgamate all boundary components of an eyeshape. Thus in the following example:

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

The code for this type of amalgamation is in the routine dragon_eye(), discussed further in EYES.

Next, we amalgamate strings which seem uncuttable. We amalgamate dragons which either share two or more common liberties, or share one liberty into the which the opponent cannot play without being captured. (ignores ko rule).

   X.    X.X     XXXX.XXX         X.O
   .X    X.X     X......X         X.X
                 XXXXXX.X         OXX

A database of connection patterns may be found in `patterns/conn.db'.

7.3 Connection

The fields black_eye.cut and white_eye.cut are set where the opponent can cut, and this is done by the B (break) class patterns in `conn.db'. There are two important uses for this field, which can be accessed by the autohelper functions xcut() and ocut(). The first use is to stop amalgamation in positions like

..X..
OO*OO
X.O.X
..O..

where X can play at * to cut off either branch. What happens here is that first connection pattern CB1 finds the double cut and marks * as a cutting point. Later the C (connection) class patterns in conn.db are searched to find secure connections over which to amalgamate dragons. Normally a diagonal connection would be deemed secure and amalgamated by connection pattern CC101, but there is a constraint requiring that neither of the empty intersections is a cutting point.

A weakness with this scheme is that X can only cut one connection, not both, so we should be allowed to amalgamate over one of the connections. This is performed by connection pattern CC401, which with the help of amalgamate_most_valuable_helper() decides which connection to prefer.

The other use is to simplify making alternative connection patterns to the solid connection. Positions where the diag_miai helper thinks a connection is necessary are marked as cutting points by connection pattern 12. Thus we can write a connection pattern like CC6:

?xxx?     straight extension to connect
XOO*?
O...?

:8,C,NULL

?xxx?
XOOb?
Oa..?

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

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:

XXXXX
OO..X
O.O.X
OOXXX

Here is a false eye:

XXXXX
XOO.X
O.O.X
OOXXX

The "topological" algorithm for determining half and false eyes is described elsewhere (see section 8.8 Topology of Half Eyes and False Eyes).

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];

struct half_eye_data {
  float value;          /* Topological eye value */
  int type;             /* HALF_EYE or FALSE_EYE */
  int num_attacks;      /* Number of attacking points */
  int attack_point[4];  /* The moves to attack a topological halfeye */
  int num_defends;      /* Number of defending points */
  int defense_point[4]; /* The moves to defend a topological halfeye */
};

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 defense points.

7.5 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 discussed below.)

struct dragon_data {
  int color;    /* its color                               */
  int id;       /* the index into the dragon2 array        */
  int origin;   /* the origin of the dragon. Two vertices  */
                /* are in the same dragon iff they have    */
                /* same origin.                            */
  int size;     /* size of the dragon                      */
  float effective_size; /* stones and surrounding spaces   */
  int crude_status;     /* (ALIVE, DEAD, UNKNOWN, CRITICAL)*/
  int status;           /* best trusted status             */
};

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

struct dragon_data2 {
  int origin;
  int adjacent[MAX_NEIGHBOR_DRAGONS];
  int neighbors;
  int hostile_neighbors;
  int moyo_size;
  float moyo_territorial_value;
  int safety;
  float weakness;
  float weakness_pre_owl;
  int escape_route;
  struct eyevalue genus;
  int heye;
  int lunch;
  int surround_status;
  int surround_size;
  int semeais;
  int semeai_margin_of_safety;
  int semeai_defense_point;
  int semeai_defense_certain;  
  int semeai_attack_point;
  int semeai_attack_certain;
  int owl_threat_status;
  int owl_status;
  int owl_attack_point;
  int owl_attack_code;
  int owl_attack_certain;
  int owl_second_attack_point;
  int owl_defense_point;
  int owl_defense_code;
  int owl_defense_certain;
  int owl_second_defense_point;
  int owl_attack_kworm;
  int owl_defense_kworm;
};

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;
  do_something(apos);
}

Similarly if you know the dragon number (which is dragon[pos].id) then you can access the dragon2 array directly, or you can access the dragon array using the DRAGON macro.

Here are the definitions of each field in the dragon arrray.

• color

  The color of the dragon.

• id

  The dragon number, used as a key into the dragon2 array.

• origin

  The origin of the dragon is a unique particular vertex of the dragon, useful for determining when two vertices belong to the same dragon. Before amalgamation the worm origins are copied to the dragon origins. Amalgamation of two dragons amounts to changing the origin of one.

• size

  The number of stones in the dragon.

• effective size

  The sum of the effective sizes of the constituent worms. Remembering that vertices equidistant between two or more worms are counted fractionally in worm.effective_size, this equals the cardinality of the dragon plus the number of empty vertices which are nearer this dragon than any other.

• crude_status

  (ALIVE, DEAD, UNKNOWN, CRITICAL). An early measure of the life potential of the dragon. It is computed before the owl code is run and is superceded by the status as soon as that becomes available.

• status

  The dragon status is the best measure of the dragon's health. It is 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.

• origin

  The origin field is duplicated here.

• adjacent
• adjacent[MAX_NEIGHBOR_DRAGONS]

  Dragons of either color near the given one are called neighbors. They are computed by the function find_neighbor_dragons(). The dragon2.adjacent array gives the dragon numbers of these dragons.

• neighbors

  Dragons of either color near the given one are called neighbors. They are computed by the function find_neighbor_dragons(). The dragon2.adjacent array gives the dragon numbers of these dragons.

• neighbors

  The number of neighbor dragons.

• hostile_neighbors

  The number of neighbor dragons of the opposite color.

• moyo_size
• float moyo_territorial_value

  The function compute_surrounding_moyo_sizes() assigns a size and a territorial value to the moyo around each dragon (see section 13.2 Territory, Moyo and Area). This is the moyo size. They are recorded in these fields.

• safety

  The dragon safety can take on one of the values

  • TACTICALLY_DEAD - a dragon consisting of a single worm found dead by the reading code (very reliable)
  • ALIVE - found alive by the owl or semeai code
  • STRONGLY_ALIVE - alive without much question
  • INVINCIBLE - definitively alive even after many tenukis
  • ALIVE_IN_SEKI - determined to be seki by the semeai code
  • CRITICAL - lives or dies depending on who moves first
  • DEAD - found to be dead by the owl code
  • INESSENTIAL - the dragon is unimportant (e.g. nakade stones) and dead

• weakness
• weakness_pre_owl

  A floating point measure of the safety of a dragon. The dragon weakness is a number between 0. and 1., higher numbers for dragons in greater need of safety. The field weakness_pre_owl is a preliminary computation before the owl code is run.

• escape_route

  A measure of the dragon's potential to escape towards safety, in case it cannot make two eyes locally. Documentation may be found in 13.9 Escape.

• struct eyevalue genus

  The approximate number of eyes the dragon can be expected to get. Not guaranteed to be accurate. The eyevalue struct, which is used throughout the engine, is declared thus:

  struct eyevalue { unsigned char a; /* # of eyes if attacker plays twice */ unsigned char b; /* # of eyes if attacker plays first */ unsigned char c; /* # of eyes if defender plays first */ unsigned char d; /* # of eyes if defender plays twice */ };

• heye

  Location of a half eye attached to the dragon.

• lunch

  If nonzero, this is the location of a boundary string which can be captured. In contrast with worm lunches, a dragon lunch must be able to defend itself.

• surround_status
• surround_size

  In estimating the safety of a dragon it is useful to know if it is surrounded. See 13.11 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).

• semeais
• semeai_defense_point
• semeai_defense_certain
• semeai_attack_point
• semeai_attack_certain

  If two dragons of opposite color both have the status CRITICAL or DEAD they are in a semeai (capturing race), and their status must be adjudicated by the function owl_analyze_semeai() in `owl.c', which attempts to 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 running out of nodes.

• owl_status

  This is a classification similar to dragon.crude_status, but based on the life and death reading in `owl.c'. The owl code (see section 12.1 The Owl Code) is skipped for dragons which appear safe by certain heuristics. If the owl code is not run, the owl status is UNCHECKED. If owl_attack() determines that the dragon cannot be attacked, it is classified as ALIVE. Otherwise, owl_defend() is run, and if it can be defended it is classified as CRITICAL, and if not, as DEAD.

• owl_attack_point

  If the dragon can be attacked this is the point to attack the dragon.

• owl_attack_code

  The owl attack code, It can be WIN, KO_A, KO_B or 0 (see Return Codes).

• owl_attack_certain

  The owl reading is able to finish analyzing the attack without running out of nodes.

• owl_second_attack_point

  A second attack point.

• owl_defense_point

  If the dragon can be defended, this is the place to play.

• owl_defense_code

  The owl defense code, It can be WIN, KO_A, KO_B or 0 (see Return Codes).

• owl_defense_certain

  The owl code is able to finish analyzing the defense without running out of nodes.

• owl_second_defense_point

  A second owl defense point.

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 displayed in White.

Save a game in sgf format using CGoban, or using the `-o' option with GNU Go itself.

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.

Execute:

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 (see section 8. Eyes and Half Eyes).
• the option -m 0x0180 to display territory, moyo and area (see section 13.2 Territory, Moyo and Area).

The colored displays are documented elsewhere (see section 5.8 Colored Display).

8. Eyes and Half Eyes

The purpose of this Chapter is to describe the algorithm used in GNU Go to determine eyes.

8.1 Local games

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 `G' and `H'.

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:

XXXXX
XOOOX
XO.OOX
XX..OX
XXOOXX
XXXXX

8.2 Eye spaces

In order that each eyespace be assignable to a dragon, it is necessary that all the dragons surrounding it be amalgamated (see section 7.2 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:

 |. X . X X . . X O X O 
 |X . . . . . X X O O O
 |O X X X X . . X O O O
 |O O O O X . O X O O O
 |. . . . O O O O X X O
 |X O . X X X . . X O O
 |X O O O O O O O X X O
 |. X X O . O X O . . X
 |X . . X . X X X X X X
 |O X X O X . X O O X O

Here the `O' dragon which is surrounded in the center has open eye space. In the middle of this open eye space are three dead `X' stones. This space is large enough that O cannot be killed. We can abstract the properties of this eye shape as follows. Marking certain vertices as follows:

 |- X - X X - - X O X O 
 |X - - - - - X X O O O
 |O X X X X - - X O O O
 |O O O O X - O X O O O
 |! . . . O O O O X X O
 |X O . X X X . ! X O O
 |X O O O O O O O X X O
 |- X X O - O X O - - X
 |X - - X - X X X X X X
 |O X X O X - X O O X O

the shape in question has the form:

!...
  .XXX.!

The marginal vertices are marked with an exclamation point (`!'). The captured `X' stones inside the eyespace are naturally marked `X'.

The precise algorithm by which the eye spaces are determined is somewhat complex. Documentation of this algorithm is in the comments in the source to the function make_domains() in `optics.c'.

The eyespaces can be conveniently displayed using a colored ascii diagram by running gnugo -E.

8.3 The eyespace as local game

In the abstraction, an eyespace consists of a set of vertices labelled:

!  .  X

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

For example, we have:

Pattern 548

 x
xX.!

:0111

Here notation is as above, except that `x' means `X' or EMPTY. The result of the pattern is not different if `X' has stones at these vertices or not.

We may abstract the local game as follows. The two players `O' and `X' take turns moving, or either may pass.

RULE 1: `O' for his move may remove any vertex marked `!' or marked `.'.

RULE 2: `X' for his move may replace a `.' by an `X'.

RULE 3: `X' may remove a `!'. In this case, each `.' adjacent to the `!' which is removed becomes a `!' . If an `X' adjoins the `!' which is removed, then that `X' and any which are connected to it are also removed. Any `.' which are adjacent to the removed `X''s then become `.'.

Thus if `O' moves first he can transform the eyeshape in the above example to:

 ...            or      !...
  .XXX.!                  .XXX.

However if `X' moves he may remove the `!' and the `.'s adjacent to the `!' become `!' themselves. Thus if `X' moves first he may transform the eyeshape to:

 !..           or    !..
  .XXX.!              .XXX!

NOTE: A nuance which is that after the `X:1', `O:2' exchange below, `O' is 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.

 |- X - X X - - X O X O 
 |X - - - - - X X O O O
 |O X X X X - - X O O O
 |O O O O X - O X O O O
 |1 2 . . O O O O X X O
 |X O . X X X . 3 X O O
 |X O O O O O O O X X O
 |- X X O - O X O - - X
 |X - - X - X X X X X X
 |O X X O X - X O O X O

We will not attempt to characterize the terminal states of the local game (some of which could be seki) or the scoring.

8.4 An example

Here is a local game which yields exactly one eye, no matter who moves first:

!
...
...!

Here are some variations, assuming `O' moves first.

!        (start position)
...
...!


...      (after `O''s move)
...!


... 
..!


... 
..


.X.       (nakade)
..

Here is another variation:

!         (start)
...
...!


!         (after `O''s move)
. .
...!


!         (after `X''s move)
. .
..X!


. .
..X!


. !
.!

8.5 Graphs

It is a useful observation that the local game associated with an eyespace depends only on the underlying graph, which as a set consists of the set of vertices, in which two elements are connected by an edge if and only if they are adjacent on the Go board. For example the two eye shapes:

..
 ..

and

....

though distinct in shape have isomorphic graphs, and consequently they are isomorphic as local games. This reduces the number of eyeshapes in the database `patterns/eyes.db'.

A further simplification is obtained through our treatment of half eyes and false eyes. Such patterns are identified by the topological analysis (see section 8.8 Topology of Half Eyes and False Eyes).

A half eye is isomorphic to the pattern (!.) . To see this, consider the following two eye shapes:

XOOOOOO
X.....O
XOOOOOO

and:

XXOOOOO
XOa...O
XbOOOOO
XXXXXXX

These are equivalent eyeshapes, with isomorphic local games {2|1}. The first has shape:

!....

The second eyeshape has a half eye at `a' which is taken when `O' or `X' plays at `b'. This is found by the topological criterion (see section 8.8 Topology of Half Eyes and False Eyes).

The graph of the eye_shape, ostensibly `....' is modified by replacing the left `.' by `!.' during graph matching.

A false eye is isomorphic to the pattern (!) . To see this, consider the following eye shape:

XXXOOOOOO
X.Oa....O
XXXOOOOOO

This is equivalent to the two previous eyeshapes, with an isomorphic local game {2|1}.

This eyeshape has a false eye at `a'. This is also found by the topological criterion.

The graph of the eye_shape, ostensibly `.....' is modified by replacing the left `.' by `!'. This is made directly in the eye data, not only during graph matching.

8.6 Eye shape analysis

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 example

XXOOOOO
XOa...O
XbOOOOO
XXXXXX

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

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

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 as two.

The following 15 cases are of interest:

• 0000 0 eyes.
• 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 does.
• 0012 3/4 eyes, 3/2 eyes if defender moves first, 0 eyes if attacker does.
• 0022 1* eye, 2 eyes if defender moves first, 0 eyes if attacker does.
• 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 does.
• 0222 2 eyes, attacker can threaten to destroy both.
• 1111 1 eye.
• 1112 1 eye, defender can threaten to make another eye.
• 1122 3/2 eyes, 2 eyes if defender moves first, 1 eye if attacker does.
• 1222 2 eyes, attacker can threaten to destroy one eye.
• 2222 2 eyes.

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

Pattern 6141

 X
XX.@x

:1122

which e.g. matches in this position:

.OOOXXX
OOXOXOO
OXXba.O
OOOOOOO

Now it may look like `X' could take away both eyes by playing `a' followed by `b', giving 0122 as eye value. This is where the subtlety of the definition of the first digit in the eye value comes into play. It does not say that the attacker is allowed two consecutive moves but only that he is allowed to play "another move". The crucial property of this shape is that when `X' plays at a to destroy (at least) one eye, `O' can answer at `b', giving:

.OOOXXX
OO.OXOO
O.cOX.O
OOOOOOO

Now `X' has to continue at `c' in order to keep `O' at one eye. After this `O' plays tenuki and `X' cannot destroy the remaining eye by another move. Thus the eye value is indeed 1122.

As a final note, some of the eye values indicating a threat depend on suicide to be allowed, e.g.

Pattern 301
 
X.X

:1222

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

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:

   OOXX
   O.O.
   OO.X

A FALSE EYE is an eye vertex which cannot become a proper eye. Here are two examples of false eyes for O:

   OOX         OOX
   O.O         O.OO
   XOO         OOX

We describe now the topological algorithm used to find half eyes and false eyes. In this section we ignore the possibility of ko.

False eyes and half eyes can locally be characterized by the status of the diagonal intersections from an eye space. For each diagonal intersection, which is not within the eye space, there are three distinct possibilities:

• occupied by an enemy (X) stone, which cannot be captured.
• either empty and X can safely play there, or occupied by an X stone that can both be attacked and defended.
• occupied by an O stone, an X stone that can be attacked but not defended, or it's empty and X cannot safely play there.

We give the first possibility a value of two, the second a value of one, and the last a value of zero. Summing the values for the diagonal intersections, we have the following criteria:

• sum >= 4: false eye
• sum == 3: half eye
• sum <= 2: proper eye

If the eye space is on the edge, the numbers above should be decreased by 2. An alternative approach is to award diagonal points which are outside the board a value of 1. To obtain an exact equivalence we must however give value 0 to the points diagonally off the corners, i.e. the points with both coordinates out of bounds.

The algorithm to find all topologically false eyes and half eyes is:

For all eye space points with at most one neighbor in the eye space, evaluate the status of the diagonal intersections according to the criteria above and classify the point from the sum of the values.

8.9 Eye Topology with Ko

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':

.?O?   good for O
OO.O
O.O?
XOX.
.X..

.?O?   good for X
OO.O
OXO?
X.X.
.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:

e <= 2     - proper eye
2 < e < 3  - worse than proper eye, better than half eye
e = 3      - half eye
3 < e < 4  - worse than half eye, better than false eye
e >= 4     - 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
(a)   ..OO          e < 2
      OO.O
      O.OO      e = 1 + a
      XOX.
      .X..


      .X..      better than half eye, worse than proper eye
(a')  ..OO      2 < e < 3
      OO.O
      OXOO      e = 1 + b
      X.X.
      .X..

      
      .X..      better than half eye, worse than proper eye
(b)   .XOO      2 < e < 3
      OO.O
      O.OO      e = 2 + a
      XOX.
      .X..

      
      .X..      better than false eye, worse than half eye
(b')  .XOO      3 < e < 4
      OO.O
      OXOO      e = 2 + b
      X.X.
      .X..

      
      .X..
      XOX.      (slightly) better than proper eye
(c)   O.OO          e < 2
      OO.O
      O.OO      e = 2a
      XOX.
      .X..

      
      .X..
      XOX.      proper eye, some aji
(c')  O.OO      e ~ 2
      OO.O
      OXOO      e = a + b
      X.X.
      .X..

      
      .X..
      X.X.      better than half eye, worse than proper eye
(c'') OXOO      2 < e < 3
      OO.O
      OXOO      e = 2b
      X.X.
      .X..

      
      .X...
      XOX..     better than half eye, worse than proper eye
(d)   O.O.X     2 < e < 3
      OO.O.
      O.OO.     e = 1 + 2a
      XOX..
      .X...

      
      .X...
      XOX..     half eye, some aji
(d')  O.O.X     e ~ 3
      OO.O.
      OXOO.     e = 1 + a + b
      X.X..
      .X...

      
      .X...
      X.X..     better than false eye, worse than half eye
(d'') OXO.X     3 < e < 4
      OO.O.
      OXOO.     e = 1 + 2b
      X.X..
      .X...

      
      .X...
      XOX..     better than false eye, worse than half eye
(e)   O.OXX     3 < e < 4
      OO.O.
      O.OO.     e =  2 + 2a
      XOX..
      .X...

      
      .X...
      XOX..     false eye, some aji
(e')  O.OXX     e ~ 4
      OO.O.
      OXOO.     e = 2 + a + b
      X.X..
      .X...

      
      .X...
      X.X..     (slightly) worse than false eye
(e'') OXOXX     4 < e
      OO.O.
      OXOO.     e = 2 + 2b
      X.X..
      .X...

It may seem obvious that we should use

(i)   a=1/2, b=3/2

(ii)  a=2/3, b=4/3
(iii) a=3/4, b=5/4
(iv)  a=4/5, b=6/5

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')    a+b             2       2       2       2           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+a+b           3       3       3       3           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+a+b           4       4       4       4           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.

8.10 False Margins

The following situation is rare but special enough to warrant separate attention:

   OOOOXX
   OXaX..
   ------

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 (X), not (X!).

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 are not adjoining.

       uabc
        def
        ghi

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.

   +---
   |ab
   |cd

We get friendly influence at `a' if we have friendly influence at `b' or `c' and no lively unfriendly stone at `b', `c' or `d'.

Here are the public functions in `optics.c', except some simple access functions used by autohelpers. The statically declared functions are documented in the source code.

• void make_domains(struct eye_data b_eye[BOARDMAX], struct eye_data w_eye[BOARDMAX], int owl_call)

  This function is called from make_dragons() and from owl_determine_life(). It marks the black and white domains (eyeshape regions) and collects some statistics about each one.

• void partition_eyespaces(struct eye_data eye[BOARDMAX], int color)

  Find connected eyespace components and compute relevant statistics.

• void propagate_eye(int origin, struct eye_data eye[BOARDMAX])

  propagate_eye(origin) copies the data at the (origin) to the rest of the eye (invariant fields only).

• int find_eye_dragons(int origin, struct eye_data eye[BOARDMAX], int eye_color, int dragons[], int max_dragons)

  Find the dragon or dragons surrounding an eye space. Up to max_dragons dragons adjacent to the eye space are added to the dragon array, and the number of dragons found is returned.

• 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 color = EMPTY.

• 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 heye[BOARDMAX])

  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 territory at all.

• 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_mask[BOARDMAX])

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

• void set_eyevalue(struct eyevalue *e, int a, int b, int c, int d)

  (see section 8.7 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 alternating play.

• int max_eyes(struct eyevalue *e)

  Number of eyes if defender plays first followed by alternating play.

• int max_eye_threat(struct eyevalue *e)

  Number of eyes if defender plays first twice (the threat of the first move by defender).

• void add_eyevalues(struct eyevalue *e1, struct eyevalue *e2, struct eyevalue *sum)

  Add the eyevalues *e1 and *e2, leaving the result in *sum. It is safe to let sum be the same as e1 or e2.

• char * eyevalue_to_string(struct eyevalue *e)

  Produces a string containing the eyevalue. Note: the result string is stored in a statically allocated buffer which will be overwritten the next time this function is called.

• void test_eyeshape(int eyesize, int *eye_vertices) /* Test whether the optics code evaluates an eyeshape consistently. */
• int analyze_eyegraph(const char *coded_eyegraph, struct eyevalue *value, char *analyzed_eyegraph)

  Analyze an eye graph to determine the eye value and vital moves. The eye graph is given by a string which is encoded with `%' for newlines and `O' for spaces. E.g., the eye graph

  ! .X !...

  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)

  .X !.*.

  If the eye graph cannot be realized, 0 is returned, 1 otherwise.

9. The Pattern Code

9.1 Overview

Several pattern databases are in the patterns directory. This chapter primarily discusses the patterns in `patterns.db', `patterns2.db', and the pattern files `hoshi.db' etc. which are compiled from the SGF files `hoshi.sgf' (see section 9.16 The 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 `patterns2.db'.

During the execution of genmove(), the patterns are matched in `shapes.c' in order to find move reasons.

The same basic pattern format is used by `attack.db', `defense.db', `conn.db', `apats.db' and `dpats.db'. However these patterns are used for different purposes. These databases are discussed in other parts of this documentation. The patterns in `eyes.db' are entirely different and are documented elsewhere (see section 8. Eyes and Half Eyes).

The patterns described in the databases are ascii representations, of the form:

Pattern EB112

  ?X?.?       jump under
  O.*oo
  O....
  o....
  -----
  
  :8,ed,NULL

Here `O' marks a friendly stone, `X' marks an enemy stone, `.' marks an empty vertex, `*' marks O's next move, `o' marks a square either containing `O' or empty but not `X'. (The symbol `x', which does not appear in this pattern, means `X' or `.'.) Finally `?' Indicates a location where we don't care what is there, except that it cannot be off the edge of the board.

The line of `-''s along the bottom in this example is the edge of the board itself--this is an edge pattern. Corners can also be indicated. Elements are not generated for `?' markers, but they are not completely ignored - see below. The line beginning `:' describes various attributes of the pattern, such as its 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 filled with NULL.

The matcher in `matchpat.c' searches the board for places where this layout appears on the board, and the callback function shapes_callback() in `shapes.c' registers the appropriate move reasons.

After the pattern, there is some supplementary information in the format:

  :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:

  |oOO?
  |...X
  |..*?
  |..o.
  |..o?

  :8,ed,NULL

The program mkpat is capable of parsing patterns written this way, or for that matter, on the top or right edges, or in any of the four corners. As a matter of convention all the edge patterns in `patterns.db' are written on the bottom edge or in the lower left corners. In the `patterns/' directory there is a program called transpat which can rotate or otherwise transpose patterns. This program is not built by default--if you think you need it, make transpat in the `patterns/' directory and consult the usage remarks at the beginning of `patterns/transpat.c'.

9.2 Pattern Attributes

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 to add a move reason.

9.2.1 Constraint Pattern Attributes

• `s'

  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 made, though.

• `n'

  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.

• `O'

  It is checked that every friendly (`O') stone of the pattern belongs to a dragon which has status (see section 7.5 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 pattern is rejected.

• `o'

  It is checked that every friendly (`O') stone of the pattern belongs to a dragon which is classified as DEAD or UNKNOWN.

• `X'

  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.

• `x'

  It is checked that every opponent (`X') stone of the pattern belongs to a dragon which is classified as DEAD or UNKNOWN

9.2.2 Action Attributes

• `C'

  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 considered move.

• `c'

  Add strategical defense move reason for all our dragons and a small shape bonus. This classification is appropriate for weak connection patterns.

• `B'

  If two or more distinct `X' dragons occur in the pattern, the move is given the move reasons that it cuts each pair of dragons.

• `e'

  The move makes or secures territory.

• `E'

  The move attempts increase influence and create/expand a moyo.

• `d'

  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.

• `a'

  The move strategically attacks all `X' dragons in the pattern.

• `J'

  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.

• `F'

  This indicates a fuseki pattern. This is only effective together with either the `j' or `t' classification, and is used to ensure indeterministic play during fuseki.

• `j'

  Slightly less urgent joseki move. These moves will be made after those with the `J' classification. This adds the `e' and `E' classifications. If the move has the `F' classification, it also gets a fixed value of 20.1, otherwise it gets a minimum accepted value of 20. (This makes sure that GNU Go chooses randomly between different moves that have `jF' as classification.)

• `t'

  Minor joseki move (tenuki OK). This is equivalent to adding the `e' and `E' classifications together with either a fixed value of 15.07 (if the move has `F' classification) or a minimum value of 15 (otherwise).

• `U'

  Urgent joseki move (never tenuki). This is equivalent to the `d' and `a' classifications together with a shape bonus of 15 and a minimum accepted value of 40.

A commonly used class is OX (which rejects pattern if either side has dead stones). The string `-' may be used as a placeholder. (In fact any characters other than the above and `,' are ignored.)

The types `o' and `O' could conceivably appear in a class, meaning it applies only to UNKNOWN. `X' and `x' could similarly be used together. All classes can be combined arbitrarily.

9.3 Pattern Attributes

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.

• terri(x)

  Forces the territorial value of the move to be at least x.

• minterri(x)

  Forces the territorial value of the move to be at least x.

• maxterri(x)

  Forces the territorial value of the move to be at most x.

• value(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.

• shape(x)

  Adds x to the move's shape value.

• followup(x)

  Adds x to the move's followup value.

The meaning of these values is documented in See section 6. Move generation.

9.4 Helper Functions

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 board locations.

The actual helper functions are in `helpers.c'. They are declared in `patterns.h'.

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:

/*

?O.           ?Ob
.X*           aX*
?O.           ?Oc

:8,C,wedge_helper
*/

The image on the left is the actual pattern. On the right we've taken this image and added letters to label apos, bpos, and cpos. The position of *, the point where GNU Go will move if the pattern is adopted, is passed through the parameter move.

int 
wedge_helper(ARGS)
{
  int apos, bpos, cpos;
  int other = OTHER_COLOR(color);
  int success = 0;
  
  apos = OFFSET(0, -2);
  bpos = OFFSET(-1, 0);
  cpos = OFFSET(1, 0);

  if (TRYMOVE(move, color)) {
    if (TRYMOVE(apos, other)) {
      if (board[apos] == EMPTY || attack(apos, NULL))
        success = 1;
      else if (TRYMOVE(bpos, color)) {
        if (!safe_move(cpos, other))
          success = 1;
        popgo();
      }
      popgo();
    }
    popgo();
  }
  
  return success;
}

The OFFSET lines tell GNU Go the positions of the three stones at `a', `b', and `c'. To decide whether the pattern guarantees a connection, we do some reading. First we use the TRYMOVE macro to place an `O' at `move' and let `X' draw back to `a'. Then we ask whether `O' can capture these stones by calling attack(). The test if there is a stone at `a' before calling attack() is in this position not really necessary but it's good practice to do so, because if the attacked stone should happen to already have been captured while placing stones, GNU Go would crash with an assertion failure.

If this attack fails we let `O' connect at `b' and use the safe_move() function to examine whether a cut by `X' at `c' could be immediately captured. Before we return the result we need to remove the stones we placed from the reading stack. This is done with the function popgo().

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.

Pattern Conn311

O*.
?XO

:8,C,NULL

O*a
?BO

;oplay_attack_either(*,a,a,B)

Here we have given the label `a' to the empty spot to the right of the considered move and the label `B' to the `X' stone in the pattern. In addition to these, `*' can also be used as a label. A label may be any lowercase or uppercase ascii letter except OoXxt. By convention we use uppercase letters for `X' stones and lowercase for `O' stones and empty intersections. When labeling a stone that's part of a larger string in the pattern, all stones of the string should be marked with the label. (These conventions are not enforced by the pattern compiler, but to make the database consistent and easy to read they should be followed.)

The labels can now be used in the constraint expression. In this example we have a reading constraint which should be interpreted as "Play an `O' stone at `*' followed by an `X' stone at `a'. Accept the pattern if `O' now can capture either at `a' or at `B' (or both strings)."

The functions that are available for use in the constraints are listed in the section `Autohelpers Functions' below. Technically the constraint expression is transformed by mkpat into an automatically generated helper function in `patterns.c'. The functions in the constraint are replaced by C expressions, often functions calls. In principle any valid C code can be used in the constraints, but there is in practice no reason to use anything more than boolean and arithmetic operators in addition to the autohelper functions. Constraints can span multiple lines, which are then concatenated.

9.6 Autohelper Actions

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.

Example:

Pattern EJ4

...*.     continuation
.OOX.
..XOX
.....
-----

:8,Ed,NULL

...*.     never play a here
.OOX.
.aXOX
.....
-----

>antisuji(a)

The line starting with `>' is the action line. In this case it tells the move generation that the move at a should not be considered, whatever move reasons are found by other patterns. The action line uses the labels from the constraint diagram. Both constraint and action can be used in the same pattern. If the action only needs to refer to `*', no constraint diagram is required. Like constraints, actions can span multiple lines.

Here is a partial list of the autohelper macros which are typically called from action lines. This list is not complete. If you cannot find an autohelper macro in an action line in this list, consult `mkpat.c' to find out what function in the engine is actually called. If no macro exists which does what you want, you can add macros by editing the list in `mkpat.c'.

• antisuji(a);

  Mark `a' as an antisuji, that is, a move that must never be played.

• replace(a,*)

  This is appropriate if the move at `*' is definitely better than the move at `a'. The macro adds a point redistribution rule. Any points which are assigned to `a' during the move generation by any move reason are redistributed to `*'.

• prevent_attack_threat(a)

  Add a reverse followup value because the opponent's move here would threaten to capture `a'.

• threaten_to_save(a)

  Add a followup value because the move at `*' threatens to rescue the dead string at `a'.

• defend_against_atari(a)

  Estimate the value of defending the string `a' which can be put into atari and add this as a reverse followup value.

• add_defend_both_move(a,b);

• add_cut_move(c,d);

  Add to the move reasons that the move at `*' threatens to cut `c' and `d'.

9.7 Autohelper Functions

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.

lib(x)
lib2(x)
lib3(x)
lib4(x)

Number of first, second, third, and fourth order liberties of a worm respectively. See section 7. Worms and Dragons, the documentation on worms for definitions.

xlib(x)
olib(x)

The number of liberties that an enemy or own stone, respectively, would obtain if played at the empty intersection `x'.

xcut(x)
ocut(x)

Calls cut_possible (see section 18.1 General Utilities) to determine whether `X' or `O' can cut at the empty intersection `x'.

ko(x)

True if `x' is either a stone or an empty point involved in a ko position.

status(x)

The matcher status of a dragon. status(x) returns an integer that can have the values ALIVE, UNKNOWN, CRITICAL, or DEAD (see section 7. Worms and Dragons).

alive(x)
unknown(x)
critical(x)
dead(x)

Each function true if the dragon has the corresponding matcher status and false otherwise (see section 7. Worms and Dragons).

status(x)

Returns the status of the dragon at `x' (see section 7. Worms and Dragons).

genus(x)

The number of eyes of a dragon. It is only meaningful to compare this value against 0, 1, or 2.

xarea(x)
oarea(x)
xmoyo(x)
omoyo(x)
xterri(x)
oterri(x)

These functions call whose_territory(), whose_moyo() and whose_area() (see section 13.2 Territory, Moyo and Area). 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 be secure territory.

weak(x)

True for a dragon that is perceived as weak.

attack(x)
defend(x)

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

safe_xmove(x)
safe_omove(x)

True if an enemy or friendly stone, respectively, can safely be played at `x'. By safe it is understood that the move is legal and that it cannot be captured right away.

legal_xmove(x)
legal_omove(x)

True if an enemy or friendly stone, respectively, can legally be played at x.

o_somewhere(x,y,z, ...)
x_somewhere(x,y,z, ...)

True if O (respectively X) has a stone at one of the labelled vertices. In the diagram, these vertices should be marked with a `?'.

odefend_against(x,y)
xdefend_against(x,y)

True if an own stone at `x' would stop the enemy from safely playing at `y', and conversely for the second function.

does_defend(x,y)
does_attack(x,y)

True if a move at `x' defends/attacks the worm at `y'. For defense a move of the same color as `y' is tried and for attack a move of the opposite color.

xplay_defend(a,b,c,...,z)
oplay_defend(a,b,c,...,z)
xplay_attack(a,b,c,...,z)
oplay_attack(a,b,c,...,z)

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 special cases.

The special label `?' can be used to represent a tenuki. Thus oplay_defend(a,?,b,c) tries moves by `O' at `a' and `b', as if `X' plays the second move in another part of the board, then asks if `c' can be defended. The tenuki cannot be the first move of the sequence, nor does it need to be: instead of oplay_defend(?,a,b,c) you can use xplay_defend(a,b,c).

xplay_defend_both(a,b,c,...,y,z)
oplay_defend_both(a,b,c,...,y,z)
xplay_attack_either(a,b,c,...,y,z)
oplay_attack_either(a,b,c,...,y,z)

These functions are similar to the previous ones. The difference is that the last *two* arguments denote worms to be attacked or defended simultaneously. Obviously `y' and `z' must have the same color. If either location is empty, it is assumed that an attack has been successful or a defense has failed. The typical use for these functions is in cutting patterns, where it usually suffices to capture either cutstone.

The function xplay_defend_both plays alternate moves beginning with an `X' at `a'. Then it passes the last two arguments to defend_both in `engine/utils.c'. This function checks to determine whether the two strings can be simultaneously defended.