Table of Contents

Node:Top, Next:, Previous:(dir), Up:(dir)

Node:Introduction, Next:, Previous:Top, Up:Top

Introduction

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

Node:About, Next:, Up:Introduction

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. For one thing, we've paid a lot of attention to life and death. GNU Go 3.0 can consistently give GNU Go 2.6 a four stone handicap. In a four stone game against GNU Go 2.6, GNU Go 3.0 very often kills a group. GNU Go 3.2 is even stronger than 3.0.

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.

Node:Copyright, Next:, Previous:About, Up:Introduction

Copyrights

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

All files are under the GNU General Public License (see GPL), 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 GTP License).

The two files gmp.c and gmp.h were placed in the public domain by William Shubert, their author, and are free for unrestricted use.

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.

Node:Authors, Next:, Previous:Copyright, Up:Introduction

Authors

GNU Go maintainers are Daniel Bump and Gunnar Farnebäck. GNU Go authors (in chronological order of contribution) are Man Li, Daniel Bump, David Denholm, Gunnar Farnebäck, Nils Lohner, Jerome Dumonteil, Tommy Thorn, Nicklas Ekstrand, Inge Wallin, Thomas Traber, Douglas Ridgway, Teun Burgers, Tanguy Urvoy, Thien-Thi Nguyen, Heikki Levanto, Mark Vytlacil, Adriaan van Kessel, Wolfgang Manner, Jens Yllman, Don Dailey, Måns Ullerstam, Arend Bayer and Trevor Morris.

Node:Thanks, Next:, Previous:Authors, Up:Introduction

Thanks

We would like to thank Arthur Britto, Tim Hunt, 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.

Node:TODO, Previous:Thanks, Up:Introduction

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 GPL). But if you want your changes to the program to be incorporated into the version we distribute we need you to assign the copyright.

Please contact the GNU Go maintainers, Daniel Bump (bump@math.stanford.edu) and Gunnar Farnebäck (gf@isy.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.

General

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.

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.

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.

Node:Installation, Next:, Previous:Introduction, Up:Top

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

Node:GNU/Linux and Unix, Next:, Up:Installation

GNU/Linux and Unix

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

   ./configure [OPTIONS]
   make

Several configure options will be explained in detail in the next section (see Configure Options). 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-experimental-semeai --enable-owl-threats

turns on two experimental options.

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) or Jago (on any platform with a Java runtime environment).

You can get the most recent version of CGoban 1 from Bill Shubert's web site: <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 CGoban, for instructions on how to run GNU Go from Cgoban, or See Jago, for Jago.

Node:Configure Options, Next:, Previous:GNU/Linux and Unix, Up:Installation

Configure Options

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

Node:Ram Cache, Next:, Up:Configure Options

Ram Cache

By default, GNU Go makes a cache of 16 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.

Node:Default Level, Next:, Previous:Ram Cache, Up:Configure Options

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.

Node:DFA Option, Next:, Previous:Default Level, Up:Configure Options

DFA Configure Option

There are two distinct implementations of the pattern matcher in GNU Go. The DFA (Discrete Finite-state Automata) option was considered experimental in GNU Go 3.0 but is now standard. You can disable it by with the configure option ./configure --disable-dfa. The option is harder to debug than the old matcher but significantly faster (see DFA).

Node:Experimental Options, Previous:DFA Option, Up:Configure Options

Experimental Options

There are a number of experimental configure options. For example you can ./configure --enable-experimental-semeai or ./configure --disable-experimental-semeai to turn the experimental reading module on or 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.

Node:Windows and MS-DOS, Next:, Previous:Configure Options, Up:Installation

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

Node:DJGPP, Next:, Up:Windows and MS-DOS

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 gnugo source available as gnugo-3.2.tar.gz you can build the executable as follows: 

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

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

Node:Cygwin, Next:, Previous:DJGPP, Up:Windows and MS-DOS

Windows NT, Windows 95/98 using Cygwin

