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

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

Introduction

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

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 by the Free Software Foundation except for the files gmp.c and gmp.h, which are copyrighted by Bill Shubert (wms@igoweb.org).

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 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 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 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 file win/makefile.win is also in the public domain and is free for unrestricted use.

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 and Don Dailey.

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

And thanks to Alan Crossman, Stephan Somogyi, Pierce Wetter and Mathias Wagner for help with Macintosh.

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.

  1. Report and fix bugs.
    Bugs are an important cause of weakness in any Go program! 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.
  2. 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.
  3. Tune the pattern databases.
    This 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.
  4. Extend and tune the Joseki database.
  5. Rewrite the semeai module
    The semeai module is vastly in need of improvement. In fact, semeai can probably only be analyzed by reading to discover what backfilling is needed before we can make atari.
  6. Write a connection analysis module.
    The connection analysis is today completely static and has a hard time identifying mutually dependent connections or moves that simultaneously threatens two or more connections. This could be improved by writing a connection reader, which like the owl code uses pattern matching to find a small amount of key moves to try.
  7. 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 this the move generation heuristics in the reading code needs to be refined. Some improvements should also be possible to obtain by tuning the move ordering.
  8. Automatically search for errors.
    In some positions GNU Go may report a group as alive or connected with a living group. But after the opponent has placed one stone GNU Go may change the status to dead, without going through a critical status. It would be nice if these positions could be automatically identified and logged for later analysis.

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.0.0. Now do: 

   ./configure [OPTIONS]
   make

The most important configure options, cache size, default level and dfa will be explained in detail in the next section (see Configure Options). Probably you do not need to set these unless you are dissatisfied with GNU Go's performance for any reason.

As an example, 

   ./configure --enable-cache-size=32 --enable-level=8

creates a 48 Mb cache in RAM and sets the level to 8. Both these defaults can be overridden at run time.

If you do not specify any options, the default level is 10 (highest supported), and the default cache size is 16, and the DFA is not enabled.

If you have a slow machine or find GNU Go too slow you may want to decrease the default level. At level 8 the engine is playing about 1.6 times faster than at level 10.

Increasing the cache size will improve performance up to a point -- once the cache is so large that it cannot be kept in RAM, GNU Go will start swapping (characterized by frequent hard drive accesses) and performance will degrade.

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

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=48

creates a cache of size 48 megabytes. If you omit this, your default cache size will be 16 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, Previous:Default Level, Up:Configure Options

DFA Configure Option

If you ./configure --enable-dfa you get the experimental DFA (Discrete Finite-State Automata) pattern matcher. This will result in a larger but somewhat faster engine. The option is considered experimental because it is new and harder to debug but sufficiently tested that it is probably safe.

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.0 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.0.0.tar.gz you can build the executable as follows: 

       tar zxvf gnugo-3.0.0.tar.gz
       cd gnugo-3.0.0
       ./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.0.0.tar.gz you can type: 

  tar zxvf gnugo-3.0.0.tar.gz
  cd gnugo-3.0.0
  ./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.0.0.tar.gz
  cd gnugo-3.0.0
  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://mathsrv.ku-eichstaett.de/MGF/homes/grothmann/jago/Go.html>

  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://mathsrv.ku-eichstaett.de/MGF/homes/grothmann/jago/Go.html>

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

The single parameter --level is a convenient way of choosing whether to play stronger or faster. This single parameter controls a host of other parameters which may optionally 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.

These 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:, 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:Move Generation Basics, Next:, Previous:Definitions, Up:Overview

Move Generation Basics

The engine of GNU Go takes a positions and a color to move and generates the (supposedly) optimal move. This is done by the function genmove() in 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.0

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

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

This will build a file called gnugo-3.0.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.0.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.

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.0, 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 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. Of the data in parentheses tells 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 moyos found by GNU Go can be displayed from an xterm or rxvt window or from the Linux console using the -m option. This takes a parameter: 

-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)
    8       0x08         print initial moyo influence
   16       0x10         print influence
   32       0x20         numeric influence
   64       0x40         moyo strength
  128       0x80         moyo attenuation

The first three options are somewhat superceded because these data are no longer used by the engine.

These options can be combined by adding the levels. Levels 16, 32, 64 and 128 don't do much unless you also specify level 8. Thus one might use the hexadecimal option -m0x018 if you want to see the influence function displayed graphically.

See Moyo, for the first three items.

See Influential Display, for the last five items.

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 helps the application programmer keep tracks of the moves in a game, and to undo or redo moves. Games can be saved to SGF files and then later be read back again. These are also within libengine.a.

The resposibility of the application is to provide the user with a user interface, graphical or not, and let the user interact with the engine.

Node:Getting Started, Next:, Previous:API, Up:API

How to use the engine in your own program: getting started

To use the GNU Go engine in your own program you must include the file gnugo.h. This file describes the whole public API. There is another file, liberty.h, which describes the internal interface within the engine. If you want to make a new module within the engine, e.g. for suggesting moves you will have to include this file also. In this section we will only describe the public interface.

Before you do anything else, you have to call the function init_gnugo(). This function initializes everything within the engine. It takes one parameter: the number of megabytes the engine can use for the internal hash table. In addition to this the engine will use a few megabytes for other purposes such as data describing groups (liberties, life status, etc), eyes and so on.

Node:Basic Data Structures, Next:, Previous:Getting Started, Up:API

Basic Data Structures in the Engine

There are some basic definitions in gnugo.h which are used everywhere. The most important of these are the numeric declarations of colors. Each intersection on the board is represented by one of these: 

     color              value
     EMPTY                0
     WHITE                1
     BLACK                2

In addition to these, the following values can be used in special places, such as describing the borders of eyes: 

     color                     value
     GRAY (GRAY_BORDER)          3
     WHITE_BORDER                4
     BLACK_BORDER                5

There is a macro, OTHER_COLOR(color) which can be used to get the other color than the parameter. This macro can only be used on WHITE or BLACK, but not on EMPTY or one of the border colors.

Node:The Position Struct, Next:, Previous:Basic Data Structures, Up:API

The Position Struct

The basic data structure in the interface to the engine is the Position. A Position is used to store the current position of a game including the location of all black and white stones, a possible ko, and the number of captured stones on each side. Here is the definition of Position: 

     typedef unsigned char Intersection;

     typedef struct {
       int          boardsize;
       Intersection board[MAX_BOARD][MAX_BOARD];
       int          ko_i;
       int          ko_j;
       int          last_i[2];
       int          last_j[2];

       float        komi;
       int          white_captured;
       int          black_captured;
     } Position;

Here Intersection stores EMPTY, WHITE or BLACK. It is currently defined as an unsigned char to make it reasonably efficient in both storage and access time. The position stores a two-dimensional array of Intersections with the size MAX_BOARD. MAX_BOARD is the value of the biggest board size that the engine supports; it is currently set to 21. There is also a MIN_BOARD which is set to 3.

To indicate what board size is actually used, there is a member, boardsize, which should be in the range between MIN_BOARD and MAX_BOARD.

A location on the board is represented by a pair of integers in the range [0 ... boardsize-1]. The convention used within GNU Go is that the first integer indicates the row number from the top and the second integer indicates the column number from the left. Thus the coordinate (2,5) is F5 (A) in the small diagram below. 

           A B C D E F G
         7 . . . . . . . 7
         6 . . . . . . . 6
         5 . . . . . A . 5
         4 . . . . . . . 4
         3 . . . . . . . 3
         2 . . . . . . . 2
         1 . . . . . . . 1
           A B C D E F G

A pass move is represented by the pair (-1,-1). A convention within the code is to use the suffix i and j for the first and the last coordinate.

If there is a ko present on the board, that is if one stone was captured the last move and the capturing stone can be recaptured, the pair (ko_i, ko_j) points at the empty intersection where the stone was just captured (a in the diagram below). 

           A B C D E F G
         7 . . . . . . . 7
         6 . . . . . . . 6
         5 . . . O X . . 5
         4 . . O a O X . 4
         3 . . . O X . . 3
         2 . . . . . . . 2
         1 . . . . . . . 1
           A B C D E F G

If no ko is present, ko_i should be set to -1.

The last two moves played are stored in (last_i[], last_j[]).

As the game progresses the number of prisoners on each side are maintained in the members white_captured and black_captured.

The komi used in the ongoing game is also stored in the Position. The reason for this is that in some instances, GNU Go plays differently whether it is ahead, behind or the position is even. So the komi is an important input to the move generation.

Node:Positional Functions, Previous:The Position Struct, Up:API

Functions which manipulate a Position

All the functions in the engine that manipulate Positions have names prefixed by gnugo_. Here is a complete list, as defined in gnugo.h:

Functions which manipulate the go position

Status functions

These functions examines the position in different ways and tells the status of groups and other items.

Special functions

These functions are only used in special situations, such as when the program wants to access internal data structures within the engine. They should only be used when the programmer has a good knowledge of the internals of GNU Go.

Game handling

The functions (in see Positional Functions) are all that are needed to create a fully functional go program. But to make the life easier for the programmer, there is a small set of functions specially designed for handling ongoing games.

The data structure describing an ongoing game is the Gameinfo. It is defined as follows: 

typedef struct {
  int       handicap;

  Position  position;
  int       move_number;
  int       to_move;		/* whose move it currently is */
  SGFTree   moves;		/* The moves in the game. */

  int       seed;		/* random seed */
  int       computer_player;	/* BLACK, WHITE, or EMPTY (used as BOTH) */

  char      outfilename[128];	/* Trickle file */
  FILE      *outfile;
} Gameinfo;

The meaning of handicap should be obvious. The position field is of course the current position, move_number is the number of the current move and to_move is the color of the side whose turn it is to move.

The SGF tree moves is used to store all the moves in the entire game, including a header node which contains, among other things, komi and handicap. If a player wants to undo a move, this can most easily be done by replaying all the moves in the tree except for the last one. This is the way it is implemented in gameinfo_undo_move().

If one or both of the opponents is the computer, the fields seed and computer_player are used. Otherwise they can be ignored. seed is used to store the number used to seed the random number generator. Given the same moves from the opponent, GNU Go will try to vary its game somewhat using a random function. But if the random generator is given the same seed, GNU Go will always play the same move. This is good, e.g. when we debug the engine but could also be used for other purposes.

GNU Go can use a trickle file to continuously save all the moves of an ongoing game. This file can also contain information about internal state of the engine such as move reasons for various locations or move valuations for the 10 highest valued moves. The name of this file should be stored in outfilename and the file pointer to the open file is stored in outfile. If no trickle file is used, outfilename[0] will contain a null character and outfile will be set to NULL.

Functions which manipulate a Gameinfo

All the functions in the engine that manipulate Gameinfos have names prefixed by gameinfo_. Here is a complete list, as defined in gnugo.h:

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

Handling SGF trees in memory

SGF - Smart Game Format - is a file format which is used for storing game records for a number of different games, among them chess and go. The format is a framework with special adaptions to each game. This is not a description of the file format standard. Too see the exact definition of the file format, see <http://www.red-bean.com/sgf/>.

GNU Go contains a library to handle go game records in the SGF format in memory and to read and write SGF files. This library - libsgf.a - is in the sgf subdirectory. To use the SGF routines, include the file sgftree.h.

Each game record is stored as a tree of nodes, where each node represents a state of the game, often after some move is made. Each node contains zero or more properties, which gives meaning to the node. There can also be a number of child nodes which are different variations of the game tree. The first child node is the main variation.

Here is the definition of SGFNode, and SGFProperty, the data structures which are used to encode the game tree. 

typedef struct SGFProperty_t {
  struct SGFProperty_t *next;
  short  name;
  char   value[1];
} SGFProperty;

typedef struct SGFNode_t {
  SGFProperty      *props;
  struct SGFNode_t *parent;
  struct SGFNode_t *child;
  struct SGFNode_t *next;
} SGFNode;

Each node of the SGF tree is stored in an SGFNode struct. It has a pointer to a linked list of properties (see below) called props. It also has a pointer to a linked list of children, where each child is a variation which starts at this node. The variations are linked through the next pointer and each variation continues through the child pointer. Each and every node also has a pointer to its parent node (the parent field), except the top node whose parent pointer is NULL.

An SGF property is encoded in the SGFPoperty struct. It is linked in a list through the next field. A property has a name which is encoded in a short int. Symbolic names of properties can be found in sgf_properties.h.

Some properties also have a value, which could be an integer, a floating point value, a character or a string. These values can be accessed or set through special functions (see below).

Functions which manipulate SGF nodes and properties

All the functions which create and manipulate SGF trees are prefixed by sgf. The SGF code was donated to us by Thomas Traber, so they don't follow the naming conventions of GNU Go perfectly.

Low level functions

These functions let the caller create nodes or access nodes easier.

Functions which manipulate SGF properties

Functions which manipulate SGF nodes

High level functions

The SGFTree datatype

Sometimes we just want to record an ongoing game or something similarly simple and not do any sofisticated tree manipulation. In that case we can use the simplified interface provided by SGFTree below. 

typedef struct SGFTree_t {
  SGFNode *root;
  SGFNode *lastnode;
} SGFTree;

An SGFTree contains a pointer to the root node of an SGF tree and a pointer to the node that we last accessed. Most of the time this will be the last move of an ongoing game.

Most of the functions which manipulate an SGFTree work exactly like their SGFNode counterparts, except that they work on the current node of the tree.

All the functions below that take arguments tree and node will work on:

  1. node if non-NULL
  2. tree->lastnode if non-NULL
  3. The current end of the game tree.
in that order.

Functions that manipulate sgftrees

Node:Libboard, Next:, Previous:SGF, Up:Top

The Board Library

The foundation of the GNU Go engine is a library of very efficient routines for handling go boards. This board library, called libboard, can be used for those programs that only need a basic go board but no AI capability. One such program is patterns/joseki subdirectory, which compiles joseki pattern databases from SGF files.

The library consists of the following files:

To use the board library, you must include liberty.h just like when you use the whole engine, but of course you cannot use all the functions declared in it, i.e. the functions that are part of the engine, but not part of the board library. You must link your application with libboard.a.

Node:Board Data Structures, Next:, Up:Libboard

Board Data structures

The basic data structures of the board correspond tightly to the Position struct described in See The Position Struct. They are all stored in global variables for efficiency reasons, the most important of which are: 

int           board_size;
Intersection  p[MAX_BOARD][MAX_BOARD];
int           board_ko_i;
int           board_ko_j;
int           last_moves_i[2];
int           last_moves_j[2];

float         komi;
int           white_captured;
int           black_captured;

Hash_data     hashdata;

The description of the Position struct is applicable to these variables also, so we won't duplicate it here. All these variables are globals for performance reasons. Behind these variables, there are a number of other private data structures. These implement incremental handling of strings, liberties and other properties (see Incremental Board). The variable hashdata contains information about the hash value for the current position (see Hashing).

These variables should never be manipulated directly, since they are only the front end for the incremental machinery. They can be read, but should only be written by using the functions described in the next section. If you write directly to them, the incremental data structures will become out of sync with each other, and a crash is the likely result.

Node:Board Setup Functions, Next:, Previous:Board Data Structures, Up:Libboard

Board Functions

These functions are all the public functions in engine/board.c.

Setup Functions

These functions are used when you want to set up a new position without actually playing out moves.

Node:Move Functions, Next:, Previous:Board Setup Functions, Up:Libboard

Move Functions

Reading, often called search in computer game theory, is a fundamental process in GNU Go. This is the process of generating hypothetical future boards in order to determine the answer to some question, for example "can these stones live." Since these are hypothetical future positions, it is important to be able to undo them, ultimately returning to the present board. Thus a move stack is maintained during reading. When a move is tried, by the function trymove, or its variant tryko. This function pushes the current board on the stack and plays a move. The stack pointer stackp, which keeps track of the position, is incremented. The function popgo() pops the move stack, decrementing stackp and undoing the last move made.

Every successful trymove() must be matched with a popgo(). Thus the correct way of using this function is: 

  if (trymove(i, j, color, [message], k, l, komaster, kom_i, kom_j)) {
       ...    [potentially lots of code here]
       popgo();
  }

Here the komaster is only set if a conditional ko capture has been made at an earlier move. This feature of the tactical and owl reading code in GNU Go is used to prevent redundant reading when there is a ko on the board (see Ko). If komaster is not defined then take the last three parameters to be EMPTY, and -1, -1.

Node:Status Functions, Next:, Previous:Move Functions, Up:Libboard

Status Functions

These functions are used for inquiring about properties of the current position or of potential moves.

Node:String Functions, Previous:Status Functions, Up:Libboard

String and Miscellaneous Functions

These functions are used for getting information like liberties, member stones and similar about strings. Most of these are here because they have a particularly efficient implementation through access to the incremental data structures behind the scene.

Miscellaneous Functions

Hashing of Board Positions

Hashing of go positions in a hash table (sometimes also called a transposition table) is implemented in libboard, in hash.c and cache.c to be exact.

To use the hash function, you must include hash.h and to use the entire hash table, you must include cache.h in your program. The details are described in Hashing.

Node:Move Generation, Next:, Previous:Libboard, Up:Top

Move generation

Node:MG Intro, Next:, Previous:Move Generation, Up:Move Generation

Introduction

GNU Go 3.0 has a move generation scheme that is substantially different from earlier versions. In particular, it is 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:

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

Node:MG Overview, Next:, Previous:MG Intro, Up:Move Generation

Overview

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

  1. information gathering
  2. generation of moves and move reasons
  3. valuation of the suggested moves

This is somewhat simplified. In reality there is some overlap between the steps.

Node:MG Info, Next:, Previous:MG Overview, Up:Move Generation

Information gathering

First we have to collect as much information as possible about the current position. Such information could be life and death of the groups, moyo status, connection of groups and so on. Information gathering are performed by the following functions, called in this order:

See Examining the Position, for a more exact itinerary of the information-gathering portion of the move-generation proces.

See Worms and Dragons, for more detailed documentation about make_worms and make_dragons.

Node:MG Reasons, Next:, Previous:MG Info, Up:Move Generation

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. The different kinds of move reasons considered by GNU Go are:

ATTACK_MOVE
DEFEND_MOVE
Attack or defend a worm.
ATTACK_THREAT_MOVE
DEFEND_THREAT_MOVE
Threaten to attack or defend a worm.
NON_ATTACK_MOVE
NON_DEFEND_MOVE
a non-attacking or non-defending move.
ATTACK_EITHER_MOVE
a move that attacks either on of two worms.
DEFEND_BOTH_MOVE
a move that simultaneously defends two worms.
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
BLOCK_TERRITORY_MOVE
a move that expands our territory or blocks opponents expansion.
EXPAND_MOYO_MOVE
a move expanding a moyo.
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 Pattern Classification) 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.
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.

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.

