Programmer's Introduction
GNU Go Internals
utils.c and printutils.c
Appendices
Indices
This is GNU Go 3.2, a Go program. Development versions of GNU Go may be
found at <http://www.gnu.org/software/gnugo/devel.html>. Contact
us at gnugo@gnu.org if you are interested in helping.
The challenge of Computer Go is not to beat the computer, but to program the computer.
In Computer Chess, strong programs are capable of playing at the highest level, even challenging such a player as Garry Kasparov. No Go program even as strong as amateur shodan exists. The challenge is to write such a program.
To be sure, existing Go programs are strong enough to be interesting as opponents, and the hope exists that some day soon a truly strong program can be written.
GNU Go is getting stronger. For one thing, we've paid a lot of attention to life and death. GNU Go 3.0 can consistently give GNU Go 2.6 a four stone handicap. In a four stone game against GNU Go 2.6, GNU Go 3.0 very often kills a group. GNU Go 3.2 is even stronger than 3.0.
Until now, Go programs have always been distributed as binaries only. The algorithms in these proprietary programs are secret. No-one but the programmer can examine them to admire or criticise. As a consequence, anyone who wished to work on a Go program usually had to start from scratch. This may be one reason that Go programs have not reached a higher level of play.
Unlike most Go programs, GNU Go is Free Software. Its algorithms and source code are open and documented. They are free for any one to inspect or enhance. We hope this freedom will give GNU Go's descendents a certain competetive advantage.
Here is GNU Go's Manual. There are doubtless inaccuracies. The ultimate documentation is in the commented source code itself.
The first three chapters of this manual are for the general user. Chapter 3 is the User's Guide. The rest of the book is for programmers, or persons curious about how GNU Go works. Chapter 4 is a general overview of the engine. Chapter 5 introduces various tools for looking into the GNU Go engine and finding out why it makes a certain move, and Chapters 6-7 form a general programmer's reference to the GNU Go API. The remaining chapters are more detailed explorations of different aspects of GNU Go's internals.
Copyright 1999, 2000, 2001, 2002 by the Free Software Foundation except as noted below.
All files are under the GNU General Public License (see GPL),
except gmp.c, gmp.h, gtp.c, gtp.h, the files
interface/html/* and win/makefile.win.
The files gtp.c and gtp.h are copyright the Free Software
Foundation. In the interests of promoting the Go Text Protocol these
two files are licensed under a less restrictive license than the GPL
and are free for unrestricted use (see GTP License).
The two files gmp.c and gmp.h were placed in the public domain
by William Shubert, their author, and are free for unrestricted use.
The files interface/html/* are not part of GNU Go but are a separate
program and are included in the distribution for the convenience of anyone
looking for a CGI interface to GNU Go. They were placed in the public domain
by their author, Douglas Ridgway, and are free for unrestricted use.
The files regression/games/golois/*sgf are copyright Tristan
Cazenave and are included with his permission.
The SGF files in regression/games/handtalk/ are copyright Jessie Annala
and are used with permission.
The SGF files in regression/games/mertin13x13/ are copyright Stefan
Mertin and are used with permission.
The remaining SGF files are either copyright by the FSF or are in the public domain.
GNU Go maintainers are Daniel Bump and Gunnar Farnebäck. GNU Go authors (in chronological order of contribution) are Man Li, Daniel Bump, David Denholm, Gunnar Farnebäck, Nils Lohner, Jerome Dumonteil, Tommy Thorn, Nicklas Ekstrand, Inge Wallin, Thomas Traber, Douglas Ridgway, Teun Burgers, Tanguy Urvoy, Thien-Thi Nguyen, Heikki Levanto, Mark Vytlacil, Adriaan van Kessel, Wolfgang Manner, Jens Yllman, Don Dailey, Måns Ullerstam, Arend Bayer and Trevor Morris.
We would like to thank Arthur Britto, Tim Hunt, Piotr Lakomy, Paul Leonard, Jean-Louis Martineau, Andreas Roever and Pierce Wetter for helpful correspondence. Thanks to everyone who stepped on a bug (and sent us a report)!
Thanks to Gary Boos, Peter Gucwa, Martijn van der Kooij, Michael Margolis, Trevor Morris, Måns Ullerstam, Don Wagner and Yin Zheng for help with Visual C++.
Thanks to Alan Crossman, Stephan Somogyi, Pierce Wetter and Mathias Wagner for help with Macintosh. And thanks to Marco Scheurer and Shigeru Mabuchi for helping us find various problems.
Thanks to Jessie Annala for the Handtalk games.
Special thanks to Ebba Berggren for creating our logo, based on a
design by Tanguy Urvoy and comments by Alan Crossman. The old
GNU Go logo was adapted from Jamal Hannah's typing GNU:
<http://www.gnu.org/graphics/atypinggnu.html>.
Both logos can be found in doc/newlogo.* and doc/oldlogo.*.
We would like to thank Stuart Cracraft, Richard Stallman and Man Lung Li for their interest in making this program a part of GNU, William Shubert for writing CGoban and gmp.c, Rene Grothmann for Jago and Erik van Riper and his collaborators for NNGS.
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.
These issues are of tactical nature, i.e. they concern some specific feature or the infrastructure of the engine. Some of these are quiet small, maybe doable in a day for an experienced GNU Go programmer. They might also be useful project to start with for a new project member. Some of them are bigger and demand a deeper knowledge of the engine internals. The issues are presented here in an approximate order of perceived difficulty.
These issues are strategic in nature. They will help us to improve the playing strength of the program and/or enhance certain aspects of it.
These are some ideas that have been floated on the mailing list. Some of them are down-to-earth, and some are just blue sky ramblings. They are presented here for inspiration.
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/>.
Untar the sources, change to the directory gnugo-3.2. Now do:
./configure [OPTIONS] make
Several configure options will be explained in detail in the next section (see Configure Options). You do not need to set these unless you are dissatisfied with GNU Go's performance or wish to vary the experimental options.
As an example,
./configure --enable-experimental-semeai --enable-owl-threats
turns on two experimental options.
You have now made a binary called interface/gnugo. Now
(running as root) type
make install
to install gnugo in /usr/local/bin.
There are different methods of using GNU Go. You may run it from the command line by just typing:
gnugo
but it is nicer to run it using CGoban 1 (under X-Windows) or Jago (on any platform with a Java runtime environment).
You can get the most recent version of CGoban 1 from Bill Shubert's web site:
<http://www.igoweb.org/~wms/comp/cgoban/index.html> The CGoban version
number MUST be 1.9.1 at least or it won't work. CGoban 2 will not work.
See CGoban, for instructions on how to run GNU Go from Cgoban, or See Jago, for Jago.
There are three options which you should consider configuring, particularly if you are dissatisfied with GNU Go's performance.
By default, GNU Go makes a cache of 16 Megabytes in RAM for its internal use. The cache is used to store intermediate results during its analysis of the position.
Increasing the cache size will often give a modest speed improvement. If your system has lots of RAM, consider increasing the cache size. But if the cache is too large, swapping will occur, causing hard drive accesses and degrading performance. If your hard drive seems to be running excessively your cache may be too large. On GNU/Linux systems, you may detect swapping using the program 'top'. Use the 'f' command to toggle SWAP display.
You may override the size of the default cache at compile time by running one of:
./configure --enable-cache-size=n
to set the cache size to n megabytes. For example
./configure --enable-cache-size=32
creates a cache of size 32 megabytes. If you omit this, your default
cache size will be 8 MB. You must recompile and reinstall
GNU Go after reconfiguring it by running make and
make install.
You may override the compile-time defaults by running gnugo with the
option --cache-size n, where n is the size in
megabytes of the cache you want, and --level where n is the
level desired. We will discuss setting these parameters next in detail.
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.
There are two distinct implementations of the pattern matcher in GNU
Go. The DFA (Discrete Finite-state Automata) option was considered
experimental in GNU Go 3.0 but is now standard. You can disable it by
with the configure option ./configure --disable-dfa. The
option is harder to debug than the old matcher but significantly
faster (see DFA).
There are a number of experimental configure options. For example
you can ./configure --enable-experimental-semeai or
./configure --disable-experimental-semeai to turn
the experimental reading module on or off. If you want to
find out what experimental options were compiled into your
GNU Go binary you can run gnugo --options to find
out.
experimental-semeai. Use the new semeai module based on
the owl code.
experimental-influence. Use the experimental influence
module. Enabled by default.
experimental-connections. Use the experimental connection
analysis. Enabled by default.
alternate-connections. Use in conjunction with
experimental-connections. Uses an alternative implementation of
the experimental connection analysis. Enabled by default.
owl-threats. Compute owl threats. This makes GNU Go
stronger but can make the program slower. Enable this option if you have a
fast CPU.
GNU Go is being developed on Unix variants. GNU Go is easy to build and install on those platforms. GNU Go 3.2 has support for building on MS-DOS, Windows 3.x, Windows NT/2000 and Windows 95/98.
There are two approaches to building GNU Go on Microsoft platforms.
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.
The rest of this section gives more details on the various ways to compile GNU go for Microsoft platforms.
On these platforms DJGPP can be used. GNU Go installation has been tested in a DOS-Box with long filenames on Windows 95/98. GNU Go compiles out-of-the box with the DJGPP port of GCC using the standard Unix build and install procedure.
Some URLs for DJGPP:
DJGPP home page: <http://www.delorie.com/djgpp/>
DJGPP ftp archive on simtel:
<ftp://ftp.simtel.net/pub/simtelnet/gnu/djgpp/v2/>
<ftp://ftp.simtel.net/pub/simtelnet/gnu/djgpp/v2gnu/>
Once you have a working DJGPP environment and you have downloaded the gnugo source available as gnugo-3.2.tar.gz you can build the executable as follows:
tar zxvf gnugo-3.2.tar.gz
cd gnugo-3.2
./configure
make
Optionally you can download glib for DJGPP to get a working version of snprintf.
On these platforms the Cygwin environment can be installed. Recent
versions of Cygwin install very easily with the setup program available
from the cygwin homepage. <<http://sourceware.cygnus.com/cygwin/>.
GNU Go compiles out-of-the box using the standard Unix build procedure
on the Cygwin environment. After installation of cygwin and fetching
gnugo-3.2.tar.gz you can type:
tar zxvf gnugo-3.2.tar.gz cd gnugo-3.2 ./configure make
The generated executable is not a stand-alone executable: it needs cygwin1.dll that comes with the Cygwin environment. cygwin1.dll contains the emulation layer for Unix.
Cygwin Home page: <http://sourceware.cygnus.com/cygwin/>
Optionally you can use glib to get a working version of snprintf. Glib builds out of the box on cygwin.
The Cygwin environment also comes with MinGW32. This generates an executable that relies only on Microsoft DLLs. This executable is thus completely comparable to a Visual C executable and easier to distribute than the Cygwin executable. To build on cygwin an executable suitable for the win32 platform type the following at your cygwin prompt:
tar zxvf gnugo-3.2.tar.gz cd gnugo-3.2 env CC='gcc -mno-cygwin' ./configure make
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.
Notes:
msdev gnugo.dsw /make "gnugo - Win32 Release"
FILE MKPAT OPTIONS INPUT FILES
conn.c mkpat -c conn conn.db
patterns.c mkpat -b pat patterns.db, patterns2.db
apatterns.c mkpat -X attpat attack.db
dpatterns.c mkpat defpat defense.db
influence.c mkpat -c influencepat influence.db
endgame.c mkpat -b endpat endgame.db
owl_attackpat.c mkpat -b owl_attackpat owl_attackpats.db
owl_vital_apat.c mkpat -b owl_vital_apat owl_vital_apats.db
owl_defendpat.c mkpat -b owl_defendpat owl_defendpats.db
fuseki9.c mkpat -b -f fuseki9 fuseki9.db
fuseki19.c mkpat -b -f fuseki19 fuseki19.db
josekidb.c mkpat -b joseki hoshi.db, komoku.db,
sansan.db, takamoku.db
mokuhazushi.db
GNU Go does not come with its own graphical user interface. The Java client jago can be used.
To run Jago you need a Java Runtime Environment (JRE). This can
be obtained from <http://www.javasoft.com/>. This is the runtime
part of the Java Development Kit (JDK) and consists of the Java
virtual machine, Java platform core classes, and supporting files.
The Java virtual machine that comes with I.E. 5.0 works also.
Jago: <http://www.rene-grothmann.de/jago/>
gnugo --quiet --mode gmp
gnugo --help from a cygwin or DOS window for a list of
options
--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.
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.
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.
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.
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.
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:
Return or Space
Select point as the next move. An error is signalled for invalid locations. Illegal locations, on the other hand, show up in the GNUGO Console buffer.
q or Q
Quit. Both Board and Console buffers are deleted.
R
Resign.
C-l
Refresh. Includes restoring default window configuration.
M-_
Bury both Board and Console buffers (when the boss is near).
p
Pass; i.e., select no location for your move.
:
Extended command. After typing the : you can type a
command for GNU Go. The possible commands are as in See Ascii.
Jago, like CGoban is a client capable of providing GNU Go with a graphical user interface. Unlike CGoban, it does not require X-Windows, so it is an attractive alternative under Windows. You will need a Java runtime environment. Obtain Jago at
<http://www.rene-grothmann.de/jago/>
and follow the links there for the Java runtime environment.
The Go Modem Protocol (GMP) was developed by Bruce Wilcox with input from
David Fotland, Anders Kierulf and others, according to the history in
<http://www.britgo.org/tech/gmp.html>.
Any Go program should support this protocol since it is a standard. Since CGoban supports this protocol, the user interface for any Go program can be done entirely through CGoban. The programmer can concentrate on the real issues without worrying about drawing stones, resizing the board and other distracting issues.
GNU Go 3.0 introduced a new protocol, the Go Text Protocol (see GTP) which we hope can serve the functions currently used by the GMP.
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.
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/>
--help, -h
Print a help message describing the options. This will also tell you the defaults of various parameters, most importantly the level and cache size. The default values of these parameters can be set before compiling byconfigure. If you forget the defaults you can find out using--help.
--boardsize size
Set the board size
--komi num
Set the komi
--level level
GNU Go can play with different strengths and speeds. Level 10 is the default. Decreasing the level will make GNU Go faster but less accurate in its reading.
--quiet, --silent
Don't print copyright and other messages. Messages specifically
requested by other command line options, such as --trace,
are not supressed.
-l, --infile filename
Load the named SGF file. GNU Go will generate a move for the player who is about to move. If you want to override this and generate a move for the other player you may add the optioncolor <color>where <color> isblackorwhite.
--orientation n
Combine with-l. The Go board can be oriented in 8 different ways, counting reflections and rotations of the position; this option selects an orientation (default 0). The parameternis an integer between 0 and 7.
-L, --until move
Stop loading just before the indicated move is played. move can be either the move number or location.
-o, --outfile filename
Write sgf output to file
--mode mode
Force the playing mode ('ascii', 'emacs,' 'gmp' or 'gtp'). The default is ASCII, but if no terminal is detected GMP (Go Modem Protocol) will be assumed. In practice this is usually what you want, so you may never need this option.
-M, --cache-size megs
Memory in megabytes used for caching of read results. The default size is 8 unless you configure gnugo with the commandconfigure --enable-cache-size=sizebefore compiling to make size the default (see Installation). GNU Go stores results of its reading calculations in a Hash table (see Hashing). If the Hash table is filled, it is emptied and the reading continues, but some reading may have to be repeated that was done earlier, so a larger cache size will make GNU Go run faster, provided the cache is not so large that swapping occurs. Swapping may be detected on GNU/Linux machines using the programtop. However, if you have ample memory or if performance seems to be a problem you may want to increase the size of the cache using this option.
--chinese-rules
Use Chinese rules. This means that the Chinese or Area Counting is followed. It may affect the score of the game by one point in even games, more if there is a handicap (since in Chinese Counting the handicap stones count for Black).
--japanese-rules
Use Japanese Rules. This is the default unless you specify
--enable-chinese-rules as a configure option.
--copyright: Display the copyright notice
--version or -v: Print the version number
--printsgf filename:
Create an SGF file
containing a diagram of the board. Useful with -L to
create diagrams from games.
--options
Print which experimental configure options were compiled into the program (see Experimental Options).
--level amount
The higher the level, the deeper GNU Go reads. Level 10 is the default. If GNU Go plays too slowly on your machine, you may want to decrease it.
This single parameter --level is the best way of
choosing whether to play stronger or faster. It controls
a host of other parameters which may themselves be set
individually at the command line. The default values of
these parameters may be found by running gnugo --help.
Unless you are working on the program you probably don't
need these options. Instead, just adjust the single
variable --level. The remaining options are of
use to developers tuning the program for performance and
accuracy.
-D, --depth depth
Deep reading cutoff. When reading beyond this depth (default 16) GNU Go assumes that any string which can obtain 3 liberties is alive. Thus GNU Go can read ladders to an arbitrary depth, but will miss other types of capturing moves.
--branch-depth
This sets thebranch_depth, typically a little below thedepth. Betweenbranch_depthanddepth, attacks on strings with 3 liberties are considered but branching is inhibited, so fewer variations are considered.
-B, --backfill-depth depth
Deep reading cutoff. Beyond this depth (default 12) GNU Go will no longer try backfilling moves in its reading.
--backfill2-depth depth
Another depth controlling how deeply GNU Go looks for backfilling moves. The moves tried belowbackfill2_depthare generally more obscure and time intensive than those controlled bybackfill_depth, so this parameter has a lower default.
-F, --fourlib-depth depth
Deep reading cutoff. When reading beyond this depth (default 7) GNU Go assumes that any string which can obtain 4 liberties is alive.
-K, --ko-depth depth
Deep reading cutoff. Beyond this depth (default 8) GNU Go no longer tries very hard to analyze kos.
--branch-depth depth
Deep reading cutoff. Below this depth (default 8), GNU Go still tries to attack strings with only 3 liberties, but only tries one move at each node.
--aa_depth depth
The reading functionatari_atarilooks for combinations beginning with a series of ataris, and culminating with some string having an unexpected change in status (e.g. alive to dead or critical). This command line optio sets the parameteraa_depthwhich determines how deeply this function looks for combinations.
--superstring-depth
A superstring (see Superstrings) is an amalgamation of
tightly strings. Sometimes the best way to attack or defend a
string is by attacking or defending an element of the superstring.
Such tactics are tried below superstring_depth and this
command line option allows this parameter to be set.
The preceeding options are documented with the reading code (see Reading Basics).
--owl-branch Below this depth Owl only considers one move. Default 8.
--owl-reading Below this depth Owl assumes the dragon has escaped.
Default 20.
--owl-node-limit
If the number of variations exceeds this limit, Owl assumes the dragon can
make life. Default 1000. We caution the user that increasing
owl_node_limit does not necessarily increase the strength of the
program.
--color color
Choose your color ('black' or 'white').
--handicap number
Choose the number of handicap stones (0-9)
--replay color
Replay all moves in a game for either or both colors. If used with the-ooption the game record is annotated with move values. This option requires-l filename. The color can be:When the move found by genmove differs from the move in the sgf file the values of both moves are reported thus:
- white: replay white moves only
- black: replay black moves only
- both: replay all moves
Move 13 (white): GNU Go plays C6 (20.60) - Game move F4 (20.60)This option is useful if one wants to confirm that a change such as a speedup or other optimization has not affected the behavior of the engine. Note that when several moves have the same top value (or nearly equal) the move generated is not deterministic (though it can be made deterministic by starting with the same random seed). Thus a few deviations from the move in the sgf file are to be expected. Only if the two reported values differ should we conclude that the engine plays differently from the engine which generated the sgf file. See Regression.
-a, --allpats
Test all patterns, even those smaller in value than the largest move
found so far. This should never affect GNU Go's final move, and it
will make it run slower. However this can be very useful when "tuning"
GNU Go. It causes both the traces and the output file (-o) to
be more informative.
-T, --printboard: colored display of dragons.
Use rxvt, xterm or Linux Console. (see Colored Display)
-E: colored display of eye spaces
Use rxvt, xterm or Linux Console. (see Colored Display)
-d, --debug level
Produce debugging output. The debug level is given in hexadecimal, using the bits defined in the following table fromengine/gnugo.h. A list of these may be produced using--debug-flags. Here they are in hexadecimal:DEBUG_INFLUENCE 0x0001 DEBUG_EYES 0x0002 DEBUG_OWL 0x0004 DEBUG_ESCAPE 0x0008 DEBUG_MATCHER 0x0010 DEBUG_DRAGONS 0x0020 DEBUG_SEMEAI 0x0040 DEBUG_LOADSGF 0x0080 DEBUG_HELPER 0x0100 DEBUG_READING 0x0200 DEBUG_WORMS 0x0400 DEBUG_MOVE_REASONS 0x0800 DEBUG_OWL_PERFORMANCE 0x1000 DEBUG_LIFE 0x2000 DEBUG_FILLLIB 0x4000 DEBUG_READING_PERFORMANCE 0x8000 DEBUG_SCORING 0x010000 DEBUG_AFTERMATH 0x020000 DEBUG_ATARI_ATARI 0x040000 DEBUG_READING_CACHE 0x080000 DEBUG_TERRITORY 0x100000 DEBUG_OWL_PERSISTENT_CACHE 0X200000These debug flags are additive. If you want to turn on both dragon and worm debugging you can use
-d0x420.
-H, --hash level
hash (see engine/gnugo.h for bits).
-w, --worms
Print more information about worm data.
-m, --moyo level
moyo debugging, show moyo board. The level is fully documented elsewhere (see Influential Display).
-b, --benchmark number
benchmarking mode - can be used with -l.
-S, --statistics
Print statistics (for debugging purposes).
-t, --trace
Print debugging information. Use twice for more detail.
-r, --seed seed
Set random number seed. This can be used to guarantee that GNU Go will make
the same decisions on multiple runs through the same game. If seed is
zero, GNU Go will play a different game each time.
--decide-string location
Invoke the tactical reading code (see Tactical Reading to decide
whether the string at location can be captured, and if so, whether it
can be defended. If used with -o, this will produce a variation tree
in SGF.
--decide-dragon location
Invoke the owl code (see The Owl Code) to decide whether the dragon at
location can be captured, and whether it can be defended. If used with
-o, this will produce a variation tree in SGF.
--score method
Requires-l. method can be "end", "last", "aftermath" or a move. "end" and "aftermath" are appropriate when the game is complete, or nearly so, and both try to supply an accurate final score. The other options may be used to get an estimate during the middle of the game. Any of these options may be combined with--chinese-ruleif you want to use Chinese (Area) counting.
- last
load the sgf file up to the last move, then estimate territory using the Bouzy 5/21 algorithm (see Moyo).- end
finish the game by selfplaying from the end of the file until two passes, then estimate territory using the Bouzy 5/21 algorithm (see Moyo).- aftermath
finish the game by selfplaying from the end of the file until two passes, then estimate territory using the most accurate scoring algorithm available. Slower than--score last, and while these algorithms usually agree, if they differ,--score aftermathis most likely to be correct.- move, e.g.
--score J17load file until move is reached and estimate territorial balance using the Bouzy 5/21 algorithm. The--score endand--score aftermathoptions are only useful at or near the end of the game, so if you want an estimate of the score in the middle, use this method.
--printsgf output file
load SGF file, output final position (requires-l) as another SGF file. Illegal moves are indicated with the privateILproperty. This property is not used in the FF4 SGF specification, so we are free to preempt it. This feature is used in the CGI interface ininterface/html/gg.cgi.
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.
examine_position() does.
genmove().
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.
GNU Go represents the board in a one-dimensional array called
board. For some purposes a two dimensional indexing of the
board by parameters (i,j) might be used.
The board array includes out-of-board markers around the
board. To make the relation to the old two-dimensional board
representation clear, this figure shows how the 1D indices correspond
to the 2D indices when MAX_BOARD is 7.
j -1 0 1 2 3 4 5 6 i +---------------------------------- -1| 0 1 2 3 4 5 6 7 0| 8 9 10 11 12 13 14 15 1| 16 17 18 19 20 21 22 23 2| 24 25 26 27 28 29 30 31 3| 32 33 34 35 36 37 38 39 4| 40 41 42 43 44 45 46 47 5| 48 49 50 51 52 53 54 55 6| 56 57 58 59 60 61 62 63 7| 64 65 66 67 68 69 70 71 72
To convert between a 1D index pos and a 2D index (i,j),
the macros POS, I, and J are provided, defined as
below:
#define POS(i, j) ((MAX_BOARD + 2) + (i) * (MAX_BOARD + 1) + (j)) #define I(pos) ((pos) / (MAX_BOARD + 1) - 1) #define J(pos) ((pos) % (MAX_BOARD + 1) - 1)
All 1D indices not corresponding to points on the board have the out
of board marker value GRAY. Thus if board_size and
MAX_BOARD both are 7, this looks like
j -1 0 1 2 3 4 5 6 i +---------------------------------- -1| # # # # # # # # 0| # . . . . . . . 1| # . . . . . . . 2| # . . . . . . . 3| # . . . . . . . 4| # . . . . . . . 5| # . . . . . . . 6| # . . . . . . . 7| # # # # # # # # #
The indices marked # have value GRAY.
If MAX_BOARD is 7 and board_size is only 5:
j -1 0 1 2 3 4 5 6 i +---------------------------------- -1| # # # # # # # # 0| # . . . . . # # 1| # . . . . . # # 2| # . . . . . # # 3| # . . . . . # # 4| # . . . . . # # 5| # # # # # # # # 6| # # # # # # # # 7| # # # # # # # # #
Navigation on the board is done by the SOUTH, WEST,
NORTH, and EAST macros,
#define NS (MAX_BOARD + 1) #define WE 1 #define SOUTH(pos) ((pos) + NS) #define WEST(pos) ((pos) - 1) #define NORTH(pos) ((pos) - NS) #define EAST(pos) ((pos) + 1)
There are also shorthand macros SW, NW, NE,
SE, SS, WW, NN, EE for two step
movements.
Any movement from a point on the board to an adjacent or diagonal vertex is guaranteed to produce a valid index into the board array, and the color found is GRAY if it is not on the board. To do explicit tests for out of board there are two macros
#define ON_BOARD(pos) (board[pos] != GRAY) #define ON_BOARD1(pos) (((unsigned) (pos) < BOARDSIZE) && board[pos] != GRAY)
where the first one should be used in the algorithms and the second one is useful for assertion tests.
Important: The 2D coordinate (-1,-1), which is used for
pass and sometimes to indicate no point, maps to the 1D coordinate
0, not to -1. Instead of a plain 0, use one of the
macros NO_MOVE or PASS_MOVE.
A loop over multiple directions is straightforwardly written:
for (k = 0; k < 4; k++) {
int d = delta[k];
do_something(pos + d);
}
The following constants are useful for loops over the entire board and allocation of arrays with a 1-1 mapping to the board.
#define BOARDSIZE ((MAX_BOARD + 2) * (MAX_BOARD + 1) + 1) #define BOARDMIN (MAX_BOARD + 2) #define BOARDMAX (MAX_BOARD + 1) * (MAX_BOARD + 1)
BOARDSIZE is the actual size of the 1D board array,
BOARDMIN is the first index corresponding to a point on the
board, and BOARDMAX is one larger than the last index corresponding to
a point on the board.
Often one wants to traverse the board, carrying out some function at every vertex. Here are two possible ways of doing this:
int m, n;
for (m = 0; m < board_size; m++)
for (n = 0; n < board_size; n++) {
do_something(POS(m, n));
}
Or:
int pos;
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (ON_BOARD(pos))
do_something(pos);
}
The engine of GNU Go takes a position and a color to move and
generates the (supposedly) optimal move. This is done by the function
genmove() in engine/genmove.c.
The move generation is done in three passes:
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:
make_worms()
Collect information about all connected sets of stones
(strings) and cavities. This information is stored in
the worm[] array. (see Worms)
compute_initial_influence()
Decides which areas of the board are influenced by which
player. This function is run a second time later at
the end of make_dragons(), since GNU Go's opinion
about the safety of groups may change, and it is
important to have the influence function as accurate as
possible. see Influence
make_dragons()
Collect information about connected strings, which are called dragons. Important information here is number of eyes, life status, and connectedness between string. (see Dragons.)
A more detailed
Once we have found out all about the position it is time to generate the best move. Moves are proposed by a number of different modules called move generators. The move generators themselves do not set the values of the moves, but enumerate justifications for them, called move reasons. The valuation of the moves comes last, after all moves and their reasons have been generated.
The move generators in version 3.2 are:
fuseki()
Generate a move in the early fuseki.
semeai()
Find out if two dead groups of opposite colors are next to each other and, if so, try to kill the other group. This module will eventually be rewritten along the lines of the owl code.
shapes()
Find patterns frompatterns/patterns.dbin the current position. Each pattern is matched in each of the 8 possible orientations obtainable by rotation and reflection. If the pattern matches, a so called "constraint" may be tested which makes use of reading to determine if the pattern should be used in the current situation. Such constraints can make demands on number of liberties of strings, life and death status, and reading out ladders, etc. The patterns may call helper functions, which may be hand coded (inpatterns/helpers.c) or autogenerated.The patterns can be of a number of different classes with different goals. There are e.g. patterns which try to attack or defend groups, patterns which try to connect or cut groups, and patterns which simply try to make good shape. In addition to the large pattern database called by
shapes(), pattern matching is used by other modules for different tasks throughout the program. See Patterns, for a complete documentation of patterns.
atari_atari()
See if there are any combination threats and either propose them or defend against them.
owl_reasons()
The Owl Code (see The Owl Code) which has been run duringexamine_position), beforeowl_reasons()executes, has decided whether different groups can be attacked. The modulereview_owl_reasonsreviews the statuses of every dragon and assigns move reasons for attack and defense. Unlike the other move generation modules, this one is called fromexamine_position().
endgame_shapes()
If no move is found with a value greater than 6.0, this module matches a
set of extra patterns which are designed for the endgame. The endgame
patterns can be found in patterns/endgame.db.
revise_semeai()
If no move is found, this module changes the status of opponent groups involved in a semeai fromDEADtoUNKNOWN. After this, genmove runsshapesandendgame_shapesagain to see if a new move turns up.
fill_liberty()
Fill a common liberty. This is only used at the end of the game. If necessary a backfilling or backcapturing move is generated.
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.
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 wormunconditional_life()find_worm_attacks_and_defenses(): for each attackable worm: setworm.attackadd_attack_move()find_attack_patterns()to find a few more attacks for each defensible worm setworm.defendadd_defense_moveif point of attack is not adjacent to worm see if it defendsfind_defense_patterns()to find a few more defenses for each attackable worm try each liberty if it attacksadd_attack_moveif it defendsadd_defense_movefind 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 threatscompute_initial_influence()(see Influence)compute_influence()find_influence_patterns()at each intersectionaccumulate_influence()segment_influence()make_dragons()(see Dragons) initialize dragon data find the inessential wormsmake_domains()initialize eye datacompute_primary_domains()fill out arrays black_eye and white_eye describing eyeshapes find_cuts() for every eyespaceoriginate_eye()count_neighbors()find_connections()amalgamate dragons sharing an eyespaceinitialize_supplementary_dragon_data()find adjacent worms which can be captured (dragon lunches) find topological half eyes and false eyesmodify_eye_spaces()for each eye spacecompute_eyes()store the results in black_eye, white_eye arrays compute the genus of each dragon for each dragoncompute_escape()resegment_initial_influence()for each dragoninfluence_get_moyo_size()for each dragoncompute_dragon_status()find_neighbor_dragons()purge_persistent_owl_cache()for each dragon which seems surrounded tryowl_attack()andowl_defend()if appropriate find owl threats for each dragon set dragon.matcher_status for each dragon set dragon2.safetysemeai()revise opinion of which worms are inessential count non-dead dragons of each colorowl_reasons()(see The Owl Code)compute_initial_influence()again (see Influence)
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.0endgame_shapes()if no move found yetrevise_semeai()shapes()endgame_shapes()if still no move foundfill_liberty()if still no move found pass
The GNU Go engine is contained in two directories, engine/ and
patterns/. Code related to the user interface, reading and
writing of smart go format files, and testing are found in the
directories interface/, sgf/, and regression/. Code
borrowed from other GNU programs is contained in utils/. That
directory also includes some code developed within GNU Go which is not
go specific. Documentation is in doc/.
In this document we will describe some of the individual files comprising
the engine code in engine/ and patterns/. In interface/
we mention two files:
gmp.c
This is the Go Modem Protocol interface (courtesy of William Shubert and others). This takes care of all the details of exchanging setup and moves with Cgoban, or any other driving program recognizing the Go Modem Protocol.
main.c
This containsmain(). Thegnugotarget is thus built in theinterface/directory.
engine/In engine/ there are the following files:
aftermath.c
Contains algorithms which may be called at the end of the game to generate moves that will generate moves to settle the position, if necessary playing out a position to determine exactly the status of every group on the board, which GNU Go can get wrong, particularly if there is a seki. This module is the basis for the most accurate scoring algorithm available in GNU Go.
board.c
This file contains code for the maintenance of the board. For example it contains the important functiontrymove()which tries a move on the board, andpopgo()which removes it by popping the move stack. At the same time vital information such as the number of liberties for each string and their location is updated incrementally.
clock.c
Clock code, including code allowing GNU Go to automatically adjust its level in order to avoid losing on time in tournaments.
dragon.c
This containsmake_dragons(). This function is executed before the move-generating modulesshapes()semeai()and the other move generators but aftermake_worms. It tries to connect worms into dragons and collect important information about them, such as how many liberties each has, whether (in GNU Go's opinion) the dragon can be captured, if it lives, etc.
fuseki.c
Generates fuseki (opening) moves from a database.
filllib.c
Code to force filling of dame (backfilling if necessary) at the end of the game.
genmove.c
This file containsgenmove()and its supporting routines, particularlyexamine_position().
globals.c
This contains the principal global variables used by GNU Go.
gnugo.h
This file contains declarations forming the public interface to the engine.
hash.c and cache.c
Hashing code implementing Zobrist hashing. (see Hashing) The code inhash.cprovides a way to hash board positions into compact descriptions which can be efficiently compared. The code incache.cimplements a kind of database for storing reading results, so they can be quickly retrieved. The caching code uses the board hashes as keys to the database. They are split since these functionalities are sufficiently demarked that either file could be reimplemented without affecting the other one. Note also thatmatchpat()uses the hashing code without also using the caching code.
hash.h and cache.h
Header files forhash.candcache.c.
influence.c and influence.h.
This code determines which regions of the board are under the influence of either player. (see Influence)
liberty.h
Header file for the engine. The name "liberty" connotes freedom (see Copying).
life.c
The code in this file contains an alternative approach to life and death based on reading instead of the static approach inoptics.c. This code is experimental. It is reasonably accurate but too slow. It is activated when gnugo is invoked with the--lifeoption.
matchpat.c
This file contains the pattern matchermatchpat(), which looks for patterns at a particular board location. The actual patterns are in thepatterns/directory. The functionmatchpat()is called by every module which does pattern matching, notablyshapes.
move_reasons.c
This file contains the code which assigns values to every move after all the move reasons are gen
optics.c
This file contains the code to recognize eye shapes, documented in See Eyes.
owl.c
This file does life and death reading. The paradigm is that moves are played by both players trying to expand and shrink the eyespace until a static configuration is reached where it can be analyzed by the code inoptics.corlife.c.
printutils.c
Print utilities
reading.c
This file contains code to determine whether any given string can be attacked or defended. See Tactical Reading, for details.
score.c
Implements the Bouzy algorithms (see Moyo) and contains code for scoring the game.
semeai.c
This file contains semeai(), the module which tries to
win capturing races. This module does not work particularly
well and will eventually be replaced.
shapes.c
This file containsshapes(), the module called bygenmove()which tries to find moves which match a pattern (see Patterns).
showbord.c
This file contains showboard(), which draws an ASCII
representation of the board, depicting dragons (stones
with same letter) and status (color). This was the
primary interface in GNU Go 1.2, but is now a debugging
aid.
worm.c
This file containsmake_worms(), code which is run at the beginning of each move cycle, before the code indragon.c, to determine the attributes of every string. These attributes are things like liberties, wether the string can be captured (and how), etc
utils.c
An assortment of utilities, described in greater detail below.
patterns/The directory patterns/ contains files related to pattern matching.
Currently there are several types of patterns. A partial list:
patterns.db and patterns2.db
hoshi.db etc. which are
automatically build from the files hoshi.sgf etc. These comprise
our small Joseki library.
owl_attackpats.db, owl_defendpats.db
and owl_vital_apats.db. These generate moves for the owl
code (see The Owl Code).
conn.db (see Connections Database)
influence.db and barriers.db
(see Influence)
eyes.db (see Eyes).
The following list contains, in addition to distributed source files
some intermediate automatically generated files such as patterns.c.
These are C source files produced by "compiling" various pattern
databases, or in some cases (such as hoshi.db) themselves
automatically generated pattern databases produced by "compiling"
joseki files in Smart Go Format.
conn.db
Database of connection patterns.
conn.c
Automatically generated file, containing connection patterns in form of struct arrays, compiled bymkpatfromconn.db.
eyes.c
Automatically generated file, containing eyeshape patterns in form of struct arrays, compiled bymkpatfromeyes.db.
eyes.h
Header file for eyes.c.
eyes.db
Database of eyeshape patterns. See Eyes, for details.
helpers.c
These are helper functions to assist in evaluating moves by matchpat.
hoshi.sgf
Smart Go Format file containing 4-4 point openings
hoshi.db
Automatically generated database of 4-4 point opening
patterns, make by compiling hoshi.sgf
joseki.c
Joseki compiler, which takes a joseki file in Smart Go Format, and produces a pattern database.
komoku.sgf
Smart Go Format file containing 3-4 point openings
komoku.db
Automatically generated database of 3-4 point opening
patterns, make by compiling komoku.sgf
mkeyes.c
Pattern compiler for the eyeshape databases. This program takeseyes.dbas input and produceseyes.cas output.
mkpat.c
Pattern compiler for the move generation and connection databases. Takes the filepatterns.dbtogether with the autogenerated Joseki pattern fileshoshi.db,komoku.db,sansan.db,mokuhadzushi.db,takamoku.dband producespatterns.c, or takesconn.dband producesconn.c.
mokuhazushi.sgf
Smart Go Format file containing 5-3 point openings
mokuhazushi.db
Pattern database compiled from mokuhadzushi.sgf
sansan.sgf
Smart Go Format file containing 3-3 point openings
sansan.db
Pattern database compiled from sansan.sgf
takamoku.sgf
Smart Go Format file containing 5-4 point openings
takamoku.db
Pattern database compiled from takamoku.sgf.
patterns.c
Pattern data, compiled from patterns.db by mkpat.
patterns.h
Header file relating to the pattern databases.
patterns.db and patterns2.db
These contain pattern databases in human readable form.
Please follow the coding conventions at:
<http://www.gnu.org/prep/standards_toc.html>
Please preface every function with a brief description of its usage.
Please help to keep this Texinfo documentation up-to-date.
A function gprintf() is provided. It is a cut-down
printf, supporting only %c, %d,
%s, and without field widths, etc. It does, however,
add some useful facilities:
%m
Takes two parameters, and displays a formatted board co-ordinate.
Trace messages are automatically indented to reflect the current stack depth, so it is clear during read-ahead when it puts a move down or takes one back.
format string suppresses the indentation.
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, ...):
WhileTRACEis intended to afford an overview of what GNU Go is considering,DEBUGallows occasional in depth study of a module, usually needed when something goes wrong.flagsis one of theDEBUG_*symbols inengine/gnugo.h. TheDEBUGmacro tests to see if that bit is set in thedebugvariable, and prints the message if it is. The debug variable is set using the-dcommand-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.
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.
We have adopted the convention of putting the word FIXME in comments to denote known bugs, etc.
If you are using Emacs, you may find it fast and convenient to use
Emacs' built-in facility for navigating the source. Switch to the
root directory gnugo-3.2.x/ and execute the command:
find . -print|grep "\.[ch]$" | xargs etags
This will build a file called gnugo-3.2.x/TAGS. Now to
find any GNU Go function, type M-. and enter the
command which you wish to find, or just RET if
the cursor is at the name of the function sought.
The first time you do this you will be prompted for the location
of the TAGS table. Enter the path to gnugo-3.2.x/TAGS, and
henceforth you will be able to find any function with a minimum
of keystrokes.
In this chapter we will discuss methods of finding out how GNU Go understands a given position. These methods will be of interest to anyone working on the program, or simply curious about its workings.
In practice, most tuning of GNU Go is done in conjunction
with maintaining the regression/ directory
(see Regression).
We assume that you have a game GNU Go played saved as an sgf file, and you want to know why it made a certain move.
A quick way to find out roughly the reason for a move is to run
gnugo -l filename -t -L move number
(You may also want to add --quiet to suppress the copyright
message.) In GNU Go 3.2, the moves together with their reasons are
listed, followed by a numerical analysis of the values given to each
move.
If you are tuning (see Tuning) you may want to add the -a
option. This causes GNU Go to report all patterns matched, even ones
that cannot affect the outcome of the move. The reasons for doing
this is that you may want to modify a pattern already matched
instead of introducing a new one.
If you use the -w option, GNU Go will report the statuses of
worms and dragons around the board. This type of information is
available by different methods, however (see Debugboard,
see Colored Display).
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.
The --decide-string option is used to check the tactical reading code
(see Tactical Reading). This option takes an argument, which is a location
on the board in the usual algebraic notation (e.g.
--decide-string C17). This will tell you whether the reading code (in
engine/reading.c) believes the string can be captured, and if so,
whether it believes it can be defended, which moves it finds to attack or
defend the move, how many nodes it searched in coming to these
conclusions. Note that when GNU Go runs normally (not with
--decide-string) the points of attack and defense are
computed when make_worms() runs and cached in
worm.attack and worm.defend.
If used with an output file (-o filename)
--decide-string will produce a variation tree showing
all the variations which are considered. This is a useful way
of debugging the reading code, and also of educating yourself
with the way it works. The variation tree can be displayed
graphically using CGoban.
At each node, the comment contains some information. For example you may find a comment:
attack4-B at D12 (variation 6, hash 51180fdf) break_chain D12: 0 defend3 D12: 1 G12 (trivial extension)
This is to be interpreted as follows. The node in question
was generated by the function attack3() in engine/reading.c,
which was called on the string at D12. The data in
parentheses tell you the values of count_variations and
hashdata.hashval.
The second value ("hash") you probably will not need to know
unless you are debugging the hash code, and we will not discuss it.
But the first value ("variation") is useful when using the debugger
gdb. You can first make an output file using
the -o option, then walk through the reading with
gdb, and to coordinate the SGF file with the debugger,
display the value of count_variations. Specifically,
from the debugger you can find out where you are as follows:
(gdb) set dump_stack() B:D13 W:E12 B:E13 W:F12 B:F11 (variation 6)
If you place yourself right after the call to trymove()
which generated the move in question, then the variation number
in the SGF file should match the variation number displayed by
dump_stack(), and the move in question will be the
last move played (F11 in this example).
This displays the sequence of moves leading up to the variation
in question, and it also prints count_variations-1.
The second two lines tell you that from this node, the function
break_chain() was called at D12 and returned 0 meaning
that no way was found of rescuing the string by attacking
an element of the surrounding chain, and the function
defend3() was called also at D12 and returned 1,
meaning that the string can be defended, and that
G12 is the move that defends it. If you have trouble
finding the function calls which generate these comments,
try setting sgf_dumptree=1 and setting a breakpoint in
sgf_trace.
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.
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.
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.
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.
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.
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:
Instead of -T, try this with -E. This gives a colored
display of the eyespaces, with marginal eye spaces marked !
(see Eyes).
The option -m level can give colored displays of the
various quantities which are computed in engine/moyo.c.
The regions found by Bouzy's algorithm (see Moyo) can be displayed with the following options:
-m level
use or (hexadecimal) cumulative values for printing these reports :
1 0x01 ascii printing of territorial evaluation (5/21)
2 0x02 ascii printing of moyo evaluation (5/10)
4 0x04 ascii printing of area (4/0)
These data are today only used in the score estimation.
The rest of the engine uses instead the new influence algorithm explained
in See Influence. To get a colored display of the influence regions
found by this module, use -m 0x18 to see the initial influence,
and e.g. -m 0x10 --debug-influence D5 to see the influence
after having made the move D5. There are various other options available
for numerical displays influence; for a detailed description see
See Influential Display.
These options can be combined by adding the levels.
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. Games can be saved to
SGF files and then later be read back again. These are also within
libengine.a.
The responsibility of the application is to provide the user with a user interface, graphical or not, and let the user interact with the engine.
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.
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.
GNU Go uses two different representations of the board, for most purposes a one-dimensional one, but for a few purposes a two dimensional one (see Libboard). The one-dimensional board was introduced before GNU Go 3.2, while the two-dimensional board dates back to the ancestral program written by Man Lung Li before 1995. The API still uses the one-dimensional board, so the API functions have not changed much since GNU Go 3.0.
A basic data structure in the engine is the board_state struct.
This structure is internal to the engine and is defined in liberty.h.
typedef unsigned char Intersection;
struct board_state {
int board_size;
Intersection board[BOARDSIZE];
int board_ko_pos;
int black_captured;
int white_captured;
Intersection initial_board[BOARDSIZE];
int initial_board_ko_pos;
int initial_white_captured;
int initial_black_captured;
int move_history_color[MAX_MOVE_HISTORY];
int move_history_pos[MAX_MOVE_HISTORY];
int move_history_pointer;
float komi;
int move_number;
};
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 board state
contains an array of Intersection's representing the board.
The move history is contained in the struct. Also contained in
the struct is the location of a ko (EMPTY) if the last
move was not a ko capture, the komi, the number of captures, and
corresponding data for the initial position at the beginning
of the move history.
All the functions in the engine that manipulate Positions have names
prefixed by gnugo_. These functions still use the two-dimensional
representation of the board (see The Board). Here is a complete list, as
prototyped in gnugo.h:
void init_gnugo(float memory)
Initialize the gnugo engine. This needs to be called once only.
void gnugo_clear_board(int boardsize)
Clear the board.
void gnugo_set_komi(float new_komi)
Set the komi.
void gnugo_add_stone(int i, int j, int color)
Place a stone on the board
void gnugo_remove_stone(int i, int j)
Remove a stone from the board
int gnugo_is_pass(int i, int j)
Return true if (i,j) is PASS_MOVE
void gnugo_play_move(int i, int j, int color)
Play a move and start the clock
int gnugo_undo_move(int n)
Undo n permanent moves. Returns 1 if successful and 0 if it fails. If n moves cannot be undone, no move is undone.
int gnugo_play_sgfnode(SGFNode *node, int to_move)
Perform the moves and place the stones from the SGF node on the board. Return the color of the player whose turn it is to move.
int gnugo_play_sgftree(SGFNode *root, int *until, SGFNode **curnode)
Play the moves in ROOT UNTIL movenumber is reached. Return the color of the player whose turn it is to move.
int gnugo_is_legal(int i, int j, int color)
Interface to is_legal().
int gnugo_is_suicide(int i, int j, int color)
Interface to is_suicide().
int gnugo_placehand(int handicap)
Interface to placehand. Sets up handicap pieces and returns the number of placed handicap stones.
void gnugo_recordboard(SGFNode *root)
Interface to sgffile_recordboard()
int gnugo_sethand(int handicap, SGFNode *node)
Interface to placehand. Sets up handicap stones and returns the number of placed handicap stones, updating the sgf file
int gnugo_genmove(int *i, int *j, int color)
Interface to genmove().
int gnugo_attack(int m, int n, int *i, int *j)
Interface to attack().
int gnugo_find_defense(int m, int n, int *i, int *j)
Interface to find_defense().
void gnugo_who_wins(int color, FILE *outfile)
Interface to who_wins().
float gnugo_estimate_score(float *upper, float *lower)
Put upper and lower score estimates into*upper,*lowerand return the average. A positive score favors white. In computing the upper bound,CRITICALdragons are awarded to white; in computing the lower bound, they are awarded to black.
void gnugo_examine_position(int color, int how_much)
Interface to examine_position.
int gnugo_get_komi()
Report the komi.
void gnugo_get_board(int b[MAX_BOARD][MAX_BOARD])
Place the board into the b array.
int gnugo_get_boardsize()
Report the board size.
int gnugo_get_move_number()
Report the move number.
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;
int to_move; /* whose move it currently is */
SGFTree game_record; /* Game record in sgf format. */
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. to_move is the
color of the side whose turn it is to move.
The SGF tree game_record is used to store all the moves in the entire
game, including a header node which contains, among other things, komi
and handicap.
If one or both of the opponents is the computer, the field
computer_player is used. Otherwise it can be ignored.
GNU Go can use a trickle file to continuously save all the moves of an
ongoing game. This file can also contain information about internal
state of the engine such as move reasons for various locations or move
valuations. The name of this file should
be stored in outfilename and the file pointer to the open file is
stored in outfile. If no trickle file is used,
outfilename[0] will contain a null character and outfile
will be set to NULL.
All the functions in the engine that manipulate Gameinfos have names
prefixed by gameinfo_. Here is a complete list, as prototyped in
gnugo.h:
void gameinfo_clear(Gameinfo *ginfo, int boardsize, float komi)
Initialize the Gameinfo structure.
void gameinfo_print(Gameinfo *ginfo)
Print a gameinfo.
void gameinfo_load_sgfheader(Gameinfo *gameinfo, SGFNode *head)
Reads header info from sgf structure and sets the appropriate variables.
void gameinfo_play_move(Gameinfo *ginfo, int i, int j, int color)
Make a move in the game. Return 1 if the move was legal. In that case the move is actually done. Otherwise return 0.
int gameinfo_play_sgftree_rot(Gameinfo *gameinfo, SGFNode *head, const char *untilstr, int orientation)
Play the moves in an SGF tree. Walk the main variation, actioning the properties into the playing board. Returns the color of the next move to be made. Head is an sgf tree. Untilstr is an optional string of the form either 'L12' or '120' which tells it to stop playing at that move or move number. When debugging, this is the location of the move being examined.
int gameinfo_play_sgftree(Gameinfo *gameinfo, SGFNode *head, const char *untilstr)
Same as previous function, using standard orientation.
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).
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.
These functions let the caller create nodes or access nodes easier.
SGFNode *sgfNewNode(void)
Allocate and return a new instance of SGFNode. The node is
cleared.
SGFProperty *sgfMkProperty(const char *name, const char *value,
SGFNode *node, SGFProperty *last)
Allocate and return a new instance ofSGFProperty. Thenameshould be 1 or 2 characters long. This function should probably not be used directly. Instead, use thesgfAddPropertyfunctions.
SGFNode *sgfPrev(SGFNode *node)
Return the previous node in a chain. This is done by going to the parent
node and then search through the children until the same node is found.
If there is no previous node, NULL is returned.
SGFNode *sgfRoot(SGFNode *node)
Return the root of the tree. Ifnodealready is the root,nodeitself is returned.
int sgfGetIntProperty(SGFNode *node, const char *name, int
*value)
Get the propertynameinnodeas an integer. The value is returned invalue. Returns 1 if successful, otherwise returns 0.
int sgfGetFloatProperty(SGFNode *node, const char *name,
float *value)
Get the propertynameinnodeas a floating point value. The value is returned invalue. Returns 1 if successful, otherwise returns 0.
int sgfGetCharProperty(SGFNode *node, const char *name, char
**value)
Get the propertynameinnodeas a string of characters. The value is returned invalue. Returns 1 if successful, otherwise returns 0.
void sgfAddProperty(SGFNode *node, const char *name, const
char *value)
Add a new property to node. There is no check to see if there
already is a property with the same name. The property value has to be a
character string.
void sgfAddPropertyInt(SGFNode *node, const char *name, long
val)
Add an integer property tonode. This function converts the value to a string and callssgfAddProperty.
void sgfAddPropertyFloat(SGFNode *node, const char *name,
float val)
Add a floating point property tonode. This function converts the value to a string and callssgfAddProperty.
void sgfOverwriteProperty(SGFNode *node, const char *name,
const char *text)
Overwrite the propertynameinnodewith the stringtext. If the property does not yet exist innode, it is added usingsgfAddProperty.
void sgfOverwritePropertyInt(SGFNode *node, const char
*name, int value)
Overwrite the propertynameinnodewith the integervalue. If the property does not yet exist innode, it is added usingsgfAddPropertyInt.
void sgfOverwritePropertyFloat(SGFNode *node, const char
*name, float value)
Overwrite the propertynameinnodewith the floating point numbervalue. If the property does not yet exist innode, it is added usingsgfAddPropertyFloat.
SGFNode *sgfAddStone(SGFNode *node, int color, int movex,
int movey)
Add a stone tonode. Properties added is eitherAB(black stone) orAW(white stone).
SGFNode *sgfAddPlay(SGFNode *node, int who, int movex, int
movey)
Add a child node with a move tonode. Properties added is eitherB(black move) orW(white move). A pass is coded by(-1, -1).This function does not add a property to the node itself, but adds a child node instead. If there are previous child nodes, the new node is placed before the other ones, so this function should be used if you want to add a main branch to the tree. To add a variation, use
sgfAddPlayLastinstead.
SGFNode *sgfAddPlayLast(SGFNode *node, int who, int movex,
int movey)
Add a child node with a move tonode. Properties added is eitherB(black move) orW(white move). A pass is coded by(-1, -1).If there are previous child nodes in
node, the move is added by adding the child node last, so this function should be used when you want to add a variation to the game tree.
int sgfPrintCharProperty(FILE *file, SGFNode *node, const
char *name)
Print the properties of typenameinnodeonfile.
int sgfPrintCommentProperty(FILE *file, SGFNode *node, const
char *name)
Print the comment properties of typenameinnodeonfile.
void sgfWriteResult(SGFNode *node, float score, int
overwrite)
Add aRE(result) property tonode. This property will contain the game result. Ifoverwriteis zero the result is written only if no previous result property exists.
SGFNode *sgfCircle(SGFNode *node, int i, int j)
Add aCR(circle) property at(i, j)tonode.
SGFNode *sgfSquare(SGFNode *node, int i, int j)
CallssgfMarkto add aMA(mark) property at(i, j)tonode.
SGFNode *sgfTriangle(SGFNode *node, int i, int j)
Add aTR(triangle) property at(i, j)tonode.
SGFNode *sgfMark(SGFNode *node, int i, int j)
Add aMA(mark) property at(i, j)tonode.
SGFNode *sgfAddComment(SGFNode *node, const char *comment)
Add aC(comment) property tonode.
SGFNode *sgfBoardText(SGFNode *node, int i, int j, const
char *text)
Add aLB(label) property at(i, j)tonode.
SGFNode *sgfBoardChar(SGFNode *node, int i, int j, char c)
Add aLB(label) property at(i, j)tonode. This functions is a utility function that converts the character to a string and callssgfBoardText.
SGFNode *sgfBoardNumber(SGFNode *node, int i, int j, int
number)
Add a numeric label at(i, j)by callingsgfBoardText.
SGFNode *sgfStartVariant(SGFNode *node)
Start a new variation in the game tree. This means that thenextpointer ofnodeis followed to the end of the list and a new node is inserted there. A pointer to the new node is returned.
SGFNode *sgfStartVariantFirst(SGFNode *node)
Same as sgfStartVariant, except that the node is placed first in
the list. This means that the new variation will be the main variation
of the game tree. Returns a pointer to the new node.
SGFNode *sgfAddChild(SGFNode *node)
Adds a child node to node. If there already are children, the new
node is placed last in the list. Returns a pointer to the new node.
SGFNode *sgfCreateHeaderNode(int boardsize, float komi)
Create a new SGF node with the two propertiesSZ(size) andKM(komi). More properties, likeHA(handicap), can later be added to it.The idea with this node is to store the game info and to use as a root node for the game.
SGFNode *readsgffile(const char *filename)
Read an SGF file and return the resulting tree.
void sgf_write_header(SGFNode *root, int overwrite, int
seed, float komi)
Write random seed, date, ruleset, komi and SGF file version to the header noderoot. Ifoverwriteis non-zero, it overwrites the values in the node, otherwise it just writes those that are missing.Ruleset is always set to "Japanese", date is set to the current date.
int writesgf(SGFNode *root, const char *filename)
Write the tree starting inrootto the filefilename. Iffilenameis-, the tree is written tostdout. Returns 1 if successful, otherwise returns 0.
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:
node if non-NULL
tree->lastnode if non-NULL
void sgftree_clear(SGFTree *tree)
Clear therootandlastnodepointers oftree.NOTE:This function does not free any memory. That has to be done separately.
int sgftree_readfile(SGFTree *tree, const char *infilename)
Read an SGF file with the nameinfilenameand store it intree. Return 1 if successful, otherwise return 0.lastnodewill be set toNULL.
SGFNode *sgftreeNodeCheck(SGFTree *tree, SGFNode *node)
Return the node to work on as described above. This is:in that order.
nodeif non-NULLtree->lastnodeif non-NULL- The current end of the tree.
SGFNode *sgftreeAddPlay(SGFTree *tree, SGFNode *node, int
color int movex, int movey)
Add a move ofcolorat(movex,movey)to the tree. See sgfAddPlay.
SGFNode *sgftreeAddPlayLast(SGFTree *tree, SGFNode *node,
int color, int movex, int movey)
Add a variation ofcolorat(movex,movey)to the tree. See sgfAddPlayLast.
SGFNode *sgftreeAddStone(SGFTree *tree, SGFNode *node, int
color, int movex, int movey)
Add a stone ofcolorat(movex,movey)to the tree.
void sgftreeWriteResult(SGFTree *tree, float score, int
overwrite)
Add the result to the tree. If there already is a result, only overwrite
it if overwrite is non-zero.
SGFNode *sgftreeCircle (SGFTree *tree, SGFNode *node, int
i, int j)
Add a circle property at (i, j) to the tree.
SGFNode *sgftreeSquare (SGFTree *tree, SGFNode *node, int
i, int j)
Add a square property at (i, j) to the tree.
SGFNode *sgftreeTriangle(SGFTree *tree, SGFNode *node, int
i, int j)
Add a triangle property at (i, j) to the tree.
SGFNode *sgftreeMark(SGFTree *tree, SGFNode *node, int i, int j)
Add a mark property at (i, j) to the tree.
SGFNode *sgftreeAddComment(SGFTree *tree, SGFNode *node,
const char *comment)
Add a comment property to the tree. This is a property of the node itself, and has no position on the board.
SGFNode *sgftreeBoardText(SGFTree *tree, SGFNode *node, int
i, int j, const char *text)
Add a text property at (i, j) to the tree.
SGFNode *sgftreeBoardChar(SGFTree *tree, SGFNode *node, int
i, int j, char c)
Add a character at (i, j) to the tree.
SGFNode *sgftreeBoardNumber(SGFTree *tree, SGFNode *node,
int i, int j, int number)
Add a number at (i, j) to the tree.
SGFNode *sgftreeStartVariant(SGFTree *tree, SGFNode *node)
Start a new variation in the tree. See sgfStartVariant.
SGFNode *sgftreeStartVariantFirst(SGFTree *tree, SGFNode
*node)
Start a new main variation in the tree. See sgfStartVariantFirst.
SGFNode *sgftreeCreateHeaderNode(SGFTree *tree, int
boardsize, float komi)
Add a header node first in tree.
void sgftreeSetLastNode(SGFTree *tree, SGFNode
*last_node)
Explicitly set the last accessed node intreetolast_node.
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.c, which compiles joseki pattern
databases from SGF files.
The library consists of the following files:
board.c
The basic board code. It uses incremental algorithms for keeping track of strings and liberties on the go board.
hash.c
Code for hashing go positions.
globals.c
Global variables needed in the rest of the files. This file also contains global variables needed in the rest of the engine.
sgffile.c
Implementation of output file in SGF format.
showbord.c
Print go boards.
printutils.c
Utilities for printing go boards and other things.
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.
The basic data structures of the board correspond tightly to the
board_state struct described in See The Board State. They are all
stored in global variables for efficiency reasons, the most important of which
are:
int board_size; Intersection board[MAXSIZE]; int board_ko_pos; 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.
These functions are all the public functions in engine/board.c.
These functions are used when you want to set up a new position without actually playing out moves.
void clear_board()
Clears the internal board (board[]), resets the ko position,
captured stones and recalculates the hash value.
void setup_board(Intersection new_board[MAX_BOARD][MAX_BOARD], int ko_pos, int *last, float new_komi, int w_captured, int b_captured)
Set up a new board position using the parameters.
void add_stone(int pos, int color)
Place a stone on the board and update the hashdata. No captures are done.
void remove_stone(int pos)
Remove a stone from the board and update the hashdata.
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(pos, color, ... )) {
... [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).
void play_move(int pos, int color)
Play a move at(pos). If you want to test for legality you should first callis_legal(). This function strictly follows the algorithm:
- Place a stone of given color on the board.
- If there are any adjacent opponent strings without liberties, remove them and increase the prisoner count.
- If the newly placed stone is part of a string without liberties, remove it and increase the prisoner count.
int trymove(int pos, int color, const char *message, int str, int komaster, int kom_pos)
Returns true if(pos)is a legal move forcolor. In that case, it pushes the board on the stack and makes the move, incrementingstackp. If the reading code is recording reading variations (as with--decide-stringor with-o), the string*messagewill be inserted in the SGF file as a comment. The comment will also refer to the string atstrif this is not0. The komaster and ko position variables are described elsewhere (see Ko)
int TRY_MOVE()
Wrapper around trymove which suppresses*messageand(k,l). Used inhelpers.c
int tryko(int pos, int color, const char *message, int komaster, int kom_pos)
tryko()pushes the position onto the stack, and makes a moveposofcolor. The move is allowed even if it is an illegal ko capture. It is to be imagined thatcolorhas made an intervening ko threat which was answered and now the continuation is to be explored. Return 1 if the move is legal with the above caveat. Returns zero if it is not legal because of suicide.
void popgo()
Pops the move stack. This function must (eventually) be called after a succesfultrymoveortrykoto restore the board position. It undoes all the changes done by the call totrymove/trykoand leaves the board in the same state as it was before the call.NOTE: If
trymove/trykoreturns0, i.e. the tried move was not legal, you must not callpopgo.
int komaster_trymove(int pos, int color, const char *message, int str, int komaster, int kom_pos, int *new_komaster, int *new_kom_pos, int *is_conditional_ko, int consider_conditional_ko)
Variation oftrymove/trykowhere ko captures (both conditional and unconditional) must follow a komaster scheme (see Ko).
int move_in_stack(int pos, int cutoff)
Returns true if at least one move been played at (pos)
at deeper than level 'cutoff' in the reading tree.
void void get_move_from_stack(int k, int *move, int *color)
Retrieve the move numberkfrom the move stack. The move location is returned in(*move), and the color that made the move is returned in*color.
void dump_stack(void)
Handy for debugging the reading code under GDB. Prints the move stack.
Usage: (gdb) set dump_stack().
void reset_trymove_counter()
Reset the trymove counter. This counter is incremented every time that a variant oftrymoveortrykois called.
int get_trymove_counter()
Retrieve the trymove counter.
These functions are used for inquiring about properties of the current position or of potential moves.
int is_pass(int pos)
Returns true if the move (pos) is PASS_MOVE, that is, 0.
int is_legal(int pos, int color)
Returns true if a move atposis legal forcolor.
int is_ko(int pos, int color, int *ko_pos)
Return true if the moveposbycoloris a ko capture whether capture is a legal ko capture on this move or not. If*ko_posare non-NULL, then the location of the captured ko stone are returned through*ko_pos. If the move is not a ko capture,*ko_posis set to 0.
int is_illegal_ko_capture(int pos, int color)
Return true if the movePOSbycolorwould be an illegal ko capture. There is no need to call bothis_koandis_illegal_ko_capture.
int is_self_atari(int pos, int color)
Return true if a move bycoloratposwould be a self atari, i.e. whether it would get only one liberty. This function returns true also for the case of a suicide move.
int is_suicide(int pos, int color)
Returns true if a move atposis suicide forcolor.
int does_capture_something(int pos, int color)
Returns true if a move at pos does capture any stone for the
other side.
int stones_on_board(int color)
Return the number of stones of the indicated color(s) on the board. This only count stones in the permanent position, not stones placed bytrymove()ortryko(). Usestones_on_board(BLACK | WHITE)to get the total number of stones on the board.
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.
void find_origin(int str)
Find the origin of a worm or a cavity, i.e. the point with the smallest 1D board coordinate. The idea is to have a canonical reference point for a string (see Worms).
int findstones(int str, int maxstones, int *stones)
Find the stones of the string atstr.strmust not be empty. The locations of up tomaxstonesstones are written into*stone. The full number of stones is returned.
int countstones(int str)
Count the number of stones in a string.
void mark_string(int str, char mx[BOARDMAX], char mark)
For each stone in the string at pos, set mx to value mark. If some of the stones in the string are marked prior to calling this function, only the connected unmarked stones starting from pos are guaranteed to become marked. The rest of the string may or may not become marked. (In the current implementation, it will.)
int liberty_of_string(int pos, int str)
Returns true ifposis a liberty of the string atstr.
int neighbor_of_string(int pos, int str)
Returns true if pos is adjacent to the string at str.
int same_string(int str1, int str2)
Returns true ifstr1andstr2belong to the same string.
int findlib(int str, int maxlib, int *libs)
int findlib
Find the liberties of the string at str. str must not be empty. The locations of up to maxlib liberties are written intolibs[]. The full number of liberties is returned. If you want the locations of all liberties, whatever their number, you should passMAXLIBSas the value for maxlib and allocate space forlibs[]accordingly.
int countlib(int str)
Count the number of liberties of the string at str, which
must not be empty.
int fastlib(int pos, int color, int ignore_capture)
Count the liberties a stone of the given color would get if played at
pos. Captures are ignored based on the ignore_capture flag. (pos)
must be empty. It will fail if there is more than one string neighbor of the
same color. In this case, the return value is -1. Captures are not handled,
so if ignore_capture is 0, and a capture is required, -1 is returned. The
intent of this function is to be as fast as possible, not necessarily
complete.
int approxlib(int pos, int color, int maxlib, int *libs)
Find the liberties a stone of the given color would get if played atpos, ignoring possible captures of opponent stones.posmust be empty. Iflibs != NULL, the locations of up tomaxlibliberties are written intolibs[]. The counting of liberties may or may not be halted when maxlib is reached. The number of liberties found is returned. If you want the number or the locations of all liberties, however many they are, you should passMAXLIBSas the value formaxliband allocate space forlibs[]accordingly.
int count_common_libs(int str1, int str2)
Find the number of common liberties of the two strings at str1 and str2.
int find_common_libs(int str1, int str2, int maxlib, int *libs)
Find the common liberties of the two strings atstr1andstr2. The locations of up to maxlib common liberties are written intolibs[]. The full number of common liberties is returned. If you want the locations of all common liberties, whatever their number, you should passMAXLIBSas the value for maxlib and allocate space forlibs[]accordingly.
int have_common_lib(int str1, int str2, int *lib)
Determine whether two strings have at least one common liberty.
If they have and lib != NULL, one common liberty is returned in *lib.
int chainlinks(int str, int adj[MAXCHAIN])
Returns (in theadjarray) the chains surrounding the string atstr. The number of chains is returned.
int chainlinks2(int str, int adj[MAXCHAIN], int lib)
Returns (in theadjarray) the chains surrounding the string atstrhaving exactlylibliberties. The number of chains is returned.
incremental_order_moves(int move, int color, int str, int *number_edges, int *number_same_string, int *number_own, int *number_opponent, int *captured_stones, int *threatened_stones, int *saved_stones, int *number_open)
Help collect the data needed byorder_moves()inreading.c. It's the caller's responsibility to initialize the result parameters.
GNU Go 3.0 introduced a move generation scheme substantially different from earlier versions. In particular, it was different from the method of move generation in GNU Go 2.6.
In the old scheme, various move generators suggested different moves with attached values. The highest such value then decided the move. There were two important drawbacks with this scheme:
The basic idea of the new move generation scheme is that the various move generators suggest reasons for moves, e.g. that a move captures something or connects two strings, and so on. When all reasons for the different moves have been found, the valuation starts. The primary advantages are
The 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:
This is somewhat simplified. In reality there is some overlap between the steps.
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:
make_worms
Collect information about all connected sets of stones
(strings) and cavities. This information is stored in
the worm array.
make_dragons
Collect information about connected strings, which are called dragons. Important information here is number of eyes, life status, and connectedness between strings. The information is stored in the arraysdragonbut also indragon2.
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.
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. A partial list of of move reasons considered by GNU Go are:
ATTACK_MOVE
DEFEND_MOVE
ATTACK_THREAT_MOVE
DEFEND_THREAT_MOVE
EITHER_MOVE
ALL_MOVE
CONNECT_MOVE
CUT_MOVE
ANTISUJI_MOVE
SEMEAI_MOVE
SEMEAI_THREAT
EXPAND_TERRITORY_MOVE
BLOCK_TERRITORY_MOVE
EXPAND_MOYO_MOVE
VITAL_EYE_MOVE
STRATEGIC_ATTACK_MOVE
STRATEGIC_DEFEND_MOVE
OWL_ATTACK_MOVE
OWL_DEFEND_MOVE
OWL_ATTACK_THREAT
OWL_DEFEND_THREAT
OWL_PREVENT_THREAT
UNCERTAIN_OWL_ATTACK
UNCERTAIN_OWL_DEFENSE
MY_ATARI_ATARI_MOVE
YOUR_ATARI_ATARI_MOVE
The attack and defend move types can have a suffix to denote moves whose
result depends on a ko, e.g. OWL_ATTACK_MOVE_GOOD_KO. Here
..._GOOD_KO and ..._BAD_KO correspond to KO_A and
KO_B as explained in Ko.
See engine/move_reasons.h for the full of move reasons.
NOTE: Some of these are reasons for not playing a move.
More detailed discussion of these move reasons will be found in the next section.
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.)
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.
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.
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.
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.
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.)
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.
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.
Just as the tactical reading code tries to determine when a worm
can be attacked or defended, the owl code tries to determine
when a dragon can get two eyes and live. The function owl_reasons()
generates the corresponding move reasons.
The owl attack and owl defense move reasons are self explanatory.
The owl attack threat reason is generated if owl attack on an
opponent's dragon fails but the owl code determines that the
dragon can be killed with two consecutive moves. The killing
moves are stored in dragon[pos].owl_attack_point
and dragon[pos].owl_second_attack_point.
Similarly if a friendly dragon is dead but two moves can revive it, an owl defense threat move reason is generated.
The prevent threat reasons are similar but with the colors reversed: if the opponent has an attack threat move then a move which removes the threat gets a prevent threat move reason.
The owl uncertain move reasons are generated when the owl code runs out of nodes. In order to prevent the owl code from running too long, a cap is put on the number of nodes one owl read can generate. If this is exceeded, the reading is cut short and the result is cached as usual, but marked uncertain. In this case an owl uncertain move reason may be generated. For example, if the owl code finds the dragon alive but is unsure, a move to defend may still be generated.
The function atari_atari tries to find a sequence of ataris
culminating in an unexpected change of status of any opponent string,
from ALIVE to CRITICAL. Once such a sequence of ataris
is found, it tries to shorten it by rejecting irrelevant moves.
At the end of the move generation process, the function
value_move_reasons() tries to assign values to the
moves for the purpose of selecting the best move. The
single purpose of the move valuation is to try to rank
the moves so that the best move gets the highest
score. In principle these values could be arbitrary,
but in order to make it easier to evaluate how well the
valuation performs, not to mention simplify the tuning,
we try to assign values which are consistent with the
usual methods of counting used by human Go players,
as explained for example in The Endgame by Ogawa
and Davies.
Moves are valued with respect to four different criteria. These are
All of these are floats and should be measured in terms of actual points.
The territorial value is the total change of expected territory caused by this move. This includes changes in the status of groups if the move is an attack or a defense move.
Beginning with GNU Go 3.0, the influence function plays an important role in estimating territory (see Influence and Territory). It is used to make a guess at each intersection how likely it is that it will become black or white territory. The territorial value sums up the changes in these valuations.
Strategical value is a measure of the effect the move has on the safety of all groups on the board. Typically cutting and connecting moves have their main value here. Also edge extensions, enclosing moves and moves towards the center have high strategical value. The strategical value should be the sum of a fraction of the territorial value of the involved dragons. The fraction is determined by the change in safety of the dragon.
Shape value is a purely local shape analysis. An important role of this measure is to offset mistakes made by the estimation of territorial values. In open positions it's often worth sacrificing a few points of (apparent) immediate profit to make good shape. Shape value is implemented by pattern matching, the Shape patterns.
Secondary value is given for move reasons which by themselves are not sufficient to play the move. One example is to reduce the number of eyes for a dragon that has several or to attack a defenseless worm.
When all these values have been computed, they are summed, possibly weighted (secondary value should definitely have a small weight), into a final move value. This value is used to decide the move.
The algorithm for computing territorial value is in the function
estimate_territorial_value. As the name suggests, it seeks
to estimate the change in territory.
It considers all groups that are changed from alive to death or vice-versa
due to this move. Also, it makes an assumption whether the move should be
considered safe. If so, the influence module is called: The function
influence_delta_territory estimates the territorial effect of
both the stone played and of the changes of group status'.
The result returned by the influence module is subject to a number of corrections. This is because some move reasons cannot be evaluated by a single call to the influence function, such as moves depending on a ko.
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.
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.
A pattern may assign a minimum (and sometimes also a maximum)
value. For example the Joseki patterns have values which are
prescribed in this way, or ones with a value field.
One prefers not to use this approach but in practice it is
sometimes needed.
In the fuseki, there are often several moves with identical minimum value. GNU Go chooses randomly between such moves, which ensures some indeterminacy of GNU Go's play. Later in the game, GNU Go's genuine valuation of such a move is used as a secondary criterion.
Secondary move reasons are weighed very slightly. Such a move can tip the scales if all other factors are equal.
Followup value refers to value which may acrue if we get two
moves in a row in a local area. It is assigned for moves that threaten
to attack or defend a worm or dragon. Also, since GNU Go 3.2 the influence
module makes an assessment of the possible purely territorial followup
moves. In cases where these two heuristics are not sufficient we
add patterns with a followup_value autohelper macro.
Usually, the followup value gives only a small contribution; e.g. if it the followup value is very large, then GNU Go treats the move as sente by doubling its value. However, if the largest move on the board is a ko which we cannot legally take, then such a move becomes attractive as a ko threat and the full followup value is taken into account.
The following functions are defined in move_reasons.c.
void clear_move_reasons(void)
Initialize move reason data structures.
void add_lunch(int eater, int food)
See if a lunch is already in the list of lunches, otherwise add a new entry. A lunch is in this context a pair ofeater(a dragon) andfood(a worm).
void remove_lunch(int eater, int food)
Remove a lunch from the list of lunches. A lunch is in this context a pair ofeater(a dragon) andfood(a worm).
int move_reason_known(int pos, int type, int what)
Check whether a move reason already is recorded for a move. Negative value forwhatmeans only matchtype.
int attack_move_reason_known(int pos, int what)
Check whether an attack move reason already is recorded for a move. Negative value forwhatmeans only matchtype.
int defense_move_reason_known(int pos, int what)
Check whether a defense move reason already is recorded for a move. Negative value forwhatmeans only matchtype.
int owl_defense_move_reason_known(int pos, int what)
Check whether an owl defense move reason already is recorded for a move. Negative value forwhatmeans only matchtype.
void add_attack_move(int pos, int ww, int code)
Add to the reasons for the move atposthat it attacks the worm atww.
void add_defense_move(int pos, int ww, int code)
Add to the reasons for the move atposthat it defends the worm atww.
void add_attack_threat_move(int pos, int ww, int code)
Add to the reasons for the move atposthat it threatens to attack the worm atww.
void remove_attack_threat_move(int pos, int ww)
Remove an attack threat move reason.
void add_defense_threat_move(int pos, int ww, int code)
Add to the reasons for the move atposthat it defends the worm atww.
int get_attack_threats(int pos, int max_strings, int strings[])
Report all, or up to max_strings, strings that are threatened
at pos.
int get_defense_threats(int pos, int max_strings, int strings[])
Report all, or up to max_strings, strings that might be defended
at pos.
int get_biggest_owl_target(int pos)
Report the biggest dragon that is owl-affected (possibily with ko)
by a move at pos.
void add_connection_move(int pos, int dr1, int dr2)
Add to the reasons for the move atposthat it connects the dragons atdr1anddr2. Require that the dragons are distinct.
void add_cut_move(int pos, int dr1, int dr2)
Add to the reasons for the move atposthat it cuts the dragons atdr1anddr2. Require that the dragons are distinct.
void add_antisuji_move(int pos)
Add to the reasons for the move at (pos that it is an anti-suji. This means that it is a locally inferior move, or for some other reason, must not be played.
void add_semeai_move(int pos, int dr)
Add to the reasons for the move atposthat it wins the dragon (friendly or not) atdrin semeai. Since it is possible that in some semeai one player can kill but the other can only make seki, it is possible that one dragon is already alive in seki. Therefore separate move reasons must be added for the two dragons.
void add_semeai_threat(int pos, int dr)
Add to the reasons for the move atposthat given two moves in a row a move here can win the dragon (friendly or not) atdrin semeai. Such a move can be used as a ko threat, and it is also given some value due to uncertainty in the counting of liberties.
void add_vital_eye_move(int pos, int eyespace, int color)
Add to the reasons for the move atposthat its the vital point for the eye space ateyespaceofcolor.
void add_either_move(int pos, int reason1, int target1, int reason2, int target2)
Add to the reasons for the move atposthat it will accomplish one of two things: eitherreason1ontarget1orreason2ontarget2. At this time,reasoncan only beATTACK_STRING. More reasons will be implemented in the future.
void add_all_move(int pos, int reason1, int target1, int reason2, int target2)
Add to the reasons for the move atposthat it will accomplish both of two things:reason1ontarget1andreason2ontarget2. At this time,reasoncan only beDEFEND_STRING. More reasons will be implemented in the future.
void add_block_territory_move(int pos)
Add to the reasons for the move at pos that it secures
territory by blocking.
void add_block_territory_move(int pos)
Add to the reasons for the move at pos that it secures
territory by blocking.
void add_expand_territory_move(int pos)
Add to the reasons for the move at pos that it expands
territory.
void add_expand_moyo_move(int pos)
Add to the reasons for the move at pos that it expands moyo.
void add_shape_value(int pos, float value)
This function is called when a shape value for the move at pos
is found. We keep track of the largest positive shape value found, and the
total number of positive contributions, as well as the largest
negative shape value found, and the total number of negative
shape contributions.
void add_worthwhile_threat_move(int pos)
Flag that this move is worthwhile to play as a pure threat move.
float compute_shape_factor(int pos)
This function computes 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. 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.
void add_strategical_attack_move(int pos, int dr)
Add to the reasons for the move atposthat it attacks the dragondron a strategical level.
void add_strategical_defense_move(int pos, int dr)
Add to the reasons for the move atposthat it defends the dragondron a strategical level.
void add_owl_attack_move(int pos, int dr, int code)
Add to the reasons for the move atposthat the owl code reports an attack on the dragondr.
void add_owl_defense_move(int pos, int dr, int code)
Add to the reasons for the move atposthat the owl code reports a defense of the dragondr.
void add_owl_attack_threat_move(int pos, int dr, int code)
Add to the reasons for the move atposthat the owl code reports a move threatening to attack the dragon enemydr. That is, if the attacker is given two moves in a row,poscan be the first move.
void add_owl_uncertain_defense_move(int pos, int dr)
The owl code found the friendly dragon alive, or the unfriendly dragon dead, and an extra point of attack or defense was found, so this might be a good place to play.
void add_owl_uncertain_attack_move(int pos, int dr)
The owl code found the opponent dragon alive, or the friendly dragon dead, but was uncertain, and this move reason propose an attack or defense which is expected to fail but might succeed.
void add_owl_defense_threat_move(int pos, int dr, int code)
Add to the reasons for the move atposthat the owl code reports a move threatening to rescue the dragondr. That is, if the defender is given two moves in a row,poscan be the first move.
void add_my_atari_atari_move(int pos, int size)
Add to the reasons for the move at pos that it captures
at least one of a set of worms which individually are tactically
safe (such as a double atari). Only one such move reason is
permitted per move.
void add_your_atari_atari_move(int pos, int size)
Add to the reasons for the move at pos that it stops a
combination attack for the opponent.
void add_owl_prevent_threat_move(int pos, int dr)
Add to the reasons for the move atposthat the owl code reports a move threatening to defend the dragon enemydr, and thatposis a move which attacks the dragon. That is, if the defender is given two moves in a row,poscan be the first move. Hopefully playing atposmakes it harder for the dragon to live.
void add_followup_value(int pos, float value)
Add value of followup moves.
void add_reverse_followup_value(int pos, float value)
Add value of inverse followup moves.
int set_minimum_move_value(int pos, float value)
Set a minimum allowed value for the move.
void set_minimum_territorial_value(int pos, float value)
Set a minimum allowed territorial value for the move.
void set_maximum_territorial_value(int pos, float value)
Set a maximum allowed territorial value for the move.
void add_replacement_move(int from, int to)
Add a point redistribution rule, sending the points fromfromtoto.
void get_saved_worms(int pos, int saved[BOARDMAX])
Find worms rescued by a move at pos.
void get_saved_dragons(int pos, int saved[BOARDMAX])
Find dragons rescued by a move at pos.
void list_move_reasons(int color)
List the move reasons for color.
void discard_redundant_move_reasons(int pos)
This function checks the list of move reasons for redundant move reasons and marks them accordingly in their status field.
int is_antisuji_move(int pos)
Look through the move reasons to see whether pos is an antisuji move.
int move_connects_strings(int pos, int color)
Count how many distinct strings are (solidly) connected by the move
at pos. Add a bonus for strings with few liberties. Also add
bonus for opponent strings put in atari or removed.
int move_reasons_confirm_safety(int move, int color, int minsize)
Find saved dragons and worms, then call confirm_safety().
The file value_moves.c contains the function
int review_move_reasons(int *the_move, float *val, int color,
float pure_threat_value, float score) which assigns values to all the
moves. The parameter pure_threat_value is the value assigned to a move
which only threatens to capture or kill something. The reason for
playing these is that the move may be effective because we have
misevaluated the dangers or because the opponent misplays.
Apart from this function, the functions in this file are declared static. However they are so important that we document many of them here.
static void find_more_attack_and_defense_moves(int color)
Test all moves which defend, attack, connect or cut to see if they also attack or defend some other worm.
static void find_more_owl_attack_and_defense_moves(int color)
Test certain moves to see whether they (too) can owl attack or defend an owl critical dragon. Tested moves are
- Strategical attacks or defenses for the dragon.
- Vital eye points for the dragon.
- Tactical attacks or defenses for a part of the dragon.
- Moves connecting the dragon to something else.
static int strategically_sound_defense(int aa, int tt)
It's often bad to run away with a worm that is in a strategically weak position. This function gives heuristics for determining whether a move atttto defend the wormaais strategically sound.
static void induce_secondary_move_reasons(int color)
Any move that captures or defends a worm also connects or cuts the surrounding dragons. Find these secondary move reasons. We also let an owl attack count as a strategical defense of our neighbors of the owl attacked dragon. We only do this for tactically safe dragons, however, because otherwise the effects of capturing has already been taken into account elsewhere.
static void examine_move_safety(int color)
Examine the strategical and tactical safety of the moves. This is used to decide whether or not the stone should generate influence when the move is evaluated. The idea is to avoid overestimating the value of strategically unsafe defense moves and connections of dead dragons. This sets the move.move_safety field.
static float dragon_safety(int dr, int ignore_dead_dragons)
An attempt to estimate the safety of a dragon. Safety values are:
- DEAD
- ALIVE
- CRITICAL
- INESSENTIAL
- TACTICALLY DEAD
- WEAK
- WEAKLY ALIVE
- SEKI
- STRONGLY ALIVE
- INVINCIBLE
- INSUBSTANTIAL
static float connection_value(int dragona, int dragonb, int tt, float margin)
Strategical value of connecting (or cutting) the dragon atdragonato the dragon atdragonb. Notice that this function is assymetric. This is becauseconnection_value(a, b)is intended to measure the strategical value on the a dragon from a connection to the b dragon. The parametermarginis the margin by which we are ahead. If this exceeds 20 points we use the cautious impact values which value connections more. This is because we can afford to waste a move making sure of safety. If the margin is between 0 and 20 points we interpret linearly between the two sets of impact values. (Seevalue_moves.cfor more information.)
static float adjusted_worm_attack_value(int pos, int ww)
Usually the value of attacking a worm is twice its effective size, but when evaluating certain move reasons we need to adjust this to take effects on neighbors into account, e.g. for anATTACK_EITHERmove reason. This does not apply to the attack and defense move reasons, however, because then the neighbors already have separate attack or defense move reasons (if such apply). If the worm has an adjacent (friendly) dead dragon we add its value. At least one of the surrounding dragons must be alive. If not, the worm must produce an eye of sufficient size, and that should't be accounted for here. As a guess, we suppose that a critical dragon is alive for our purpose here. On the other hand if it has an adjacent critical worm, and ifposdoes not defend that worm, we subtract the value of the worm, sinceposmay be defended by attacking that worm. We make at most one adjustment of each type.
static void estimate_territorial_value(int pos, int color, float score)
Estimate the direct territorial value of a move at pos.
static void estimate_strategical_value(int pos, int color, float score)
Estimate the strategical value of a move at pos.
static int compare_move_reasons(const void *p1, const void *p2)
Compare two move reasons, used for sorting before presentation.
static float value_move_reasons(int pos, int color, float pure_threat_value, float score)
Combine the reasons for a move at pos into a simple numerical value.
static void value_moves(int color, float pure_threat_value, float score)
Loop over all possible moves and value the move reasons for each.
static void print_top_moves(void)
Search through all board positions for the 10 highest valued moves and print them.
static void reevaluate_ko_threats(int ko_move, int color)
This function is called if the biggest move on board was an illegal ko capture.
static void redistribute_points(void)
Redistribute points. When one move is declared a replacement for another by a replacement move reason, the move values for the inferior move are transferred to the replacement.
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.
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.
The array struct worm_data worm[MAX_BOARD] collects information about
the worms. We will give definitions of the various fields. Each field has
constant value at each vertex of the worm. We will define each field.
struct worm_data {
int color;
int size;
float effective_size;
int origin;
int liberties;
int liberties2;
int liberties3;
int liberties4;
int lunch;
int cutstone;
int cutstone2;
int genus;
int inessential;
int invincible;
int unconditional_status;
int attack_points[MAX_TACTICAL_POINTS];
int attack_codes[MAX_TACTICAL_POINTS];
int defense_points[MAX_TACTICAL_POINTS];
int defend_codes[MAX_TACTICAL_POINTS];
int attack_threat_points[MAX_TACTICAL_POINTS];
int attack_threat_codes[MAX_TACTICAL_POINTS];
int defense_threat_points[MAX_TACTICAL_POINTS];
int defense_threat_codes[MAX_TACTICAL_POINTS];
};
color
If the worm isBLACKorWHITE, that is its color. Cavities (empty worms) have an additional attribute which we call bordercolor. This will be one ofBLACK_BORDER,WHITE_BORDERorGRAY_BORDER. Specifically, if all the worms adjacent to a given empty worm have the same color (black or white) then we define that to be the bordercolor. Otherwise the bordercolor is gray.Rather than define a new field, we keep this data in the field color. Thus for every worm, the color field will have one of the following values:
BLACK,WHITE,GRAY_BORDER,BLACK_BORDERorWHITE_BORDER. The last three categories are empty worms classified by bordercolor.
size
This field contains the cardinality of the worm.
effective_size
This is the number of stones in a worm plus the number of empty intersections that are at least as close to this worm as to any other worm. Intersections that are shared are counted with equal fractional values for each worm. This measures the direct territorial value of capturing a worm. effective_size is a floating point number. Only intersections at a distance of 4 or less are counted.
origin
Each worm has a distinguished member, called its origin. The purpose of this field is to make it easy to determine when two vertices lie in the same worm: we compare their origin. Also if we wish to perform some test once for each worm, we simply perform it at the origin and ignore the other vertices. The origin is characterized by the test:worm[pos].origin == pos.
liberties
liberties2
liberties3
liberties4
For a nonempty worm the field liberties is the number of liberties of the string. This is supplemented byLIBERTIES2,LIBERTIES3andLIBERTIES4, which are the number of second order, third order, and fourth order liberties, respectively. The definition of liberties of order >1 is adapted to the problem of detecting the shape of the surrounding cavity. In particular we want to be able to see if a group is loosely surrounded. a liberty of order n is an empty vertex which may be connected to the string by placing n stones of the same color on the board, but no fewer. The path of connection may pass through an intervening group of the same color. The stones placed at distance >1 may not touch a group of the opposite color. Connections through ko are not permitted. Thus in the following configuration:.XX... We label the .XX.4. XO.... liberties of XO1234 XO.... order < 5 of XO1234 ...... the O group: .12.4. .X.X.. .X.X..The convention that liberties of order >1 may not touch a group of the opposite color means that knight's moves and one space jumps are perceived as impenetrable barriers. This is useful in determining when the string is becoming surrounded.
The path may also not pass through a liberty at distance 1 if that liberty is flanked by two stones of the opposing color. This reflects the fact that the O stone is blocked from expansion to the left by the two X stones in the following situation:
X. .O X.We say that n is the distance of the liberty of order n from the dragon.
lunch
If nonzero, lunch points to a boundary worm which can be easily
captured. (It does not matter whether or not the string can be
defended.)
We have two distinct notions of cutting stone, which we keep track
of in the separate fields worm.cutstone and worm.cutstone2.
We use currently use both concepts in parallel.
cutstone
This field is equal to 2 for cutting stones, 1 for potential cutting stones. Otherwise it is zero. Definitions for this field: a cutting stone is one adjacent to two enemy strings, which do not have a liberty in common. The most common type of cutting string is in this situation:XO OXA potential cutting stone is adjacent to two enemy strings which do share a liberty. For example, X in:
XO O.For cutting strings we set
worm[].cutstone=2. For potential cutting strings we setworm[].cutstone=1.
cutstone2
Cutting points are identified by the patterns in the connections database. Proper cuts are handled by the fact that attacking and defending moves also count as moves cutting or connecting the surrounding dragons. Thecutstone2field is set duringfind_cuts(), called frommake_domains().
genus
There are two separate notions of genus for worms and dragons. The dragon notion is more important, sodragon[pos].genusis a far more useful field thanworm[pos].genus. Both fields are intended as approximations to the number of eyes. The genus of a string is the number of connected components of its complement, minus one. It is an approximation to the number of eyes of the string.
inessential
An inessential string is one which meets a criterion designed to guarantee that it has no life potential unless a particular surrounding string of the opposite color can be killed. More precisely an inessential string is a string S of genus zero, not adjacent to any opponent string which can be easily captured, and which has no edge liberties or second order liberties, and which satisfies the following further property: If the string is removed from the board, then the empty worm E which is the worm closure of the set of vertices which it occupied has bordercolor the opposite of the removed string. The empty worm E (empty, that is, as a worm of the board modified by removal of S) consists of the union of support of S together with certain other empty worms which we call the boundary components of S.The inessential strings are used in the amalgamation of cavities in
make_dragons().
invincible
An invincible worm is one which GNU Go thinks
cannot be captured. Invincible worms are computed by the
function unconditional_life() which tries to
find those worms of the given color that can never be captured,
even if the opponent is allowed an arbitrary number of consecutive
moves.
Unconditional status is also set by the functionunconditional_life. This is set ALIVE for stones which are invincible. Stones which can not be turned invincible even if the defender is allowed an arbitrary number of consecutive moves are given an unconditional status of DEAD. Empty points where the opponent cannot form an invincible worm are called unconditional territory. The unconditional status is set toWHITE_BORDERorBLACK_BORDERdepending on who owns the territory. Finally, if a stone can be captured but is adjacent to unconditional territory of its own color, it is also given the unconditional statusALIVE. In all other cases the unconditional status isUNKNOWN.To make sense of these definitions it is important to notice that any stone which is alive in the ordinary sense (even if only in seki) can be transformed into an invincible group by some number of consecutive moves. Well, this is not entirely true because there is a rare class of seki groups not satisfying this condition. Exactly which these are is left as an exercise for the reader. Currently
unconditional_life, which strictly follows the definitions above, calls such seki groups unconditionally dead, which of course is a misfeature. It is possible to avoid this problem by making the algorithm slightly more complex, but this is left for a later revision.
int attack_points[MAX_TACTICAL_POINTS]
attack_codes[MAX_TACTICAL_POINTS]
int defense_points[MAX_TACTICAL_POINTS];
int defend_codes[MAX_TACTICAL_POINTS];
If the tactical reading code (see Tactical Reading) finds that the worm can be attacked,attack_points[0]is a point of attack, andattack_codes[0]is the attack code,WIN,KO_AorKO_B. If multiple attacks are known,attack_points[k]andattack_codes[k]are used. Similarly with the defense codes and defense points.
int attack_threat_points[MAX_TACTICAL_POINTS];
int attack_threat_codes[MAX_TACTICAL_POINTS];
int defense_threat_points[MAX_TACTICAL_POINTS];
int defense_threat_codes[MAX_TACTICAL_POINTS];
These are points that threaten to attack or defend a worm.
The function makeworms() will generate data for all worms.
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.
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 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.
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.
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; the fields
attack_point[] point to up to 4 points to attack
the half eye, and similarly defense_point[] gives points
to defend the half eye.
struct half_eye_data half_eye[MAX_BOARD];
struct half_eye_data {
float value; /* Topological eye value */
int type; /* HALF_EYE or FALSE_EYE */
int num_attacks; /* Number of attacking points */
int attack_point[4]; /* The moves to attack a topological halfeye */
int num_defends; /* Number of defending points */
int defense_point[4]; /* The moves to defend a topological halfeye */
};
The array struct half_eye_data half_eye[MAX_BOARD]
contains information about half and false eyes. If the type is
HALF_EYE then up to four moves are recorded which can
either attack or defend the eye. In rare cases the attack points
could be different from the defense points.
The array struct dragon_data dragon[MAX_BOARD]
collects information about the dragons. We will give definitions of the
various fields. Each field has constant value at each vertex of the
dragon.
struct dragon_data {
int color;
int id;
int origin;
int size;
float effective_size;
int status;
int owl_threat_status;
int owl_status;
int owl_attack_point;
int owl_attack_code;
int owl_attack_certain;
int owl_second_attack_point;
int owl_defense_point;
int owl_defense_code;
int owl_defense_certain;
int owl_second_defense_point;
int matcher_status;
};
extern struct dragon_data dragon[BOARDMAX];
Other fields attached to the dragon are contained in the dragon_data2
struct array.
struct dragon_data2 {
int origin;
int adjacent[MAX_NEIGHBOR_DRAGONS];
int neighbors;
int hostile_neighbors;
int moyo;
int safety;
int escape_route;
int genus;
int heyes;
int heye;
int lunch;
int semeai;
int semeai_margin_of_safety;
};
extern struct dragon_data2 *dragon2;
The difference between the two arrays is that the dragon array
is indexed by the board, and there is a copy of the dragon data
at every stone in the dragon, while there is only one copy of
the dragon2 data. The dragons are numbered, and the id field
of the dragon is a key into the dragon2 array. Two macros DRAGON
and DRAGON2 are provided for gaining access to the two arrays.
#define DRAGON2(pos) dragon2[dragon[pos].id] #define DRAGON(d) dragon[dragon2[d].origin]
Thus if you know the position pos of a stone in the dragon
you can access the dragon array directly, for example accessing the
origin with dragon[pos].origin. However if you need a field
from the dragon2 array, you can access it using the DRAGON2 macro,
for example you can access its neighor dragons by
for (k = 0; k < DRAGON2(pos).neighbors; k++) {
int d = DRAGON2(pos).adjacent[k];
int apos = dragon2[d].origin;
do_something(apos);
}
Similarly if you know the dragon number (which is dragon[pos].id)
then you can access the dragon2 array directly, or you can
access the dragon array using the DRAGON macro.
Here are the definitions of each field in the dragon arrray.
color
For strings, this isBLACKorWHITE. For caves, it isBLACK_BORDER,WHITE_BORDERorGRAY_BORDER. The meaning of these concepts is the same as for worms.
id
The dragon number. This is a key into the dragon2 array.
origin
The origin of the dragon is a unique particular vertex of the dragon, useful for determining when two vertices belong to the same dragon. Before amalgamation the worm origins are copied to the dragon origins. Amalgamation of two dragons amounts to changing the origin of one.
size
This is the cardinality of the dragon.
effective_size
The sum of the effective sizes of the constituent worms.
Remembering that vertices equidistant between two or more worms are
counted fractionally in worm.effective_size, this equals the
cardinality of the dragon plus the number of empty vertices which are
nearer this dragon than any other.
genus
The genus of a nonempty dragon consists of the number of distinct adjacent caves whose bordercolor is the color of the dragon, minus the number of false eyes found. The genus is a computable approximation to the number of eyes a dragon has.
escape_route
This is a measure of the escape potential of the dragon. If
dragon.escape_route is large, GNU Go believes that the
dragon can escape, so finding two eyes locally becomes less
urgent. Further documentation may be found else where
(see Escape).
status
An attempt is made to classify the dragons asALIVE,DEAD,CRITICALorUNKNOWN. TheCRITICALclassification means that the fate of the dragon depends on who moves first in the area. The exact definition is in the functioncompute_dragon_status(). If the dragon is found to be surrounded, the status isDEADif it has less than 1.5 eyes or if the reading code determines that it can be killed,ALIVEif it has 2 or more eyes, andCRITICALif it has 1.5 eyes. A lunch generally counts as a half eye in these calculations. If it has less than 2 eyes but seems possibly able to escape, the status may beUNKNOWN.
owl_status
This is a classification similar todragon.status, but based on the life and death reading inowl.c. The owl code (see The Owl Code) is only run on dragons with dragon.escape_route>5 and dragon2.moyo>10. If these conditions are not met, the owl status isUNCHECKED. Ifowl_attack()determines that the dragon cannot be attacked, it is classified asALIVE. Otherwise,owl_defend()is run, and if it can be defended it is classified asCRITICAL, and if not, asDEAD.
owl_attack_code
If the owl code finds that the dragon can be attacked, this is the attack code. It may beWIN,KO_A,KO_B, or (if the dragon cannot be attacked) 0.
owl_attack_point
If the owl code finds that the dragon can be attacked, this is the point of attack.
owl_attack_certain
The functionowl_attack, which is used to setowl_attack_codeandowl_attack_point, is given an upper bound ofowl_node_limitin the number of nodes it is allowed to generate. If this is exceeded the result is considered uncertain and this flag is set.
owl_second_attack_point
Under certain circumstances the owl functionowl_threaten_attackis asked if the dragon can be killed with two moves in a row. If two such killing moves are found, they are cached inowl_attacki_point(owl_second_attack_point.
owl_defense_code
If the owl code finds that the dragon can be defended, this is the defense code (WIN,KO_A,KO_B); otherwise it is 0.
owl_defense_point
If the owl code finds that the dragon can be defended, this is the move.
owl_defense_certain
owl_second_defense_point
Similar to owl_attack_certain and
owl_second_attack_point.
matcher_status
This is the status used by the pattern matcher. Ifowl_statusis available (notUNCHECKED) this is used. Otherwise, we use thestatusfield, except that we upgradeDEADtoUNKNOWN.
Here are definitions of each field in the dragon2 array.
origin
Duplicates the origin field from the dragon array.
adjacent[MAX_NEIGHBOR_DRAGONS]
An array of adjacent dragons.
neighbors
The number of adjacent dragons.
hostile_neighbors
The number of adjacent dragons of the opposite color.
moyo
Size of the surrounding influence moyo. Computed by
compute_surrounding_moyo_sizes(), calling the influence code.
safety
This is a finer measure of dragon safety thanmatcher_status. In addition to the valuesALIVE,DEADandCRITICALit can take the valuesINESSENTIAL,TACTICALLY_DEAD,WEAK,WEAKLY_ALIVE,ALIVE_IN_SEKI,STRONGLY_ALIVEandINVINCIBLE.
escape_route
A measure of the escape potential of the dragon. Further documentation may be found elsewhere (see Escape).
genus
The "genus" of a nonempty dragon consists of the number of distinct adjacent caves whose bordercolor is the color of the dragon, minus the number of false eyes found. The genus is a computable approximation to the number of eyes a dragon has.
heyes
This is the number of half eyes the dragon has. A "half eye" is a pattern where an eye may or may not materialize, depending on who moves first.
heye
If any half eyes are found, this field points to a move which will create an eye.
lunch
If nonzero, this field points to the location of a boundary worm which can be easily capture. In contrast with the worm version of this parameter we exclude strings which cannot be saved.
semeai
True if the dragon is part of a semeai.
semeai_margin_of_safety
Small if the semeai is close. Currently not reliable.
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).
Here are the public functions in engine/worm.c:
void make_worms(int save_verbose)
This function finds all worms and assembles some data about them. Each worm is marked with an origin. This is an arbitrarily chosen element of the worm, in practice the algorithm puts the origin at the first element when they are given the lexicographical order, though its location is irrelevant for applications. To see if two stones lie in the same worm, compare their origins.
int is_same_worm(int w1, int w2)
Test whether two worms are the same. Used by autohelpers. Before this function can be called, build_worms must have been run.
int is_worm_origin(int w, int pos)
Test whether the origin of the worm atwispos.
void change_defense(int str, int move, int dcode)
change_defense(str, move, dcode)is used to add and remove defense points. It can also be used to change the defense code. The meaning of the call is that the stringstrcan be defended bymovewith defense codedcode. Ifdcodeis zero, the move is removed from the list of defense moves if it was previously listed.
void change_attack(int str, int move, int acode)
change_attack(str, move, acode)is used to add and remove attack points. It can also be used to change the attack code. The meaning of the call is that the stringstrcan be attacked bymovewith attack codeacode. Ifacodeis zero, the move is removed from the list of attack moves if it was previously listed.
void change_defense_threat(int str, int move, int dcode)
Used to add and remove defense threat points. It can also be used to change the defense threat code. The meaning of the call is that the stringstrcan threaten to be defended bymovewith defense threat codedcode. Ifdcodeis zero, the move is removed from the list of defense threat moves if it was previously listed.
void change_attack_threat(int str, int move, int acode)
Used to add and remove attack threat points. It can also be used to change the attack threat code. The meaning of the call is that the stringstrcan threaten to be attacked bymovewith attack threat codeacode. Ifacodeis zero, the move is removed from the list of attack threat moves if it was previously listed.
int attack_move_known(int move, int str)
Check whethermoveis listed as an attack point forstrand return the attack code. Ifmoveis not listed, return 0.
int defense_move_known(int move, int str)
Check whethermoveis listed as a defense point forstrand return the defense code. Ifmoveis not listed, return 0.
int attack_threat_move_known(int move, int str)
Check whethermoveis listed as an attack threat point forstrand return the attack threat code. Ifmoveis not listed, return 0.
int defense_threat_move_known(int move, int str)
Check whethermoveis listed as a defense threat point forstrand return the defense threat code. Ifmoveis not listed, return 0.
void propagate_worm(int pos)
propagate_worm() takes the worm data at one stone and copies it to the remaining members of the worm.
Here are the public functions in engine/dragon.c:
void make_dragons(int color, int stop_before_owl, int save_verbose)
This basic function finds all dragons and collects some basic information about them in the dragon array.coloris the player in turn to move. This does in no way affect the information collected about the dragons, but it does affect what information is passed on to the move generation code. Ifcolor == EMPTYno information at all is passed on to the move generation.
void show_dragons(void)
print status info on all dragons. (Can be invoked from gdb).
int is_same_dragon(int d1, int d2)
Test whether two dragons are the same. Used by autohelpers and elsewhere.
int are_neighbor_dragons(int d1, int d2)
Test whether two dragons are neighbors.
void ascii_report_dragon(char *string)
void report_dragon(int m, int n)
For use in gdb, print details of the dragon. Add this to your.gdbinitfile:define dragon set ascii_report_dragon("$arg0") endNow 'dragon S8' will report the details of the S8 dragon.
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 sometimes more
accurate. You can enable it by using the option --life.
optics.c
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
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
optics.c.
The eyespaces can be conveniently displayed using a colored
ascii diagram by running gnugo -E.
In the abstraction, an eyespace consists of a set of vertices labelled:
! . X
Tables of many eyespaces are found in the database
patterns/eyes.db. Each of these may be thought of as a local
game. The result of this game is listed after the eyespace in the form
:max,min, where max is the number of eyes the pattern
yields if O moves first, while min is the number of eyes
the pattern yields if X moves first. The player who owns the eye
space is denoted O throughout this discussion. Since three eyes
are no better than two, there is no attempt to decide whether the space
yields two eyes or three, so max never exceeds 2. Patterns with min>1
are omitted from the table.
For example, we have:
Pattern 548 x 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 model.
|- X - X X - - X O X O |X - - - - - X X O O O |O X X X X - - X O O O |O O O O X - O X O O O |1 2 . . O O O O X X O |X O . X X X . 3 X O O |X O O O O O O O X X O |- X X O - O X O - - X |X - - X - X X X X X X |O X X O X - X O O X O
We will not attempt to characterize the terminal states of the local game (some of which could be seki) or the scoring.
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) ... ...! ! (afterO's move) . . ...! ! (afterX's move) . . ..X! . . ..X! . ! .!
It is a useful observation that the local game associated with an eyespace depends only on the underlying graph, which as a set consists of the set of vertices, in which two elements are connected by an edge if and only if they are adjacent on the Go board. For example the two eye shapes:
.. .. and ....
though distinct in shape have isomorphic graphs, and consequently
they are isomorphic as local games. This reduces the number of
eyeshapes in the database patterns/eyes.db.
A further simplification is obtained through our treatment of half eyes and false eyes. Such patterns are identified by the topological analysis (see Eye Topology).
A half eye is isomorphic to the pattern (!.) . To see this,
consider the following two eye shapes:
XOOOOOO X.....O XOOOOOO and: XXOOOOO XOa...O XbOOOOO XXXXXXX
These are equivalent eyeshapes, with isomorphic local games {2|1}. The first has shape:
!....
The second eyeshape has a half eye at a which is taken when O
or X plays at b. This is found by the topological
criterion (see Eye Topology).
The graph of the eye_shape, ostensibly .... is modified by replacing
the left . by !. during graph matching.
A false eye is isomorphic to the pattern (!) . To see this,
consider the following eye shape:
XXXOOOOOO X.Oa....O XXXOOOOOO
This is equivalent to the two previous eyeshapes, with an isomorphic local game {2|1}.
This eyeshape has a false eye at a. This is also found by the
topological criterion.
The graph of the eye_shape, ostensibly ..... is modified by replacing
the left . by !. This is made directly in the eye data,
not only during graph matching.
The patterns in patterns/eyes.db are compiled into graphs
represented essentially by arrays in patterns/eyes.c.
Each actual eye space as it occurs on the board is also compiled into a graph. Half eyes are handled as follows. Referring to the example
XXOOOOO XOa...O XbOOOOO XXXXXX
repeated from the preceding discussion, the vertex at b is
added to the eyespace as a marginal vertex. The adjacency
condition in the graph is a macro (in optics.c): two
vertices are adjacent if they are physically adjacent,
or if one is a half eye and the other is its key point.
In recognize_eyes(), each such graph arising from an actual eyespace is
matched against the graphs in eyes.c. If a match is found, the
result of the local game is known. If a graph cannot be matched, its
local game is assumed to be {2|2}.
A HALF EYE is a pattern where an eye may or may not materialize,
depending on who moves first. Here is a half eye for O:
OOXX O.O. OO.X
A FALSE EYE is a cave which cannot become an eye. Here are
two examples of false eyes for O:
OOX OOX O.O O.OO XOO OOX
We describe now the topological algorithm used to find half eyes and false eyes. In this section we ignore the possibility of ko.
False eyes and half eyes can locally be characterized by the status of the diagonal intersections from an eye space. For each diagonal intersection, which is not within the eye space, there are three distinct possibilities:
X) stone, which cannot be captured.
X can safely play there, or occupied
by an X stone that can both be attacked and defended.
O stone, an X stone that can be attacked
but not defended, or it's empty and X cannot safely play there.
We give the first possibility a value of two, the second a value of one, and the last a value of zero. Summing the values for the diagonal intersections, we have the following criteria:
If the eye space is on the edge, the numbers above should be decreased by 2. An alternative approach is to award diagonal points which are outside the board a value of 1. To obtain an exact equivalence we must however give value 0 to the points diagonally off the corners, i.e. the points with both coordinates out of bounds.
The algorithm to find all topologically false eyes and half eyes is:
For all eye space points with at most one neighbor in the eye space, evaluate the status of the diagonal intersections according to the criteria above and classify the point from the sum of the values.
This section extends the topological eye analysis to handle ko. We
distinguish between a ko in favor of O' and one in favor of X:
.?O? good for O OO.O O.O? XOX. .X.. .?O? good for X OO.O OXO? X.X. .X..
Preliminarily we give the former the symbolic diagonal value a
and the latter the diagonal value b. We should clearly have
0 < a < 1 < b < 2. Letting e be the topological eye value
(still the sum of the four diagonal values), we want to have the
following properties:
e <= 2 - proper eye 2 < e < 3 - worse than proper eye, better than half eye e = 3 - half eye 3 < e < 4 - worse than half eye, better than false eye e >= 4 - false eye
In order to determine the appropriate values of a and b we
analyze the typical cases of ko contingent topological eyes:
.X.. (slightly) better than proper eye
(a) ..OO e < 2
OO.O
O.OO e = 1 + a
XOX.
.X..
.X.. better than half eye, worse than proper eye
(a') ..OO 2 < e < 3
OO.O
OXOO e = 1 + b
X.X.
.X..
.X.. better than half eye, worse than proper eye
(b) .XOO 2 < e < 3
OO.O
O.OO e = 2 + a
XOX.
.X..
.X.. better than false eye, worse than half eye
(b') .XOO 3 < e < 4
OO.O
OXOO e = 2 + b
X.X.
.X..
.X..
XOX. (slightly) better than proper eye
(c) O.OO e < 2
OO.O
O.OO e = 2a
XOX.
.X..
.X..
XOX. proper eye, some aji
(c') O.OO e ~ 2
OO.O
OXOO e = a + b
X.X.
.X..
.X..
X.X. better than half eye, worse than proper eye
(c'') OXOO 2 < e < 3
OO.O
OXOO e = 2b
X.X.
.X..
.X...
XOX.. better than half eye, worse than proper eye
(d) O.O.X 2 < e < 3
OO.O.
O.OO. e = 1 + 2a
XOX..
.X...
.X...
XOX.. half eye, some aji
(d') O.O.X e ~ 3
OO.O.
OXOO. e = 1 + a + b
X.X..
.X...
.X...
X.X.. better than false eye, worse than half eye
(d'') OXO.X 3 < e < 4
OO.O.
OXOO. e = 1 + 2b
X.X..
.X...
.X...
XOX.. better than false eye, worse than half eye
(e) O.OXX 3 < e < 4
OO.O.
O.OO. e = 2 + 2a
XOX..
.X...
.X...
XOX.. false eye, some aji
(e') O.OXX e ~ 4
OO.O.
OXOO. e = 2 + a + b
X.X..
.X...
.X...
X.X.. (slightly) worse than false eye
(e'') OXOXX 4 < e
OO.O.
OXOO. e = 2 + 2b
X.X..
.X...
It may seem obvious that we should use
(i) a=1/2, b=3/2but this turns out to have some drawbacks. These can be solved by using either of
(ii) a=2/3, b=4/3 (iii) a=3/4, b=5/4 (iv) a=4/5, b=6/5
Summarizing the analysis above we have the following table for the
four different choices of a and b.
case symbolic a=1/2 a=2/3 a=3/4 a=4/5 desired
value b=3/2 b=4/3 b=5/4 b=6/5 interval
(a) 1+a 1.5 1.67 1.75 1.8 e < 2
(a') 1+b 2.5 2.33 2.25 2.2 2 < e < 3
(b) 2+a 2.5 2.67 2.75 2.8 2 < e < 3
(b') 2+b 3.5 3.33 3.25 3.2 3 < e < 4
(c) 2a 1 1.33 1.5 1.6 e < 2
(c') a+b 2 2 2 2 e ~ 2
(c'') 2b 3 2.67 2.5 2.4 2 < e < 3
(d) 1+2a 2 2.33 2.5 2.6 2 < e < 3
(d') 1+a+b 3 3 3 3 e ~ 3
(d'') 1+2b 4 3.67 3.5 3.4 3 < e < 4
(e) 2+2a 3 3.33 3.5 3.6 3 < e < 4
(e') 2+a+b 4 4 4 4 e ~ 4
(e'') 2+2b 5 4.67 4.5 4.4 4 < e
We can notice that (i) fails for the cases (c"), (d), (d"), and (e).
The other three choices get all values in the correct intervals. The
main distinction between them is the relative ordering of (c") and (d)
(or analogously (d") and (e)). If we do a more detailed analysis of
these we can see that in both cases O can secure the eye
unconditionally if he moves first while X can falsify it with ko
if he moves first. The difference is that in (c"), X has to make
the first ko threat, while in (d), O has to make the first ko threat.
Thus (c") is better for O and ought to have a smaller topological eye
value than (d). This gives an indication that (iv) is the better choice.
We can notice that any value of a, b satisfying
a+b=2 and 3/4<a<1 would have the same qualities as choice
(iv) according to the analysis above. One interesting choice is
a=7/8, b=9/8 since these allow exact computations with floating
point values having a binary mantissa. The latter property is shared by
a=3/4 and a=1/2.
When there are three kos around the same eyespace, things become more complex. This case is, however, rare enough that we ignore it.
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!).
optics.cHere are the public functions in optics.c, except some simple
access functions used by autohelpers. The statically declared functions
are documented in the source code.
void make_domains(struct eye_data b_eye[BOARDMAX], struct eye_data w_eye[BOARDMAX], int owl_call)
This function is called frommake_dragons()and fromowl_determine_life(). It marks the black and white domains (eyeshape regions) and collects some statistics about each one.
void compute_eyes(int pos, int *max, int *min, int *attack_point, int *defense_point, struct eye_data eye[BOARDMAX], struct half_eye_data heye[BOARDMAX], int add_moves, int color)
Given an eyespace with origin pos, this function computes the
minimum and maximum numbers of eyes the space can yield. If max and
min are different, then vital points of attack and defense are also
generated.
void compute_eyes_pessimistic(int pos, int *max, int *min, int *pessimistic_min, int *attack_point, int *defense_point, struct eye_data eye[BOARDMAX], struct half_eye_data heye[BOARDMAX])
This function works like compute_eyes(), except that it also gives
a pessimistic view of the chances to make eyes.
void propagate_eye(int origin, struct eye_data eye[BOARDMAX])
Copies the data at origin to the rest of the eye (invariant
fields only).
static int recognize_eye(int pos, int *attack_point, int *defense_point, int *max, int *min, struct eye_data eye[BOARDMAX], struct half_eye_data heye[BOARDMAX], int add_moves, int color)
Declared static but documented here because of its importance. The life code supplies an alternative version of this function calledrecognize_eye2(). Hereposis the origin of an eyespace. Returns 1 if there is a pattern ineyes.dbmatching the eyespace, or 0 if no match is found. If there is a key point for attack,*attack_pointis set to its location, orNO_MOVEif there is none. Similarly*defense_pointis the location of a vital defense point.*minand*maxare the minimum and maximum number of eyes that can be made in this eyespace respectively. Vital attack/defense points exist if and only if*min != *max. Ifadd_moves==1, this function may add a move_reason forcolorat a vital point which is found by the function. Ifadd_moves==0, setcolor==EMPTY.
void add_false_eye(int pos, struct eye_data eye[BOARDMAX], struct half_eye_data heye[BOARDMAX])
This function turns a proper eyespace into a margin.
float topological_eye(int pos, int color, struct eye_data b_eye[BOARDMAX], struct eye_data w_eye[BOARDMAX], struct half_eye_data heye[BOARDMAX])
See See Eye Topology. Evaluate the eye space atpostopologically (see Eye Topology). Returns 2 or less ifposis a proper eye forcolor; between 2 and 3 if the eye can be made false only by ko; 3 ifposis a half eye; between 3 and 4 if the eye can be made real only by ko; 4 ifposis a false eye. Attack and defense points for control of the diagonals are stored in theheye[]array.
connections.c
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:
|oOO? |...X |..*? |..o. |..o? :8,ed,NULL
The program mkpat is capable of parsing patterns written this
way, or for that matter, on the top or right edges, or in any
of the four corners. As a matter of convention all the edge patterns
in patterns.db are written on the bottom edge or in the lower left
corners. In the patterns/ directory there is a program called
transpat which can rotate or otherwise transpose patterns.
This program is not built by default--if you think you need it,
make transpat in the patterns/ directory and
consult the usage remarks at the beginning of patterns/transpat.c.
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.
s
Safety of the move is not checked. This is appropriate for sacrifice patterns. If this classification is omitted, the matcher requires that the stone played cannot be trivially captured. Even with s classification, a check for legality is made, though.
n
In addition to usual check that the stone played cannot be trivially captured, it is also confirmed that an opponent move here could not be captured.
O
It is checked that every friendly (O) stone of the pattern belongs to a dragon which has matcher_status (see Dragons)ALIVEorUNKNOWN. TheCRITICALmatcher status is excluded. It is possible for a string to haveALIVEmatcher_status and still be tactically critical, since it might be amalgamated into an ALIVE dragon, and the matcher status is constant on the dragon. Therefore, an additional test is performed: if the pattern contains a string which is tactically critical, and if*does not rescue it, the pattern is rejected.
o
It is checked that every friendly (O) stone of the pattern belongs to a dragon which is classified asDEADorUNKNOWN.
X
It is checked that every opponent (X) stone of the pattern belongs to a dragon with matcher_statusALIVE,UNKNOWNorCRITICAL. Note that there is an asymmetry withOpatterns, whereCRITICALdragons are rejected.
x
It is checked that every opponent (X) stone of the pattern belongs to a dragon which is classified asDEADorUNKNOWN
C
If two or more distinct O dragons occur in the pattern, the move is given the move reasons that it connects each pair of dragons. An exception is made for dragons where the underlying worm can be tactically captured and is not defended by the considered move.
c
Add strategical defense move reason for all our dragons and a small shape bonus. This classification is appropriate for weak connection patterns.
B
If two or more distinct X dragons occur in the pattern, the
move is given the move reasons that it cuts each pair of
dragons.
b
The move secures territory by blocking it from intrusion.
e
The move makes territory by expanding, e.g. along the edge.
E
The move attempts increase influence and create/expand a moyo.
d
The move strategically defends all O dragons in the pattern, except those that can be tactically captured and are not tactically defended by this move. If any O dragon should happen to be perfectly safe already, this only reflects in the move reason being valued to zero.
a
The move strategically attacks all X dragons in the pattern.
J
Standard joseki move. Unless there is an urgent move on the board these moves are made as soon as they can be. This is equivalent to adding thedandaclassifications together with a minimum accepted value of 27.
F
This indicates a fuseki pattern. This is only effective together with either thejortclassification, and is used to ensure indeterministic play during fuseki.
j
Slightly less urgent joseki move. These moves will be made after those with theJclassification. This adds theeandEclassifications. If the move has theFclassification, it also gets a fixed value of 20.1, otherwise it gets a minimum accepted value of 20. (This makes sure that GNU Go chooses randomly between different moves that havejFas classification.)
t
Minor joseki move (tenuki OK). This is equivalent to adding theeandEclassifications together with either a fixed value of 15.07 (if the move hasFclassification) or a minimum value of 15 (otherwise).
U
Urgent joseki move (never tenuki). This is equivalent to thedandaclassifications together with a shape bonus of 15 and a minimum accepted value of 40.
A commonly used class is OX (which rejects pattern if either side
has dead stones). The string - may be used as a placeholder. (In
fact any characters other than the above and , are ignored.)
The types o and O could conceivably appear in a class, meaning it
applies only to UNKNOWN. X and x could similarly be used together.
All classes can be combined arbitrarily.
The second and following fields in the : line of a pattern
are optional and of the form value1(x),value2(y),.... The available set
of values are as follows.
terri(x)
Forces the territorial value of the move to be at least x.
minterri(x)
Forces the territorial value of the move to be at least x.
maxterri(x)
Forces the territorial value of the move to be at most x.
value(x)
Forces the final value of the move to be at least x.
minvalue(x), maxvalue(x)
Forces the final value of the move to be at least/most x.
shape(x)
Adds x to the move's shape value.
followup(x)
Adds x to the move's followup value.
The meaning of these values is documented in See Move Generation.
Helper functions can be provided to assist the matcher in deciding
whether to accept a pattern, register move reasons, and setting
various move values. The helper is supplied with the compiled pattern
entry in the table, and the (absolute) position on the board of the
* point.
One difficulty is that the helper must be able to cope with all the possible transformations of the pattern. To help with this, the OFFSET macro is used to transform relative pattern coordinates to absolute board locations.
The actual helper functions are in helpers.c. They are declared
in patterns.h.
As an example to show how to write a helper function, we consider
a hypothetical helper called wedge_helper. Such a helper
used to exist, but has been replaced by a constraint. Due to
its simplicity it's still a good example. The helper begins with a
comment:
/* ?O. ?Ob .X* aX* ?O. ?Oc :8,C,wedge_helper */
The image on the left is the actual pattern. On the right we've taken
this image and added letters to label apos, bpos, and
cpos. The position of *, the point where GNU Go will move if the
pattern is adopted, is passed through the parameter move.
int
wedge_helper(ARGS)
{
int apos, bpos, cpos;
int other = OTHER_COLOR(color);
int success = 0;
apos = OFFSET(0, -2);
bpos = OFFSET(-1, 0);
cpos = OFFSET(1, 0);
if (TRYMOVE(move, color)) {
if (TRYMOVE(apos, other)) {
if (board[apos] == EMPTY || attack(apos, NULL))
success = 1;
else if (TRYMOVE(bpos, color)) {
if (!safe_move(cpos, other))
success = 1;
popgo();
}
popgo();
}
popgo();
}
return success;
}
The OFFSET lines tell GNU Go the positions of the three stones at
a, b, and c. To decide whether the pattern
guarantees a connection, we do some reading. First we use the
TRYMOVE macro to place an O at move and let
X draw back to a. Then we ask whether O can capture
these stones by calling attack(). The test if there is a stone at
a before calling attack() is in this position not really
necessary but it's good practice to do so, because if the attacked stone
should happen to already have been captured while placing stones, GNU Go
would crash with an assertion failure.
If this attack fails we let O connect at b and use the
safe_move() function to examine whether a cut by X at
c could be immediately captured. Before we return the result we
need to remove the stones we placed from the reading stack. This is done
with the function popgo().
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.
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.
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.
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.
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
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
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.
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.
Here are the public functions in connections.c.
static void cut_connect_callback(int m, int n, int color,
struct pattern *pattern, int ll, void *data)
Try to match all (permutations of) connection patterns at(m,n). For each match, if it is a B pattern, set cutting point in worm data structure and make eye space marginal for the connection inhibiting entries of the pattern. If it is aCpattern, amalgamate the dragons in the pattern.
void find_cuts(void)
Find cutting points which should inhibit amalgamations and sever
the adjacent eye space. This goes through the connection database
consulting only patterns of type B. When such a function is found,
the function cut_connect_callback is invoked.
void find_connections(void)
Find explicit connection patterns and amalgamate the involved dragons.
This goes through the connection database consulting patterns except those of
type B, E or e. When such a function is found, the function
cut_connect_callback is invoked.
Find explicit connection patterns and amalgamate the involved dragons.
This goes through the connection database consulting only patterns
of type E (see Connections Database). When such a function is found, the
function cut_connect_callback is invoked.
Find explicit connection patterns and amalgamate the involved dragons.
This goes through the connection database consulting only patterns
of type e (see Connections Database). When such a function is found, the
function cut_connect_callback is invoked.
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.
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)
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 \.
X or
an O. This helps performance, since all transformations can be
rejected at once if the anchor stone does not match. (Ideally, we
could just define that the anchor is always O or always X, but some
patterns contain no O and some contain no X.)
? 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
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.
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.
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:
SQ or MA property) to decide how large part of the
board should be included in the pattern.
W or B property) with the natural interpretation.
If the square mark is missing or the move is a pass, no pattern is
produced for the node.
LB property), which must be a single letter each.
If there is at least one label, a constraint diagram will be
produced with these labels.
C property). As the first character it should have one of the
following characters to decide its classification:
U - urgent move
S or J - standard move
s or j - lesser joseki
T - trick move
t - minor joseki move (tenuki OK)
0 - antisuji (A can also be used)
In addition to this, rows starting with the following characters are recognized:
# - Comments. These are copied into the patterns file, above the diagram.
; - Constraints. These are copied into the patterns file, below the
constraint diagram.
> - Actions. These are copied into the patterns file, below the
constraint diagram.
: - Colon line. This is a little more complicated, but the colon
line of the produced patterns always start out with ":8,s" for
transformation number and sacrifice pattern class (it usually
isn't a sacrifice, but it's pointless spending time checking for
tactical safety). Then a joseki pattern class character is
appended and finally what is included on the colon line in the
comment for the SGF node.
Example: If the comment in the SGF file looks like
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,*)
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.
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). Since GNU Go 3.2, this is enabled
by default. You can still get back the traditional pattern matcher
by running configure --disable-dfa and then recompiling
GNU Go.
Otherwise, a finite state machine called a Deterministic Finite State Automaton (What is a DFA) will be built off line from the pattern database. This is used at runtime to speedup pattern matching (Pattern matching with DFA and Incremental Algorithm). The runtime speedup is at the cost of an increase in memory use and compile time.
The general idea is as follows:
For each intersection of the board, its neighbourhood is scanned following
a predefined path. The actual path used does not matter very much; GNU Go
uses a spiral as shown below.
In each step of the path, the pattern matcher jumps into a state determined by what it has found on the board so far. If we have successfully matched one or several patterns in this step, this state immediately tells us so (in its attribute). But the state also implicitly encodes which further patterns can still get matched: The information stored in the state contains in which state to jump next, depending on whether we find a black, white or empty intersection (or an intersection out of board) in the next step of the path. The state will also immediately tell us if we cannot find any further pattern (by telling us to jump into the error state).
These sloppy explanations may become clearer with the definitions in the next section (What is a DFA).
Reading the board following a predefined path reduces the two dimentional pattern matching to a linear text searching problem. For example, this pattern
?X? .O? ?OO
scanned following the path
B C4A 5139 628 7
gives the string "OO?X.?*O*?*?" where "?" means 'don't care' and "*" means 'don't care, can even be out of board'.
So we can forget that we are dealing with two dimensional patterns and consider linear patterns.
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:
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:
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.
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;
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.
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:
Give by synchronization product the following one:
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.
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.
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.
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.
engine/reading.c
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(str, &apos) will return WIN
if the string at str can be captured. The point of attack
(in case it is vulnerable) is returned in apos. However
many times we do not care about the point of attack. In this
case, we can substitute a null pointer: attack(str,
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 16 in the
distribution, but it may also be set at the command line using
the -D or --depth option. If depth is
increased, GNU Go will be stronger and slower. GNU Go will read
moves past depth, but in doing so it makes simplifying
assumptions that can cause it to miss moves.
Specifically, when stackp > depth, GNU Go assumes that as
soon as the string can get 3 liberties it is alive. This
assumption is sufficient for reading ladders.
The branch_depth is typically set a little below depth.
Between branch_depth and depth, attacks on strings with
3 liberties are considered, but branching is inhibited, so fewer
variations are 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 12. Below
this depth, GNU Go will try "backfilling" to capture stones.
For example in this situation:
.OOOOOO. on the edge of the board, O can capture X but OOXXXXXO in order to do so he has to first play at a in .aObX.XO preparation for making the atari at b. This is -------- called backfilling.
Backfilling is only tried with stackp <= backfill_depth. The
parameter backfill_depth may be set using the -B
option.
The fourlib_depth is a parameter with a default of only 7.
Below this depth, GNU Go will try to attack strings with
four liberties. The fourlib_depth may be set using the
-F option.
The parameter ko_depth is a similar cutoff. If
stackp<ko_depth, the reading code will make experiments
involving taking a ko even if it is not legal to do so (i.e., it
is hypothesized that a remote ko threat is made and answered
before continuation). This parameter may be set using the
-K option.
A partial list of the functions in reading.c (see Reading Functions for a fuller list).
int attack(int str, int *move)
This basic function determines if the string atstrcan be attacked, and if so,*movereturns the attacking move, unless*moveiis a null pointer. (Use null pointers if you are interested in the result of the attack but not the attacking move itself.) Returns 1 if the attack succeeds, otherwise 0. ReturnsKO_AorKO_Bif the result depends on ko: returnsKO_Aif the attack succeeds provided attacker is willing to ignore any ko threat. ReturnsKO_Bif attack succeeds provided attacker has a ko threat which must be answered.
find_defense(int str, int *move)
Attempts to find a move that will save the string atstr. It returns true if such a move is found, with*movethe location of the saving move (unless*moveare null pointers). It is not checked that tenuki defends, so this may give an erroneous answer if!attack(str). ReturnsKO_AorKO_Bif the result depends on ko. ReturnsKO_Aif the string can be defended providedcoloris willing to ignore any ko threat. ReturnsKO_Bifcolorhas a ko threat which must be answered.
safe_move(int str, int color) :
The functionsafe_move(str, color)checks whether a move atstris illegal or can immediately be captured. Ifstackp==0the result is cached. If the move only can be captured by a ko, it's considered safe. This may or may not be a good convention.
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().
hash.h
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:
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.
These random numbers are generated once at initialization time and then used throughout the life time of the hash table.
The hash table consists of 3 parts:
Each Read Result contains:
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.
The basic hash structures are declared in engine/hash.h and
engine/cache.c
typedef struct hashposition_t {
Compacttype board[COMPACT_BOARD_SIZE];
int ko_pos;
} 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 data1;
unsigned int data2;
struct read_result_t *next;
} Read_result;
The data1 field packs into 32 bits the following fields:
komaster: 2 bits (EMPTY, BLACK, WHITE, or GRAY) kom_pos : 10 bits (allows MAX_BOARD up to 31) routine : 4 bits (currently 10 different choices) str1 : 10 bits stackp : 5 bits
The data2 field packs into 32 bits the following fields:
status : 2 bits (0 free, 1 open, 2 closed) result1: 4 bits result2: 4 bits move : 10 bits str2 : 10 bits
The komaster and (kom_pos) field are
documented in See Ko.
When a new result node is created, 'status' is set to 1 'open'. This is then set to 2 'closed' when the result is entered. The main use for this is to identify open result nodes when the hashtable is partially cleared. Another potential use for this field is to identify repeated positions in the reading, in particular local double or triple 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:
The following functions are defined in hash.c:
void hash_init()
Initialize the entire hash system.
int hashdata_compare(Hash_data *key1, Hash_data *key2)
Returns 0 if *key1 == *key2, 2 if the hashvalues differ, or 1 if
only the hashpositions differ.
This adheres (almost) to the standard compare function semantics
which are used e.g. by the comparison functions used in qsort().
void hashposition_dump(Hashposition *pos, FILE *outfile)
Dump an ASCII representation of the contents of a Hashposition onto the FILE outfile.
int hashdata_diff_dump(Hash_data *key1,Hash_data *key2 )
Compare two Hashdata structs. If equal: return zero. If not: dump a human readable summary of any differences to stderr. The return value is the same as for hashdata_compare. This function is primarily intended to be used in assert statements.
void hashdata_recalc(Hash_data *target, Intersection *p, int kopos)
Calculate the compactboard and the hashvalue in one function. They are always used together and it saves us a loop and a function call.
void hashdata_set_ko(Hash_data *hd, int pos)
Set or remove a ko at pos.
void hashdata_remove_ko(Hash_data *hd)
Remove any ko from the hash value and hash position.
void hashdata_invert_stone(Hash_data *hd, int pos, int color)
Set or remove a stone ofcoloratposin a Hash_data.
void read_result_dump(Read_result *result, FILE *outfile)
Dump an ASCII representation of the contents of a Read_result onto the FILE outfile.
void hashnode_dump(Hashnode *node, FILE *outfile)
Dump an ASCII representation of the contents of a Hashnode onto the FILE outfile.
int hashtable_init(Hashtable *table, int tablesize, int num_nodes, int num_results)
Initialize a hash table for a given total size and size of the hash table. Returns 0 if something went wrong. Just now this means that there wasn't enough memory available.
Hashtable * hashtable_new(int tablesize, int num_nodes, int num_results)
Allocate a new hash table and return a pointer to it. Return NULL if there is insufficient memory.
void hashtable_clear(Hashtable *table)
Clear an existing hash table.
void hashtable_clear_if_full(Hashtable *table)
Clear an existing hash table only if it happens to be full. By full we mean that we are either out of positions or read results.
Hashnode * hashtable_enter_position(Hashtable *table, Hash_data *hd)
Enter a position with a given hash value into the table. Return a pointer to the hash node where it was stored. If it is already there, don't enter it again, but return a pointer to the old one.
Hashnode * hashtable_search(Hashtable *table, Hash_data *hd)
Given a Hashposition and a Hash value, find the hashnode which contains this position with the given hash value.
void hashtable_dump(Hashtable *table, FILE *outfile)
Dump an ASCII representation of the contents of a Hashtable onto the FILE outfile.
The following macros are defined in hash.h
rr_get_komaster(rr)
rr_get_kom_pos(rr)
rr_get_routine(rr)
rr_get_str1(rr)
rr_get_stackp(rr)
rr_get_str2(rr)
rr_get_str(rr)
rr_get_status(rr)
rr_get_result1(rr)
rr_get_result2(rr)
rr_get_move(rr)
rr_get_result(rr)
Get the constituent parts of a Read_result.
The following macros and functions are defined in
engine/reading.c:
static int get_read_result(int routine, int *si, int *sj, Read_result **read_result)
Return a Read_result for the current position, routine and location. For performance, the location is changed to the origin of the string.
READ_RETURN0(Read_result *read_result)
Cache a negative read result.
READ_RETURN(Read_result *read_result, int *pointi, int *pointj, int resulti, int resultj, int value)
Ifpointiandpointjare not null pointers, then give(*pointi, *pointj)the values(resulti, resultj). Then cache theread_result. Clear the hashtable if full and returnvalue.
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.
1. We also include the successful
move, which is most often a part of the reading shadow, but
sometimes not, for example with the function attack1().
1 with
the character 2.
2 are
labelled with the character 3.
-1 instead of the more logical 4 because it
is slightly faster to code this way.
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_pos. 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_pos is set to the location of the captured ko
stone.
If the opponent is komaster, the reading functions will not try to
take the ko at kom_pos. Also, the komaster is normally not
allowed to take another ko. The exception is a nested ko, characterized
by the condition that the captured ko stone is at distance 1 both
vertically and horizontally from kom_pos, which is the location
of the last stone taken by the komaster. Thus in this situation:
.OX
OX*X
OmOX
OO
Here if m is the location of kom_pos, then the move at
* is allowed.
The rationale behind this rule is that in the case where there are two kos on the board, the komaster cannot win both, and by becoming komaster he has already chosen which ko he wants to win. But in the case of a nested ko, taking one ko is a precondition to taking the other one, so we allow this.
If the komaster's opponent takes a ko, then both players have taken
one ko. In this case komaster is set to GRAY and after this further
ko captures are not allowed.
If the ko at kom_pos is filled, then the komaster
reverts to EMPTY.
The komaster scheme used in GNU Go 3.0 is known as komaster scheme 1.
It may be summarized as follows. It is assumed that O is about to move.
EMPTY.
EMPTY.
O and
kom_pos to the location of the ko, where a stone was
just removed.
O:
kom_pos then komaster reverts to
EMPTY.
X:
kom_pos is not allowed. Any other ko capture
is allowed. If O takes another ko, komaster becomes GRAY.
GRAY:
kom_pos is
filled then the komaster reverts to EMPTY.
In GNU Go 3.2 a new komaster scheme 5 is used. It may be described as follows.
Komaster remains EMPTY if previous move was not a ko capture. Komaster is set to WEAK_KO if previous move was a ko capture and kom_pos is set to the old value of board_ko_pos.
Komaster is set to O and kom_pos to the location of the ko, where a stone was just removed.
Play at kom_pos is not allowed. Any other ko capture is allowed. If O takes another ko, komaster becomes GRAY_X.
Ko captures are not allowed. If the ko at kom_pos is filled then the komaster reverts to EMPTY.
Komaster is changed to WEAK_X and kom_pos to the old value of board_ko_pos.
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_pos: A2 6 . . O . . . . . 5 O O O . . . . . 4 O X O O . . . . 3 X . X O O O O . 2 . X X X O . . . 1 X O . . . . . . A B C D E F G H
W takes the ko at B3 after which the komaster is GRAY and
ko recaptures are not allowed.
8 . . . . . . . . komaster: GRAY 7 . . O . . . . . kom_pos: B4 6 . . O . . . . . 5 O O O . . . . . 4 O . O O . . . . 3 X O X O O O O . 2 . X X X O . . . 1 X O . . . . . . A B C D E F G H
Since B is not allowed any ko recaptures, there is nothing he can do and he is found dead. Thus the komaster scheme produces the correct result.
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 unconditionally while K2
defends it with ko (code KO_A).
After Black (X) takes the ko at K3, white can do nothing but retake the ko conditionally, becoming komaster. B cannot do much, but in one variation he plays at K4 and W takes at H1. The following position 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.
The following alternate schemes have been proposed. It is assumed
that O is the player about to move.
kom_pos to the location of the ko, where a stone was
just removed.
kom_pos. Komaster parameters unchanged.
O and
kom_pos to the location of the ko, where a stone was
just removed.
O:
is_ko(kom_pos, X) returns false. In that case,
kom_pos is updated to the new ko position, i.e. the stone
captured by this move.
X:
kom_pos. Komaster parameters unchanged.
A superstring is an extended string, where the extensions are through the following kinds of connections:
OO
... O.O XOX X.X
OO .. OO
.O O.
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.
Here we list the publically callable functions in reading.c.
The return codes of these functions are explained elsewhere
(see Reading Basics). To briefly repeat this, a reading
function return WIN if the attack succeeds unconditionally, 0 if it doesn't.
It returns KO_A or KO_B if the result depends on ko:
KO_A if the attack succeeds provided attacker is willing to
ignore any ko threat (the attacker makes the first ko capture).
KO_B if attack succeeds provided attacker has a ko threat
which must be answered (the defender makes the first ko capture).
int attack(int str, int *move)
Determines if the string atstrcan be captured, and if so,*movereturns the attacking move, unlessmoveis a null pointer. Use a null pointer if you are interested in the result of the attack but not the attacking move itself.
int find_defense(int str, int *move)
Attempts to find a move that will save the string atstr. It returnsWINif such a move is found, with*movethe location of the saving move, unlessmoveis a null pointer. It is not checked that tenuki defends, so this may give an erroneous answer if!attack(str).
int attack_and_defend(int str, int *attack_code, int *attack_point, int *defend_code, int *defense_point)
This is a frontend to theattack()andfind_defense()functions, which guarantees a consistent result. If a string cannot be attacked, 0 is returned and*attack_codeis 0. If a string can be attacked and defended,WINis returned,*attack_codeand*defend_codeare both non-zero, and*attack_point,*defense_pointboth point to vertices on the board. If a string can be attacked but not defended, 0 is again returned,*attack_codeis non-zero,*defend_codeis 0, and*attack_pointpoints to a vertex on the board. This function in particular guarantees that if there is an attack, it will never returndefense_point = NO_MOVE, which means the string is safe without defense. Separate calls toattack()andfind_defense()may occasionally give this result, due to irregularities introduced by the persistent reading cache.
int attack_either(int astr, int bstr)
Returns true if there is a move which guarantees that at least one of the stringsastrandbstrcan be captured. A typical application for this is in connection patterns, where after a cut it suffices to capture one of the cutting stones. The current implementation only looks for uncoordinated attacks. This is insufficient to find double ataris or moves such asain positions likeXOOOOOOOX XOXXOXXOX XX..a..XX ---------where neither of the threatenedXstones can be captured outright. Still either can be captured by a move down toa.
int defend_both(int astr, int bstr)
Returns true if both the stringsastrandbstrcan be defended simultaneously or if there is no attack. A typical application for this is in connection patterns, where after a cut it's necessary to defend both cutting stones. The current implementation only makes halfhearted attempts to find coordinated defense moves. A proper implementation would require some serious reading.
int break_through(int apos, int bpos, int cpos)
returnsWINif a position can succesfully be broken through andCUTif it can be cut. The position is assumed to have the shape (the colors may be reversed).O. dbe OXO aFcIt isXto move and try to capture at least one ofa,b, andc. If this succeeds,Xis said to have broken through the position. OtherwiseXmay try to cut through the position, which means keepingFsafe and getting a tactically safe string at eitherdore. Important:a,b, andcmust be given in the correct order.
int attack_threats(int str, int max_points, int moves[], int codes[])
Return up to max_threats threats to capture the string atstr. If the string is directly attackable the number of threats is reported to be 0. NOTE: You can call attack_threats withmoves[]andcodes[]already partly filled in. So if you want to get the threats from scratch, you have to set them to 0 yourself.
int safe_move(int move, int color)
Checks whether a move atmoveis illegal or can immediately be captured. Ifstackp==0the result is cached. If the move only can be captured by a ko, it's considered safe.
void purge_persistent_reading_cache()
Remove persistent cache entries which are no longer current.
void reading_hotspots(float values[BOARDMAX])
Based on the entries in the reading cache and their nodes field, compute where the relatively most expensive tactical reading is going on.
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:
dumpwill print the move stack.nvmoves to the next variationascii i jconverts (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
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.
owl.c
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:
stackp > owl_branch_depth then only one move is tried per
variation.
stackp > owl_reading_depth then the reading terminates,
and the situation is declared a win for the defender (since
deep reading may be a sign of escape).
owl_node_limit, the reading also
terminates with a win for the defender.
patterns/owl_attackpats.db and
patterns/owl_defendpats.db with value 100 is considered a win: if
such a pattern is found by owl_attack or owl_defend, the
function returns true. This feature must be used most carefully.
The functions owl_attack() and owl_defend() may, like
attack() and find_defense(), return an attacking or
defending move through their pointer arguments. If the position is
already won, owl_attack() may or may not return an attacking
move. If it finds no move of interest, it will return PASS, that
is, 0. The same goes for owl_defend().
When owl_attack() or owl_defend() is called,
the dragon under attack is marked in the array goal.
The stones of the dragon originally on the board are marked
with goal=1; those added by owl_defend() are marked
with goal=2. If all the original strings of the original dragon
are captured, owl_attack() considers the dragon to be defeated,
even if some stones added later can make a live group.
Only dragons with small escape route are studied when the
functions are called from make_dragons().
The owl code can be conveniently tested using the
--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.
owl.cIn 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.
As with the tactical reading code, return codes are WIN, 0,
or KO_A or KO_B if the position is ko. Thus for example
owl_attack()
KO_A if the attack prevails provided attacker is willing to
ignore any ko threat (the attacker makes the first ko capture).
KO_B if attack succeeds provided attacker has a ko threat
which must be answered (the defender makes the first ko capture).
The public functions in owl.c are:
void owl_analyze_semeai(int apos, int bpos, int *resulta, int *resultb, int *move, int owl)
Called whenaposandbpospoint to adjacent dragons of the opposite color, both withmatcher_statusDEADorCRITICAL, analyzes the semeai, assuming that the player of theaposdragon moves first.
int owl_attack(int target, int *attack_point, int *certain)
Returns true if a move can be found to attack the dragon attarget, in which case*attack_pointis the recommended move.attack_pointcan be a null pointer if only the result is needed. The array goal marks the extent of the dragon. This must be maintained during reading. Call this function only whenstackp==0; otherwise you can calldo_owl_attackbut you must set up the goal and boundary arrays by hand first.
int owl_threaten_attack(int target, int *attack1, int *attack2)
Returns true if the dragon attargetcan be captured given two moves in a row. The first two moves to capture the dragon are given as*attack1and*attack2.
int owl_defend(int target, int *defense_point, int *certain)
Returns true if a move can be found to defend the dragon attarget, in which case*defense_pointis the recommended move.
defense_point can be a null pointer if the result is not needed.
int owl_threaten_defense(int target, int *defend1, int *defend2)
Returns true if the dragon attargetcan be defended given two moves in a row. The first two moves to defend the dragon are given as*defend1and*defend2.
void owl_reasons(int color)
Add owl reasons. This function should be called once during genmove.
int owl_does_defend(int move, int target)
Use the owl code to determine whether the move atmovemakes the dragon attargetowl safe. This is used to test whether tactical defenses are strategically viable and whether a vital eye point does kill an owl critical dragon. Should be called only whenstackp==0.
int owl_confirm_safety(int move, int target, int *defense_point)
Use the owl code to determine whether the dragon atmoveis owl safe after an own move attarget. This is used to detect blunders. In case the dragon is not safe, it also tries to find a defense point makingtargetsafe in a later move. Should be called only whenstackp==0.
int owl_does_attack(int move, int target)
Use the owl code to determine whether the attack move atShould be called only whenmoveof the dragontargetis effective, i.e. whether it kills the stones.
stackp==0.
int owl_connection_defends(int move, int target1, int target2)
Use the owl code to determine whether connecting the two dragonstarget1andtarget2by playing atmoveresults in a living dragon. Should be called only whenstackp==0.
int owl_lively(int pos)
True unlessposisEMPTYor occupied by a lunch for the goal dragon. Used during make_domains (see the functionis_livelyinoptics.c). A "lively" worm is one that might be alive, hence cannot be ignored in determining eye spaces.
int owl_substantial(int str)
This function, called whenstackp==0, returns true if capturing the string atstrresults in a live group.
int obvious_false_eye(int pos, int color)
Conservative relative of topological_eye. Essentially the same algorithm is used, but only tactically safe opponent strings on diagonals are considered. This may underestimate the false/half eye status, but it should never be overestimated.
int owl_topological_eye(int pos, int color)
Retrieve topological eye values stored in the half_eye[] array of
the current owl data.
accumlate_influence()
engine/influence.c
We define call stones lively if they cannot be tactically attacked, or if they have a tactical defense and belong to the player whose turn it is. Similarly, stones that cannot be strategically attacked (in the sense of the life-and-death analysis), or that have a strategical defense and belong to the player to move, are called alive 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.
All these extra influence sources, as well as connections, are controlled by a pattern database, which consists of the two files patterns/influence.db and patterns/barriers.db. The details are explained in Influential Patterns.
The information obtained from the influence computation is used in a variety of places in the engine, and the influence module is called several times in the process of the move generation. The details of the influence computation vary according to the needs of the calling function.
After GNU Go has decided about the tactical stability of strings, the
influence module gets called the first time. Here all lively stones act
as an influence source of default strength 100. The result is stored in
the variables initial_influence and initial_opposite_influence,
and it is used as an important information for guessing the strength of
dragons. For example,
a dragon that is part of a moyo of size 25 is immediately considered alive.
For dragons with a smaller moyo size, a life-and-death analysis will be
done by the owl code (see Life and Death Reading). A dragon with a
moyo size of only 5 will be considered weak, even if the owl code has
decided that it cannot be killed.
As a tool for the owl code, an "escape" influence gets computed for each dragon going through the life-and-death analysis (Escape).
Once all dragons have been evaluated, the influence module is called again
and the variables initial_influence and
initial_opposite_influence get overwritten. Of course, the dragon
status', which are available now, are taken into account. Stones belonging
to a dead dragon will not serve as an influence source, and the strengths of
other stones get adjusted according to the strength of their respective
dragon.
The result of this run is the most important tool for move evaluation. All
helper functions of patterns as explained in Patterns that
refer to influence results (e. g. olib(*) etc.) actually use these
results. More important, initial_influence serves as the reference for
computing the territorial value of a move. That is, from the influence
strengths stored in initial_influence, a territory value is
assigned to each intersection. This value is supposed to estimate the
likelyhood that this intersection will become white or black territory.
Then, for each move that gets considered in the function value_moves,
the influence module is called again via the function
compute_move_influence to assess the likely territorial balance after
this move, and the result is compared with the state before that move.
There are a number of changes from 3.0 to 3.2 in these influence computations relevant for territorial evaluation. Also, now an additional influence computation is done in order to compute the followup value of a move. Some explainations are in Territorial Details.
In this section we consider how the influence function is used to
estimate territory in the function estimate_territorial_value().
A move like * by O below is worth one point:
OXXX. OX.XX O*a.X OX.XX OXXX.
This is evaluated by the influence function in the following way:
We first assign territory under the assumption that X moves first in all
local positions in the original position; then we reassing territory,
again under the assumption that X moves first in all local positions,
but after we let O make the move at *. These two
territory assignments are compared and the difference gives the
territorial value of the move.
Technically, the assumption that X plays first everywhere is
implemented via an asymmetric pattern database in barriers.db.
What exactly is a safe connection that stops hostile influence from
passing through is different for O and X; of course such a
connection has to be tighter for stones with color O. Also,
additional intrusion influence sources are added for X in places
where X stones have natural followup moves.
In this specific example above, the asymmetry (before any move has been made)
would turn out as follows: If X is in turn to move, the white influence
would get stopped by a barrier at *, leaving 4 points of territory
for X. However, if O was next to move, then a followup move
for the white stones at the left would be assumed in the form of an extra
("intrusion") influence source at *. This would get stopped at
a, leaving three points of territory.
Returning to the valuation of a move by O at *, we get a
value of 1 for the move at *.
However, of course this move is sente once it is worth playing, and should
therefore (in miai counting) be awarded an effective value of 2. Hence we
need to recognize the followup value of a move. GNU Go 3.0 took care of
this by using patterns in patterns.db that enforced an explicit
followup value. Version 3.2 instead computes a seperate followup influence
to each move considered. In the above example, an intrusion source will
be added at a as a followup move to *. This destroys all of
Black's territory and hence gives a followup value of 3.
The pattern based followup value are still needed at some places, however.
To give another example, consider this position where we want to
estimate the value of an O move at *:
OOOXXX ..OX.. ..OX.. ...*.. ------
Before the move we assume X moves first in the local position (and
that O has to connect), which gives territory like this (lower case
letter identify territory for each player):
OOOXXX ooOXxx o.OXxx o...xx ------
Then we let O make the move at * and assume
X moves first again next. The territory then becomes (X
is also assumed to have to connect):
OOOXXX ooOXxx ooOX.x oo.O.x ------
We see that this makes a difference in territory of 4, which is what
influence_delta_territory() should report. Then again, we have followup
value, and here also a reverse followup value. The reverse followup value,
which in this case will be so high that the move is treated as reverse
sente, is added by an explicit pattern. Other sources for followup or
reverse followup values are threats to capture a rescue a string of stones.
See the code and comments in the function value_move_reaons for how
followup and reverse followup values are used to adjust the effective
move value.
To give an example of territorial value where something is captured,
consider the O move at * here,
XXXXXXXO X.OOOOXO X.O..O*O --------
As before we first let the influence function determine territory assuming X moves first, i.e. with a captured group:
XXXXXXXO XxyyyyXO Xxyxxy.O --------
Here y indicates X territory + captured stone,
i.e. these count for two points. After the O move at * we
instead get
XXXXXXXO X.OOOOXO X.OooOOO --------
and we see that X has 16 territory fewer and O
has two territory more, for a total difference of 18 points.
That the influence function counts the value of captured stones is new
in GNU Go 3.2.. Previously this was instead done using the
effective_size heuristic. The effective size is the number of
stones plus the surrounding empty spaces which are closer to
this string or dragon than to any other stones. Here the O
string would thus have effective size 6 (number of stones) + 2
(interior eye) + 2*0.5 (the two empty vertices to the left of
the string, split half each with the surrounding X string) +
1*0.33 (the connection point, split between three strings) =
9.33. As noted this value was doubled, giving 18.67 which is
reasonably close to the correct value of 18. The effective size
heuristic is still used in certain parts of the move valuation
where we can't easily get a more accurate value from the
influence function (e. g. attacks depending on a ko, attack threats).
Note that this section only describes the territorial valuation of a move. Apart from that, GNU Go uses various heuristics in assigning a strategical value (weakening and strengthening of other stones on the board) to a move. Also, the influence function isn't quite as well tuned as the examples above may seem to claim. But it should give a fairly good idea of how the design is intended.
Another matter is that so far we have only considered the change in secure territory. GNU Go 3.2 uses a revised heuristic, which is explained in the next section, to assign probable territory to each player.
This section explains how GNU Go assigns a territorial value to an intersection once the white and black influence have been computed. The intention is that an intersection that has a chance of xx% of becoming white territory is counted as 0.xx points of territory for white, and similar for black.
The algorithm in the function new_value_territory goes roughly
as follows:
If wi is the white influence at a point, and bi the black
influence, then value = ( (wi-bi)/ (wi+bi) )^3 (positive values
indicates likley white territory, negative stand for black territory)
turns out to be very simple first guess that is still far off, but
reasonable enough to be useful.
This value is then suspect a number of corrections. Assume that this first guess resulted in a positive value.
If both bi and wi are small, it gets reduced. What exactly is
"small" depends on whether the intersection is close to a corner or an edge
of the board, since it is easier to claim territory in the corner than in
the center.
Then the value at each intersection is degraded to the minimum value of its neighbors. This can be seen as a second implementation of the proverb saying that there is no territory in the center of the board. This step substantially reduces the size of spheres of territory that are open at several sides.
Finally, there are a number of patterns that explicitly forbid GNU Go to count territory at some intersections. This is used e. g. for false eyes that will eventually have to be filled in. Also, points for prisoners are added.
To fine tune this scheme, some revisions have been made to the influence computations that are relevant for territorial evaluation. This includes a reduced default attenuation and some revised pattern handling.
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 (with an attenuation of 3.0):
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.
While most of the engine uses the one dimensional board (see The Board)
the two dimensional board is still used in engine/influence.c.
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:
di*(i-m) + dj*(j-n)
between the vectors (di,dj) and (i,j) - (m,n)
(i+di, j+dj) is outside the board or occupied we
also continue with the next direction.
(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:
P, which is a property of the board
intersections. Normally this is one, i.e. unrestricted
propagation, but to stop propagation through e.g. one step
jumps, the permeability is set to zero at such intersections
through pattern matching. This is further discussed below.
A, which is a property of the influence
source and different in different directions. By default this has the
value 3 except diagonally where the number is twice as much. By
modifying the attenuation value it is possible to obtain influence
sources with a larger or a smaller effective range.
D, which is the squared cosine of the
angle between (di,dj) and (i,j) - (m,n). The idea is to
stop influence from "bending" around an interfering stone and
get a continuous behavior at the right angle cutoff. The
choice of the squared cosine for this purpose is rather
arbitrary, but has the advantage that it can be expressed as a
rational function of m, n, i, j,
di, and dj, without involving any trigonometric or
square root computations. When we are visiting the influence
source we let by convention this factor be one.
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.
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.
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.
This section explains the details of the pattern databases used for the influence computation.
First, we have the patterns in influence.db, which get matched
symmetrically for both colors.
E
These patterns add extra influence sources close to some shapes like walls. This tries to reflect their extra strength. These patterns are not used in the influence computations relevant for territory valuations, but they are useful for getting a better estimate of strengths of groups.
I
These patterns add extra influence sources at typical invasion points.
Usually they are of small strength. If they additionally have the class
s, the extra influence source is added for both colors. Otherwise,
only the player assumed to be next to move gets the benefit.
The patterns in barriers.db get matched only for O
being the player next to move.
A
Connections betweenXstones that stop influence ofO. They have to be tight enough thatOcannot break through, even though he is allowed to move first.
D
Connections betweenOstones that stop influence ofX. The stones involved can be more loosely connected than those inApatterns.
B
These indicate positions of followup moves for theOstone marked withQin the pattern. They are used to reduce the territory e. g. where a monkey jump is possible. Also, they are used in the computation of the followup influence, if theQstone was the move played (or a stone saved by the move played).
t
These patterns indicate intersections where one color will not be able to get territory, for example in a false eye. The points are set with a call to the helper non_oterritory or non_xterritory in the action of the pattern.
The intrusion patterns (B) are more powerful than the description
above might suggest. They can be very helpful in identifying weak shapes
(by adding an intrusion source for the opponent where he can break through).
A negative inference for this is that a single bad B pattern, e. g.
one that has a wrong constraint, typically causes 5 to 10 FAILs in
the regression test suite.
Influence Patterns can have autohelper constraints as usual. As for
the constraint attributes, there are (additionally to the usual
ones O, o, X and x),
attributes Y and FY. A pattern marked with Y will
only be used in the influence computations relevant for the territory
valuation, while FY patterns only get used in the other influence
computations.
The action of an influence pattern is at the moment only used for
non-territory patterns as mentioned above, and as a workaround for a
problem with B patterns in the followup influence.
To see why this workaround is necessary, consider the follwoing situation:
..XXX .a*.O .X.O. ..XXO
(Imagine that there is X territory on the left.)
The move by O at * has a natural followup move at a.
So, in the computation of the followup influence for *, there would
be an extra influence source for O at a which would destroy
a lot of black territory on the left. This would give a big followup value,
and in effect the move * would be treated as sente.
But of course it is gote, since X will answer at a, which
both stops the possible intrusion and threatens to capture *. This
situation is in fact quite common.
Hence we need an additional constraint that can tell when an intrusion pattern can be used in followup influence. This is done by misusing the action line: An additional line
>return <condition>;
gets added to the pattern. The condition should be true if the
intrusion cannot be stopped in sente. In the above example, the relevant
intrusion pattern will have an action line of the form
>return (!xplay_attack(a,b));
where b refers to the stone at *. In fact, almost all
followup-specific constraints look similar to this.
static void
accumulate_influence(struct influence_data *q, int m, int n, int color)
Limited in scope to influence.c, this is the core of the influence
function. Given the coordinates and color of an influence source, it radiates
the influence outwards until it hits a barrier or the strength of the
influence falls under a certain threshold. The radiation is performed by a
breadth first propagation, implemented by means of an internal queue.
void add_influence_source(int pos, int color, float strength, float attenuation, struct influence_data *q)
Adds an influence source at position pos with prescribed strength and attenuation. color can beBLACK,WHITEor both. If there already exists an influence source of the respective color at pos that is stronger than the new one, we do nothing.
void influence_mark_non_territory(int pos, int color)
Called from actions for t patterns. Marksposas not being territory forcolor.
int influence_get_moyo_size(int pos, int color)
Return the size of the moyo around pos.
void influence_get_moyo_segmentation(int opposite, struct moyo_data *moyos)
Export the moyo segmentation. If opposite is true, then
initial_opposite_influence is used, otherwise initial_influence.
void compute_initial_influence(int color, int dragons_known)
Compute the influence before a move has been made, which can later be compared to the influence after a move. Assume that the other color is in turn to move.
void resegment_initial_influence()
Redo the segmentation of the initial influence.
void compute_escape_influence(char goal[BOARDMAX], int color, int escape_value[BOARDMAX], int dragons_known)
Assume that the stones marked by the goal array do not generate influence and compute influence. Influence based escape values are returned in the escape_value array.
int influence_territory_color(int pos)
Return the color who has territory atpos, orEMPTY.
int influence_moyo_color(int pos)
Return the color who has moyo at pos, or EMPTY.
int influence_moyo_color_opposite(int pos)
Return the color who has moyo at pos, or EMPTY, using influence
computed with the opposite color to move.
int influence_area_color(int pos)
Return the color who has area at pos, or EMPTY.
float influence_delta_territory(int pos, int color, char saved_stones[BOARDMAX], float *followup_value)
Compute the difference in territory made by a move by color at pos.
This also includes the changes in moyo and area. In experimental-influence
mode, followup_value must not be a NULL pointer, and the followup_value will
be returned there.
float influence_estimate_score(float moyo_coeff, float area_coeff)
Estimate the score. A positive value means white is ahead. The score is estimated from the initial_influence, which must have been computed in advance. The score estimate does not include captured stones (i.e., the ones having been removed from the board) or komi. moyo_coeff and area_coeff are the relative weights to be used for the moyo and area difference respectively.
void debug_influence_move(int i, int j)
Print the influence map when we have computed influence for the
move at (i, j).
void get_initial_influence(int color, int dragons_known, float white_influence[BOARDMAX], float black_influence[BOARDMAX], int influence_regions[BOARDMAX])
Compute initial influence and export it. The color parameter tells who is in turn to move.
void get_move_influence(int move, int color, char saved_stones[BOARDMAX], float white_influence[BOARDMAX], float black_influence[BOARDMAX], int influence_regions[BOARDMAX])
Compute influence after a move and export it.
void print_initial_influence(int color, int dragons_known)
Compute initial influence and print it. Notice that it's assumed that the printmoyo global tells what information to print. The color parameter tells who is in turn to move.
void print_move_influence(int pos, int color, char saved_stones[BOARDMAX])
Compute influence after doing a move and print it. Notice that it's assumed that the printmoyo global tells what information to print.
There are various ways to obtain detailed information about the influence computations. Colored diagrams showing influence are possible from a colored xterm or rxvt window.
There are two options controlling when to generate diagrams:
-m 0x08 or -m 8
Show diagrams for the initial influence computation. This is done
twice, the first time before make_dragons() is run and the second time
after. The difference is that dead dragons are taken into account the
second time. Tactically captured worms are taken into account both
times.
--debuginfluence location
Show influence diagrams after the move at the given location. An important limitation of this option is that it's only effective for moves that the move generation is considering.
The other options control which diagrams should be generated in these situations. You have to specify at least one of the options above and at least one of the options below to generate any output.
-m 0x010 or -m 16
Show colored display of territory/moyo/area regions.This feature is very useful to get an immediate impression of the influence regions as GNU Go sees them.
- territory: cyan
- moyo: yellow
- area: red
-m 0x20 or -m 32
Show numerical influence values for white and black. These come in two separate diagrams, the first one for white, the second one for black. Notice that the influence values are represented by floats and thus have been rounded in these diagrams.
-m 0x40 or -m 64
This generates two diagrams showing the permeability for black and white influence on the board.
-m 0x80 or -m 128
This shows the strength of the influence sources for black and white across the board. You will see sources at each lively stone (with strength depending on the strength of this stone), and sources contributed by patterns.
-m 0x100 or -m 256
This shows the attenuation with which the influence sources spread influence across the board. Low attenuation indicates far-reaching influence sources.
-m 0x200 or -m 512
This shows the territory valuation of GNU Go. Each intersection is shown with a value between -1.0 and +1.0 (or -2 resp. +2 if there is a dead stone on this intersection). Positive values indicate territory for white. A value of -0.5 thus indicates a point where black has a 50% chance of getting territory.
Finally, there is the debug option -d 0x1 which turns on
on DEBUG_INFLUENCE. This gives a message for each influence pattern
that gets matched. Unfortunately, these are way too many messages making
it tedious to navigate the output. However, if you discover an influence
source with -m 0x80 that looks wrong, the debug output can
help you to quickly find out the responsible pattern.
moyo.c and score.c
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).
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.2 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.2 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.
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 subtract
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.
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).
engine/utils.c
engine/printutils.c
Utility functions from engine/utils.c. Many of these
functions underlie autohelper functions (see Autohelper Functions).
void change_matcher_status(int dr, int status)
Change the status of all the stones in the dragon at dr.
int defend_against(int move, int color, int apos)
Check whether a move at move stops the enemy from playing at (apos).
int cut_possible(int pos, int color)
Returns true if color can cut atpos, or if connection throughposis inhibited. This information is collected byfind_cuts(), using the B patterns in the connections database.
int does_attack(int move, int str)
returns true if the move atmoveattacksstr. This means that it captures the string, and thatstris not already dead.
int does_defend(int move, int str)
does_defend(move, str)returns true if the move atmovedefendsstr. This means that it defends the string, and thatstrcan be captured if no defense is made.
int somewhere(int color, int last_move, ...)
Returns true if one of the vertices listed satisfiesboard[pos]==color. Here last_move is the number of moves minus one. Example:somewhere(WHITE, 2, apos, bpos, cpos).
int play_break_through_n(int color, int num_moves, ...)
Plays a sequence of moves, alternating between the players and starting with color. After having played through the sequence, the three last coordinate pairs gives a position to be analyzed bybreak_through(), to see whether either color has managed to enclose some stones and/or connected his own stones. If any of the three last positions is empty, it's assumed that the enclosure has failed, as well as the attempt to connect. If one or more of the moves to play turns out to be illegal for some reason, the rest of the sequence is played anyway, andbreak_through()is called as if nothing special happened. Likebreak_through(), this function returns 1 if the attempt to break through was succesful and 2 if it only managed to cut through.
int play_attack_defend_n(int color, int do_attack, int num_moves, ...)
Plays a sequence of moves, alternating between the players and starting with color. After having played through the sequence, the last coordinate pair gives a target to attack or defend, depending on the value of do_attack. If there is no stone present to attack or defend, it is assumed that it has already been captured. If one or more of the moves to play turns out to be illegal for some reason, the rest of the sequence is played anyway, and attack/defense is tested as if nothing special happened. A typical use for these functions is to set up a ladder in an autohelper and see whether it works or not.
int play_attack_defend2_n(int color, int do_attack, int num_moves, ...)
Plays a sequence of moves, alternating between the players and starting with color. After having played through the sequence, the two last coordinate pairs give two targets to simultaneously attack or defend, depending on the value of do_attack. If there is no stone present to attack or defend, it is assumed that it has already been captured. If one or more of the moves to play turns out to be illegal for some reason, the rest of the sequence is played anyway, and attack/defense is tested as if nothing special happened. A typical use for these functions is to set up a crosscut in an autohelper and see whether at least one cutting stone can be captured.
void set_depth_values(int level)
Set the various reading depth parameters. Ifmandated_depth_valueis not -1 that value is used; otherwise the depth values are set as a function of level. The parametermandated_depth_valuecan be set at the command line to force a particular value of depth; normally it is -1.
void modify_depth_values(int n)
Modify the various tactical reading depth parameters. This is typically used to avoid horizon effects. By temporarily increasing the depth values when trying some move, one can avoid that an irrelevant move seems effective just because the reading hits a depth limit earlier than it did when reading only on relevant moves.
void increase_depth_values(void)
modify_depth_values(1).
void decrease_depth_values(void)
modify_depth_values(-1).
void restore_depth_values()
Sets depth and so forth to their saved values.
int accurate_approxlib(int pos, int color, int maxlib, int *libs)
Play a stone atposand count the number of liberties for the resulting string. This requiresposto be empty. This function differs fromapproxlib()by the fact that it removes captured stones before counting the liberties.
int confirm_safety(int move, int color, int size, int *defense_point, int saved_dragons[BOARDMAX], int saved_worms[BOARDMAX])
This function will detect some blunders. If the move reduces the number of liberties of an adjacent friendly string, there is a danger that the move could backfire, so the function checks that no friendly worm which was formerly not attackable becomes attackable, and it checks that no opposing worm which was not defendable becomes defendable. Only worms withworm.size>sizeare checked. The arrayssaved_dragons[]andsaved_worms[]should be one for stones belonging to dragons or worms respectively, which are supposedly saved bymove. These may beNULLif no stones are supposed to gaving been saved. For use when called fromfill_liberty(), this function may optionally return a point of defense, which, if taken, will presumably make the move at(move)safe on a subsequent turn.
int double_atari(int move, int color)
Returns true if a move bycolorfits the following shape:X* (O=color) OXcapturing one of the twoXstrings. The name is a slight misnomer since this includes attacks which are not necessarily double ataris, though the common double atari is the most important special case.
void unconditional_life(int unconditional_territory[BOARDMAX], int color)
Find those worms of the given color that can never be captured, even if the opponent is allowed an arbitrary number of consecutive moves. The coordinates of the origins of these worms are written to the worm arrays and the number of non-capturable worms is returned. The algorithm is to cycle through the worms until none remains or no more can be captured. A worm is removed when it is found to be capturable, by letting the opponent try to play on all its liberties. If the attack fails, the moves are undone. When no more worm can be removed in this way, the remaining ones are unconditionally alive. After this, unconditionally dead opponent worms and unconditional territory are identified. To find these, we continue from the position obtained at the end of the previous operation (only unconditionally alive strings remain for color) with the following steps:Remaining opponent strings in atari and remaining liberties of the unconditionally alive strings constitute the unconditional territory. Opponent strings from the initial position placed on unconditional territory are unconditionally dead. On return,
- Play opponent stones on all liberties of the unconditionally alive strings except where illegal. (That the move order may determine exactly which liberties can be played legally is not important. Just pick an arbitrary order).
- Recursively extend opponent strings in atari, except where this would be suicide.
- Play an opponent stone anywhere it can get two empty neighbors. (I.e. split big eyes into small ones).
- 4. Play an opponent stone anywhere it can get one empty neighbor. (I.e. reduce two space eyes to one space eyes.)
unconditional_territory[][]is 1 where color has unconditionally alive stones, 2 where it has unconditional territory, and 0 otherwise.
void who_wins(int color, FILE *outfile)
Score the game and determine the winner. Result is printed on
outfile.
void find_superstring(int str, int *num_stones, int *stones)
Find the stones of an extended string, where the extensions are through the following kinds of connections:
- Solid connections (just like ordinary string).
OO- Diagonal connection or one space jump through an intersection where an opponent move would be suicide or self-atari.
... O.O XOX X.X- Bamboo joint.
OO .. OO- Diagonal connection where both adjacent intersections are empty.
.O O.- 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 fromowl.c.
void find_superstring_liberties(int str, int *num_libs, int *libs, int liberty_cap)
This function computes the superstring atstras described above, but omitting connections of type 5. Then it constructs a list of liberties of the superstring which are not already liberties ofstr. Ifliberty_capis nonzero, only liberties of substrings of the superstring which have fewer thanliberty_capliberties are generated.
void find_proper_superstring_liberties(int str, int *num_libs, int *libs, int liberty_cap)
This function is the same asfind_superstring_liberties(), but it omits those liberties of the stringstr, presumably since those have already been treated elsewhere. Ifliberty_capis nonzero, only liberties of substrings of the superstring which have at mostliberty_capliberties are generated.
void find_superstring_stones_and_liberties(int str, int *num_stones, int *stones, int *num_libs, int *libs, int liberty_cap)
This function computes the superstring atstras described above, but omitting connections of type 5. Then it constructs a list of liberties of the superstring which are not already liberties ofstr. Ifliberty_capis nonzero, only liberties of substrings of the superstring which have fewer thanliberty_capliberties are generated.
void superstring_chainlinks(int str, int *num_adj, int adjs[MAXCHAIN], int liberty_cap)
Analogous to chainlinks, this function finds boundary chains of the superstring atstr, including those which are boundary chains ofstritself. Ifliberty_cap != 0, only those boundary chains with<= liberty_capliberties are reported.
void proper_superstring_chainlinks(int str, int *num_adj, int adjs[MAXCHAIN], int liberty_cap)
Analogous to chainlinks, this function finds boundary chains of the superstring atstr, omitting those which are boundary chains ofstritself. Ifliberty_cap != 0, only those boundary chains with<= liberty_capliberties are reported.
void start_timer(int n)
Start a timer. Internal timers are used for assessing time spent on various tasks.
double time_report(int n, const char *occupation, int move, double mintime)
Report time spent and restart the timer. Make no report if elapsed time is less than mintime.
Utility functions from engine/printutils.c.
The functions such as gprintf and the TRACE and
DEBUG macros are derived from vgprintf, which is
local to the file. Any one of these functions simulates the
formatted printf functions in the standard C library,
but the formats are slightly modified. One can use %c, %d, %f,
%s, and %x as usual. But there are some other formats:
The indentation referred to in the last item displays the stack depth.
int gprintf(const char *fmt, ...)
The most common formatted print function, writes to stderr.
void gfprintf(FILE *outfile, const char *fmt, ...)
Wrapper around vgprintf, writes to outfile.
void
mprintf(const char *fmt, ...)
Wrapper around vgprintf, in contrast to gprintf this one
writes to stdout.
TRACE(const char *fmt, ...)
Like gprintf, but silent if the global variable verbose is
zero.
void abortgo(const char *file, int line, const char *msg, int x, int y)
A wrapper aroundabort()which shows the state variables at the time of the problem.(i, j)are typically a related move, or(-1, -1).
const char *color_to_string(int color)
Convert a color value to a string.
const char *location_to_string(int pos)
Convert a location to a string.
void location_to_buffer(int pos, char *buf)
Convert a location to a string, writing to a buffer
const char *status_to_string(int status)
Convert a status value to a string.
const char *safety_to_string(int status)
Convert a safety value to a string.
const char *routine_to_string(int routine)
Convert a routine to a string.
const char *result_to_string(int result)
Convert a read result to a string.
int string_to_location(int boardsize, char *str, int *m, int *n)
Get the(m, n)coordinates from the string str. This means thatmis the nth row from the top andnis the column. Both coordinates are between 0 andboardsize-1, inclusive. Return 1 if ok, otherwise return 0;
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 origin; /* Coordinates of "origin", i.e. */
/* "upper left" stone. */
int liberties; /* Number of liberties. */
int libs[MAX_LIBERTIES]; /* Coordinates of 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
static int string_number[BOARDMAX];
which contains indices into the string array. This information is only
valid at nonempty vertices, however, so it is necessary to first
verify that board[pos] != EMPTY.
The string_data structure does not include an array of the stone
coordinates. This information is stored in a separate array:
static int next_stone[BOARDMAX];
This array implements 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[BOARDMAX]; 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[pos] has the same value as liberty_mark, then
pos 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 board array, this is done by calling
incremental_board_init(). It is not necessary to call this
function explicitly since any other function that needs the information
does this if it has not been done.
The interesting part of the code is the incremental update of the data structures when a stone is played and subsequently removed. To understand the strategies involved in adding a stone it is necessary to first know how undoing a move works. The idea is that as soon as some piece of information is about to be changed, the old value is pushed onto a stack which stores the value and its address. The stack is built from the following structures:
struct change_stack_entry {
int *address;
int value;
};
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:
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
pos = FIRST_STONE(s);
do {
...
pos = NEXT_STONE(pos);
} while (!BACK_TO_FIRST_STONE(s, pos));
traverses the stones of the string with number s exactly once,
with pos holding the coordinates. In general pos is
used as board coordinate and s as an index into the
string array or sometimes a pointer to an entry in the
string array.
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.
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:
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.
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.
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.
The same as above except that B1 includes the arbiter functionality and the first GTP link is shortcut.
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).
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(POS(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(POS(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");
}
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).
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 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.
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.
./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<