On these platforms the Cygwin environment can be installed. Recent versions of Cygwin install very easily with the setup program available from the cygwin homepage. <<http://sourceware.cygnus.com/cygwin/>. 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.2.tar.gz you can type: 

  tar zxvf gnugo-3.2.tar.gz
  cd gnugo-3.2
  ./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.

Cygwin Home page: <http://sourceware.cygnus.com/cygwin/>

Optionally you can use glib to get a working version of snprintf. Glib builds out of the box on cygwin.

Node:MinGW32, Next:, Previous:Cygwin, Up:Windows and MS-DOS

Windows NT, Windows 95/98 using MinGW32

The Cygwin environment also comes with MinGW32. This 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.2.tar.gz
  cd gnugo-3.2
  env CC='gcc -mno-cygwin' ./configure
  make

Node:VC, Previous:MinGW32, Up:Windows and MS-DOS

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:

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.

Node:Macintosh, Previous:Windows and MS-DOS, Up:Installation

Macintosh

If you have Mac OS X you can build GNU Go using Apple's compiler, which is derived from GCC. We recommend adding the flag -no-cpp-precom to CFLAGS.

Node:User Guide, Next:, Previous:Installation, Up:Top

Using GNU Go

Node:Documentation, Next:, Up:User Guide

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 or make gnugo.ps in the doc/ directory.

You can make an HTML version with the command makeinfo --html gnugo.texi. Better HTML documentation may be obtained using texi2html -split_chapter gnugo.texi. You can obtain the texi2html utility (version 1.61 or later) from <http://www.mathematik.uni-kl.de/~obachman/Texi2html/>. (See also <http://texinfo.org/texi2html/>.)

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.

Node:CGoban, Next:, Previous:Documentation, Up:User Guide

Running GNU Go via CGoban

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

Node:Ascii, Next:, Previous:CGoban, Up:User Guide

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.

Node:Emacs, Next:, Previous:Ascii, Up:User Guide

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. This may require Emacs 20.4 or later--it has been tested with Emacs 20.4 but does not work with Emacs 19 or Emacs 20.2.

Load interface/gnugo.el, either by M-x load-file, or by copying the file into your site-lisp directory and adding a line 

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

in your .emacs file.

Now you may start GNU Go by M-x gnugo. You will be prompted for command line options see Invoking GNU Go. Using these, you may set the handicap, board size, color and komi.

You can enter commands from the GNU Go ASCII interface after typing :. For example, to take a move back, type :back, or to list all commands, type :help.

Here are the default keybindings:

Node:Jago, Next:, Previous:Emacs, Up:User Guide

Running GNU Go via Jago

Jago, like CGoban is a client capable of providing GNU Go with a graphical user interface. Unlike CGoban, it does not require X-Windows, so it is an attractive alternative under Windows. You will need a Java runtime environment. Obtain Jago at

<http://www.rene-grothmann.de/jago/>

and follow the links there for the Java runtime environment.

Node:GMP and GTP, Next:, Previous:Jago, Up:User Guide

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 GTP) which we hope can serve the functions currently used by the GMP.

Node:Tournaments, Next:, Previous:GMP and GTP, Up:User Guide

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.

Node:SGF Support, Next:, Previous:Tournaments, Up:User Guide

Smart Go Format

The Smart Go 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/>

Node:Invoking GNU Go, Previous:SGF Support, Up:User Guide

Invoking GNU Go: Command line options

Some basic options

Other general options:

Other options affecting strength and speed

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.

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

Ascii Mode Options

Development options:

Node:Overview, Next:, Previous:User Guide, Up:Top

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.

Node:Definitions, Next:, Previous:Overview, Up:Overview

Definitions

A worm is a maximal set of vertices on the board which are connected along the horizontal and vertical lines, and are of the same color, which can be BLACK, WHITE or EMPTY. The term EMPTY applied to a worm means that the worm consists of empty (unoccupied) vertices. It does not mean that that the worm is the empty set. A string is a nonempty worm. An empty worm is called a cavity. If a subset of vertices is contained in a worm, there is a unique worm containing it; this is its worm closure. (see Worms.)