Node:MG Details, Next:, Previous:MG Reasons, Up:Move Generation

Detailed Descriptions of various Move Reasons

Node:Attack and Defense, Next:, Up:MG Details

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

Node:Threats to Attack or Defend, Next:, Previous:Attack and Defense, Up:MG Details

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.

Node:Non-Working Moves, Next:, Previous:Threats to Attack or Defend, Up:MG Details

Not working attack and defense moves

The tactical reading may come up with ineffective attacks or defenses occasionally. When these can be detected by patterns, it's possible to cancel the attack and/or defense potential of the moves by using these move reasons. This can only be done by action lines in the patterns.

Node:Multi Attack or Defense, Next:, Previous:Non-Working Moves, Up:MG Details

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.

Node:Cutting and Connecting, Next:, Previous:Multi Attack or Defense, Up:MG Details

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.

Node:Semeai, Next:, Previous:Cutting and Connecting, Up:MG Details

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.

Node:Making eyes, Next:, Previous:Semeai, Up:MG Details

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

Node:Antisuji moves, Next:, Previous:Making eyes, Up:MG Details

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.

Node:Territorial moves, Next:, Previous:Antisuji moves, Up:MG Details

Territorial moves

Any move that increases territory gets a move reason. These are the block territory and expand territory move reasons. Such move reasons are added by the b and e patterns in patterns/patterns.db. Similarly the E patterns attempt to generate or mitigate an moyo, which is a region of influence not yet secure territory, yet valuable. Such a pattern sets the "expand moyo" move reason.

Node:Owl attack and defense, Next:, Previous:Territorial moves, Up:MG Details

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[ai][aj].owl_attacki_i, dragon[ai][aj].owl_attacki_j) and (dragon[ai][aj].owl_second_attacki_i, dragon[ai][aj].owl_second_attacki_j).

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.

Node:Combination Attacks, Previous:Owl attack and defense, Up:MG Details

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, or from CRITICAL to DEAD. Once such a sequence of ataris is found, it tries to shorten it by rejecting irrelevant moves.

Node:Valuation, Next:, Previous:MG Details, Up:Move Generation

Valuation of suggested moves

Moves are valued with respect to five different criteria. These are

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

Territorial value is the amount of secure territory generated (or saved) by the move. Attack and defense moves have territorial values given by twice the number of stones in the worm plus adjacent empty space. This value is in practice approximated from the "effective size" measure.

Influence value is an estimation of the move's effect on the size of potential territory and possibly "area". This is currently implemented by using delta_moyo_simple(). This can probably be improved quite a bit. If the move captures some stones, this fact should be taken into account when computing moyo/area.

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, which primarily is intended to choose between moves having the same set of reasons. An important role of this measure is to offset mistakes made by the estimation of territorial and influence 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.

Node:Territorial value, Next:, Up:Valuation

Territorial Value

The algorithm for computing territorial value is in the function estimate_territorial_value. As the name suggests, it seeks to estimate the amount the move adds to secure territory.

This function examines every reason for the move and takes into account the safety of different dragons. For example if the reason for the move is that it attacks and kills a worm, no value is assigned if the worm is already DEAD. If the worm is not DEAD the value of the move is twice the effective size of the worm.

In addition to such additions to territory, if the move is found to be a block or expanding move, the function influence_delta_territory is consulted to find areas where after the move the influence function becomes so strong that these are counted as secure territory, or where the influence function is sufficiently weakened that these are removed from the secure territory of the opponent (see Influential Functions).

Node:Influence value, Next:, Previous:Territorial value, Up:Valuation

Influence Value

The function estimate_influence_value attempts to assign a value to the influence a move. The functions influence_delta_strict_moyo influence_delta_strict_area are called to find areas where after the move the influence function becomes strong enough that these are counted as friendly moyo or area, or which are taken away from the opponent's moyo or area (see Influential Functions).

Node:Strategical value, Next:, Previous:Influence value, Up:Valuation

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.

Node:Shape factor, Next:, Previous:Strategical value, Up:Valuation

Shape Factor

In the value field of a pattern (see Pattern Values) 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.

Node:Minimum Value, Next:, Previous:Shape factor, Up:Valuation

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.

Node:Secondary Value, Next:, Previous:Minimum Value, Up:Valuation

Secondary Value

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

Node:Threats and Followup Value, Previous:Secondary Value, Up:Valuation

Followup value refers to value which may acrue if we get two moves in a row in a local area. It is assigned by the function add_followup_value, for example through the followup_value autohelper macro.

Attack and defense threats, including owl threats are usually given a small amount of weight, as is followup value.

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 followup value or the value of the threat are taken in full.

Node:Move Generation Functions, Next:, Previous:Valuation, Up:Move Generation

Move Generation Functions

The following functions are defined in move_reasons.c.

Node:Local MG Functions, Next:, Previous:Move Generation Functions, Up:Move Generation

Local Move Generation Functions

The following functions in move_reasons.c are declared static. Their scope is limited to that file.

Node:End Game, Previous:Local MG Functions, Up:Move Generation

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.

Node:Worms and Dragons, Next:, Previous:Move Generation, Up:Top

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

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.

Node:Worms, Next:, Previous:Worms and Dragons, Up:Worms and Dragons

Worms

The array struct worm_data worm[MAX_BOARD][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 origini;
  int originj;
  int liberties;
  int liberties2;
  int liberties3;
  int liberties4;
  int attacki;
  int attackj;
  int attack_code;
  int defendi;
  int defendj;
  int defend_code;
  int lunchi;
  int lunchj;
  int cutstone;
  int cutstone2;
  int genus;
  int value;
  int ko;
  int inessential;
  int invincible;
  int unconditional_status;
};

We have two distinct notions of cutting stone, which we keep track of in the separate fields worm.cutstone and worm.cutstone2. We maintain both fields because the historically older cutstone field is needed to deal with the fact that e.g. in the position 

   OXX.O
   .OOXO
   OXX.O

the X stones are amalgamated into one dragon because neither cut works as long as the two O stones are in atari. Therefore we add one to the cutstone field for each potential cutting point, indicating that these O stones are indeed worth rescuing.

For the time being we use both concepts in parallel. It's possible we also old concept for correct handling of lunches.

The function makeworms() will generate data for all worms. For empty worms, the following fields are significant: color, size, origini and originj. The liberty, attack, defend, cutstone, genus and inessential fields have significance only for nonempty worms.

Node:Amalgamation, Next:, Previous:Worms, Up:Worms and Dragons

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 two worms means means in practice replacing the origin of one worm by the origin of the other. Amalgamation takes place in two stages: first, the amalgamation of empty worms (cavities) into empty dragons (caves); then, the amalgamation of colored worms into dragons.

Amalgamation of cavities

As we have already defined it, a cavity is an empty worm. A cave is an empty dragon.

Under certain circumstances we want to amalgamate two or more cavities into a single cave. This is done before we amalgamate strings. An example where we wish to amalgamate two empty strings is the following: 

      OOOOO
     OOXXXOO
     OXaObXO
     OOXXXOO
      OOOOO

The two empty worms at a and b are to be amalgamated.

We have already defined a string to be inessential if it meets a criterion designed to guarantee that it has no life potential unless a particular surrounding string of the opposite color can be killed. An inessential string is a string S of genus zero which is not a cutting string or potential cutting string, and which has no edge liberties or second order liberties (the last condition should be relaxed), and which satisfies the following further property: If the string is removed from the board, then the empty worm E which is the worm closure of the set of vertices which it occupied has bordercolor the opposite of the removed string.

Thus in the previous example, after removing the inessential string at the center the worm closure of the center vertex consists of an empty worm of size 3 including a and b. The latter are the boundary components.

The last condition in the definition of inessential worms excludes examples such as this: 

        OOOO
       OXXOO
      OXX.XO
      OX.XXO
      OOXXO
       OOO

Neither of the two X strings should be considered inessential (together they form a live group!) and indeed after removing one of them the resulting space has gray bordercolor, so by this definition these worms are not inessential.

Some strings which should by rights be considered inessential will be missed by this criterion.

The algorithm for amalgamation of empty worms consists of amalgamating the boundary components of any inessential worm. The resulting dragon has bordercolor the opposite of the removed string.

Any dragon consisting of a single cavity has bordercolor equal to that of the cavity.

Amalgamation of strings

Amalgamation of nonempty worms in GNU Go 3.0 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.

Node:Connection, Next:, Previous:Amalgamation, Up:Worms and Dragons

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.

Node:Half Eyes, Next:, Previous:Connection, Up:Worms and Dragons

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

The half eye data is collected in the dragon array. Before this is done, however, an auxiliary array called half_eye_data is filled with information. The field type is 0, or else HALF_EYE or FALSE_EYE depending on which type is found; and (ki, kj) points to a move to kill the half eye. 

struct half_eye_data half_eye[MAX_BOARD][MAX_BOARD];

struct half_eye_data {
  int type;         /* HALF_EYE or FALSE_EYE; */
  int num_attacks;  /* number of attacking points */
  int num_defends;  /* number of defending points */
  int ai[4];        /* (ai, aj) attacks a topological halfeye */
  int aj[4];
  int di[4];        /* (di, dj) defends a topological halfeye */
  int dj[4];
};