A dragon is a union of strings of the same color which will be treated as a unit. If two strings are in the same dragon, it is the computer's working hypothesis that they will live or die together and are effectively connected. (see Dragons.)

A superstring is a less commonly used unit which is the union of several strings but generally smaller than a dragon. The superstring code is in engine/utils.c. The definition of a superstring is slightly different if the code is called from owl.c or from reading.c.

Node:The Board, Next:, Previous:Definitions, Up:Overview

GNU Go represents the board in a one-dimensional array called board. For some purposes a two dimensional indexing of the board by parameters (i,j) might be used.

The board array includes out-of-board markers around the board. To make the relation to the old two-dimensional board representation clear, this figure shows how the 1D indices correspond to the 2D indices when MAX_BOARD is 7. 

  j  -1   0   1   2   3   4   5   6
i +----------------------------------
-1|   0   1   2   3   4   5   6   7
 0|   8   9  10  11  12  13  14  15
 1|  16  17  18  19  20  21  22  23
 2|  24  25  26  27  28  29  30  31
 3|  32  33  34  35  36  37  38  39
 4|  40  41  42  43  44  45  46  47
 5|  48  49  50  51  52  53  54  55
 6|  56  57  58  59  60  61  62  63
 7|  64  65  66  67  68  69  70  71  72

To convert between a 1D index pos and a 2D index (i,j), the macros POS, I, and J are provided, defined as below: 

#define POS(i, j)    ((MAX_BOARD + 2) + (i) * (MAX_BOARD + 1) + (j))
#define I(pos)       ((pos) / (MAX_BOARD + 1) - 1)
#define J(pos)       ((pos) % (MAX_BOARD + 1) - 1)

All 1D indices not corresponding to points on the board have the out of board marker value GRAY. Thus if board_size and MAX_BOARD both are 7, this looks like 

  j  -1   0   1   2   3   4   5   6
i +----------------------------------
-1|   #   #   #   #   #   #   #   #
 0|   #   .   .   .   .   .   .   .
 1|   #   .   .   .   .   .   .   .
 2|   #   .   .   .   .   .   .   .
 3|   #   .   .   .   .   .   .   .
 4|   #   .   .   .   .   .   .   .
 5|   #   .   .   .   .   .   .   .
 6|   #   .   .   .   .   .   .   .
 7|   #   #   #   #   #   #   #   #   #

The indices marked # have value GRAY. If MAX_BOARD is 7 and board_size is only 5: 

  j  -1   0   1   2   3   4   5   6
i +----------------------------------
-1|   #   #   #   #   #   #   #   #
 0|   #   .   .   .   .   .   #   #
 1|   #   .   .   .   .   .   #   #
 2|   #   .   .   .   .   .   #   #
 3|   #   .   .   .   .   .   #   #
 4|   #   .   .   .   .   .   #   #
 5|   #   #   #   #   #   #   #   #
 6|   #   #   #   #   #   #   #   #
 7|   #   #   #   #   #   #   #   #   #

Navigation on the board is done by the SOUTH, WEST, NORTH, and EAST macros, 

#define NS           (MAX_BOARD + 1)
#define WE           1
#define SOUTH(pos)   ((pos) + NS)
#define WEST(pos)    ((pos) - 1)
#define NORTH(pos)   ((pos) - NS)
#define EAST(pos)    ((pos) + 1)

There are also shorthand macros SW, NW, NE, SE, SS, WW, NN, EE for two step movements.

Any movement from a point on the board to an adjacent or diagonal vertex is guaranteed to produce a valid index into the board array, and the color found is GRAY if it is not on the board. To do explicit tests for out of board there are two macros 

#define ON_BOARD(pos) (board[pos] != GRAY)
#define ON_BOARD1(pos) (((unsigned) (pos) < BOARDSIZE) && board[pos] != GRAY)

where the first one should be used in the algorithms and the second one is useful for assertion tests.

Important: The 2D coordinate (-1,-1), which is used for pass and sometimes to indicate no point, maps to the 1D coordinate 0, not to -1. Instead of a plain 0, use one of the macros NO_MOVE or PASS_MOVE.

A loop over multiple directions is straightforwardly written: 

  for (k = 0; k < 4; k++) {
    int d = delta[k];
    do_something(pos + d);
  }

The following constants are useful for loops over the entire board and allocation of arrays with a 1-1 mapping to the board. 

#define BOARDSIZE    ((MAX_BOARD + 2) * (MAX_BOARD + 1) + 1)
#define BOARDMIN     (MAX_BOARD + 2)
#define BOARDMAX     (MAX_BOARD + 1) * (MAX_BOARD + 1)

BOARDSIZE is the actual size of the 1D board array, BOARDMIN is the first index corresponding to a point on the board, and BOARDMAX is one larger than the last index corresponding to a point on the board.

Often one wants to traverse the board, carrying out some function at every vertex. Here are two possible ways of doing this: 

  int m, n;
  for (m = 0; m < board_size; m++)
    for (n = 0; n < board_size; n++) {
      do_something(POS(m, n));
    }

Or: 

  int pos;
  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
    if (ON_BOARD(pos))
      do_something(pos);
  }

Node:Move Generation Basics, Next:, Previous:The Board, Up:Overview

Move Generation Basics

The engine of GNU Go takes a position and a color to move and generates the (supposedly) optimal move. This is done by the function genmove() in engine/genmove.c.

The move generation is done in three passes:

  1. Information gathering.
  2. Different modules propose moves.
  3. The values of the moves are weighted together and the best move is selected.

Information gathering

The information gathering is done by a function examine_position(), which will be discussed in greater detail in the next section. Such information could be life and death of the groups, information about moyos, connection of groups and so on. Information gathering is performed by examine_position(), which in turn calls:

A more detailed

Move generation in GNU Go 3.2

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.

The move generators in version 3.2 are:

Selecting the Move

After the move generation modules have run, the best ten moves are selected by the function review_move_reasons. This function also does some analysis to try to turn up other moves which may have been missed. The modules revise_semeai() and fill_liberty() are only run if no good move has been discovered by the other modules.

Node:Examining the Position, Next:, Previous:Move Generation Basics, Up:Overview

Examining the Position

In this section we summarize the sequence of events when examine_position() is run from genmove(). This is for reference only. Don't try to memorize it. 

purge persistent reading cache (see Persistent Cache)
make_worms() (see Worms):
  build_worms() finds and identifies the worms
  compute effective size of each worm
  unconditional_life()
  find_worm_attacks_and_defenses():
    for each attackable worm:
      set worm.attack
      add_attack_move()
    find_attack_patterns() to find a few more attacks
    for each defensible worm
      set worm.defend
      add_defense_move
      if point of attack is not adjacent to worm see if it defends
    find_defense_patterns() to find a few more defenses
    for each attackable worm try each liberty
      if it attacks add_attack_move
      if it defends add_defense_move
  find kos.
  for each worm
    find higher order liberties
  find cutting points (worm.cutstone)
  for each worm compute the genus (see Worms)
  small_semeai()
  try to improve values of worm.attack and worm.defend
  try to repair situations where adjacent worms can be
    both attacked and defended
  find worm lunches
  find worm threats
compute_initial_influence() (see Influence)
  compute_influence()
    find_influence_patterns()
  at each intersection accumulate_influence()
  segment_influence()