The array struct half_eye_data half_eye[MAX_BOARD][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.

Node:Dragons, Next:, Previous:Half Eyes, Up:Worms and Dragons

Dragons

The array struct dragon_data dragon[MAX_BOARD][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. 

struct dragon_data {
  int color;
  int id;
  int origini;
  int originj;
  int borderi;
  int borderj;
  int size;
  float effective_size;
  int heyes;
  int heyei;
  int heyej;
  int genus;
  int escape_route;
  int lunchi;
  int lunchj;
  int status;
  int owl_status;
  int owl_attacki;
  int owl_attackj;
  int owl_attack_certain;
  int owl_second_attacki;
  int owl_second_attackj;
  int owl_defendi;
  int owl_defendj;
  int owl_defend_certain;
  int owl_second_defendi;
  int owl_second_defendj;
  int old_safety;
  int matcher_status;
  int semeai;
  int semeai_margin_of_safety;
};

Here are the definitions of each field.

Node:Dragons in Color, Next:, Previous:Dragons, Up:Worms and Dragons

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 colored displays are documented elsewhere (see Colored Display).

Node:Worm and Dragon Functions, Next:, Previous:Dragons in Color, Up:Worms and Dragons

Worm and Dragon Functions

Here are the public functions in engine/worm.c:

Here are the public functions in engine/dragon.c:

Node:Dragon2, Previous:Worm and Dragon Functions, Up:Worms and Dragons

The Second Dragon Array.

In addition to dragon[][] there is a second complementary dragon data array dragon2[]. In contrast to dragon[][], the information in this one is not duplicated to every intersection of the board. Instead the dragons are numbered, using the new field id in dragon[][], and this number is used as index into the dragon2[] array. This number can of course not be assigned until all dragon amalgamations have been finished. Neither is the dragon2[] array initialized until this has been done.

The first thing this array contains is a list of neighbor dragons. The intention of this information is to be able to modify the perceived safety of a dragon with respect to the strength of its neighbors. The list of neighbors should be useful for other purposes too.

For the algorithm we refer to the source code and its comments, in the function compute_supplementary_dragon_data() in dragon.c.

To access the dragon[][] array given a dragon id number or the dragon2[] array given a board coordinate, there are the two handy macros DRAGON(d) and DRAGON2(m, n). Also notice that the dragon2[] data and the id number only are valid for non-empty dragons, i.e. not for caves.

Node:Eyes, Next:, Previous:Worms and Dragons, Up:Top

Eyes and Half Eyes

The purpose of this Chapter is to describe the algorithm used in GNU Go 3.0 to determine eyes. There are actually two alternative algorithms: the graph-based algorithm in optics.c, and the algorithm based on reading in life.c. The life code is slower than the graph based algorithm, but more accurate. You can make it the default by using the option --life. Otherwise, GNU Go will only call the life code if the graph based algorithm decides that it needs an expert opinion.

Node:Local Games, Next:, Previous:Eyes, Up:Eyes

Local games

Each connected eyespace of a dragon affords a local game which yields a local game tree. The score of this local game is the number of eyes it yields. Usually if the players take turns and make optimal moves, the end scores will differ by 0 or 1. In this case, the local game may be represented by a single number, which is an integer or half integer. Thus if n(O) is the score if O moves first, both players alternate (no passes) and make alternate moves, and similarly n(X), the game can be represented by {n(O)|n(X)}. Thus {1|1} is an eye, {2|1} is an eye plus a half eye, etc.

The exceptional game {2|0} can occur, though rarely. We call an eyespace yielding this local game a CHIMERA. The dragon is alive if any of the local games ends up with a score of 2 or more, so {2|1} is not different from {3|1}. Thus {3|1} is NOT a chimera.

Here is an example of a chimera: 

XXXXX
XOOOX
XO.OOX
XX..OX
XXOOXX
XXXXX

Node:Eye Space, Next:, Previous:Local Games, Up:Eyes

Eye spaces

In order that each eyespace be assignable to a dragon, it is necessary that all the dragons surrounding it be amalgamated (see 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 src/optics.c.

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

Node:Eye Space as Local Game, Next:, Previous:Eye Space, Up:Eyes

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 1

  x
!x*x

:2,1

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 

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

Node:Eye Example, Next:, Previous:Eye Space as Local Game, Up:Eyes

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!


. !
.!

Node:Graphs, Next:, Previous:Eye Example, Up:Eyes

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 tabulated in the database hey.h. During make_worms, which runs before the eye space analysis, the half eye and false eye patterns are tabulated in the array half_eye.

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
XXXXXX

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

ooo      half eye
OhO
*OX

and it is recorded in the half_eye array as follows. If (i,j) are the coordinates of the point a, half_eye[i][j].type==HALF_EYE and (half_eye[i][j].ki, half_eye[i][j].kj) are the coordinates of b.

The graph of the eye_shape, ostensibly .... is modified by replacing the left . by !.

Node:Eye Shape, Next:, Previous:Graphs, Up:Eyes

Eye shape analysis

The patterns in patterns/eyes.db are compiled into graphs represented essentially by linked lists 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}.

Node:Eye Topology, Next:, Previous:Eye Shape, Up:Eyes

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: 

   OOOX
   O..X
   OOOX

A FALSE EYE is a cave which cannot become an eye. Here is 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.

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:

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

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

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

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

Node:False Margins, Next:, Previous:Eye Topology, Up:Eyes

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

Node:Eye Functions, Previous:False Margins, Up:Eyes

Functions in optics.c

Here are the public functions in optics.c. The statically declared functions are documented in the source code.

Node:Patterns, Next:, Previous:Eyes, Up:Top

The Pattern Code

Node:Patterns Overview, Next:, Previous:Patterns, Up:Patterns

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

  |?X?.?
  |O.*oo
  |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.

Node:Pattern Classification, Next:, Previous:Patterns Overview, Up:Patterns

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.

Constraint Pattern Attributes

Action Attributes

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.

Node:Pattern Values, Next:, Previous:Pattern Classification, Up:Patterns

Pattern Attributes

The second third field in the : line of a pattern is optional and of the form value1(x),value2(y),.... The available set of values are as follows.

The meaning of these values is documented in See Move Generation.

Node:Helper Functions, Next:, Previous:Pattern Values, Up:Patterns

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 wedge_helper. (This helper does not exist anymore but has been replaced by a constraint, discussed in the following section. Due to its simplicity it's still a good example.) The helper begins with a comment: 

/*

?O.           ?Ob
.X*           aXt
?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 (ti, tj), (ai, aj) and (bi, bj). Of course t is always at *, the point where GNU Go will move if the pattern is adopted. 

int
wedge_helper (ARGS)
{
  int ai, aj, bi, bj, ci, cj;
  int other = OTHER_COLOR(color);
  int success = 0;

  OFFSET(0, -2, ai, aj);
  OFFSET(-1, 0, bi, bj);
  OFFSET(1, 0, ci, cj);

  if (TRYMOVE(ti, tj, color)) {
    if (TRYMOVE(ai, aj, other)) {
      if (!p[ai][aj] || attack(ai, aj, NULL, NULL))
	success = 1;
      else if (TRYMOVE(bi, bj, color)) {
	if (!safe_move(ci, cj, other))
	  success = 1;
	popgo();
      }
      popgo();
    }
    popgo();
  }

  return success;
}

The OFFSET lines tell GNU Go the positions of the three stones at a=(ai,aj), b=(bi,bj), and c=(ci,cj). To decide whether the pattern guarantees a connection, we do some reading. First we use the TRYMOVE macro to place an O at t and let X draw back to a. Then we try 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().

Node:Autohelpers and Constraints, Next:, Previous:Helper Functions, Up:Patterns

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.

Node:Autohelper Actions, Next:, Previous:Autohelpers and Constraints, Up:Patterns

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.

Node:Autohelper Functions, Next:, Previous:Autohelper Actions, Up:Patterns

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 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 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 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 Worms and Dragons). 

status(x)

Returns the status of the dragon at x (see 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)

Functions related to various kinds of influence and territory estimations, as described in See Moyo. xarea(x) evaluates to true if x is either a living enemy stone or an empty point within his "area". 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. The definition of weak is given in See Moyo. 

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.

The function xplay_attack_either plays alternate moves beginning with an X move at a. Then it passes the last two arguments to attack_either in engine/utils.c. This function looks for a move which captures at least one of the two strings. In its current implementation attack_either only looks for uncoordinated attacks and would thus miss a double atari. 

xplay_break_through(a,b,c,...,x,y,z)
oplay_break_through(a,b,c,...,x,y,z)

These functions are used to set up a position like 

.O.    .y.
OXO    xXz

and X aims at capturing at least one of x, y, and z. If this succeeds 1 is returned. If it doesn't, X tries instead to cut through on either side and if this succeeds, 2 is returned. Of course the same shape with opposite colors can also be used.

Important notice: x, y, and z must be given in the order they have in the diagram above, or any reflection and/or rotation of it. 

seki_helper(x)

Checks whether the string at x can attack any surrounding string. If so, return false as the move to create a seki (probably) wouldn't work. 

threaten_to_save(x)

Calls add_followup_value to add as a move reason a conservative estimate of the value of saving the string x by capturing one opponent stone. 

area_stone(x)

Returns the number of stones in the area around x. 

area_space(x)

Returns the amount of space in the area around x. 

eye(x)
proper_eye(x)
marginal_eye(x)

True if x is an eye space for either color, a non-marginal eye space for either color, or a marginal eye space for either color, respectively. 

antisuji(x)

Tell the move generation that x is a substandard move that never should be played. 

same_dragon(x,y)
same_worm(x,y)

Return true if x and y are the same dragon or worm respectively. 

dragonsize(x)
wormsize(x)

Number of stones in the indicated dragon or worm. 

add_connect_move(x,y)
add_cut_move(x,y)
add_attack_either_move(x,y)
add_defend_both_move(x,y)

Explicitly notify the move generation about move reasons for the move in the pattern. 

halfeye(x)

Returns true if the empty intersection at x is a half eye. 

remove_attack(x)

Inform the tactical reading that a supposed attack does in fact not work. 

potential_cutstone(x)

True if cutstone2 field from worm data is larger than one. This indicates that saving the worm would introduce at least two new cutting points. 

not_lunch(x,y)

Prevents the misreporting of x as lunch for y. For example, the following pattern tells GNU Go that even though the stone at a can be captured, it should not be considered "lunch" for the dragon at b, because capturing it does not produce an eye: 

XO|          ba|
O*|          O*|
oo|          oo|
?o|          ?o|

> not_lunch(a,b)

vital_chain(x)

Calls vital_chain to determine whether capturing the stone at x will result in one eye for an adjacent dragon. The current implementation just checks that the stone is not a singleton on the first line. 

amalgamate(x,y)

Amalgamate (join) the dragons at x and y (see Worms and Dragons). 

amalgamate_most_valuable(x,y,z)

Called when (x,y,z) point to three (preferably distinct) dragons, in situations such as this: 

.O.X
X*OX
.O.X

In this situation, the opponent can play at *, preventing the three dragons from becoming connected. However O can decide which cut to allow. The helper amalgamates the dragon at y with either x or z, whichever is largest. 

make_proper_eye(x)

This autohelper should be called when x is an eyespace which is misidentified as marginal. It is reclassified as a proper eyespace (see Eye Space). 

remove_halfeye(x)

Remove a half eye from the eyespace. This helper should not be run after make_dragons is finished, since by that time the eyespaces have already been analyzed. 

remove_eyepoint(x)

Remove an eye point. This function can only be used before the segmentation into eyespaces. 

owl_topological_eye(x,y)

Here x is an empty intersection which may be an eye or half eye for some dragon, and y is a stone of the dragon, used only to determine the color of the eyespace in question. Returns the sum of the values of the diagonal intersections, relative to x, as explained in See Eye Topology, equal to 4 or more if the eye at x is false, 3 if it is a half eye, and 2 if it is a true eye. 

owl_escape_value(x)

Returns the escape value at x. This is only useful in owl attack and defense patterns and only if the --alternative_escape option is turned on. Otherwise 0 is returned.

Node:Attack and Defense DB, Next:, Previous:Autohelper Functions, Up:Patterns

Attack and Defense Database

The patterns in attack.db and defense.db are used to assist the tactical reading in finding moves that attacks or defends worms. The matching is performed during make_worms(), at the time when the tactical status of all worms is decided. None of the classes described above are useful in these databases, instead we have two other classes. 

D  :  For each O worm in the pattern that can be tactically captured
      (worm[m][n].attack_code != 0), the move at * is tried. If it
      is found to defend the stone, this is registered as a reason
      for the move * and the defense point of the worm is set to *.

A  :  For each X worm in the pattern, it's tested whether the move
      at * captures the worm. If that is the case, this is
      registered as a reason for the move at *. The attack point of
      the worm is set to * and if it wasn't attacked before, a
      defense is searched for.

Furthermore, A patterns can only be used in attack.db and D patterns only in defense.db. Unclassified patterns may appear in these databases, but then they must work through actions to be effective.

Node:Connections Database, Next:, Previous:Attack and Defense DB, Up:Patterns

The Connections Database

The patterns in conn.db are used for helping make_dragons() amalgamate worms into dragons and to some extent for modifying eye spaces. The patterns in this database use the classifications B, C, and e. B patterns are used for finding cutting points, where amalgamation should not be performed, C patterns are used for finding existing connections, over which amalgamation is to be done, and e patterns are used for modifying eye spaces and reevaluating lunches. There are also some patterns without classification, which use action lines to have an impact. These are matched together with the C patterns. Further details and examples can be found in See Worms and Dragons.

We will illustrate these databases by example. In this situation: 

XOO
O.O
...

X cannot play safely at the cutting point, so the O dragons are to be amalgamated. Two patterns are matched here: 

Pattern CC204

O
.
O

:+,C

O
A
O

;!safe_xmove(A) && !ko(A) && !xcut(A)

Pattern CC205

XO
O.

:\,C

AO
OB

;attack(A) || (!safe_xmove(B) && !ko(B) && !xcut(B))

The constraints are mostly clear. For example the second pattern should not be matched if the X stone cannot be attacked and X can play safely at B, or if B is a ko. The constraint !xcut(B) means that connection has not previously been inhibited by find_cuts. For example consider this situation: 

OOXX
O.OX
X..O
X.OO

The previous pattern is matched here twice, yet X can push in and break one of the connections. To fix this, we include a pattern: 

Pattern CB11

?OX?
O!OX
?*!O
??O?

:8,B

?OA?
OaOB
?*bO
??O?

; !attack(A) && !attack(B) && !xplay_attack(*,a,b,*) && !xplay_attack(*,b,a,*)

After this pattern is found, the xcut autohelper macro will return true at any of the points *, a and b. Thus the patterns CB204 and CB205 will not be matched, and the dragons will not be amalgamated.

Node:Connection Functions, Next:, Previous:Connections Database, Up:Patterns

Connections Functions

Here are the public functions in connections.c.

Node:Tuning, Next:, Previous:Connection Functions, Up:Patterns

Tuning the Pattern databases

Since the pattern databases, together with the valuation of move reasons, decide GNU Go's personality, much time can be devoted to "tuning" them. Here are some suggestions.

If you want to experiment with modifying the pattern database, invoke with the -a option. This will cause every pattern to be evaluated, even when some of them may be skipped due to various optimizations.

You can obtain a Smart Go Format (SGF) record of your game in at least two different ways. One is to use CGoban to record the game. You can also have GNU Go record the game in Smart Go Format, using the -o option. It is best to combine this with -a. Do not try to read the SGF file until the game is finished and you have closed the game window. This does not mean that you have to play the game out to its conclusion. You may close the CGoban window on the game and GNU Go will close the SGF file so that you can read it.

If you record a game in SGF form using the -o option, GNU Go will add labels to the board to show all the moves it considered, with their values. This is an extremely useful feature, since one can see at a glance whether the right moves with appropriate weights are being proposed by the move generation.

First, due to a bug of unknown nature, it occasionally happens that GNU Go will not receive the SIGTERM signal from CGoban that it needs to know that the game is over. When this happens, the SGF file ends without a closing parenthesis, and CGoban will not open the file. You can fix the file by typing: 

 echo ")" >>[filename]

at the command line to add this closing parenthesis. Or you could add the ) using an editor.

Move values exceeding 99 (these should be rare) can be displayed by CGoban but you may have to resize the window in order to see all three digits. Grab the lower right margin of the CGoban window and pull it until the window is large. All three digits should be visible.

If you are playing a game without the -o option and you wish to analyze a move, you may still use CGoban's "Save Game" button to get an SGF file. It will not have the values of the moves labelled, of course.

Once you have a game saved in SGF format, you can analyze any particular move by running: 

  gnugo -l [filename] -L [move number] -t -a -w

to see why GNU Go made that move, and if you make changes to the pattern database and recompile the program, you may ask GNU Go to repeat the move to see how the behavior changes. If you're using emacs, it's a good idea to run GNU Go in a shell in a buffer (M-x shell) since this gives good navigation and search facilities.

Instead of a move number, you can also give a board coordinate to -L in order to stop at the first move played at this location. If you omit the -L option, the move after those in the file will be considered.

If a bad move is proposed, this can have several reasons. To begin with, each move should be valued in terms of actual points on the board, as accurately as can be expected by the program. If it's not, something is wrong. This may have two reasons. One possibility is that there are reasons missing for the move or that bogus reasons have been found. The other possibility is that the move reasons have been misevaluated by the move valuation functions. Tuning of patterns is with a few exceptions a question of fixing the first kind of problems.

If there are bogus move reasons found, search through the trace output for the pattern that is responsible. (Some move reasons, e.g. most tactical attack and defense, do not originate from patterns. If no pattern produced the bogus move reason, it is not a tuning problem.) Probably this pattern was too general or had a faulty constraint. Try to make it more specific or correct bugs if there were any. If the pattern and the constraint looks right, verify that the tactical reading evaluates the constraint correctly. If not, this is either a reading bug or a case where the reading is too complicated for GNU Go.

If a connecting move reason is found, but the strings are already effectively connected, there may be missing patterns in conn.db. Similarly, worms may be incorrectly amalgamated due to some too general or faulty pattern in conn.db. To get trace output from the matching of patterns in conn.db you need to add a second -t option.

If a move reason is missing, there may be a hole in the database. It could also be caused by some existing pattern being needlessly specific, having a faulty constraint, or being rejected due to a reading mistake. Unless you are familiar with the pattern databases, it may be hard to verify that there really is a pattern missing. Look around the databases to try to get a feeling for how they are organized. (This is admittedly a weak point of the pattern databases, but the goal is to make them more organized with time.) If you decide that a new pattern is needed, try to make it as general as possible, without allowing incorrect matches, by using proper classification from among snOoXx and constraints. The reading functions can be put to good use. The reason for making the patterns as general as they can be is that we need a smaller number of them then, which makes the database much easier to maintain. Of course, if you need too complicated constraints, it's usually better to split the pattern.

If a move has the correct set of reasons but still is misevaluated, this is usually not a tuning problem. There are, however, some possibilities to work around these mistakes with the use of patterns. In particular, if the territorial value is off because delta_terri() give strange results, the (min)terri and maxterri values can be set by patterns as a workaround. This is typically done by the endgame patterns, where we can know the (minimum) value fairly well from the pattern. If it should be needed, (min)value and maxvalue can be used similarly. These possibilities should be used conservatively though, since such patterns are likely to become obsolete when better (or at least different) functions for e.g. territory estimation are being developed.

In order to choose between moves with the same move reasons, e.g. moves that connect two dragons in different ways, patterns with a nonzero shape value should be used. These should give positive shape values for moves that give good shape or good aji and negative values for bad shape and bad aji. Notice that these values are additive, so it's important that the matches are unique.

Sente moves are indicated by the use of the pattern followup value. This can usually not be estimated very accurately, but a good rule is to be rather conservative. As usual it should be measured in terms of actual points on the board. These values are also additive so the same care must be taken to avoid unintended multiple matches.

You can also get a visual display of the dragons using the -T option. The default GNU Go configuration tries to build a version with color support using either curses or the ansi escape sequences. You are more likely to find color support in rxvt than xterm, at least on many systems, so we recommend running: 

  gnugo -l [filename] -L [move number] -T

in an rxvt window. If you do not see a color display, and if your host is a GNU/Linux machine, try this again in the Linux console.

Worms belonging to the same dragon are labelled with the same letters. The colors indicate the value of the field dragon.safety, which is set in moyo.c. 

Green:  GNU Go thinks the dragon is alive
Yellow: Status unknown
Blue:   GNU Go thinks the dragon is dead
Red:    Status critical (1.5 eyes) or weak by the algorithm
        in moyo.c

If you want to get the same game over and over again, you can eliminate the randomness in GNU Go's play by providing a fixed random seed with the -r option.

Node:PM Implementation, Next:, Previous:Tuning, Up:Patterns

Implementation

The pattern code in GNU Go is fairly straightforward conceptually, but because the matcher consumes a significant part of the time in choosing a move, the code is optimized for speed. Because of this there are implementation details which obscure things slightly.

In GNU Go, the ascii .db files are precompiled into tables (see patterns.h) by a standalone program mkpat.c, and the resulting .c files are compiled and linked into the main gnugo executable.

Each pattern is compiled to a header, and a sequence of elements, which are (notionally) checked sequentially at every position and orientation of the board. These elements are relative to the pattern 'anchor' (or origin). One X or O stone is (arbitrarily) chosen to represent the origin of the pattern. (We cannot dictate one or the other since some patterns contain only one colour or the other.) All the elements are in co-ordinates relative to this position. So a pattern matches "at" board position (m,n,o) if the the pattern anchor stone is on (m,n), and the other elements match the board when the pattern is transformed by transformation number o. (See below for the details of the transformations, though these should not be necessary)

Node:Symmetry & transformations, Next:, Previous:PM Implementation, Up:Patterns

Symmetry and transformations

In general, each pattern must be tried in each of 8 different permutations, to reflect the symmetry of the board. But some patterns have symmetries which mean that it is unnecessary (and therefore inefficient) to try all eight. The first character after the : can be one of 8,|,\,/, X, -, +, representing the axes of symmetry. It can also be O, representing symmetry under 180 degrees rotation. 

transformation   I    -    |     .     \    l    r     /
                ABC  GHI  CBA   IHG   ADG  CFI  GDA   IFC
                DEF  DEF  FED   FED   BEH  BEH  HEB   HEB
                GHI  ABC  IHG   CBA   CFI  ADG  IFC   GDA

                 a    b    c     d     e    f    g     h

Then if the pattern has the following symmetries, the following are true: 

|  c=a, d=b, g=e, h=f
-  b=a, c=d, e=f, g=h
\  e=a, g=b, f=c, h=d
/  h=a, f=b, g=c, e=d
O  a=d, b=c, e=h, f=g
X  a=d=e=h, b=c=f=g
+  a=b=c=d, e=f=g=h

We can choose to use transformations a,d,f,g as the unique transformations for patterns with either |, -, \, or / symmetry.

Thus we choose to order the transformations a,g,d,f,h,b,e,c and choose first 2 for X and +, the first 4 for |, -, /, and \, the middle 4 for O, and all 8 for non-symmetrical patterns.

Each of the reflection operations (e-h) is equivalent to reflection about one arbitrary axis followed by one of the rotations (a-d). We can choose to reflect about the axis of symmetry (which causes no net change) and can therefore conclude that each of e-h is equivalent to the reflection (no-op) followed by a-d. This argument therefore extends to include - and / as well as | and \.

Node:Details, Next:, Previous:Symmetry & transformations, Up:Patterns

Implementation Details

  1. An entry in the pattern header states whether the anchor is an X or an O. This helps performance, since all transformations can be rejected at once if the anchor stone does not match. (Ideally, we could just define that the anchor is always O or always X, but some patterns contain no O's and some contain no X's.)
  2. The pattern header contains the size of the pattern (ie the co-ordinates of the top left and bottom right elements) relative to the anchor. This allows the pattern can be rejected quickly if there is not room for the pattern to fit around the anchor stone in a given orientation (ie it is too near the edge of the board). The bounding box information must first be transformed like the elements before it can be tested, and after transforming, we need to work out where the top-left and bottom-right corners are.
  3. The edge constraints are implemented by notionally padding the pattern with rows or columns of ? until it is exactly 19 (or whatever the current board size is) elements wide or high. Then the pattern is quickly rejected by (ii) above if it is not at the edge. So the example pattern above is compiled as if it was written 
    "example"
.OO????????????????
*XX????????????????
o??????????????????
:8,80
  4. The elements in a pattern are sorted so that non-space elements are checked before space elements. It is hoped that, for most of the game, more squares are empty, and so the pattern can be more quickly rejected doing it this way.
  5. The actual tests are performed using an 'and-compare' sequence. Each board position is a 2-bit quantity. %00 for empty, %01 for O, %10 for X. We can test for an exact match by and-ing with %11 (no-op), then comparing with 0, 1 or 2. The test for o is the same as a test for 'not-X', ie not %10. So and with %01 should give 0 if it matches. Similarly x is a test that bit 0 is not set.

Node:grid optimization, Next:, Previous:Details, Up:Patterns

The "Grid" Optimization

The comparisons between pattern and board are performed as 2-bit bitwise operations. Therefore they can be performed in parallel, 16-at-a-time on a 32-bit machine.

Suppose the board is layed out as follows : 

 .X.O....OO
 XXXXO.....
 .X..OOOOOO
 X.X.......
 ....X...O.

which is internally stored internally in a 2d array (binary) 

 00 10 00 01 00 00 00 00 01 01
 10 10 10 10 01 00 00 00 00 00
 00 10 00 00 01 01 01 01 01 01
 10 00 10 00 00 00 00 00 00 00
 00 00 00 00 10 00 00 00 01 00

we can compile this to a composite array in which each element stores the state of a 4x4 grid of squares : 

 ????????  ????????  ???????? ...
 ??001000  00100001  10000100
 ??101010  10101010  10101001
 ??001000  00100000  10000001

 ??001000  00100001  ...
 ??101010  10101010
 ??001000  00100000
 ??001000  10001000

...

 ??100010  ...
 ??000000
 ????????
 ????????

Where '??' is off the board.

We can store these 32-bit composites in a 2d merged-board array, substituting the illegal value %11 for '??'.

Similarly, for each pattern, mkpat produces appropriate 32-bit and-value masks for the pattern elements near the anchor. It is a simple matter to test the pattern with a similar test to (5) above, but for 32-bits at a time.

Node:Joseki Compiler, Next:, Previous:grid optimization, Up:Patterns

The Joseki Compiler

GNU Go includes a joseki compiler in patterns/joseki.c. This processes an SGF file (with variations) and produces a sequence of patterns which can then be fed back into mkpat. The joseki database is currently in files in patterns/ called hoshi.sgf, komoku.sgf, sansan.sgf, mokuhazushi.sgf and takamoku.sgf. This division can be revised whenever need arises.

The SGF files are transformed into the pattern database .db format by the program in joseki.c. These files are in turn transformed into C code by the program in mkpat.c and the C files are compiled and linked into the GNU Go binary.

Not every node in the SGF file contributes a pattern. The nodes which contribute patterns have the joseki in the upper right corner, with the boundary marked with a square mark and other information to determine the resulting pattern marked in the comments.

The intention is that the move valuation should be able to choose between the available variations by normal valuation. When this fails the primary workaround is to use shape values to increase or decrease the value. It is also possible to add antisuji variations to forbid popular suboptimal moves. As usual constraints can be used, e.g. to condition a variation on a working ladder.

The joseki format has the following components for each SGF node:

Example: If the comment in the SGF file looks like 

F
:C,shape(3)
;xplay_attack(A,B,C,D,*)

the generated pattern will have a colon line 

:8,sjC,shape(3)

and a constraint 

;xplay_attack(A,B,C,D,*)

Node:Ladders in Joseki, Previous:Joseki Compiler, Up:Patterns

Ladders in Joseki

As an example of how to use autohelpers with the Joseki compiler, we consider an example where a Joseki is bad if a ladder fails. Assume we have the taisha and are considering connecting on the outside with the pattern 

--------+
........|
........|
...XX...|
...OXO..|
...*O...|
....X...|
........|
........|

But this is bad unless we have a ladder in our favor. To check this we add a constraint which may look like 

--------+
........|
........|
...XX...|
...OXO..|
...*OAC.|
....DB..|
........|
........|

;oplay_attack(*,A,B,C,D)

In order to accept the pattern we require that the constraint on the semicolon line evaluates to true. This particular constraint has the interpretation "Play with alternating colors, starting with O, on the intersections *, A, B, and C. Then check whether the stone at D can be captured." I.e. play to this position 

--------+
........|
........|
...XX...|
...OXO..|
...OOXX.|
....XO..|
........|
........|

and call attack() to see whether the lower X stone can be captured. This is not limited to ladders, but in this particular case the reading will of course involve a ladder.

The constraint diagram above with letters is how it looks in the .db file. The joseki compiler knows how to create these from labels in the SGF node. Cgoban has an option to create one letter labels, but this ought to be a common feature for SGF editors.

Thus in order to implement this example in SGF, one would add labels to the four intersections and a comment: 

;oplay_attack(*,A,B,C,D)

The appropriate constraint (autohelper macro) will then be added to the Joseki .db file.

Node:DFA, Next:, Previous:Patterns, Up:Top

The DFA pattern matcher

In this chapter, we describe the principles of the gnugo DFA pattern matcher. The aim of this system is to permit a fast pattern matching when it becomes time critical like in owl module (The Owl Code). The actual version is still experimental but is expected to be fully integrated in later versions of gnugo. If you want to test it with version 3.0 you must run configure --enable-dfa then recompile GNU Go (Using DFA). The basic principle is to generate off line a finite state machine called a Deterministic Finite State Automaton (What is a DFA) from the pattern database and then use it at runtime to speedup pattern matching (Pattern matching with DFA and Incremental Algorithm).

Node:Using DFA, Next:, Previous:DFA, Up:DFA

Using DFA

First build the program with 'configure -enable-dfa', then type 'make' as usual.

Some .db files will be compiled into DFA's by the program mkpat. DFA are stored into C files and compiled with the engine. When a DFA is found, gnugo write "<pattern database name> -> using dfa" at startup and use the dfa to "filter" patterns. When no DFA is found, the standard pattern matcher is used.

Node:Scan Path, Next:, Previous:Using DFA, Up:DFA

Scan Path

The board is scanned following a predefined path. The default path is a spiral starting from the center of the pattern. This path is used both to build the DFA and to scan the board. path.png

This path is encoded by two arrays of integers order_i[k] and order_j[k] giving the offset where to read the values on the board.

Reading the board following a predefined path reduces the two dimentional pattern matching to a linear text searching problem. This pattern for example: 

?X?
.O?
?OO

scanned following the path 

149
238
567

(i,j)->(i+1,j)->(i+1,j+1)->(i,j+1)->(i+2,j+0)->(i+2,j+1)->(i+2,j+2)...

gives the string "?.OX?OO??" where "?" means 'don't care'. We can forget the two dimensional patterns for a time to focus on linear patterns.

Node:What is a DFA, Next:, Previous:Scan Path, Up:DFA

What is a DFA

The acronym DFA means Deterministic Finite state Automaton (See http://www.eti.pg.gda.pl/~jandac/thesis/node12.html or Hopcroft & Ullman "Introduction to Language Theory" for more details). DFA are common tools in compilers design (Read Aho, Ravi Sethi, Ullman "COMPILERS: Principles, Techniques and Tools" for a complete introduction), a lot of powerfull text searching algorithm like Knuth-Morris-Pratt or Boyer-Moore algorithms are based on DFA's (See http://www-igm.univ-mlv.fr/~lecroq/string/ for a bibliography of pattern matching algorithms).

Basically, a DFA is a set of states connected by labeled transitions. The labels are the values read on the board, in gnugo these values are EMPTY, WHITE, BLACK or OUT_BOARD, denoted respectively by '.','O','X' and '#'.

The best way to represent a dfa is to draw its transition graph: the pattern "????..X" is recognized by the following DFA: dfa.png

This means that starting from state [1], if you read '.','X' or 'O' on the board, go to state [2] and so on until you reach state [5]. From state [5], if you read '.', go to state [6] otherwise go to error state [0]. And so on until you reach state [8]. As soon as you reach state [8], you recognize Pattern "????..X"

Adding a pattern like "XXo" ('o' is a wildcard for not 'X') will transform directly the automaton by synchronization product (Building the DFA). Consider the following DFA: dfa2.png

By adding a special error state and completing each state by a transition to error state when there is none, we transform easily a DFA in a Complete Deterministic Finite state Automaton (CDFA). The synchronization product (Building the DFA) is only possible on CDFA's. cdfa.png

The graph of a CDFA is coded by an array of states: The 0 state is the "error" state and the start state is 1. 

----------------------------------------------------
 state  |   .    |   O    |   X    |   #    |  att
----------------------------------------------------
      1 |      2 |      2 |      9 |      0 |
      2 |      3 |      3 |      3 |      0 |
      3 |      4 |      4 |      4 |      0 |
      5 |      6 |      0 |      0 |      0 |
      6 |      7 |      0 |      0 |      0 |
      7 |      0 |      0 |      8 |      0 |
      8 |      0 |      0 |      0 |      0 | Found pattern "????..X"
      9 |      3 |      3 |      A |      0 |
      A |      B |      B |      4 |      0 |
      B |      5 |      5 |      5 |      0 | Found pattern "XXo"
----------------------------------------------------

To each state we associate an often empty list of attributes which is the list of pattern indexes recognized when this state is reached. In 'dfa.h' this is basically represented by two stuctures: 


/* dfa state */
typedef struct state
{
  int next[4]; /* transitions for EMPTY, BLACK, WHITE and OUT_BOARD */
  attrib_t *att;
}
state_t;

/* dfa */
typedef struct dfa
{
  attrib_t *indexes; /* Array of pattern indexes */
  int maxIndexes;

  state_t *states; /* Array of states */
  int maxStates;
}
dfa_t;

Node:Pattern matching with DFA, Next:, Previous:What is a DFA, Up:DFA

Pattern matching with DFA

Recognizing with a DFA is very simple and thus very fast (See 'scan_for_pattern()' in the 'engine/matchpat.c' file).

Starting from the start state, we only need to read the board following the spiral path, jump from states to states following the transitions labelled by the values read on the board and collect the patterns indexes on the way. If we reach the error state (zero), it means that no more patterns will be matched. The worst case complexity of this algorithm is o(m) where m is the size of the biggest pattern.

Here is an example of scan:

First we build a minimal dfa recognizing these patterns: "X..X", "X???", "X.OX" and "X?oX". Note that wildcards like '?','o', or 'x' give multiple out-transitions. 

----------------------------------------------------
 state  |   .    |   O    |   X    |   #    |  att
----------------------------------------------------
      1 |      0 |      0 |      2 |      0 |
      2 |      3 |     10 |     10 |      0 |
      3 |      4 |      7 |      9 |      0 |
      4 |      5 |      5 |      6 |      0 |
      5 |      0 |      0 |      0 |      0 |    2
      6 |      0 |      0 |      0 |      0 |    4    2    1
      7 |      5 |      5 |      8 |      0 |
      8 |      0 |      0 |      0 |      0 |    4    2    3
      9 |      5 |      5 |      5 |      0 |
     10 |     11 |     11 |      9 |      0 |
     11 |      5 |      5 |     12 |      0 |
     12 |      0 |      0 |      0 |      0 |    4    2
----------------------------------------------------

We perform the scan of the string "X..XXO...." starting from state 1:

Current state: 1, substring to scan : X..XXO....

We read an 'X' value, so from state 1 we must go to state 2.

Current state: 2, substring to scan : ..XXO....

We read a '.' value, so from state 2 we must go to state 3 and so on ... 

Current state:     3, substring to scan : .XXO....
Current state:     4, substring to scan : XXO....
Current state:     6, substring to scan : XO....
Found pattern 4
Found pattern 2
Found pattern 1

After reaching state 6 where we match patterns 1,2 and 4, there is no out-transitions so we stop the matching. To keep the same match order as in the standard algorithm, the patterns indexes are collected in an array and sorted by indexes.

Node:Building the DFA, Next:, Previous:Pattern matching with DFA, Up:DFA

Building the DFA

The most flavouring point is the building of the minimal DFA recognizing a given set of patterns. To perform the insertion of a new pattern into an already existing DFA one must completly rebuild the DFA: the principle is to build the minimal CDFA recognizing the new pattern to replace the original CDFA with its synchronised product by the new one.

We first give a formal definition: Let L be the left CDFA and R be the right one. Let B be the synchronised product of L by R. Its states are the couples (l,r) where l is a state of L and r is a state of R. The state (0,0) is the error state of B and the state (1,1) is its initial state. To each couple (l,r) we associate the union of patterns recognized in both l and r. The transitions set of B is the set of transitions (l1,r1)--a-->(l2,r2) for each symbol 'a' such that both l1--a-->l2 in L and r1--a-->r2 in R.

The maximal number of states of B is the product of the number of states of L and R but almost all this states are non reachable from the initial state (1,1).

The algorithm used in function 'sync_product()' builds the minimal product DFA only by keeping the reachable states. It recursively scans the product CDFA by following simultaneously the transitions of L and R. A hast table (gtest) is used to check if a state (l,r) has already been reached, the reachable states are remapped on a new DFA. The CDFA thus obtained is minimal and recognizes the union of the two patterns sets.

For example these two CDFA's: sync-prod1.png

Give by synchronization product the following one: sync-prod2.png

It is possible to construct a special pattern database that generates an "explosive" automaton: the size of the DFA is in the worst case exponential in the number of patterns it recognizes. But it doesn't occur in pratical situations: the dfa size tends to be stable. By stable we mean that if we add a pattern which greatly increases the size of the dfa it also increases the chance that the next added pattern does not increase its size at all. Nevertheless there are many ways to reduce the size of the DFA. Good compression methods are explained in Aho, Ravi Sethi, Ullman "COMPILERS: Principles, Techniques and Tools" chapter Optimization of DFA-based pattern matchers.

Node:Incremental Algorithm, Next:, Previous:Building the DFA, Up:DFA

Incremental Algorithm

The incremental version of the DFA pattern matcher is not yet implemented in gnugo but we explain here how it will work. By definition of a deterministic automaton, scanning the same string will reach the same states every time.

Each reached state during pattern matching is stored in a stack top_stack[i][j] and state_stack[i][j][stack_idx] We use one stack by intersection (i,j). A precomputed reverse path list allows to know for each couple of board intersections (x,y) its position reverse(x,y) in the spiral scan path starting from (0,0).

When a new stone is put on the board at (lx,ly), the only work of the pattern matcher is: 


 for(each stone on the board at (i,j))
    if(reverse(lx-i,ly-j) < top_stack[i][j])
      {
         begin the dfa scan from the state
         state_stack[i][j][reverse(lx-i,ly-j)];
      }

In most situations reverse(lx-i,ly-j) will be inferior to top_stack[i][j]. This should speedup a lot pattern matching.

Node:DFA Optimizations, Previous:Incremental Algorithm, Up:DFA

Some DFA Optimizations

The dfa is constructed to minimize jumps in memory making some assumptions about the frequencies of the values: the EMPTY value is supposed to appear often on the board, so the the '.' transition are almost always successors in memory. The OUT_BOARD are supposed to be rare, so '#' transitions will almost always imply a big jump.

Node:Tactical Reading, Next:, Previous:DFA, Up:Top

Tactical reading

The process of visualizing potential moves done by you and your opponent to learn the result of different moves is called "reading". GNU Go does three distinct types of reading: tactical reading which typically is concerned with the life and death of individual strings, Owl reading which is concerned with the life and death of dragons, and life reading which attempts evaluate eye spaces. In this Chapter, we document the tactical reading code, which is in engine/reading.c. For a summary of the reading functions see See Reading Functions.

Node:Reading Basics, Next:, Previous:Tactical Reading, Up:Tactical Reading

Reading Basics

In GNU Go, tactical reading is done by the functions in engine/reading.c. Each of these functions has a separate goal to fill, and they call each other recursively to carry out the reading process.

The reading code makes use of a stack onto which board positions can be pushed. The parameter stackp is zero if GNU Go is examining the true board position; if it is higher than zero, then GNU Go is examining a hypothetical position obtained by playing several moves.

The most important public reading functions are attack and find_defense. These are wrappers for functions do_attack and do_find_defense which are declared statically in reading.c. The functions do_attack and do_find_defense call each other recursively.

The return codes of the reading (and owl) functions and owl can be 0, 1, 2 or 3. Each reading function determines whether a particular player (assumed to have the move) can solve a specific problem, typically attacking or defending a string.

The nonzero return codes are called these names in the source: 

   #define WIN  3
   #define KO_A 2
   #define KO_B 1

A return code of WIN means success, 0 failure, while KO_A and KO_B are success conditioned on ko. A function returns KO_A if the position results in ko and that the player to move will get the first ko capture (so the opponent has to make the first ko threat). A return code of KO_B means that the player to move will have to make the first ko threat.

Many of the reading functions make use of null pointers. For example, a call to attack(i, j, &ai, &aj) will return WIN if the string at (i, j) can be captured. The point of attack (in case it is vulnerable) is returned in (ai, aj). However many times we do not care about the point of attack. In this case, we can substitute a null pointer: attack(i, j, NULL, NULL).

Depth of reading is controlled by the parameters depth and branch_depth. The depth has a default value DEPTH (in liberty.h), which is set to 14 in the distribution, but it may also be set at the command line using the -D or --depth option. If depth is increased, GNU Go will be stronger and slower. GNU Go will read moves past depth, but in doing so it makes simplifying assumptions that can cause it to miss moves.

Specifically, when stackp > depth, GNU Go assumes that as soon as the string can get 3 liberties it is alive. This assumption is sufficient for reading ladders.

The branch_depth is typically set a little below depth. Between branch_depth and depth, attacks on strings with 3 liberties are considered, but branching is inhibited, so fewer variations are considered.

Currently the reading code does not try to defend a string by attacking a boundary string with more than two liberties. Because of this restriction, it can make oversights. A symptom of this is two adjacent strings, each having three or four liberties, each classified as DEAD. To resolve such situations, a function small_semeai() (in engine/semeai.c) looks for such pairs of strings and corrects their classification.

The backfill_depth is a similar variable with a default 10. Below this depth, GNU Go will try "backfilling" to capture stones. For example in this situation: 

.OOOOOO.    on the edge of the board, O can capture X but
OOXXXXXO    in order to do so he has to first play at a in
.aObX.XO    preparation for making the atari at b. This is
--------    called backfilling.

Backfilling is only tried with stackp <= backfill_depth. The parameter backfill_depth may be set using the -B option.

The fourlib_depth is a parameter with a default of only 5. Below this depth, GNU Go will try to attack strings with four liberties. The fourlib_depth may be set using the -F option.

The parameter ko_depth is a similar cutoff. If stackp<ko_depth, the reading code will make experiments involving taking a ko even if it is not legal to do so (i.e., it is hypothesized that a remote ko threat is made and answered before continuation). This parameter may be set using the -K option.

A partial list of the functions in reading.c:

The next few functions are essentially special cases of attack and find_defense. They are coded individually, and are static in engine/reading.c.

Node:Hashing, Next:, Previous:Reading Basics, Up:Tactical Reading

Hashing of Positions

To speed up the reading process, we note that a position can be reached in several different ways. In fact, it is a very common occurrence that a previously checked position is rechecked, often within the same search but from a different branch in the recursion tree.

This wastes a lot of computing resources, so in a number of places, we store away the current position, the function we are in, and which worm is under attack or to be defended. When the search for this position is finished, we also store away the result of the search and which move made the attack or defense succeed.

All this data is stored in a hash table, sometimes also called a transposition table, where Go positions are the key and results of the reading for certain functions and groups are the data. You can increase the size of the Hash table using the -M or --memory option see Invoking GNU Go.

The hash table is created once and for all at the beginning of the game by the function hashtable_new(). Although hash memory is thus allocated only once in the game, the table is reinitialized at the beginning of each move by a call to hashtable_clear() from genmove().

Node:Hash Calculation, Next:, Previous:Hashing, Up:Hashing

Calculation of the hash value

The hash algorithm is called Zobrist hashing, and is a standard technique for go and chess programming. The algorithm as used by us works as follows:

  1. First we define a go position. This positions consists of

    It is not necessary to specify the color to move (white or black) as part of the position. The reason for this is that read results are stored separately for the various reading functions such as attack3, and it is implicit in the calling function which player is to move.

  2. For each location on the board we generate random numbers:

    These random numbers are generated once at initialization time and then used throughout the life time of the hash table.

  3. The hash key for a position is the XOR of all the random numbers which are applicable for the position (white stones, black stones, and ko position).

Node:Hash Organization, Next:, Previous:Hash Calculation, Up:Hashing

Organization of the hash table

The hash table consists of 3 parts:

When the hash table is created, these 3 areas are allocated using malloc(). When the hash table is populated, all contents are taken from the Hash nodes and the Read results. No further allocation is done and when all nodes or results are used, the hash table is full. Nothing is deleted from the hash table except when it is totally emptied, at which point it can be used again as if newly initialized.

When a function wants to use the hash table, it looks up the current position using hashtable_search(). If the position doesn't already exist there, it can be entered using

hashtable_enter_position().

Once the function has a pointer to the hash node containing a function, it can search for a result of a previous search using hashnode_search(). If a result is found, it can be used, and if not, a new result can be entered after a search using hashnode_new_result().

Hash nodes which hash to the same position in the hash table (collisions) form a simple linked list. Read results for the same position, created by different functions and different attacked or defended strings also form a linked list.

This is deemed sufficiently efficient for now, but the representation of collisions could be changed in the future. It is also not determined what the optimum sizes for the hash table, the number of positions and the number of results are.

Node:Hash Structures, Next:, Previous:Hash Organization, Up:Hashing

Hash Structures

The basic hash structures are declared in hash.h. 

typedef struct hashposition_t {
  Compacttype  board[COMPACT_BOARD_SIZE];
  int          ko_i;
  int          ko_j;
} Hashposition;

Represents the board and optionally the location of a ko, which is an illegal move. The player whose move is next is not recorded. 

typedef struct {
  Hashvalue     hashval;
  Hashposition  hashpos;
} Hash_data;

Represents the return value of a function (hashval) and the board state (hashpos). 

typedef struct read_result_t {
  unsigned int compressed_data;

  int result_ri_rj;
  struct read_result_t *next;
} Read_result;

Here the compressed_data field packs into 32 bits the following fields: 

 komaster: 2 bits (EMPTY, BLACK, WHITE, or GRAY)
 kom_i   : 5 bits
 kom_j   : 5 bits
 routine : 4 bits (currently 10 different choices)
 i       : 5 bits
 j       : 5 bits
 stackp  : 5 bits

The komaster and (kom_i,kom_j) field are documented in See Ko. The integer result_ri_rj encodes: 

  unsigned char  status;
  unsigned char  result;
  unsigned char  ri;
  unsigned char  rj;

When a new result node is created, 'status' is set to 1 'open'. This is then set to 2 'closed' when the result is entered. The main use for this is to identify open result nodes when the hashtable is partially cleared. Another potential use for this field is to identify repeated positions in the reading, in particular local double or triple kos. 

typedef struct hashnode_t {
  Hash_data            key;
  Read_result        * results;
  struct hashnode_t  * next;
} Hashnode;

The hash table consists of hash nodes. Each hash node consists of The hash value for the position it holds, the position itself and the actual information which is purpose of the table from the start.

There is also a pointer to another hash node which is used when the nodes are sorted into hash buckets (see below). 

typedef struct hashtable {
  size_t         hashtablesize;	/* Number of hash buckets */
  Hashnode    ** hashtable;	/* Pointer to array of hashnode lists */

  int            num_nodes;	/* Total number of hash nodes */
  Hashnode     * all_nodes;	/* Pointer to all allocated hash nodes. */
  int            free_node;	/* Index to next free node. */

  int            num_results;	/* Total number of results */
  Read_result  * all_results;	/* Pointer to all allocated results. */
  int            free_result;	/* Index to next free result. */
} Hashtable;

The hash table consists of three parts:

Node:Hash Functions, Next:, Previous:Hash Structures, Up:Hashing

Hash Functions

The following functions are defined in hash.c:

The following macros are defined in hash.h

The following macros and functions are defined in engine/reading.c:

Node:Persistent Cache, Next:, Previous:Hash Functions, Up:Tactical Reading

Persistent Reading Cache

Some reading calculations can be safely saved from move to move.

The function store_persistent_cache() is called only by attack and find_defense, never from their static recursive counterparts do_attack and do_defend. The function store_persistent_reading_cache() attempts to cache the most expensive reading results. The function search_persistent_reading_cache attempts to retrieve a result from the cache.

If all cache entries are occupied, we try to replace the least useful one. This is indicated by the score field, which is initially the number of nodes expended by this particular reading, and later multiplied by the number of times it has been retrieved from the cache.

Once a (permanent) move is made, a number of cache entries immediately become invalid. These are cleaned away by the function purge_persistent_reading_cache(). To have a criterion for when a result may be purged, the function store_persistent_cache() computes the reading shadow and active area. If a permanent move is subsequently played in the active area, the cached result is invalidated. We now explain this algorithm in detail.

The reading shadow is the concatenation of all moves in all variations, as well as locations where an illegal move has been tried.

Once the read is finished, the reading shadow is expanded to the active area which may be cached. The intention is that as long as no stones are played in the active area, the cached value may safely be used.

Here is the algorithm used to compute the active area. This algorithm is in the function store_persistent_reading_cache(). The most expensive readings so far are stored in the persistent cache.

Node:Ko, Next:, Previous:Persistent Cache, Up:Tactical Reading

Ko Handling

The principles of ko handling are the same for tactical reading and owl reading.

We have already mentioned (see Reading Basics) that GNU Go uses a return code of KO_A or KO_B if the result depends on ko. The return code of KO_B means that the position can be won provided the player whose move calls the function can come up with a sufficiently large ko threat. In order to verify this, the function must simulate making a ko threat and having it answered by taking the ko even if it is illegal. We call such an experimental taking of the ko a conditional ko capture.

Conditional ko captures are accomplished by the function tryko(). This function is like trymove() except that it does not require legality of the move in question.

The static reading functions, and the global functions do_attack and do_find_defense have arguments komaster, kom_i and kom_j. These mediate ko captures to prevent the occurrence of infinite loops.

Normally komaster is EMPTY but it can also be BLACK, WHITE or GRAY. The komaster is set to COLOR when COLOR makes a conditional ko capture. In this case kom_i, kom_j is set to the location of the captured ko stone.

If the opponent is komaster, the reading functions will not try to take the ko at kom_i, kom_j. Also, the komaster is normally not allowed to take another ko. The exception is a nested ko, characterized by the condition that the captured ko stone is at distance 1 both vertically and horizontally from (kom_i, kom_j), which is the location of the last stone taken by the komaster. Thus in this situation: 

         .OX
         OX*X
        OmOX
         OO

Here if m is the location of (kom_i,kom_j), then the move at * is allowed.

The rationale behind this rule is that in the case where there are two kos on the board, the komaster cannot win both, and by becoming komaster he has already chosen which ko he wants to win. But in the case of a nested ko, taking one ko is a precondition to taking the other one, so we allow this.

If the komaster's opponent takes a ko, then both players have taken one ko. In this case `komaster' is set to GRAY and after this further ko captures are not allowed.

If the ko at (kom_i, kom_j) is filled, then the komaster reverts to EMPTY.

The komaster scheme may be summarized as follows. It is assumed that O is about to move.

Node:A Ko Example, Next:, Previous:Ko, Up:Tactical Reading

A Ko Example

To see the komaster scheme in action, consider this position from the file regressions/games/life_and_death/tripod9.sgf. We recommend studying this example by examining the variation file produced by the command: 

  gnugo -l tripod9.sgf --decidedragon C3 -o vars.sgf

In the lower left hand corner, there are kos at A2 and B4. Black is unconditionally dead because if W wins either ko there is nothing B can do. 

 8 . . . . . . . .
 7 . . O . . . . .
 6 . . O . . . . .
 5 O O O . . . . .
 4 O . O O . . . .
 3 X O X O O O O .
 2 . X X X O . . .
 1 X O . . . . . .
   A B C D E F G H

This is how the komaster scheme sees this. B (i.e. X) starts by taking the ko at B4. W replies by taking the ko at A1. The board looks like this: 

 8 . . . . . . . .
 7 . . O . . . . .
 6 . . O . . . . .
 5 O O O . . . . .
 4 O X O O . . . .
 3 X . X O O O O .
 2 O X X X O . . .
 1 . O . . . . . .
   A B C D E F G H

Now any move except the ko recapture (currently illegal) at A1 loses for B, so B retakes the ko and becomes komaster. The board looks like this: 

 8 . . . . . . . .         komaster: BLACK
 7 . . O . . . . .         (kom_i, kom_j): A2
 6 . . O . . . . .
 5 O O O . . . . .
 4 O X O O . . . .
 3 X . X O O O O .
 2 . X X X O . . .
 1 X O . . . . . .
   A B C D E F G H

W takes the ko at B3 after which the komaster is GRAY and ko recaptures are not allowed. 

 8 . . . . . . . .         komaster: GRAY
 7 . . O . . . . .         (kom_i, kom_j): B4
 6 . . O . . . . .
 5 O O O . . . . .
 4 O . O O . . . .
 3 X O X O O O O .
 2 . X X X O . . .
 1 X O . . . . . .
   A B C D E F G H

Since X is not allowed any ko recaptures, there is nothing he can do and he is found dead. Thus the komaster scheme produces the correct result.

Node:Another Ko Example, Next:, Previous:A Ko Example, Up:Tactical Reading

We now consider an example to show why the komaster is reset to EMPTY if the ko is resolved in the komaster's favor. This means that the ko is filled, or else that is becomes no longer a ko and it is illegal for the komaster's opponent to play there.

The position resulting under consideration is in the file regressions/games/ko5.sgf. This is the position: 

 . . . . . . O O 8
 X X X . . . O . 7
 X . X X . . O . 6
 . X . X X X O O 5
 X X . X . X O X 4
 . O X O O O X . 3
 O O X O . O X X 2
 . O . X O X X . 1
 F G H J K L M N

We recommend studying this example by examining the variation file produced by the command: 

gnugo -l ko5.sgf --quiet --decidestring L1 -o vars.sgf

The correct resolution is that H1 attacks L1 while K2 defends it with ko (code KO_A).

After Black (X) takes the ko at K3, white can do nothing but retake the ko conditionally, becoming komaster. B cannot do much, but in one variation he plays at K4 and W takes at H1. The following position results: 

 . . . . . . O O 8
 X X X . . . O . 7
 X . X X . . O . 6
 . X . X X X O O 5
 X X . X X X O X 4
 . O X O O O X . 3
 O O X O . O X X 2
 . O O . O X X . 1
 F G H J K L M N

Now it is important the O is no longer komaster. Were O still komaster, he could capture the ko at N3 and there would be no way to finish off B.

Node:Alternate Komaster Schemes, Next:, Previous:Another Ko Example, Up:Tactical Reading

The following alternate schemes have been proposed. It is assumed that O is the player about to move.

Essentially the 2.7.232 scheme.

Revised 2.7.232 version

Node:Superstrings, Next:, Previous:Alternate Komaster Schemes, Up:Tactical Reading

Superstrings

A superstring is an extended string, where the extensions are through the following kinds of connections:

  1. Solid connections (just like ordinary string). 
      OO
  2. Diagonal connection or one space jump through an intersection where an opponent move would be suicide or self-atari. 
      ...
  O.O
  XOX
  X.X
  3. Bamboo joint. 
      OO
  ..
  OO
  4. Diagonal connection where both adjacent intersections are empty. 
      .O
  O.
  5. Connection through adjacent or diagonal tactically captured stones. Connections of this type are omitted when the superstring code is called from reading.c, but included when the superstring code is called from owl.c.

Like a dragon, a superstring is an amalgamation of strings, but it is a much tighter organization of stones than a dragon, and its purpose is different. Superstrings are encountered already in the tactical reading because sometimes attacking or defending an element of the superstring is the best way to attack or defend a string. This is in contrast with dragons, which are ignored during tactical reading.

Node:Reading Functions, Next:, Previous:Superstrings, Up:Tactical Reading

Reading Functions

Here we list the publically callable functions in reading.c. The return codes of these functions are explained elsewhere (see Reading Basics).

Node:Debugging, Previous:Reading Functions, Up:Tactical Reading

Debugging the reading code

The reading code searches for a path through the move tree to determine whether a string can be captured. We have a tool for investigating this with the --decidestring option. This may be run with or without an output file.

Simply running 

gnugo -t -l [input file name] -L [movenumber] --decidestring [location]

will run attack() to determine whether the string can be captured. If it can, it will also run find_defense() to determine whether or not it can be defended. It will give a count of the number of variations read. The -t is necessary, or else GNU Go will not report its findings.

If we add -o output file GNU Go will produce an output file with all variations considered. The variations are numbered in comments.

This file of variations is not very useful without a way of navigating the source code. This is provided with the GDB source file, listed at the end. You can source this from GDB, or just make it your GDB init file.

If you are using GDB to debug GNU Go you may find it less confusing to compile without optimization. The optimization sometimes changes the order in which program steps are executed. For example, to compile reading.c without optimization, edit engine/Makefile to remove the string -O2 from the file, touch engine/reading.c and make. Note that the Makefile is automatically generated and may get overwritten later.

If in the course of reading you need to analyze a result where a function gets its value by returning a cached position from the hashing code, rerun the example with the hashing turned off by the command line option --hash 0. You should get the same result. (If you do not, please send us a bug report.) Don't run --hash 0 unless you have a good reason to, since it increases the number of variations.

With the source file given at the end of this document loaded, we can now navigate the variations. It is a good idea to use cgoban with a small -fontHeight, so that the variation window takes in a big picture. (You can resize the board.)

Suppose after perusing this file, we find that variation 17 is interesting and we would like to find out exactly what is going on here.

The macro 'jt n' will jump to the n-th variation. 

(gdb) set args -l [filename] -L [move number] --decidestring [location]
(gdb) tbreak main
(gdb) run
(gdb) jt 17

will then jump to the location in question.

Actually the attack variations and defense variations are numbered separately. (But find_defense() is only run if attack() succeeds, so the defense variations may or may not exist.) It is redundant to have to tbreak main each time. So there are two macros avar and dvar. 

(gdb) avar 17

restarts the program, and jumps to the 17-th attack variation. 

(gdb) dvar 17

jumps to the 17-th defense variation. Both variation sets are found in the same sgf file, though they are numbered separately.

Other commands defined in this file: 


dump will print the move stack.
nv moves to the next variation
ascii i j converts (i,j) to ascii

#######################################################
###############      .gdbinit file      ###############
#######################################################

# this command displays the stack

define dump
set dump_stack()
end

# display the name of the move in ascii

define ascii
set gprintf("%o%m\n",$arg0,$arg1)
end

# display the all information about a dragon

define dragon
set ascii_report_dragon("$arg0")
end

define worm
set ascii_report_worm("$arg0")
end

# move to the next variation

define nv
tbreak trymove
continue
finish
next
end

# move forward to a particular variation

define jt
while (count_variations < $arg0)
nv
end
nv
dump
end

# restart, jump to a particular attack variation

define avar
delete
tbreak sgffile_decidestring
run
tbreak attack
continue
jt $arg0
end

# restart, jump to a particular defense variation

define dvar
delete
tbreak sgffile_decidestring
run
tbreak attack
continue
finish
next 3
jt $arg0
end

Node:Life and Death Reading, Next:, Previous:Tactical Reading, Up:Top

Life and Death Reading

GNU Go does two very different types of life and death reading. First, there is the OWL code (Optics with Limit Negotiation) which attempts to read out to a point where the code in engine/optics.c (see Eyes) can be used to evaluate it.

Secondly, there is the code in engine/life.c which is a potential replacement for the code in optics.c. It attempts to evaluate eyespaces more accurately than the code in optics.c, but since it is fairly slow, it is partially disabled unless you run GNU Go with the option --life. The default use of the life code is that it can be called from optics.c when the graph based life and death code concludes that it needs an expert opinion.

Like the tactical reading code, a persistent cache is employed to maintain some of the owl data from move to move. This is an essential speedup without which GNU Go would play too slowly.

Node:The Owl Code, Next:, Up:Life and Death Reading

The Owl Code

The life and death code in optics.c, described elsewhere (see Eyes), works reasonably well as long as the position is in a terminal position, which we define to be one where there are no moves left which can expand the eye space, or limit it. In situations where the dragon is surrounded, yet has room to thrash around a bit making eyes, a simple application of the graph-based analysis will not work. Instead, a bit of reading is needed to reach a terminal position.

The defender tries to expand his eyespace, the attacker to limit it, and when neither finds an effective move, the position is evaluated. We call this type of life and death reading Optics With Limit-negotiation (OWL). The module which implements it is in engine/owl.c.

There are two reasonably small databases patterns/owl_defendpats.db and patterns/owl_attackpats.db of expanding and limiting moves. The code in owl.c generates a small move tree, allowing the attacker only moves from owl_attackpats.db, and the defender only moves from owl_defendpats.db. In addition to the moves suggested by patterns, vital moves from the eye space analysis are also tested.

A third database, owl_vital_apats.db includes patterns which override the eyespace analysis done by the optics code. Since the eyeshape graphs ignore the complications of shortage of liberties and cutting points in the surrounding chains, the static analysis of eyespace is sometimes wrong. The problem is when the optics code says that a dragon definitely has 2 eyes, but it isn't true due to shortage of liberties, so the ordinary owl patterns never get into play. In such situations owl_vital_apats.db is the only available measure to correct mistakes by the optics. Currently the patterns in owl_vital_apats.db are only matched when the level is 9 or greater.

The owl code is tuned by editing these three pattern databases, principally the first two.

A node of the move tree is considered terminal if no further moves are found from apats.db or dpats.db, or if the function compute_eyes_pessimistic() reports that the group is definitely alive or dead. At this point, the status of the group is evaluated. The functions owl_attack() and owl_defend(), with usage similar to attack() and find_defense(), make use of the owl pattern databases to generate the move tree and decide the status of the group.

The function compute_eyes_pessimistic() used by the owl code is very conservative and only feels certain about eyes if the eyespace is completely closed (i.e. no marginal vertices).

The maximum number of moves tried at each node is limited by the parameter MAX_MOVES defined at the beginning of engine/owl.c. The most most valuable moves are tried first, with the following restrictions:

The functions owl_attack() and owl_defend() may, like attack() and find_defense(), return an attacking or defending move through their pointer arguments. If the position is already won, owl_attack() may or may not return an attacking move. If it finds no move of interest, it will return PASS, that is, (-1,-1). The same goes for owl_defend().

When owl_attack() or owl_defend() is called, the dragon under attack is marked in the array goal. The stones of the dragon originally on the board are marked with goal=1; those added by owl_defend() are marked with goal=2. If all the original strings of the original dragon are captured, owl_attack() considers the dragon to be defeated, even if some stones added later can make a live group.

Only dragons with small escape route are studied when the functions are called from make_dragons().

The owl code can be conveniently tested using the --decidedragon location This should be used with -t to produce a useful trace, -o to produce an SGF file of variations produced when the life and death of the dragon at location is checked, or both. --decideposition performs the same analysis for all dragons with small escape route.

Node:Owl Functions, Previous:The Owl Code, Up:Life and Death Reading

Functions in owl.c

In this section we list the non-static functions in owl.c. Note that calls to owl_attack and owl_defend should be made only when stackp==0. If you want to set up a position, then use the owl code to analyze it, you may call do_owl_attack and do_owl_defend with stackp>0 but first you must set up the goal and boundary arrays. See owl_does_defend and owl_substantial for examples.

The reason that we do not try to write a general owl_attack which works when stackp>0 is that we make use of cached information in the calls to same_dragon from the (static) function owl_mark_dragon. This requires the dragon data to be current, which it is not when stackp>0.

Node:Influence, Next:, Previous:Life and Death Reading, Up:Top

Influence Function

Node:Influential Concepts, Next:, Previous:Influence, Up:Influence

Conceptual Outline of Influence

We define lively stones to be all stones that can't be tactically attacked or have a tactical defense. Stones that have been found to be strategically dead are called dead while all other stones are called alive. If we want to use the influence function before deciding the strategical status, all lively stones count as alive.

Every alive stone on the board works as an influence source, with influence of its color radiating outwards in all directions. The strength of the influence declines exponentially with the distance from the source.

Influence can only flow unhindered if the board is empty, however. All lively stones (regardless of color) act as influence barriers, as do connections between enemy stones that can't be broken through. For example the one space jump counts as a barrier unless either of the stones can be captured. Notice that it doesn't matter much if the connection between the two stones can be broken, since in that case there would come influence from both directions anyway.

We define territory to be the intersections where one color has no influence at all and the other player does have. We can introduce moyo and area concepts similar to those provided by the Bouzy algorithms in terms of the influence values for the two colors. "Territory" refers to certain or probable territory while "Moyo" refers to an area of dominant influence which is not necessarily guaranteed territory. "Area" refers to the breathing space around a group in which it can manoever if it is attacked.

In order to avoid finding bogus territory, we add extra influence sources at places where an invasion can be launched, e.g. at 3-3 under a handicap stone, in the middle of wide edge extensions and in the center of large open spaces anywhere. Similarly we add extra influence sources where intrusions can be made into what otherwise looks as solid territory, e.g. monkey jumps.

Walls typically radiate an influence that is stronger than the sum of the influence from the stones building the wall. To accommodate for this phenomenon, we also add extra influence sources in empty space at certain distances away from walls.

Node:The Influence Core, Next:, Previous:Influential Concepts, Up:Influence

The Core of the Influence Function

The basic influence radiation process can efficiently be implemented as a breadth first search for adjacent and more distant points, using a queue structure.

Influence barriers can be found by pattern matching, assisted by reading through constraints and/or helpers. Wall structures, invasion points and intrusion points can be found by pattern matching as well.

When influence is computed, the basic idea is that there are a number of influence sources on the board, whose contributions are summed to produce the influence values. For the time being we can assume that the living stones on the board are the influence sources, although this is not the whole story.

The function compute_influence() contains a loop over the board, and for each influence source on the board, the function accumulate_influence() is called. This is the core of the influence function. Before we get into the details, this is how the influence field from a single isolated influence source of strength 100 turns out: 

  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  1  1  1  0  0  0  0
  0  0  0  1  2  3  2  1  0  0  0
  0  0  1  3  5 11  5  3  1  0  0
  0  1  2  5 16 33 16  5  2  1  0
  0  1  3 11 33  X 33 11  3  1  0
  0  1  2  5 16 33 16  5  2  1  0
  0  0  1  3  5 11  5  3  1  0  0
  0  0  0  1  2  3  2  1  0  0  0
  0  0  0  0  1  1  1  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0

These values are in reality floating point numbers but have been rounded down to the nearest integer for presentation. This means that the influence field does not stop when the numbers become zeroes.

Internally accumulate_influence() starts at the influence source and spreads influence outwards by means of a breadth first propagation, implemented in the form of a queue. The order of propagation and the condition that influence only is spread outwards guarantee that no intersection is visited more than once and that the process terminates. In the example above, the intersections are visited in the following order: 

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

The visitation of intersections continues in the same way on the intersections marked '+ and further outwards. In a real position there will be stones and tight connections stopping the influence from spreading to certain intersections. This will disrupt the diagram above, but the main property of the propagation still remains, i.e. no intersection is visited more than once and after being visited no more influence will be propagated to the intersection.

Node:The Influence Algorithm, Next:, Previous:The Influence Core, Up:Influence

The Core of the Influence Function

Let (m, n) be the coordinates of the influence source and (i, j) the coordinates of a an intersection being visited during propagation, using the same notation as in the accumulate_influence() function. Influence is now propagated to its eight closest neighbors, including the diagonal ones, according to the follow scheme:

For each of the eight directions (di, dj), do:

  1. Compute the scalar product di*(i-m) + dj*(j-n) between the vectors (di,dj) and (i,j) - (m,n)
  2. If this is negative or zero, the direction is not outwards and we continue with the next direction. The exception is when we are visiting the influence source, i.e. the first intersection, when we spread influence in all directions anyway.
  3. If (i+di, j+dj) is outside the board or occupied we also continue with the next direction.
  4. Let S be the strength of the influence at (i, j). The influence propagated to (i+di, j+dj) from this intersection is given by P*(1/A)*D*S, where the three different kinds of damping are:

Influence is typically contributed from up to three neighbors "between" this intersection and the influence source. These values are simply added together. As pointed out before, all contributions will automatically have been made before the intersection itself is visited.

When the total influence for the whole board is computed by compute_influence(), accumulate_influence() is called once for each influence source. These invocations are totally independent and the influence contributions from the different sources are added together.

Node:Permeability, Next:, Previous:The Influence Algorithm, Up:Influence

Permeability

The permeability at the different points is initially one at all empty intersections and zero at occupied intersections. To get a useful influence function we need to modify this, however. Consider the following position: 

|......
|OOOO..
|...O..
|...a.X   ('a' empty intersection)
|...O..
|...OOO
|.....O
+------

The corner is of course secure territory for O and clearly the X stone has negligible effect inside this position. To stop X influence from leaking into the corner we use pattern matching (pattern Barrier1/Barrier2 in barriers.db) to modify the permeability for X at this intersection to zero. O can still spread influence through this connection.

Another case that needs to be mentioned is how the permeability damping is computed for diagonal influence radiation. For horizontal and vertical radiation we just use the permeability (for the relevant color) at the intersection we are radiating from. In the diagonal case we additionally multiply with the maximum permeability at the two intersections we are trying to squeeze between. The reason for this can be found in the diagram below: 

|...X    |...X
|OO..    |Oda.
|..O.    |.bc.
|..O.    |..O.
+----    +----

We don't want X influence to be spread from a to b, and since the permeability at both c and d is zero, the rule above stops this.

Node:Escape, Next:, Previous:Permeability, Up:Influence

Escape

One application of the influence code is in computing the dragon.escape_route field. This is computed by the function compute_escape() as follows. First, every intersection is assigned an escape value, ranging between 0 and 4, depending on the influence value of the opposite color.

In addition to assiging an escape value to empty vertices, we also assign an escape value to friendly dragons. This value can range from 0 to 6 depending on the status of the dragon, with live dragons having value 6.

Then we sum the values of the resulting influence escape values over the intersections (including friendly dragons) at distance 4, that is, over those intersections which can be joined to the dragon by a path of length 4 (and no shorter path) not passing adjacent to any unfriendly dragon. In the following example, we sum the influence escape value over the four vertices labelled '4'. 

   . . . . . . . . .    . . . . . . . . .
   . . . . . X . . O    . . . . . X . . O
   . . X . . . . . O    . . X . 2 . 4 . O
   X . . . . . . . .    X . . 1 1 2 3 4 .
   X O . O . . . . O    X O 1 O 1 2 3 4 O
   X O . O . . . . .    X O 1 O 1 . 4 . .
   X O . . . X . O O    X O 1 . . X . . O
   . . . X . . . . .    . 1 . X . . . . .
   X . . . . X . . .    X . . . . X . . .
   . . . . . . . . .    . . . . . . . . .

Since the dragon is trying to reach safety, the reader might wonder why compute_influence() is called with the opposite color of the dragon contemplating escape. To explain this point, we first remind the reader why there is a color parameter to compute_influence(). Consider the following example position: 

     ...XX...
     OOO..OOO
     O......O
     O......O
     --------

Whether the bottom will become O territory depends on who is in turn to play. This is implemented with the help of patterns in barriers.db, so that X influence is allowed to leak into the bottom if X is in turn to move but not if O is. There are also "invade" patterns which add influence sources in sufficiently open parts of the board which are handled differently depending on who is in turn to move.

In order to decide the territorial value of an O move in the third line gap above, influence is first computed in the original position with the opponent (i.e. X) in turn to move. Then the O stone is played to give: 

     ...XX...
     OOO.OOOO
     O......O
     O......O
     --------

Now influence is computed once more, also this time with X in turn to move. The difference in territory (as computed from the influence values) gives the territorial value of the move.

Exactly how influence is computed for use in the escape route estimation is all ad hoc. But it makes sense to assume the opponent color in turn to move so that the escape possibilities aren't overestimated. After we have made a move in the escape direction it is after all the opponent's turn.

The current escape route mechanism seems good enough to be useful but is not completely reliable. Mostly it seems to err on the side of being too optimistic.

Node:Influential Functions, Next:, Previous:Escape, Up:Influence

Influential Functions

Node:Influential Display, Previous:Influential Functions, Up:Influence

Colored display and debugging of influence

It is possible to obtain colored diagrams showing influence from a colored xterm or rxvt window.

Notice that you need to activate at least one of -m 0x8 or --debuginfluence, and at least one of -m 0x10 and -m 0x20, to get any diagrams at all. The first two determine when to print diagrams while the last two determine what diagrams to print.

Node:Moyo, Next:, Previous:Influence, Up:Top

Moyo

The file score.c contains algorithms for the computation of a number of useful things. Most can be displayed visually using the -m option (see Colored Display).

Node:Moyo history, Next:, Previous:Moyo, Up:Moyo

In GNU Go 2.6 extensive use was made of an algorithm from Bruno Bouzy's dissertation, which is available at: <ftp://www.joy.ne.jp/welcome/igs/Go/computer/bbthese.ps.Z> This algorithm starts with the characteristic function of the live groups on the board and performs n operations called dilations, then m operations called erosions. If n=5 and m=21 this is called the 5/21 algorithm.

The Bouzy 5/21 algorithm is interesting in that it corresponds reasonably well to the human concept of territory. This algorithm is still used in GNU Go 3.0 in the function estimate_score. Thus we associate the 5/21 algorithm with the word territory. Similarly we use words moyo and area in reference to the 5/10 and 4/0 algorithms, respectively.

The principle defect of the algorithm is that it is not tunable. The current method of estimating moyos and territory is in influence.c (see Influence). The territory, moyo and area concepts have been reimplemented using the influence code.

The Bouzy algorithm is briefly reimplemented in the file scoring.c and is used by GNU Go 3.0 in estimating the score.

Not all features of the old moyo.c from GNU Go 2.6 were reimplemented--particularly the deltas were not--but the reimplementation may be more readable.

Node:Bouzy, Previous:Moyo history, Up:Moyo

Bouzy's 5/21 algorithm

Bouzy's algorithm was inspired by prior work of Zobrist and ideas from computer vision for determining territory. This algorithm is based on two simple operations, DILATION and EROSION. Applying dilation 5 times and erosion 21 times determines the territory.

To get a feeling for the algorithm, take a position in the early middle game and try the colored display using the -m 1 option in an RXVT window. The regions considered territory by this algorithm tend to coincide with the judgement of a strong human player.

Before running the algorithm, dead stones (dragon.status==0) must be "removed."

Referring to page 86 of Bouzy's thesis, we start with a function taking a high value (ex : +128 for black, -128 for white) on stones on the goban, 0 to empty intersections. We may iterate the following operations:

dilation: for each intersection of the goban, if the intersection is >= 0, and not adjacent to a <0 one, then add to the intersection the number of adjacent >0 intersections. The same for other color : if the intersection is <=0, and not adjacent to a >0 one, then sub to it the number of <0 intersections.

erosion: for each intersection >0 (or <0), subtract (or add) the number of adjacent <=0 (or >=0) intersection. Stop at zero. The algorithm is just : 5 dilations, then 21 erosions. The number of erosions should be 1+n(n-1) where n=number of dilation, since this permit to have an isolated stone to give no territory. Thus the couple 4/13 also works, but it is often not good, for example when there is territory on the 6th line.

For example, let us start with a tobi. 

           128    0    128

1 dilation : 

            1          1

       1   128    2   128   1

            1          1

2 dilations : 

            1          1

       2    2     3    2    2

   1   2   132    4   132   2   1

       2    2     3    2    2

            1          1

3 dilations : 

            1          1

       2    2     3    2    2

   2   4    6     6    6    4   2

1  2   6   136    8   136   6   2   1

   2   4    6     6    6    4   2

       2    2     3    2    2

            1          1

and so on...

Next, with the same example

3 dilations and 1 erosion : 

             2     2     2

    0   4    6     6     6    4

0   2   6   136    8    136   6    2

    0   4    6     6     6    4

             2     2     2

3 dilations and 2 erosions : 

                 1

      2    6     6     6    2

      6   136    8    136   6

      2    6     6     6    2

                 1

3 dil. / 3 erosions : 

           5     6     5

      5   136    8    136   5

           5     6     5

3/4 : 

          3     5     3

      2  136    8    136   2

          3     5     3

3/5 : 

          1     4     1

         136    8    136

          1     4     1

3/6 : 

                3

         135    8    135

                3

3/7 : 

         132    8    132

We interpret this as a 1 point territory.

Node:Utility Functions, Next:, Previous:Moyo, Up:Top

Utility Functions

In this Chapter, we document some of the utilities which may be called from the GNU Go engine. If there are differences between this documentation and the source files, the source files are the ultimate reference. You may find it convenient to use Emacs' built in facility for navigating the source to find functions and their in-source documentation (see Navigating the Source).

Node:General Utilities, Next:, Up:Utility Functions

General Utilities

Utility functions from engine/utils.c. Many of these functions underlie autohelper functions (see Autohelper Functions).

Node:Print Utilities, Previous:General Utilities, Up:Utility Functions

Print utilities

Utility functions from engine/printutils.c.

Node:Incremental Board, Next:, Previous:Utility Functions, Up:Top

Incremental Algorithms in Reading

The algorithms in board.c implement a method of incremental board updates that keeps track of the following information for each string:

The basic data structure is 

struct string_data {
  int color;                  /* Color of string, BLACK or WHITE */
  int size;                   /* Number of stones in string. */
  int origini;                /* Coordinates of "origin", i.e. */
  int originj;                /* "upper left" stone. */
  int liberties;              /* Number of liberties. */
  int libi[MAX_LIBERTIES];    /* Coordinates of liberties. */
  int libj[MAX_LIBERTIES];
  int neighbors;              /* Number of neighbor strings */
  int neighborlist[MAXCHAIN]; /* List of neighbor string numbers. */
  int mark;                   /* General purpose mark. */
};

struct string_data string[MAX_STRINGS];

It should be clear that almost all information is stored in the string array. To get a mapping from the board coordinates to the string array we have 

int string_number[MAX_BOARD][MAX_BOARD];

which contains indices into the string array. This information is only valid at nonempty vertices, however, so it is necessary to first verify that p[i][j] != EMPTY.

The string_data structure does not include an array of the stone coordinates. This information is stored in a separate array (or rather two): 

int next_stonei[MAX_BOARD][MAX_BOARD];
int next_stonej[MAX_BOARD][MAX_BOARD];

These arrays implement cyclic linked lists of stones. Each vertex contains a pointer to another (possibly the same) vertex. Starting at an arbitrary stone on the board, following these pointers should traverse the entire string in an arbitrary order before coming back to the starting point. As for the 'string_number' array, this information is invalid at empty points on the board. This data structure has the good properties of requiring fixed space (regardless of the number of strings) and making it easy to add a new stone or join two strings.

Additionally the code makes use of some work variables: 

static int ml[MAX_BOARD][MAX_BOARD];
static int liberty_mark;
static int string_mark;
static int next_string;
static int strings_initialized = 0;

The ml array and liberty_mark are used to "mark" liberties on the board, e.g. to avoid counting the same liberty twice. The convention is that if ml[i][j] has the same value as liberty_mark, then (i, j) is marked. To clear all marks it suffices to increase the value of liberty_mark, since it is never allowed to decrease.

The same relation holds between the mark field of the string_data structure and string_mark. Of course these are used for marking individual strings.

next_string gives the number of the next available entry in the string array. Then strings_initialized is set to one when all data structures are known to be up to date. Given an arbitrary board position in the p array, this is done by calling incremental_board_init(). It is not necessary to call this function explicitly since any other function that needs the information does this if it has not been done.

The interesting part of the code is the incremental update of the data structures when a stone is played and subsequently removed. To understand the strategies involved in adding a stone it is necessary to first know how undoing a move works. The idea is that as soon as some piece of information is about to be changed, the old value is pushed onto a stack which stores the value and its address. The stack is built from the following structures: 

struct change_stack_entry {
  int *address;
  int value;
};

struct change_stack_entry change_stack[STACK_SIZE];
int change_stack_index;

and manipulated with the macros 

BEGIN_CHANGE_RECORD()
PUSH_VALUE(v)
POP_MOVE()

Calling BEGIN_CHANGE_RECORD() stores a null pointer in the address field to indicate the start of changes for a new move. As mentioned earlier PUSH_VALUE() stores a value and its corresponding address. Assuming that all changed information has been duly pushed onto the stack, undoing the move is only a matter of calling POP_MOVE(), which simply assigns the values to the addresses in the reverse order until the null pointer is reached. This description is slightly simplified because this stack can only store 'int' values and we need to also store changes to the board. Thus we have two parallel stacks where one stores int values and the other one stores Intersection values.

When a new stone is played on the board, first captured opponent strings, if any, are removed. In this step we have to push the board values and the next_stone pointers for the removed stones, and update the liberties and neighbor lists for the neighbors of the removed strings. We do not have to push all information in the 'string' entries of the removed strings however. As we do not reuse the entries they will remain intact until the move is pushed and they are back in use.

After this we put down the new stone and get three distinct cases:

  1. The new stone is isolated, i.e. it has no friendly neighbor.
  2. The new stone has exactly one friendly neighbor.
  3. The new stone has at least two friendly neighbors.

The first case is easiest. Then we create a new string by using the number given by next_string and increasing this variable. The string will have size one, next_stone points directly back on itself, the liberties can be found by looking for empty points in the four directions, possible neighbor strings are found in the same way, and those need also to remove one liberty and add one neighbor.

In the second case we do not create a new string but extend the neighbor with the new stone. This involves linking the new stone into the cyclic chain, if needed moving the origin, and updating liberties and neighbors. Liberty and neighbor information also needs updating for the neighbors of the new stone.

In the third case finally, we need to join already existing strings. In order not to have to store excessive amounts of information, we create a new string for the new stone and let it assimilate the neighbor strings. Thus all information about those can simply be left around in the 'string' array, exactly as for removed strings. Here it becomes a little more complex to keep track of liberties and neighbors since those may have been shared by more than one of the joined strings. Making good use of marks it all becomes rather straightforward anyway.

The often used construction 

    FIRST_STONE(s, i, j);
    do {
        ...
        NEXT_STONE(i, j);
    } while (!BACK_TO_FIRST_STONE(s, i, j));

traverses the stones of the string with number s exactly once, with (i, j) holding the coordinates. In general (i, j) are used as board coordinates and s as an index into the string array or sometimes a pointer to an entry in the string array.

Node:GTP, Next:, Previous:Incremental Board, Up:Top

The Go Text Protocol

Node:The Go Text Protocol, Next:, Previous:GTP, Up:GTP

The GNU Go Text Protocol

GNU Go 3.0 introduces a new interface, the Go Text Protocol (GTP). The intention is to make an interface that is better suited for machine-machine communication than the ascii interface and simpler, more powerful, and more flexible than the Go Modem Protocol.

The GTP has two principal current applications: it is used in the test suite (see Regression) and it is used to communicate with gnugoclient, which is not part of the GNU Go distribution, but has been used to run GNU Go on NNGS. Other potential uses might be any of the current uses of the GMP, for which the GTP might serve as a replacement. This would likely entail extension and standardization of the protocol.

A sample GTP session may look as follows: 

  hannah 2289% ./interface/gnugo --quiet --mode gtp
  1 loadsgf regression/games/incident156.sgf 249
  =1

  2 countlib C3
  =2 4

  3 findlib C3
  =3 C4 B3 D3 B2

  5 attack C3
  =5 0

  owl_attack C3
  = 1 B4

  3 owl_defend C3
  =3 1 B5

  owl_attack A2
  ? vertex must not be empty

  quit
  =

By specifying --mode gtp GNU Go starts in the GTP interface. No prompt is used, just start giving commands. The commands have the common syntax 

[id] command_name [arguments]

The command is exactly one line long, i.e. it ends as soon as a newline appears. It's not possible to give multiple commands on the same line. Before the command name an optional identity number can be specified. If present it must be an integer between 0 and 2^31-1. The id numbers may come in any order or be reused. The rest of the line after the command name is assumed to be arguments for the command. Empty lines are ignored, as is everything following a hash sign up to the end of the line.

If the command is successful, the response is of the form 

=[id] result

Here = indicates success and id is the identity number given in the command or the empty string if the id was omitted. This is followed by the result, which is a text string ending with two consecutive newlines.

If the command fails for some reason, the response takes the form 

?[id] error_message

Here ? indicates failure, id is as before, and error_message gives an explanation for the failure. This string also ends with two consecutive newlines.

The available commands may always be listed using the single command help. Currently this gives the list below. 

attack
black
boardsize
color
combination_attack
countlib
debug_influence
debug_move_influence
decrease_depths
defend
dragon_data
dragon_status
dump_stack
echo
eval_eye
final_score
findlib
fixed_handicap
genmove_black
genmove_white
get_life_node_counter
get_owl_node_counter
get_reading_node_counter
get_trymove_counter
gg_genmove
help
increase_depths
influence
is_legal
komi
level
loadsgf
move_influence
name
new_score
owl_attack
owl_defend
popgo
prisoners
quit
report_uncertainty
reset_life_node_counter
reset_owl_node_counter
reset_reading_node_counter
reset_trymove_counter
same_dragon
showboard
trymove
tune_move_ordering
version
white
worm_cutstone
worm_data

For exact specification of their arguments and results we refer to the comments of the functions in interface/play_gtp.c.

Node:Protocol applications, Next:, Previous:The Go Text Protocol, Up:GTP

The protocol is asymmetric and involves two parties, which we may call A and B. A is typically some kind of arbiter or relay and B is a go engine. All communication is initiated by A in form of commands, to which B responds.

Potential setups include:

  1. Regression testing. 
    A (regression script) -- B (engine).
    A sets up a board position and asks B to e.g. generate a move or find an attack on a specific string.
  2. Human vs program. 
    A (GUI) -- B (engine)
    The GUI relays moves between the human and the engine and asks the engine to generate moves. Optionally the GUI may also use GTP to ask the engine which moves are legal or give a score when the game is finished.
  3. Program vs program with arbiter. 
    B1 (engine 1) -- A (arbiter) -- B2 (engine 2)
    A relays moves between the two engines and alternately asks the engines to generate moves. This involves two different GTP channels, the first between A and B1, and the second between A and B2. There is no direct communication between B1 and B2. The arbiter dictates board size, komi, rules, etc.
  4. Program vs program without arbiter.
    The same as above except that B1 includes the arbiter functionality and the first GTP link is shortcut.
  5. Connection between go server and program. 
    Go server -- A (relay) -- B (engine)
    A talks with a go server using whatever protocol is needed and listens for match requests. When one arrives it accepts it, starts the go engine and issues GTP commands to set up board size, komi, etc. and if a game is restarted it also sets up the position. Then it relays moves between the server and the engine and asks the engine to generate new moves when it is in turn.

Setups 1 and 5 are in active and regular use with GNU Go. Programs implementing setup 3 are also distributed with GNU Go (the files interface/gtp_examples/twogtp and interface/gtp_examples/2ptkgo.pl).

Node:Protocol conventions, Next:, Previous:Protocol applications, Up:GTP

The GTP is currently unfinished and unstandardized. It is hoped that it will grow to fill the needs currently served by the GMP and perhaps other functions. As it is yet unstandardized, this section gives some general remarks which we hope will constrain its development. We also discuss how the GTP is implemented in GNU Go, for the benefit of anyone wishing to add new commands. Notice that the current set of GTP commands is a mix of generally useful ones and highly GNU Go specific ones. Only the former should be part of a standardized protocol while the latter should be private extensions.

The purpose of the protocol is machine-machine communication. It may be tempting to modify the protocol so that it becomes more comfortable for the human user, for example with an automatic showboard after every move. This is absolutely not the purpose of the protocol! Use the ascii interface instead if you're inclined to make such a change.

Newlines are implemented differently on different operating systems. On Unix, a newline is just a line feed LF (ascii \012). On DOS/Windows it is CRLF (\013\012). Thus whether GNU Go sends a carriage return with the line feed depends on which platform it is compiled for. The arbiter should silently discard carriage returns.

Applications using GTP should never have to guess about the basic structure of the responses, defined above. The basic construction for coding a GTP command can be found in gtp_countlib(): 

static int
gtp_countlib(char *s, int id)
{
  int i, j;
  if (!gtp_decode_coord(s, &i, &j))
    return gtp_failure(id, "invalid coordinate");

  if (p[i][j] == EMPTY)
    return gtp_failure(id, "vertex must not be empty");

  return gtp_success(id, "%d", countlib(i, j));
}

The functions gtp_failure() and gtp_success() automatically ensures the specified response format, assuming the strings they are printing do not end with a newline.

Sometimes the output is too complex for use with gtp_success, e.g. if we want to print vertices, which gtp_success() doesn't support. Then we have to fall back to the construction in e.g. gtp_genmove_white(): 

static int
gtp_genmove_white(char *s, int id)
{
  int i, j;
  UNUSED(s);
  if (genmove(&i, &j, WHITE) >= 0)
    play_move(i, j, WHITE);

  gtp_printid(id, GTP_SUCCESS);
  gtp_print_vertex(i, j);
  return gtp_finish_response();
}

Here gtp_printid() writes the equal sign and the request id while gtp_finish_response() adds the final two newlines. The next example is from gtp_influence(): 

  gtp_printid(id, GTP_SUCCESS);
  get_initial_influence(color, 1, white_influence,
			black_influence, influence_regions);
  print_influence(white_influence, black_influence, influence_regions);
  /* We already have one newline, thus can't use gtp_finish_response(). */
  gtp_printf("\n");
  return GTP_OK;

As we have said, the response should be finished with two newlines. Here we have to finish up the response ourselves since we already have one newline in place.

One problem that can be expected to be common is that an engine happens to finish its response with three (or more) rather than two consecutive newlines. This is an error by the engine that the controller can easily detect and ignore. Thus a well behaved engine should not send stray newlines, but should they appear the controller should ignore them. The opposite problem of an engine failing to properly finish its response with two newlines will result in deadlock. Don't do this mistake!

Although it doesn't suffice in more complex cases, gtp_success() is by far the most convenient construction when it does. For example, the function gtp_report_uncertainty takes a single argument which is expected to be "on" or "off", after which it sets the value of report_uncertainty, a variable which affects the form of future GTP responses, reports success, and exits. The function is coded thus: 

static int
gtp_report_uncertainty(char *s, int id)
{
  if (!strncmp(s, "on", 2)) {
    report_uncertainty = 1;
    return gtp_success(id, "");
  }
  if (!strncmp(s, "off", 3)) {
    report_uncertainty = 0;
    return gtp_success(id, "");
  }
  return gtp_failure(id, "invalid argument");
}

Node:Regression with GTP, Previous:Protocol conventions, Up:GTP

Regression testing with GTP

GNU Go uses GTP for regression testing. These tests are implemented as files with GTP commands, which are fed to GNU Go simply by redirecting stdin to read from a file. The output is filtered so that equal signs and responses from commands without id numbers are removed. These results are then compared with expected results encoded in GTP comments in the file, using matching with regular expressions. More information can be found in the regression chapter (see Regression).

Node:Regression, Next:, Previous:GTP, Up:Top

Regression testing

The standard purpose of regression testing is to avoid getting the same bug twice. When a bug is found, the programmer fixes the bug and adds a test to the test suite. The test should fail before the fix and pass after the fix. When a new version is about to be released, all the tests in the regression test suite are run and if an old bug reappears, this will be seen quickly since the appropriate test will fail.

The regression testing in GNU Go is slightly different. A typical test case involves specifying a position and asking the engine what move it would make. This is compared to one or more correct moves to decide whether the test case passes or fails. It is also stored whether a test case is expected to pass or fail, and deviations in this status signify whether a change has solved some problem and/or broken something else. Thus the regression tests both include positions highlighting some mistake being done by the engine, which are waiting to be fixed, and positions where the engine does the right thing, where we want to detect if a change breaks something.

Regression testing in GNU Go

Regression testing is performed by the files in the regression/ directory. The tests are specified as GTP commands in files with the suffix .tst, with corresponding correct results and expected pass/fail status encoded in GTP comments following the test. To run a test suite the shell scripts test.sh, eval.sh, and regress.sh can be used. There are also Makefile targets to do this. If you make all_batches most of the tests are run.

Game records used by the regression tests are stored in the directory regression/games/ and its subdirectories.

Test suites

The regression tests are grouped into suites and stored in files as GTP commands. A part of a test suite can look as follows: 

# Connecting with ko at B14 looks best. Cutting at D17 might be
# considered. B17 (game move) is inferior.
loadsgf games/strategy25.sgf 61
90 gg_genmove black
#? [B14|D17]

# The game move at P13 is a suicidal blunder.
loadsgf games/strategy25.sgf 249
95 gg_genmove black
#? [!P13]

loadsgf games/strategy26.sgf 257
100 gg_genmove black
#? [M16]*

Lines starting with a hash sign, or in general anything following a hash sign, are interpreted as comments by the GTP mode and thus ignored by the engine. GTP commands are executed in the order they appear, but only those on numbered lines are used for testing. The comment lines starting with #? are magical to the regression testing scripts and indicate correct results and expected pass/fail status. The string within brackets is matched as a regular expression against the response from the previous numbered GTP command. A particular useful feature of regular expressions is that by using | it is possible to specify alternatives. Thus B14|D17 above means that if either B14 or D17 is the move generated in test case 90, it passes. There is one important special case to be aware of. If the correct result string starts with an exclamation mark, this is excluded from the regular expression but afterwards the result of the matching is negated. Thus !P13 in test case 95 means that any move except P13 is accepted as a correct result.

In test case 100, the brackets on the #? line is followed by an asterisk. This means that the test is expected to fail. If there is no asterisk, the test is expected to pass. The brackets may also be followed by a &, meaning that the result is ignored. This is primarily used to report statistics, e.g. how many tactical reading nodes were spent while running the test suite.

Performing tests

./test.sh blunder.tst runs the tests in blunder.tst and prints the results of the commands on numbered lines, which may look like: 

1 E5
2 F9
3 O18
4 B7
5 A4
6 E4
7 E3
8 A3
9 D9
10 J9
11 B3
12 C6
13 C6

This is usually not very informative, however. More interesting is ./eval.sh blunder.tst which also compares the results above against the correct ones in the test file and prints a report for each test on the form: 

1 failed: Correct '!E5', got 'E5'
2 failed: Correct 'C9|H9', got 'F9'
3 PASSED
4 failed: Correct 'B5|C5|C4|D4|E4|E3|F3', got 'B7'
5 PASSED
6 failed: Correct 'D4', got 'E4'
7 PASSED
8 failed: Correct 'B4', got 'A3'
9 failed: Correct 'G8|G9|H8', got 'D9'
10 failed: Correct 'G9|F9|C7', got 'J9'
11 failed: Correct 'D4|E4|E5|F4|C6', got 'B3'
12 failed: Correct 'D4', got 'C6'
13 failed: Correct 'D4|E4|E5|F4', got 'C6'

The result of a test can be one of four different cases:

If you want a less verbose report, ./regress.sh . blunder.tst does the same thing as the previous command, but only reports unexpected results. The example above is compressed to 

3 unexpected PASS!
5 unexpected PASS!
7 unexpected PASS!

For convenience the tests are also available as makefile targets. For example, make blunder runs the tests in the blunder test suite by executing eval.sh blunder.tst. make test runs all test suites in a sequence using the regress.sh script.

Node:Copying, Next:, Previous:Regression, Up:Top

Copying

The program GNU Go is distributed under the terms of the GNU General Public License (GPL). Its documentation is distributed under the terms of the GNU Free Documentation License (GFDL).

Node:GPL, Next:, Previous:Copying, Up:Copying

GNU GENERAL PUBLIC LICENSE

Version 2, June 1991

Copyright © 1989, 1991 Free Software Foundation, Inc.
59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

Everyone is permitted to copy and distribute verbatim copies
of this license document, but changing it is not allowed.

Preamble

The licenses for most software are designed to take away your freedom to share and change it. By contrast, the GNU General Public License is intended to guarantee your freedom to share and change free software--to make sure the software is free for all its users. This General Public License applies to most of the Free Software Foundation's software and to any other program whose authors commit to using it. (Some other Free Software Foundation software is covered by the GNU Library General Public License instead.) You can apply it to your programs, too.

When we speak of free software, we are referring to freedom, not price. Our General Public Licenses are designed to make sure that you have the freedom to distribute copies of free software (and charge for this service if you wish), that you receive source code or can get it if you want it, that you can change the software or use pieces of it in new free programs; and that you know you can do these things.

To protect your rights, we need to make restrictions that forbid anyone to deny you these rights or to ask you to surrender the rights. These restrictions translate to certain responsibilities for you if you distribute copies of the software, or if you modify it.

For example, if you distribute copies of such a program, whether gratis or for a fee, you must give the recipients all the rights that you have. You must make sure that they, too, receive or can get the source code. And you must show them these terms so they know their rights.

We protect your rights with two steps: (1) copyright the software, and (2) offer you this license which gives you legal permission to copy, distribute and/or modify the software.

Also, for each author's protection and ours, we want to make certain that everyone understands that there is no warranty for this free software. If the software is modified by someone else and passed on, we want its recipients to know that what they have is not the original, so that any problems introduced by others will not reflect on the original authors' reputations.

Finally, any free program is threatened constantly by software patents. We wish to avoid the danger that redistributors of a free program will individually obtain patent licenses, in effect making the program proprietary. To prevent this, we have made it clear that any patent must be licensed for everyone's free use or not licensed at all.

The precise terms and conditions for copying, distribution and modification follow.

  1. This License applies to any program or other work which contains a notice placed by the copyright holder saying it may be distributed under the terms of this General Public License. The "Program", below, refers to any such program or work, and a "work based on the Program" means either the Program or any derivative work under copyright law: that is to say, a work containing the Program or a portion of it, either verbatim or with modifications and/or translated into another language. (Hereinafter, translation is included without limitation in the term "modification".) Each licensee is addressed as "you".

    Activities other than copying, distribution and modification are not covered by this License; they are outside its scope. The act of running the Program is not restricted, and the output from the Program is covered only if its contents constitute a work based on the Program (independent of having been made by running the Program). Whether that is true depends on what the Program does.

  2. You may copy and distribute verbatim copies of the Program's source code as you receive it, in any medium, provided that you conspicuously and appropriately publish on each copy an appropriate copyright notice and disclaimer of warranty; keep intact all the notices that refer to this License and to the absence of any warranty; and give any other recipients of the Program a copy of this License along with the Program.

    You may charge a fee for the physical act of transferring a copy, and you may at your option offer warranty protection in exchange for a fee.

  3. You may modify your copy or copies of the Program or any portion of it, thus forming a work based on the Program, and copy and distribute such modifications or work under the terms of Section 1 above, provided that you also meet all of these conditions:
    1. You must cause the modified files to carry prominent notices stating that you changed the files and the date of any change.
    2. You must cause any work that you distribute or publish, that in whole or in part contains or is derived from the Program or any part thereof, to be licensed as a whole at no charge to all third parties under the terms of this License.
    3. If the modified program normally reads commands interactively when run, you must cause it, when started running for such interactive use in the most ordinary way, to print or display an announcement including an appropriate copyright notice and a notice that there is no warranty (or else, saying that you provide a warranty) and that users may redistribute the program under these conditions, and telling the user how to view a copy of this License. (Exception: if the Program itself is interactive but does not normally print such an announcement, your work based on the Program is not required to print an announcement.)

    These requirements apply to the modified work as a whole. If identifiable sections of that work are not derived from the Program, and can be reasonably considered independent and separate works in themselves, then this License, and its terms, do not apply to those sections when you distribute them as separate works. But when you distribute the same sections as part of a whole which is a work based on the Program, the distribution of the whole must be on the terms of this License, whose permissions for other licensees extend to the entire whole, and thus to each and every part regardless of who wrote it.

    Thus, it is not the intent of this section to claim rights or contest your rights to work written entirely by you; rather, the intent is to exercise the right to control the distribution of derivative or collective works based on the Program.

    In addition, mere aggregation of another work not based on the Program with the Program (or with a work based on the Program) on a volume of a storage or distribution medium does not bring the other work under the scope of this License.

  4. You may copy and distribute the Program (or a work based on it, under Section 2) in object code or executable form under the terms of Sections 1 and 2 above provided that you also do one of the following:
    1. Accompany it with the complete corresponding machine-readable source code, which must be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or,
    2. Accompany it with a written offer, valid for at least three years, to give any third party, for a charge no more than your cost of physically performing source distribution, a complete machine-readable copy of the corresponding source code, to be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or,
    3. Accompany it with the information you received as to the offer to distribute corresponding source code. (This alternative is allowed only for noncommercial distribution and only if you received the program in object code or executable form with such an offer, in accord with Subsection b above.)

    The source code for a work means the preferred form of the work for making modifications to it. For an executable work, complete source code means all the source code for all modules it contains, plus any associated interface definition files, plus the scripts used to control compilation and installation of the executable. However, as a special exception, the source code distributed need not include anything that is normally distributed (in either source or binary form) with the major components (compiler, kernel, and so on) of the operating system on which the executable runs, unless that component itself accompanies the executable.

    If distribution of executable or object code is made by offering access to copy from a designated place, then offering equivalent access to copy the source code from the same place counts as distribution of the source code, even though third parties are not compelled to copy the source along with the object code.

  5. You may not copy, modify, sublicense, or distribute the Program except as expressly provided under this License. Any attempt otherwise to copy, modify, sublicense or distribute the Program is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance.
  6. You are not required to accept this License, since you have not signed it. However, nothing else grants you permission to modify or distribute the Program or its derivative works. These actions are prohibited by law if you do not accept this License. Therefore, by modifying or distributing the Program (or any work based on the Program), you indicate your acceptance of this License to do so, and all its terms and conditions for copying, distributing or modifying the Program or works based on it.
  7. Each time you redistribute the Program (or any work based on the Program), the recipient automatically receives a license from the original licensor to copy, distribute or modify the Program subject to these terms and conditions. You may not impose any further restrictions on the recipients' exercise of the rights granted herein. You are not responsible for enforcing compliance by third parties to this License.
  8. If, as a consequence of a court judgment or allegation of patent infringement or for any other reason (not limited to patent issues), conditions are imposed on you (whether by court order, agreement or otherwise) that contradict the conditions of this License, they do not excuse you from the conditions of this License. If you cannot distribute so as to satisfy simultaneously your obligations under this License and any other pertinent obligations, then as a consequence you may not distribute the Program at all. For example, if a patent license would not permit royalty-free redistribution of the Program by all those who receive copies directly or indirectly through you, then the only way you could satisfy both it and this License would be to refrain entirely from distribution of the Program.

    If any portion of this section is held invalid or unenforceable under any particular circumstance, the balance of the section is intended to apply and the section as a whole is intended to apply in other circumstances.

    It is not the purpose of this section to induce you to infringe any patents or other property right claims or to contest validity of any such claims; this section has the sole purpose of protecting the integrity of the free software distribution system, which is implemented by public license practices. Many people have made generous contributions to the wide range of software distributed through that system in reliance on consistent application of that system; it is up to the author/donor to decide if he or she is willing to distribute software through any other system and a licensee cannot impose that choice.

    This section is intended to make thoroughly clear what is believed to be a consequence of the rest of this License.

  9. If the distribution and/or use of the Program is restricted in certain countries either by patents or by copyrighted interfaces, the original copyright holder who places the Program under this License may add an explicit geographical distribution limitation excluding those countries, so that distribution is permitted only in or among countries not thus excluded. In such case, this License incorporates the limitation as if written in the body of this License.
  10. The Free Software Foundation may publish revised and/or new versions of the General Public License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns.

    Each version is given a distinguishing version number. If the Program specifies a version number of this License which applies to it and "any later version", you have the option of following the terms and conditions either of that version or of any later version published by the Free Software Foundation. If the Program does not specify a version number of this License, you may choose any version ever published by the Free Software Foundation.

  11. If you wish to incorporate parts of the Program into other free programs whose distribution conditions are different, write to the author to ask for permission. For software which is copyrighted by the Free Software Foundation, write to the Free Software Foundation; we sometimes make exceptions for this. Our decision will be guided by the two goals of preserving the free status of all derivatives of our free software and of promoting the sharing and reuse of software generally.
  12. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.
  13. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.

How to Apply These Terms to Your New Programs

If you develop a new program, and you want it to be of the greatest possible use to the public, the best way to achieve this is to make it free software which everyone can redistribute and change under these terms.

To do so, attach the following notices to the program. It is safest to attach them to the start of each source file to most effectively convey the exclusion of warranty; and each file should have at least the "copyright" line and a pointer to where the full notice is found. 

one line to give the program's name and an idea of what it does.
Copyright (C) 19yy  name of author

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.

Also add information on how to contact you by electronic and paper mail.

If the program is interactive, make it output a short notice like this when it starts in an interactive mode: 

Gnomovision version 69, Copyright (C) 19yy name of author
Gnomovision comes with ABSOLUTELY NO WARRANTY; for details
type `show w'.  This is free software, and you are welcome
to redistribute it under certain conditions; type `show c'
for details.

The hypothetical commands show w and show c should show the appropriate parts of the General Public License. Of course, the commands you use may be called something other than show w and show c; they could even be mouse-clicks or menu items--whatever suits your program.

You should also get your employer (if you work as a programmer) or your school, if any, to sign a "copyright disclaimer" for the program, if necessary. Here is a sample; alter the names: 

Yoyodyne, Inc., hereby disclaims all copyright
interest in the program `Gnomovision'
(which makes passes at compilers) written
by James Hacker.

signature of Ty Coon, 1 April 1989
Ty Coon, President of Vice

This General Public License does not permit incorporating your program into proprietary programs. If your program is a subroutine library, you may consider it more useful to permit linking proprietary applications with the library. If this is what you want to do, use the GNU Library General Public License instead of this License.

Node:GFDL, Next:, Previous:GPL, Up:Copying

GNU FREE DOCUMENTATION LICENSE

Version 1.1, March 2000

Copyright (C) 2000  Free Software Foundation, Inc.
59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

Everyone is permitted to copy and distribute verbatim copies
of this license document, but changing it is not allowed.

  1. PREAMBLE

    The purpose of this License is to make a manual, textbook, or other written document "free" in the sense of freedom: to assure everyone the effective freedom to copy and redistribute it, with or without modifying it, either commercially or noncommercially. Secondarily, this License preserves for the author and publisher a way to get credit for their work, while not being considered responsible for modifications made by others.

    This License is a kind of "copyleft", which means that derivative works of the document must themselves be free in the same sense. It complements the GNU General Public License, which is a copyleft license designed for free software.

    We have designed this License in order to use it for manuals for free software, because free software needs free documentation: a free program should come with manuals providing the same freedoms that the software does. But this License is not limited to software manuals; it can be used for any textual work, regardless of subject matter or whether it is published as a printed book. We recommend this License principally for works whose purpose is instruction or reference.

  2. APPLICABILITY AND DEFINITIONS

    This License applies to any manual or other work that contains a notice placed by the copyright holder saying it can be distributed under the terms of this License. The "Document", below, refers to any such manual or work. Any member of the public is a licensee, and is addressed as "you".

    A "Modified Version" of the Document means any work containing the Document or a portion of it, either copied verbatim, or with modifications and/or translated into another language.

    A "Secondary Section" is a named appendix or a front-matter section of the Document that deals exclusively with the relationship of the publishers or authors of the Document to the Document's overall subject (or to related matters) and contains nothing that could fall directly within that overall subject. (For example, if the Document is in part a textbook of mathematics, a Secondary Section may not explain any mathematics.) The relationship could be a matter of historical connection with the subject or with related matters, or of legal, commercial, philosophical, ethical or political position regarding them.

    The "Invariant Sections" are certain Secondary Sections whose titles are designated, as being those of Invariant Sections, in the notice that says that the Document is released under this License.

    The "Cover Texts" are certain short passages of text that are listed, as Front-Cover Texts or Back-Cover Texts, in the notice that says that the Document is released under this License.

    A "Transparent" copy of the Document means a machine-readable copy, represented in a format whose specification is available to the general public, whose contents can be viewed and edited directly and straightforwardly with generic text editors or (for images composed of pixels) generic paint programs or (for drawings) some widely available drawing editor, and that is suitable for input to text formatters or for automatic translation to a variety of formats suitable for input to text formatters. A copy made in an otherwise Transparent file format whose markup has been designed to thwart or discourage subsequent modification by readers is not Transparent. A copy that is not "Transparent" is called "Opaque".

    Examples of suitable formats for Transparent copies include plain ASCII without markup, Texinfo input format, LaTeX input format, SGML or XML using a publicly available DTD, and standard-conforming simple HTML designed for human modification. Opaque formats include PostScript, PDF, proprietary formats that can be read and edited only by proprietary word processors, SGML or XML for which the DTD and/or processing tools are not generally available, and the machine-generated HTML produced by some word processors for output purposes only.

    The "Title Page" means, for a printed book, the title page itself, plus such following pages as are needed to hold, legibly, the material this License requires to appear in the title page. For works in formats which do not have any title page as such, "Title Page" means the text near the most prominent appearance of the work's title, preceding the beginning of the body of the text.

  3. VERBATIM COPYING

    You may copy and distribute the Document in any medium, either commercially or noncommercially, provided that this License, the copyright notices, and the license notice saying this License applies to the Document are reproduced in all copies, and that you add no other conditions whatsoever to those of this License. You may not use technical measures to obstruct or control the reading or further copying of the copies you make or distribute. However, you may accept compensation in exchange for copies. If you distribute a large enough number of copies you must also follow the conditions in section 3.

    You may also lend copies, under the same conditions stated above, and you may publicly display copies.

  4. COPYING IN QUANTITY

    If you publish printed copies of the Document numbering more than 100, and the Document's license notice requires Cover Texts, you must enclose the copies in covers that carry, clearly and legibly, all these Cover Texts: Front-Cover Texts on the front cover, and Back-Cover Texts on the back cover. Both covers must also clearly and legibly identify you as the publisher of these copies. The front cover must present the full title with all words of the title equally prominent and visible. You may add other material on the covers in addition. Copying with changes limited to the covers, as long as they preserve the title of the Document and satisfy these conditions, can be treated as verbatim copying in other respects.

    If the required texts for either cover are too voluminous to fit legibly, you should put the first ones listed (as many as fit reasonably) on the actual cover, and continue the rest onto adjacent pages.

    If you publish or distribute Opaque copies of the Document numbering more than 100, you must either include a machine-readable Transparent copy along with each Opaque copy, or state in or with each Opaque copy a publicly-accessible computer-network location containing a complete Transparent copy of the Document, free of added material, which the general network-using public has access to download anonymously at no charge using public-standard network protocols. If you use the latter option, you must take reasonably prudent steps, when you begin distribution of Opaque copies in quantity, to ensure that this Transparent copy will remain thus accessible at the stated location until at least one year after the last time you distribute an Opaque copy (directly or through your agents or retailers) of that edition to the public.

    It is requested, but not required, that you contact the authors of the Document well before redistributing any large number of copies, to give them a chance to provide you with an updated version of the Document.

  5. MODIFICATIONS

    You may copy and distribute a Modified Version of the Document under the conditions of sections 2 and 3 above, provided that you release the Modified Version under precisely this License, with the Modified Version filling the role of the Document, thus licensing distribution and modification of the Modified Version to whoever possesses a copy of it. In addition, you must do these things in the Modified Version:

    1. Use in the Title Page (and on the covers, if any) a title distinct from that of the Document, and from those of previous versions (which should, if there were any, be listed in the History section of the Document). You may use the same title as a previous version if the original publisher of that version gives permission.
    2. List on the Title Page, as authors, one or more persons or entities responsible for authorship of the modifications in the Modified Version, together with at least five of the principal authors of the Document (all of its principal authors, if it has less than five).
    3. State on the Title page the name of the publisher of the Modified Version, as the publisher.
    4. Preserve all the copyright notices of the Document.
    5. Add an appropriate copyright notice for your modifications adjacent to the other copyright notices.
    6. Include, immediately after the copyright notices, a license notice giving the public permission to use the Modified Version under the terms of this License, in the form shown in the Addendum below.
    7. Preserve in that license notice the full lists of Invariant Sections and required Cover Texts given in the Document's license notice.
    8. Include an unaltered copy of this License.
    9. Preserve the section entitled "History", and its title, and add to it an item stating at least the title, year, new authors, and publisher of the Modified Version as given on the Title Page. If there is no section entitled "History" in the Document, create one stating the title, year, authors, and publisher of the Document as given on its Title Page, then add an item describing the Modified Version as stated in the previous sentence.
    10. Preserve the network location, if any, given in the Document for public access to a Transparent copy of the Document, and likewise the network locations given in the Document for previous versions it was based on. These may be placed in the "History" section. You may omit a network location for a work that was published at least four years before the Document itself, or if the original publisher of the version it refers to gives permission.
    11. In any section entitled "Acknowledgements" or "Dedications", preserve the section's title, and preserve in the section all the substance and tone of each of the contributor acknowledgements and/or dedications given therein.
    12. Preserve all the Invariant Sections of the Document, unaltered in their text and in their titles. Section numbers or the equivalent are not considered part of the section titles.
    13. Delete any section entitled "Endorsements". Such a section may not be included in the Modified Version.
    14. Do not retitle any existing section as "Endorsements" or to conflict in title with any Invariant Section.

    If the Modified Version includes new front-matter sections or appendices that qualify as Secondary Sections and contain no material copied from the Document, you may at your option designate some or all of these sections as invariant. To do this, add their titles to the list of Invariant Sections in the Modified Version's license notice. These titles must be distinct from any other section titles.

    You may add a section entitled "Endorsements", provided it contains nothing but endorsements of your Modified Version by various parties-for example, statements of peer review or that the text has been approved by an organization as the authoritative definition of a standard.

    You may add a passage of up to five words as a Front-Cover Text, and a passage of up to 25 words as a Back-Cover Text, to the end of the list of Cover Texts in the Modified Version. Only one passage of Front-Cover Text and one of Back-Cover Text may be added by (or through arrangements made by) any one entity. If the Document already includes a cover text for the same cover, previously added by you or by arrangement made by the same entity you are acting on behalf of, you may not add another; but you may replace the old one, on explicit permission from the previous publisher that added the old one.

    The author(s) and publisher(s) of the Document do not by this License give permission to use their names for publicity for or to assert or imply endorsement of any Modified Version.

  6. COMBINING DOCUMENTS

    You may combine the Document with other documents released under this License, under the terms defined in section 4 above for modified versions, provided that you include in the combination all of the Invariant Sections of all of the original documents, unmodified, and list them all as Invariant Sections of your combined work in its license notice.

    The combined work need only contain one copy of this License, and multiple identical Invariant Sections may be replaced with a single copy. If there are multiple Invariant Sections with the same name but different contents, make the title of each such section unique by adding at the end of it, in parentheses, the name of the original author or publisher of that section if known, or else a unique number. Make the same adjustment to the section titles in the list of Invariant Sections in the license notice of the combined work.

    In the combination, you must combine any sections entitled "History" in the various original documents, forming one section entitled "History"; likewise combine any sections entitled "Acknowledgements", and any sections entitled "Dedications". You must delete all sections entitled "Endorsements."

  7. COLLECTIONS OF DOCUMENTS

    You may make a collection consisting of the Document and other documents released under this License, and replace the individual copies of this License in the various documents with a single copy that is included in the collection, provided that you follow the rules of this License for verbatim copying of each of the documents in all other respects.

    You may extract a single document from such a collection, and distribute it individually under this License, provided you insert a copy of this License into the extracted document, and follow this License in all other respects regarding verbatim copying of that document.

  8. AGGREGATION WITH INDEPENDENT WORKS

    A compilation of the Document or its derivatives with other separate and independent documents or works, in or on a volume of a storage or distribution medium, does not as a whole count as a Modified Version of the Document, provided no compilation copyright is claimed for the compilation. Such a compilation is called an "aggregate", and this License does not apply to the other self-contained works thus compiled with the Document, on account of their being thus compiled, if they are not themselves derivative works of the Document.

    If the Cover Text requirement of section 3 is applicable to these copies of the Document, then if the Document is less than one quarter of the entire aggregate, the Document's Cover Texts may be placed on covers that surround only the Document within the aggregate. Otherwise they must appear on covers around the whole aggregate.

  9. TRANSLATION

    Translation is considered a kind of modification, so you may distribute translations of the Document under the terms of section 4. Replacing Invariant Sections with translations requires special permission from their copyright holders, but you may include translations of some or all Invariant Sections in addition to the original versions of these Invariant Sections. You may include a translation of this License provided that you also include the original English version of this License. In case of a disagreement between the translation and the original English version of this License, the original English version will prevail.

  10. TERMINATION

    You may not copy, modify, sublicense, or distribute the Document except as expressly provided for under this License. Any other attempt to copy, modify, sublicense or distribute the Document is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance.

  11. FUTURE REVISIONS OF THIS LICENSE

    The Free Software Foundation may publish new, revised versions of the GNU Free Documentation License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. See http://www.gnu.org/copyleft/.

    Each version of the License is given a distinguishing version number. If the Document specifies that a particular numbered version of this License "or any later version" applies to it, you have the option of following the terms and conditions either of that specified version or of any later version that has been published (not as a draft) by the Free Software Foundation. If the Document does not specify a version number of this License, you may choose any version ever published (not as a draft) by the Free Software Foundation.

ADDENDUM: How to use this License for your documents

To use this License in a document you have written, include a copy of the License in the document and put the following copyright and license notices just after the title page: 

  Copyright (C)  year  your name.
  Permission is granted to copy, distribute and/or modify this document
  under the terms of the GNU Free Documentation License, Version 1.1
  or any later version published by the Free Software Foundation;
  with the Invariant Sections being list their titles, with the
  Front-Cover Texts being list, and with the Back-Cover Texts being list.
  A copy of the license is included in the section entitled ``GNU
  Free Documentation License''.

If you have no Invariant Sections, write "with no Invariant Sections" instead of saying which ones are invariant. If you have no Front-Cover Texts, write "no Front-Cover Texts" instead of "Front-Cover Texts being list"; likewise for Back-Cover Texts.

If your document contains nontrivial examples of program code, we recommend releasing these examples in parallel under your choice of free software license, such as the GNU General Public License, to permit their use in free software.

Node:GTP License, Previous:GFDL, Up:Copying

The Go Text Protocol License

In order to facilitate the use of the Go Text Protocol, the two files gtp.c and gtp.h are licensed under the following terms.

Copyright 2001 by the Free Software Foundation.

Permission is hereby granted, free of charge, to any person obtaining a copy of this file gtp.x, to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, provided that the above copyright notice(s) and this permission notice appear in all copies of the Software and that both the above copyright notice(s) and this permission notice appear in supporting documentation.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

Except as contained in this notice, the name of a copyright holder shall not be used in advertising or otherwise to promote the sale, use or other dealings in this Software without prior written authorization of the copyright holder.

Node:Concept Index, Next:, Previous:Copying, Up:Top

Concept Index

Node:Functions Index, Previous:Concept Index, Up:Top

Functions Index

Table of Contents