make_dragons() (see Dragons)
  initialize dragon data
  find the inessential worms
  make_domains()
    initialize eye data
    compute_primary_domains()
    fill out arrays black_eye and white_eye
      describing eyeshapes
    find_cuts()
    for every eyespace
      originate_eye()
    count_neighbors()
  find_connections()
  amalgamate dragons sharing an eyespace
  initialize_supplementary_dragon_data()
  find adjacent worms which can be captured (dragon lunches)
  find topological half eyes and false eyes
  modify_eye_spaces()
  for each eye space
    compute_eyes()
    store the results in black_eye, white_eye arrays
  compute the genus of each dragon
  for each dragon
    compute_escape()
  resegment_initial_influence()
  for each dragon
    influence_get_moyo_size()
  for each dragon
     compute_dragon_status()
  find_neighbor_dragons()
  purge_persistent_owl_cache()
  for each dragon which seems surrounded
     try owl_attack() and owl_defend()
     if appropriate find owl threats
  for each dragon
     set dragon.matcher_status
  for each dragon
     set dragon2.safety
  semeai()
  revise opinion of which worms are inessential
  count non-dead dragons of each color
owl_reasons() (see The Owl Code)
compute_initial_influence() again (see Influence)

Node:Sequence of Events, Next:, Previous:Examining the Position, Up:Overview

Sequence of Events

In this section we summarize the sequence of events during the move generation and selection phases of genmove(), which take place after the information gathering phase has been completed. 

fuseki()
shapes()
review_move_reasons()
  find_more_attack_and_defense_moves()
  remove_opponent_attack_and_defense_moves()
  do_remove_false_attack_and_defense_moves()
  examine_move_safety()
  induce_secondary_move_reasons()
  value_moves()
  find the ten best moves
if the value of the best move is < 6.0
  endgame_shapes()
if no move found yet
  revise_semeai()
  shapes()
  endgame_shapes()
if still no move found
  fill_liberty()
if still no move found
    pass

Node:Roadmap, Next:, Previous:Sequence of Events, Up:Overview

Roadmap

The GNU Go engine is contained in two directories, engine/ and patterns/. Code related to the user interface, reading and writing of smart go format files, and testing are found in the directories interface/, sgf/, and regression/. Code borrowed from other GNU programs is contained in utils/. 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:

Files in engine/

In engine/ there are the following files:

Files in patterns/

The directory patterns/ contains files related to pattern matching. Currently there are several types of patterns. A partial list:

The following list contains, in addition to distributed source files some intermediate automatically generated files such as patterns.c. These are C source files produced by "compiling" various pattern databases, or in some cases (such as hoshi.db) themselves automatically generated pattern databases produced by "compiling" joseki files in Smart Go Format.

Node:Coding Styles, Next:, Previous:Roadmap, Up:Overview

Coding styles and conventions

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.

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:

A variant mprintf sends output to stderr. 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.

Assertions

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

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

FIXME

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

Node:Navigating the Source, Previous:Coding Styles, Up:Overview

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.2.x/ and execute the command: 

find . -print|grep "\.[ch]$" | xargs etags

This will build a file called gnugo-3.2.x/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.2.x/TAGS, and henceforth you will be able to find any function with a minimum of keystrokes.

Node:Analyzing, Next:, Previous:Overview, Up:Top

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

We assume that you have a game GNU Go played saved as an sgf file, and you want to know why it made a certain move.

Node:Traces, Next:, Previous:Analyzing, Up:Analyzing

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.2, 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 Tuning) you may want to add the -a option. This causes GNU Go to report all patterns matched, even ones that cannot affect the outcome of the move. The reasons for doing this is that you may want to modify a pattern already matched instead of 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 Debugboard, see Colored Display).

Node:Output File, Next:, Previous:Traces, Up:Analyzing

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.

Node:Decide string, Next:, Previous:Output File, Up:Analyzing

Checking the reading code

The --decide-string option is used to check the tactical reading code (see 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.

Node:Decide dragon, Next:, Previous:Decide string, Up:Analyzing

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.

Node:GTP and GDB techniques, Next:, Previous:Decide dragon, Up:Analyzing

GTP and GDB techniques

You can use the Go Text Protocol (see GTP) to determine the statuses of dragons and other information needed for debugging. The GTP command dragon_data P12 will list the dragon data of the dragon at P12 and worm_data will list the worm data; other GTP commands may be useful as well.

You can also conveniently get such information from GDB. A suggested .gdbinit file may be found in See Debugging. 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.

Node:Debugboard, Next:, Previous:GTP and GDB techniques, Up:Analyzing

Debugboard

A useful utility called debugboard is made in the interface/debugboard/ directory. This can be run in an Xterm. Use a smaller font since it requires 50 rows and 80 columns. This runs examine_position(), then makes a graphical display of the board. Using the cursor movement keys, you can move around the board and find out the contents of the worm, dragon and eye arrays.

Node:Scoring, Next:, Previous:Debugboard, Up:Analyzing

Scoring the game

GNU Go can score the game. If done at the last move, this is usually accurate unless there is a seki. 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. 

gnugo --score last -l filename

loads the sgf file to the end of the file and estimates the winner after the last stored move by estimating the territory. 

gnugo --score end -l filename

loads the sgf file and GNU Go continues to play after the last stored move by itself up to the very end. Then the winner is determined by estimating the territory. 

gnugo --score aftermath -l filename

loads the sgf file and GNU Go continues to play after the last stored move by itself up to the very end. Then the winner is determined by the most accurate algorithm available. Slower but more accurate than --score end. 

gnugo --score L10 -l filename

loads the sgf file until a stone is placed on L10. Now the winner will be estimated as with gnugo --score last.

Any of these commands may be combined with --chinese-rules if you want to use Chinese (area) counting. 

gnugo --score 100 -l filename

loads the sgf file until move number 100. Now the winner will be estimated as with gnugo --score last.

If the option -o outputfilename is provided, the results will also be written as comment at the end of the output file.

Node:Colored Display, Previous:Scoring, Up:Analyzing

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

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

Eye Space Display

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

Moyo Display

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

The regions found by Bouzy's algorithm (see Moyo) 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)

These data are today only used in the score estimation.

The rest of the engine uses instead the new influence algorithm explained in See Influence. 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 See Influential Display.

These options can be combined by adding the levels.

Node:API, Next:, Previous:Analyzing, Up:Top

Application Programmers Interface to GNU Go

If you want to write your own interface to GNU Go, or if you want to create a go application using the GNU Go engine, this chapter is of interest to you.

First an overview: GNU Go consists of two parts: the GNU Go engine and a program (user interface) which uses this engine. These are linked together into one binary. The current program implements the following user modes:

The GNU Go engine can be used in other applications. For example, supplied with GNU Go is another program using the engine, called debugboard, in the directory interface/debugboard/. The program debugboard lets the user load SGF files and can then interactively look at different properties of the position such as group status and eye status.

The purpose of this Chapter is to show how to interface your own program such as debugboard with the GNU Go engine.

Figure 1 describes the structure of a program using the GNU Go engine. 

                 +-----------------------------------+
                 |                                   |
                 |          Go application           |
                 |                                   |
                 +-----+----------+------+           |
                 |     |          |      |           |
                 |     |   Game   |      |           |
                 |     | handling |      |           |
                 |     |          |      |           |
                 |     +----+-----+      |           |
                 |   SGF    |    Move    |           |
                 | handling | generation |           |
                 |          |            |           |
                 +----------+------------+-----------+
                 |                                   |
                 |           Board handling          |
                 |                                   |
                 +-----------------------------------+

        Figure 1: The structure of a program using the GNU Go engine

The foundation is a library called libboard.a which provides efficient handling of a go board with rule checks for moves, with incremental handling of connected strings of stones and with methods to efficiently hash go positions.

On top of this, there is a library which helps the application use smart go files, SGF files, with complete handling of game trees in memory and in files. This library is called libsgf.a

The main part of the code within GNU Go is the move generation library which given a position generates a move. This part of the engine can also be used to manipulate a go position, add or remove stones, do tactical and strategic reading and to query the engine for legal moves. These functions are collected into libengine.a.

The game handling code he