utils.c
This is GNU Go, 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.
Copyright 1999 and 2000 by the Free Software Foundation except for
the files gmp.c and gmp.h, which are copyrighted by
Bill Shubert (wms@hevanet.com).
All files are under the GNU General Public License (see Copying),
except gmp.c and gmp.h, the files interface/html/* and
win/makefile.win. The two files gmp.c and gmp.h are in
the public domain 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 file
win/makefile.win is also in the public domain and is free for
unrestricted use.
GNU Go authors (in chronological order of contribution) are Man Li, Daniel Bump, David Denholm, Gunnar Farneback, Nils Lohner, Jerome Dumonteil, Tommy Thorn, Nicklas Ekstrand, Inge Wallin, Thomas Traber, Douglas Ridgway, Teun Burgers, Tangay Urvoy and Thien-Thi Nguyen.
We would like to thank Jean-Louis Martineau, Piotr Lakomy and Paul Leonard for helpful correspondence. Thanks to everyone who stepped on a bug (and sent us a report)!
Thanks to Peter Gucwa, Heikki Levanto, Michael Margolis and Gary Boos for help with Visual C++.
We would like to thank Stuart Cracraft, Richard Stallman and Man Li for
their interest in making this program a part of GNU, William
Shubert for writing CGoban and gmp.c and Rene Grothmann for Jago.
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. 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 disclaimer. Please contact the GNU Go maintainer, Daniel Bump (bump@math.stanford.edu), to get more information and the papers to sign.
Below is a list of things YOU could work on. We are already working on some of these tasks, but don't let that stop you. Please contact us or the person assigned to task for further discussion.
1. If you can, send us bug FIXES as well as bug reports. If you see some bad behavior, figure out what causes it, and what to do about fixing it. And send us a patch! If you find an interesting bug and cannot tell us how to fix it, we would be happy to have you tell us about it anyway. Send us the sgf file (if possible) and attach other relevant information, such as the GNU Go version number. In cases of assertion failures and segmentation faults we probably want to know what operating system and compiler you were using, in order to determine if the problem is platform dependent.
2. Tuning the pattern database. This is a sort of art. It is not necessary to do any programming to do this since many of the patterns do not require helpers, or can be handled using autohelpers.
We would like it if a few more Dan level players would learn this skill.
3. The reading code assumes that a string with five liberties is safe. Sometimes this leads to expanding a dead group into enemy territory, a simple waste. An improvement in strength would result from giving heuristics for the strategical viability of a group, based on moyo/escape route considerations. This is also useful for deciding whether a cut is reasonable or needs defending against.
4. The escape potential of a group is today estimated by counting fourth order liberties. While this isn't completely unreasonable, it's also not accurate enough anymore. An improved implementation might use pattern matching (with autohelpers to assist with reading) to identify running moves and ways to break through enclosure.
5. Semeai module is vastly in need of improvement. In fact, semeai can probably be only analyzed by reading to discover what backfilling is needed before we can make atari. Also, semeai module should be able to change the status of dragons.
6. The eye space evaluation doesn't work very well for semi-open spaces along the edges. An improvement here might require extending the basic "local game" model for life and death analysis, as described in See Eyes.
7. The eye space evaluation knows about "chimeras", positions where one player can make two eyes in one move but the opponent also can destroy both in one move. This information is, however, currently not used in the higher levels of life and death reasoning. There are also other interesting positions, such as moves making an eye in sente (i.e. by threatening to make another eye), that would need some consideration. For inspiration you may wish to read the paper "Eyespace Values in Go" by Howard Landman. The paper is linked from the GNU Go development web page.
8. The eye space evaluation would also need to learn about local games ending in various kinds of kos.
9. Life and death reading. The eyespace evaluation is currently completely static. This has the advantage of being very fast, but needing a fairly large pattern database. To incorporate various life and death subtleties in this scheme may require enlarging the pattern database more than we want and/or being very tricky to get right. An alternative is to use reading to deal with some of the complications and then perform static evaluation on the nodes.
10. More life and death reading. One could also consider using reading to fully play out the local games (see Eyes). While this probably would be too slow to employ in actual play, it would still be useful for verifying and/or automatically generating the eye space database. (Inge Wallin has started working on this.)
11. Very much time in the reading is spent counting liberties. It's possible that the reading could be made faster by keeping track of the liberty counts while doing and undoing moves. There is, however, a certain amount of overhead involved here, so a proof of concept would definitely be necessary.
Version 2, June 1991
Copyright © 1989, 1991 Free Software Foundation, Inc. 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed.
The licenses for most software are designed to take away your freedom to share and change it. By contrast, the GNU General Public License is intended to guarantee your freedom to share and change free software--to make sure the software is free for all its users. This General Public License applies to most of the Free Software Foundation's software and to any other program whose authors commit to using it. (Some other Free Software Foundation software is covered by the GNU Library General Public License instead.) You can apply it to your programs, too.
When we speak of free software, we are referring to freedom, not price. Our General Public Licenses are designed to make sure that you have the freedom to distribute copies of free software (and charge for this service if you wish), that you receive source code or can get it if you want it, that you can change the software or use pieces of it in new free programs; and that you know you can do these things.
To protect your rights, we need to make restrictions that forbid anyone to deny you these rights or to ask you to surrender the rights. These restrictions translate to certain responsibilities for you if you distribute copies of the software, or if you modify it.
For example, if you distribute copies of such a program, whether gratis or for a fee, you must give the recipients all the rights that you have. You must make sure that they, too, receive or can get the source code. And you must show them these terms so they know their rights.
We protect your rights with two steps: (1) copyright the software, and (2) offer you this license which gives you legal permission to copy, distribute and/or modify the software.
Also, for each author's protection and ours, we want to make certain that everyone understands that there is no warranty for this free software. If the software is modified by someone else and passed on, we want its recipients to know that what they have is not the original, so that any problems introduced by others will not reflect on the original authors' reputations.
Finally, any free program is threatened constantly by software patents. We wish to avoid the danger that redistributors of a free program will individually obtain patent licenses, in effect making the program proprietary. To prevent this, we have made it clear that any patent must be licensed for everyone's free use or not licensed at all.
The precise terms and conditions for copying, distribution and modification follow.
Activities other than copying, distribution and modification are not covered by this License; they are outside its scope. The act of running the Program is not restricted, and the output from the Program is covered only if its contents constitute a work based on the Program (independent of having been made by running the Program). Whether that is true depends on what the Program does.
You may charge a fee for the physical act of transferring a copy, and you may at your option offer warranty protection in exchange for a fee.
These requirements apply to the modified work as a whole. If identifiable sections of that work are not derived from the Program, and can be reasonably considered independent and separate works in themselves, then this License, and its terms, do not apply to those sections when you distribute them as separate works. But when you distribute the same sections as part of a whole which is a work based on the Program, the distribution of the whole must be on the terms of this License, whose permissions for other licensees extend to the entire whole, and thus to each and every part regardless of who wrote it.
Thus, it is not the intent of this section to claim rights or contest your rights to work written entirely by you; rather, the intent is to exercise the right to control the distribution of derivative or collective works based on the Program.
In addition, mere aggregation of another work not based on the Program with the Program (or with a work based on the Program) on a volume of a storage or distribution medium does not bring the other work under the scope of this License.
The source code for a work means the preferred form of the work for making modifications to it. For an executable work, complete source code means all the source code for all modules it contains, plus any associated interface definition files, plus the scripts used to control compilation and installation of the executable. However, as a special exception, the source code distributed need not include anything that is normally distributed (in either source or binary form) with the major components (compiler, kernel, and so on) of the operating system on which the executable runs, unless that component itself accompanies the executable.
If distribution of executable or object code is made by offering access to copy from a designated place, then offering equivalent access to copy the source code from the same place counts as distribution of the source code, even though third parties are not compelled to copy the source along with the object code.
If any portion of this section is held invalid or unenforceable under any particular circumstance, the balance of the section is intended to apply and the section as a whole is intended to apply in other circumstances.
It is not the purpose of this section to induce you to infringe any patents or other property right claims or to contest validity of any such claims; this section has the sole purpose of protecting the integrity of the free software distribution system, which is implemented by public license practices. Many people have made generous contributions to the wide range of software distributed through that system in reliance on consistent application of that system; it is up to the author/donor to decide if he or she is willing to distribute software through any other system and a licensee cannot impose that choice.
This section is intended to make thoroughly clear what is believed to be a consequence of the rest of this License.
Each version is given a distinguishing version number. If the Program specifies a version number of this License which applies to it and "any later version", you have the option of following the terms and conditions either of that version or of any later version published by the Free Software Foundation. If the Program does not specify a version number of this License, you may choose any version ever published by the Free Software Foundation.
If you develop a new program, and you want it to be of the greatest possible use to the public, the best way to achieve this is to make it free software which everyone can redistribute and change under these terms.
To do so, attach the following notices to the program. It is safest to attach them to the start of each source file to most effectively convey the exclusion of warranty; and each file should have at least the "copyright" line and a pointer to where the full notice is found.
one line to give the program's name and an idea of what it does. Copyright (C) 19yy name of author This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
Also add information on how to contact you by electronic and paper mail.
If the program is interactive, make it output a short notice like this when it starts in an interactive mode:
Gnomovision version 69, Copyright (C) 19yy name of author Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'. This is free software, and you are welcome to redistribute it under certain conditions; type `show c' for details.
The hypothetical commands show w and show c should show
the appropriate parts of the General Public License. Of course, the
commands you use may be called something other than show w and
show c; they could even be mouse-clicks or menu items--whatever
suits your program.
You should also get your employer (if you work as a programmer) or your school, if any, to sign a "copyright disclaimer" for the program, if necessary. Here is a sample; alter the names:
Yoyodyne, Inc., hereby disclaims all copyright interest in the program `Gnomovision' (which makes passes at compilers) written by James Hacker. signature of Ty Coon, 1 April 1989 Ty Coon, President of Vice
This General Public License does not permit incorporating your program into proprietary programs. If your program is a subroutine library, you may consider it more useful to permit linking proprietary applications with the library. If this is what you want to do, use the GNU Library General Public License instead of this License.
In short, ./configure; make will build GNU Go; optionally (running
as root) make install will put it into /usr/local/bin and also
install the man page. You also will probably want to install CGoban.
Get the most recent tar file from <ftp.gnu.org> or a mirror. A list
of mirrors may be found at:
<http://www.gnu.org/order/ftp.html>
Untar the sources, change to the directory gnugo-2.6/. Now do:
./configure make
This makes a binary called interface/gnugo. Now (running as root) type
make install
This will install gnugo in /usr/local/bin/, and also install the man
page gnugo.6 into /usr/man/man6/.
There are two methods of using GNU Go. You may run it from the
command line by just typing gnugo, but it is nicer to run it under
X-Windows using CGoban.
Obtain the most recent version of CGoban from Bill Shubert's web site:
<http://www.inetarena.com/~wms/comp/cgoban>
The CGoban version number MUST be 1.9.1 at least or it won't work. Instructions for using CGoban are elsewhere in this document see CGoban.
On one GNU/Linux machine an incompatible /usr/include/curses.h (from
BSD) had declarations inconsistent with those in
/usr/include/term.h. The symptom of this problem is compilation errors
in engine/moyo.c and engine/showbord.c.
In this case, the correct curses.h was found in /usr/include/ncurses
and a correct compilation was obtained after changing
#include <curses.h>
to
#include <ncurses/curses.h>
in engine/moyo.c and engine/showbord.c. If you have a problem
with errors in engine/moyo.c and engine/showbord.c caused by
curses you should try such a remedy first. If this doesn't work, you shouldn't
curse. Run configure --disable-color to turn off the color option and
compile again. Another alternative if you want color is
configure --without-curses --enable-color. This will substitute
ansi escape sequences for curses.
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.html. You can obtain the
texi2html utility from
<http://www.mathematik.uni-kl.de/~obachman/Texi2html/>. (See also
<http://texinfo.org/texi2html/>.) Unfortunately Version 1.58 of
texi2html does not support the @option and @command
tags. These are supported in Version 1.60-Beta. However our current
recommendation is to use Version 1.58, and to add the lines
'command', 'CODE', 'option', 'SAMP',
to the style_map around line 178 of the perl script.
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. 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.
Other command line options can be listed by typing gnugo --help
-or- man gnugo from any terminal.
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 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. Type in a string to be passed directly to the inferior GNUGO process."
Jago, like CGoban is a client capable of providing GNU Go with a graphical user interface. Unlike CGoban, it does not require X-Windows, so it is an attractive alternative under Windows. You will need a Java runtime environment. Obtain Jago at
<http://mathsrv.ku-eichstaett.de/MGF/homes/grothmann/jago/Go.html>
and follow the links there for the Java runtime environment.
The Go Modem Protocol (GMP) was developed by Bruce Wilcox with input from David Fotland, Anders Kierulf and others, according to the history in
<ftp://www.joy.ne.jp/welcome/igs/Go/programs/protocol.Z>
Any Go program should use this protocol since it is 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.
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/>
--quiet
Don't print copyright and other messages
-l, --infile filename
Load the named SGF file
-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', 'test' or 'gmp'). 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.
-p --playstyle style
Select a style of opening play. The possibilities are:
standard(default opening)no_fuseki(fuseki module turned off)tenuki(often plays elsewhere in the opening)fearless(risky style of play)aggressive(tenuki and fearless)
-D, --depth depth
Deep reading cutoff. When reading beyond this depth (default 14) GNU Go assumes that any string which can obtain 3 liberties is alive. Thus GNU Go can read ladders to an arbitrary depth, but will miss other types of capturing moves.
-B, --backfill_depth depth
Deep reading cutoff. Beyond this depth (default 9) GNU Go will no longer try backfilling moves in its reading.
-F, --fourlib_depth depth
Deep reading cutoff. When reading beyond this depth (default 5) 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.
-M, --memory megs
Memory in megabytes used for hashing (default 8). GNU Go stores results of its reading calculations in a Hash table. If the Hash table gets full, the reading continues, but more slowly. The symptoms of this is that (1) there is an unusually complicated situation on the board and (2) GNU Go is playing slowly. Normally 8 megabytes is adequate to prevent this. However if you have ample memory, or if you have increased the reading depth using the-D,-B,-For-Kyou may want to increase the size of the Hash cache using this option.
--boardsize size: Set the board size
--color color: Choose your color ('black' or 'white')
--handicap number: Choose the number of handicap stones (0-9)
--komi num Set the komi
--testmode mode
This option requires-l filename, implies test mode. The mode can be:See Regression.
- move: test at move node only
- annotation: test at annotation node only
- both: test at move and annotation nodes
- game: test to see if gnugo considered each move made
-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 or Linux Console. (see Colored Display)
-E: colored display of eye spaces
Use RXVT 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/liberty.h.
- DEBUG_GENERAL 0x0001
- DEBUG_COUNT 0x0002
- DEBUG_BOARD 0x0004
- DEBUG_CAPTURE 0x0008
- DEBUG_STACK 0x0010
- DEBUG_WIND 0x0020
- DEBUG_HELPER 0x0040
- DEBUG_LOADSGF 0x0080
- DEBUG_WORMS 0x0100
- DEBUG_LADDER 0x0200
- DEBUG_MATCHER 0x0400
- DEBUG_DEFENDER 0x0800
- DEBUG_ATTACKER 0x1000
- DEBUG_BORDER 0x2000
- DEBUG_DRAGONS 0x4000
- DEBUG_SAVESGF 0x8000
- DEBUG_HEY 0x10000
- DEBUG_SEMEAI 0x20000
- DEBUG_EYES 0x40000
-H, --hash level
hash (see liberty.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 Colored Display).
-b, --benchmark number
benchmarking mode - can be used with -l.
-s, --stack
stack trace (for debugging purposes).
-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.
--decidestring location
Analyze 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.
--score until
Requires-l. until can be "end", "last" or a move.
- end - finish the game by selfplaying from the end of the file until two passes
- last - estimate territorial balance at the end of the of the file
- move - load file until move is reached and estimate territorial balance
--printsgf output file
load SGF file, output final position (requires -l).
--analyze:The analyze options allow analysis of a game stored as sgf file by using
--testmode. When using --testmode with --analyze
move tree variations are ignored.
The --analyze option also works with --benchmark and
--score. The analyze functions will be executed on every move
in --benchmark and --testmode game.
If used with --analyzerfile filename, the results
of the analysis are written to the file filename.
Analyzed board states on other modes:
--score end:
gnugo analyzes every move it makes at the end of the
file until the game is finished.
--score last:
board state at the end of the file will be analyzed
--score move number:
board state just before movenum will be analyzed
--score position:
board state just before position is occupied will be analyzed
--testmode annotation:
board state just before the annotated node is reached will be
analyzed
--analyze options:You can give more than one --analyze option also by
concatenating with "" or by using commas without space.
gnugo --score end --analyzerfile outputfile -l inputfilewill create outputfile and writes the inputfile to it plus the endgame moves for scoring and adds the result property. If you want to overwrite an already existing result property use
--analyze overwrite. This also overwrites DT, AP and RU.
gnugo --score end --analyzerfile outputfile -l inputfile \
--analyze dragonstatus
same as above, but writes to outputfile the dragonstatus for every
move gnugo made from the last move in inputfile to the end of the
game.
gnugo --testmode game --analyzerfile outputfile -l inputfile \
--analyze wormliberties
loads inputfile and writes to outputfile the number of liberties for each worm on
every move.
gnugo --testmode annotation --analyzerfile outputfile -l inputfile \
--analyze capture
loads inputfile and writes to outputfile the capturing move for each
weak group on every move followed by a annotation (see Regression)
This document is an overview of the GNU Go internals. Further documentation of how any one module or routine works may be found in the comments in the source files.
In this document wherever we define a concept we use CAPITAL LETTERS for the term being defined.
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 recomputed. 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.
The engine of GNU Go takes a positions and a color to move and
generates the (supposedly) optimal move. This is done by the function
genmove() in engine/genmove.c.
The move generation is done in two passes:
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 string.
- make_moyo()
Calculate the "territory", "moyo" and "area" for both
sides. "Territory," as used here, is not solid,
incontestible territory, but rather the regions
which are deemed likely to become actual territory.
"Moyo" is the larger region of strong influence which could
become territory if the other side does nothing about it.
"Area" is a still larger region of general influence.
This function also assigns "weakness" to groups which
are strategically vulnerable because of strong opposing
influence. Weakness is accounted for in the field
dragon.safety (see see Dragon).
See Dragon, for make_worms() and make_dragons() more detailed
documentation.
See Moyo, for the algorithms in make_moyo.
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 move generators with a value attached to them. The values are compared and the best move is picked. If two or more moves have the same value, one of them is picked at random.
The move generators in version 2.6 are:
- fuseki()
Generate a move in the early fuseki. This module is undocumented but will be replaced by something better in the future.
- 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 is probably the one in the worst condition currently and badly in need of improvement.
- 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.
See Patterns, for a complete documentation of patterns.
- attacker()
Looks for strings of the opposite color with four liberties or less and tries to kill them.
- defender()
Looks for strings of my color with four liberties or less and tries to defend them.
- eye_finder()
Finds groups of either color which can make two eyes in the next move and looks for the vital point in the eye shapes.
- revise_semeai()
If no move is found yet, change status of opponent groups involved in a semeai fromDEADtoUNKNOWN. After this, genmove runs shapes again to see if a new move turns up.
- fill_liberty()
Fill a common liberty. This is only used at the end of the game. If necessary a backfilling or backcapturing move is generated.
The GNU Go engine is contained in two directories, engine/ and
patterns/. Code related to the user interface, reading and
writing of smart go format files and testing are found in
the directories interface/, sgf/ and
regression/. Code borrowed from other GNU programs is
contained in utils/. Documentation is in docs/.
In this document we will describe the all individual files comprising
the engine code in engine/ and patterns/. In interface/
we mention one file:
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.
In engine/ there are the following files:
attdef.c :
This file containsattacker(),defender()andeye_finder(), three of the move generators called bygenmove(). The moduleattacker()proposes moves which attack enemy strings, whiledefender()proposes moves which defend friendly strings. The reading necessary to decide whether a string can be captured or defended is contained inreading.c, and has already been called bymake_worms(). If a string can be defended, there may be different possible defensive moves, and some of the patterns found byshapes()may move the points of defense. This is the only case where data compiled bymake_worms()andmake_dragons()is changed by a later routine. Because of this feature,shapes()is called beforedefender().Also in
attdef.ciseye_finder(). This module looks for dragons having one and a half eyes. If such a dragon (of either color) is found,eye_finder()proposes making or destroying the half eye.
dragon.c :
This containsmake_worms()andmake_dragons(). These routines are executed before the move-generating modulesshapes(),attacker(),defender(),semeai()andeye_finder(). They find all the worms and dragons and collect important information about them, such as how many liberties each has, whether (in GNU Go's opinion) the string or dragon can be captured, etc. This information remains unchanged until the next move, with one exception: some patterns can move the point of defense of a friendly worm which is under attack.
filllib.c :
Code to force filling of dame (backfilling if necessary) at the end of the game.
fuseki.c :
This module generates fuseki (large scale opening) moves at the beginning of the game. This file is undocumented but will be replaced by something better in the future.
genmove.c :
This file containsgenmove(), is the routine responsible for generating the next move. Opening moves are generated directly in this file, but it calls on other modules for other moves. The modules called by genmove areshapes()(inshapes.c),attacker()anddefender()(inattdef.c),semeai()(insemeai.c) andeye_finder()(inattdef.c). Each module proposes moves, each with a value, andgenmove()selects the one with the highest value.
hash.c :
Hashing code used by for reading. (see Hashing)
hash.h :
header file for hash.c.
liberty.h :
Header file for the whole program.
main.c :
Miscellaneous book-keeping (parsing args, signal
handlers, etc.) sgf file interfaces (reading and writing)
high level game playing (collecting moves from genmove(),
keeping track of passes, etc.) Contains very little
knowledge about go : only that each side plays
alternately, and that two passes marks the end of the
game.
matchpat.c :
This file contains matchpat(), which looks for
patterns at a particular board location.
moyo.c :
This file contains code to estimate territory and influence. See Moyo, for details.
reading.c :
This file contains code to determine whether any given string can be attacked or defended. See Reading, for details.
semeai.c :
This contains semeai(), the module which tries to
win capturing races.
sethand.c :
Initially populate the board with handicap stones.
showbord.c :
This 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.
shapes.c :
This file containsshapes(), the module called bygenmove()which tries to find moves which match a pattern. The pattern matcher has some sophisticated features. (see Patterns). Briefly, the pattern may take into account both friendly and opposing strength in the area, a string's escape potential, whether or not the pattern makes or breaks a valuable connection, whether it involves a dragon classified as dead, and it can also call a helper function hand tailored to the program which typically does some further reading to decide whether the pattern is appropriate.
optics.c :
This contains the code to recognize eye shapes, documented in See Eyes.
worm.c :
This file contains code which is run at the beginning
of each move cycle, before the code in dragon.c, to
determine the attributes of every string.
utils.c :
An assortment of utilities, described in greater detail below.
The directory patterns/ contains files related to pattern matching.
Currently search for 3 types of patterns: move generation patterns
(in patterns.db and similar files such as hoshi.db, autogenerated
from hoshi.sgf See Patterns, for details); eyeshape
patterns (See Eyes, for eyes.db) and connection patterns
(See Dragon, for conn.db).
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 :
This contains the pattern database in human readable form. See PATTERNS for documentation.
engine/utils.cOnly a portion of these functions are documented here. Others are discussed elsewhere see Utility Functions.
legal() :
Determines whether a move is legal.
trymove() :
Pushes the board position on the stack, increments stackp, places the stone on the board if the move is legal, removes captures and increments stackp.
pushgo() :
Pushes the board position on the stack and increments stackp.
popgo() :
Pops the stack.
gprintf() :
printf-like fn (see below under TRACING)
TRACE, VTRACE, DEBUG () - see below under Tracing.
abortgo() :
Wrapper around abort() which dumps the stack. Usually
this is invoked by means of the macro ASSERT (see
ASSERTIONS) below.
utils.c :
Board utility functions :
---
approxlib() :
Counts liberties, but as an optimisation, can be given an upper limit, above which it can stop counting.
count() :
Low level helper for approxlib(), but is used by other fns
updateboard() :
Place a piece on the board, remove captures, and update state information (for ko)
The most important global variable is p[][], which is the go board.
Each element contains EMPTY, WHITE or BLACK.
stackp is the STACK POINTER. When this is zero, p[][]
contains the actual board position. When trymove() is
called, it generates a new board position by placing a stone on
the board and calling updateboard(). Then stackp
is incremented. The old position is saved on the stack.
Thus the value stackp equals the ply below the
current position at which the reading code is thinking.
The state of the board can be saved and restored using pushgo()
and popgo().
p[][] should not be written to directly. Trial moves should
be made using trymove(), which pushes the board, places the
piece, checks the move is legal, and updates the board.
popgo() undoes the move. When a move is actually made,
updateboard() places the piece and removes prisoners.
approxlib() and count() can be called without
actually placing a piece. They report what the number of
liberties would be if a given piece was placed.
Other important data structures are dragon[][] and
worm[][]. These contain information about groups of
stones, whether they are alive or dead, where they can be
attacked, whether they are cutting groups (split enemy
groups), etc.
size, lib, and libi[], libj[]
are global variables written to by count() and
approxlib(). They return the size of the group, and the
number and positions of the liberties.
*NOTE* : if the count is truncated because it reaches the
limit on the number of liberties, then size and
lib may be smaller than the true value.
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 two useful facilities :
%m :
takes two parameters, and displays a formatted board co-ordinate
indentation :
trace messages are automatically indented to reflect the current stack depth, so it is clear during read-ahead when it puts a move down or takes one back.
As a workaround, "outdent" %o at the beginning of the
format string suppresses the indentation.
gprintf() is intended to be wrapped by one of the following:
TRACE(fmt, ...) :
print the message if the 'verbose' variable > 0.
(verbose is set by -t on the command line)
VTRACE(fmt, ...) :
Verbose trace, only if verbose > 1
(not currently used)
DEBUG(flags, fmt, ...) :
whileTRACEis intended to afford an overview of what GNU Go is considering,DEBUGallows occassional in depth study of a module, usually needed when something goes wrong. 'flags' is one of theDEBUG_*symbols inengine/liberty.h. TheDEBUGmacro tests to see if that bit is set in the 'debug' variable, and prints the message if it is. The debug variable is set using the-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. In practice levels 3 and 4 should
only be used when running inside gdb because
the volume of tracing is prohibitive. You can set the
trace level at the command line by -t for
verbose=1, -t -t for verbose=2,
etc.
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.
A quick way to find out roughly the reason for a move is to run
gnugo -l filename -t -a -w -L move number
(You may also want to add --quiet to suppress the copyright
message.) In GNU Go 2.6, the weights with which each move is proposed
are listed.
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 `?'.
Another type of SGF output file is provided by --analyzerfile
(see Invoking GNU Go).
The --decidestring option is used to check the reading code.
This option takes an argument, which is a location on the board in the
usual algebraic notation (e.g. --decidestring C17). This will
tell you whether the reading code 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
--decidestring) the points of attack and defense are cached in
worm.attack and worm.defend. Later, however, they may be
moved, for example during shapes() in response to a D
pattern, so the final points of attack and defense which are found may
differ from those found by --decidestring.
If used with an output file (-o filename)
--decidestring will produce a variation tree showing
all the variations which are considered.
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 and estimates the winner after the last stored move by measuring the influence.
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 counting the territory.
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.
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.
If the option --analyzerfile outputfilename is provided,
the results will be written as comment at the end of the output file,
the result property will be set and the territory will be marked.
You can get a colored ASCII display of the board in which each dragon
is assigned a different letter; and the different safety values
(ALIVE, DEAD, UNKNOWN, CRITICAL) have different
colors. This is very handy for debugging.
Save a game in sgf format using CGoban, or using the -o option with
GNU Go itself.
Open an rxvt window. (Xterm will not work. You may also use the
Linux console.)
Execute:
gnugo -l [filename] -L [movenum] -T to get the colored display.
The color scheme: Green = ALIVE; Yellow = UNKNOWN;
White = 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:
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 moyos found by GNU Go can be displayed from an rxvt window or from the
Linux console using the -m option. This takes a parameter:
-m level
use cumulative values for printing these debug reports :
1 = ascii printing of territorial evaluation (5/21)
2 = table of delta_terri values
4 = ascii printing of moyo evaluation (5/10)
8 = table of delta_moyo values
16 = ascii printing of area (weak groups?) (4/0)
32 = list of area characteristics
64 = table of meta_connect values
128 = trace -p fearless option (big_move priority)
Definitions of these fields is given elsewhere (see Moyo).
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.
In this document wherever we define a concept we use CAPITAL LETTERS for the term being defined.
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 involve simplifying assumptions which can be refined in later implementations.
The array struct worm_data worm[19][19] collects information about the
worms. We will give definitions of the various fields. Each field has
constant value at each vertex of the worm. We will define each field.
struct worm_data {
{
int color;
int size;
float effective_size;
int origini;
int originj;
int liberties;
int liberties2;
int liberties3;
int liberties4;
int attacki;
int attackj;
int attack_code;
int lunchi;
int lunchj;
int defendi;
int defendj;
int defend_code;
int cutstone;
int cutstone2;
int genus;
int value;
int ko;
int inessential;
};
COLOR: If the worm is BLACK or WHITE, that is its color.
Cavities (empty worms) have an additional attribute which we call
BORDERCOLOR. This will be one of BLACK_BORDER, WHITE_BORDER or
GRAY_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_BORDER or WHITE_BORDER.
The last three categories are empty worms classified by bordercolor.
SIZE: This field contains the cardinality of the worm.
ORIGIN: Each worm has a distinguished member, called
its ORIGIN. Its coordinates are (origini, originj). 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[m][n].origini == m) && (worm[m][n].originj == n).
LIBERTIES: For a nonempty worm the field liberties is the number of liberties of the string. This is supplemented by LIBERTIES2, LIBERTIES3 and LIBERTIES4, which are the number of second order, third order and fourth order liberties, respectively.
The definition of liberties of order >1 is adapted to the problem of detecting the shape of the surrounding 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: ..2.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.
We say that n is the DISTANCE of the liberty of order n from the dragon.
ATTACK: If it is determined that the string may be
easily captured, (attacki, attackj) points to an
attacking move. In the present implementation, this
is only used for strings with <4 liberties. The
algorithm in reading.c is fairly reliable at finding
ladders but poor at finding nets (geta). This module
therefore needs rewriting. If no attacking move is
found, then attacki == -1.
ATTACK_CODE: 1 if the worm can be captured unconditionally,
2 or 3 if it can be captured with ko.
If can be captured provided the attacker is willing
to ignore any ko threat, then the attack_code == 2.
If it can be captured provided the attacker can
come up with a sufficiently large ko threat, then
the attack_code == 3.
LUNCH: If lunchi != -1 then (lunchi, lunchj) points
to a boundary worm which can be easily captured.
(It does not matter whether or not the string
can be defended.)
DEFEND: If there is an attack on the string (stored in the ATTACK
field defined above), and there is a move which defends the
string, this move is stored in (defendi, defendj). Otherwise
defendi == -1.
DEFEND_CODE: 1 if the worm can be defended unconditionally,
2 or 3 if it can be defended with ko.
If can be defended provided the defender is willing
to ignore any ko threat, then the defend_code == 2.
If it can be captured provided the defender can
come up with a sufficiently large ko threat, then
the defend_code == 3.
CUTSTONE: This field is equal to 2 for cutting stones, 1 for potential cutting stones. Otherwise it is zero. Definitions for this field:
A CUTTING STONE is one adjacent to two enemy strings, which do not have a liberty in common. The most common type of cutting string is in this situation.
XO
OX
A POTENTIAL CUTTING STONE is adjacent to two enemy strings which do share a liberty. For example, X in:
XO
O.
For cutting strings we set worm[m][n].cutstone=2. For
potential cutting strings we set worm[m][n].cutstone=1.
GENUS: There are two separate notions of genus for worms and
dragons. The dragon notion is more important, so
dragon[m][n].genus is a far more useful field than
worm[m][n].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.
VALUE: A measure of the value of the worm.
KO: For every ko, the flag ko is set to 1 at the ko stone
which is in atari, and also at the ko cavity adjacent
to it. Thus in this situation:
XO
X.XO
XO
the flag ko is set to 1 at the rightmost X stone, and also
at the cavity to its left.
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_dragon.
The function makeworms() will generate data for all worms. For
empty worms, the following fields are significant: color,
size, origini and originj. The liberty,
attack, defend, cutstone, genus and
inessential fields have significance only for nonempty worms.
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 makedragons() will amalgamate worms into dragons by
maintaining separate arrays worms[] and dragons[] containing
similar data. Each dragon is a union of worms. Just as the data maintained in
worm[19][19] is constant on each worm, the data in
dragon[19][19] 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 worm 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 2.6 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 6 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 3, but there is a constraint requiring that neither of the empty intersections is a cutting point.
This is far from perfect. It would be better to amalgamate in either direction, preferably leaving the smallest part as a tail to save or sacrifice.
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 CC23c:
?xx? XO*? straight extension to connect O..? :8,90,0,C,5,5,0,2,2,NULL ?xx? XOb? 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, and 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 type is 0, or else HALF_EYE or FALSE_EYE depending on
which type is found; and (ki, kj) points to a move to kill the half
eye.
struct half_eye_data half_eye[19][19];
struct half_eye_data {
int type; /* HALF_EYE or FALSE_EYE; */
int ki; /* (ki,kj) is the move to kill or live */
int kj;
};
The arrays half_eye[19][19], half_eyei[19][19] and
half_eyej[19][19] are filled. First, half_eye[m][n] is zero
unless a half eye or false eye is found at the empty vertex (m,n); in
this case, it is assigned the value FALSE_EYE or HALF_EYE, and
(half_eyei[m][n], half_eyej[m][n]) points to the dragon having
the false or half eye.
The DISTANCE from an empty vertex to black is the length of the shortest path from the vertex to any black stone, not passing through a white stone. The STRATEGIC DISTANCE is defined similarly except that the path may not pass through any liberty of any white stone, except possibly at the beginning. The distance or strategic distance is -1 (representating infinity) if no such path may be found. Distance and strategic distance to white are defined similarly.
For example in the following diagram on the edge, the distance from the
vertex at a to the color X is six:
........... ..X.XXOOO... ...XOO.a.OO ........... -----------
because we can find the following path of length 6 from a to X:
........... ..X.XXOOO... ...6OO1a.OO ...5432.... -----------
The strategic distance is infinite, however. The above path is
not admissible for strategic distance, because at 3 and 4 it
passes through O's liberties. The path at 1 also is an O
liberty but this is admissible since it is at the very beginning
of the path.
We maintain these data in the arrays distance_to_black[19][19]
and distance_to_white[19][19], and similarly for the
strategic_distance. They may also be accessed by the functions
distance_to() and strategic_distance_to() in utils.c.
The array struct dragon_data dragon[19][19] collects information
about the dragons. We will give definitions of the various
fields. Each field has constant value at each vertex of the
dragon. We will define each field.
struct dragon_data {
int color;
int origini;
int originj;
int borderi;
int borderj;
int size;
float effective_size;
int heyes;
int heyei;
int heyej;
int genus;
int escape_route;
int escape2;
int lunchi;
int lunchj;
int status;
int safety;
int vitality;
int semeai;
};
COLOR: For strings, this is BLACK or WHITE.
For caves, it is BLACK_BORDER, WHITE_BORDER or
GRAY_BORDER. The meaning of these concepts is the same as for worms.
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.
BORDER: This field is relevant for caves. If the color of the
cave is BLACK_BORDER or WHITE_BORDER then the surrounding worms
all have the same color BLACK or WHITE and these have been
amalgamated into a dragon with origin (borderi, borderj).
SIZE: This is the cardinality of the dragon.
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. If any half eyes are found,
(heyi,heyj) points to a move which will create an eye.
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.
VALUE: A measure of the value of the dragon.
ESCAPE ROUTE: The field dragon[m][n].escape_route is the maximum
value of worm[i][j].liberties4 over the worms of the dragon. This is a
measure of the escape potential of the string.
LUNCH: If lunchi != -1, then (lunchi, lunchj) points to a
boundary worm which can be captured easily. In contrast with the worm version
of this parameter, we exclude strings which cannot be saved.
STATUS: An attempt is made to classify the dragons as ALIVE, DEAD,
CRITICAL or UNKNOWN. The CRITICAL classification means
that the fate of the dragon depends on who moves first in the area. The exact
definition is in the function dragon_status(). If the dragon is found
to be surrounded, the status is DEAD if it has less than 1.5 eyes or if the
reading code determines that it can be killed, ALIVE if it has 2 or more eyes,
and CRITICAL if 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 be UNKNOWN.
It is of the utmost importance accomplish this classification as accurately as possible. Unfortunately this is not easy. A problem is that the algorithm described is that it occasionally classifies dragons as DEAD which can actually form two eyes.
SAFETY: This is a field similar to status but more useful for some
purposes. In moyo.c there is a heuristic test for weakness
based on the influence of surrounding dragons. The safety field
is the same as the status unless the status is UNKNOWN. If the status
is UNKNOWN then dragon.safety is set to CRITICAL if it is
found to be weak by the algorithm in moyo.c.
VITALITY: A measure of the life potential of the dragon, used in semeai().
SEMEAI: true if the dragon is involved in a semeai (capturing race).
You can get a colored ASCII display of the board in which each dragon
is assigned a different letter; and the different safety values
(ALIVE, DEAD, UNKNOWN, CRITICAL) have different
colors. This is very handy for debugging.
Save a game in sgf format using CGoban, or using the -o option with
GNU Go itself.
Open an rxvt window. (Xterm will not work. You may also use the
Linux console.)
Execute:
gnugo -l [filename] -L [movenum] -T to get the colored display.
The color scheme: Green = ALIVE; Yellow = UNKNOWN;
White = 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).
The purpose of this document is to describe the algorithm used in GNU Go 2.6 to determine eyes.
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
src/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 1 x !x*x :2,1
Here notation is as above, except that x means X or
EMPTY. The result of the pattern is not different if X has
stones at these vertices or not.
We may abstract the local game as follows. The two players O
and X take turns moving, or either may pass.
RULE 1: O for his move may remove any vertex marked !
or marked . .
RULE 2: X for his move may replace a . by an X.
RULE 3: X may remove a !. In this case, each .
adjacent to the "!" which is removed becomes a "!" . If an
"X" adjoins the "!" which is removed, then that "X" and any
which are connected to it are also removed. Any . which
are adjacent to the removed X's then become .
Thus if O moves first he can transform the eyeshape in
the above example to:
... or !... .XXX.! .XXX.
However if X moves he may remove the ! and the .s
adjacent to the ! become ! themselves. Thus if X
moves first he may transform the eyeshape to:
!.. or !.. .XXX.! .XXX!
NOTE: A nuance which is that after the X:1, O:2
exchange below, O is threatening to capture three X stones,
hence has a half eye to the left of 2. This is subtle, and there are
other such subtleties which our abstraction will not capture. Some of
these at least can be dealt with by a refinements of the scheme, but
we will content ourselves for the time being with a simplified
|- X - X X - - X O X O |X - - - - - X X O O O |O X X X X - - X O O O |O O O O X - O X O O O |1 2 . . O O O O X X O |X O . X X X . 3 X O O |X O O O O O O O X X O |- X X O - O X O - - X |X - - X - X X X X X X |O X X O X - X O O X O
We will not attempt to characterize the terminal states of the local game (some of which could be seki) or the scoring.
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 tabulated in the
database hey.h. During make_worms, which runs before the
eye space analysis, the half eye and false eye patterns are
tabulated in the array half_eye.
A half eye is isomorphic to the pattern (!.) . To see this,
consider the following two eye shapes:
XOOOOOO X.....O XOOOOOO and: XXOOOOO XOa...O XbOOOOO XXXXXX
These are equivalent eyeshapes, with isomorphic local games {2|1}. The first has shape:
!....
The second eyeshape has a half eye at a which is taken when O
or X plays at b. This is found by the topological
criterion (see Eye Topology).
ooo half eye OhO *OX
and it is recorded in the half_eye array as follows. If (i,j)
are the coordinates of the point a, half_eye[i][j].type==HALF_EYE
and (half_eye[i][j].ki, half_eye[i][j].kj) are the coordinates
of b.
The graph of the eye_shape, ostensibly .... is modified by replacing
the left . by !.
The patterns in patterns/eyes.db are compiled into graphs
represented essentially by linked lists in patterns/eyes.c.
Each actual eye space as it occurs on the board is also compiled into a graph. Half eyes are handled as follows. Referring to the example
XXOOOOO XOa...O XbOOOOO XXXXXX
repeated from the preceding discussion, the vertex at b is
added to the eyespace as a marginal vertex. The adjacency
condition in the graph is a macro (in optics.c): two
vertices are adjacent if they are physically adjacent,
or if one is a half eye and the other is its key point.
In recognize_eyes, each such graph arising from an actual eyespace is
matched against the graphs in eyes.c. If a match is found, the
result of the local game is known. If a graph cannot be matched, its
local game is assumed to be {2|2}.
A HALF EYE is a pattern where an eye may or may not materialize,
depending on who moves first. Here is a half eye for O:
OOOX O..X OOOX
A FALSE EYE is a cave which cannot become an eye. Here is are
two examples of false eyes for O:
OOX OOX O.O O.OO XOO OOX
We describe now the topological algorithm used to find half eyes and false eyes.
False eyes and half eyes can locally be characterized by the status of the diagonal intersections from an eye space. For each diagonal intersection, which is not within the eye space, there are three distinct possibilities:
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.
The file moyo.c contains algorithms for the computation of
a number of useful things. Most can be displayed visually using
the -m option (see Colored Display).
Bouzy's dissertation is available at:
<ftp://www.joy.ne.jp/welcome/igs/Go/computer/bbthese.ps.Z>
It contains an algorithm inspired by prior work of Zobrist and ideas from computer vision for determining territory. This algorithm is based on two simple operations, DILATION and EROSION. Applying dilation 5 times and erosion 21 times determines the territory.
To get a feeling for the algorithm, take a position in the early
middle game and try the colored display using the -m 1 option
in an RXVT window. The regions considered territory by this algorithm
tend to coincide with the judgement of a strong human player.
Before running the algorithm, dead stones (dragon.status==0)
must be "removed."
Referring to page 86 of Bouzy's thesis, we start with a function taking a high value (ex : +128 for black, -128 for white) on stones on the goban, 0 to empty intersections. We may iterate the following operations:
dilation : for each intersection of the goban, if the intersection is >= 0, and not adjacent to a <0 one, then add to the intersection the number of adjacent >0 intersections. The same for other color : if the intersection is <=0, and not adjacent to a >0 one, then sub to it the number of <0 intersections.
erosion : for each intersection >0 (or <0), substract (or add) the number of adjacent <=0 (or >=0) intersection. Stop at zero.
It's unbelievable, but it works.
the algorithm is just : 5 dilations, then 21 erosion. 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
I interpret this as a 1 point territory.
The file moyo.c currently uses this algorithm by three ways : 5/21 for territory evaluation, 5/10 for moyo evaluation, and 4/0 for "area ownership", aka "big moyo" and meta cut/connect. Beware, these evaluations don't care of the life and death status of groups. It's only a "graphical" analysis of areas of influence.
After dragon evaluation, the function make_moyo() is called
once to make the static evaluation of the goban : make_moyo()
returns the difference in estimated territory (terri_eval[0])
and computes terri_eval[3] and moyo_eval[3]. It also
computes the area_grid for area ownership & (future) weak group
analysis. All functions assume that stones evaluated DEAD in
the Dragon structure are really dead, and act as they were removed
from the board. Technically, the dilations are made with binary
operators (one row of the goban is stored in two integer, one black
and one white), then the result is stored in a classical array
[19][19] for the erosion computation.
These functions can be used with a color argument whose value is for
current player or for opponent color: delta_terri,
diff_terri, delta_terri_color, delta_moyo,
diff_moyo, delta_moyo_color, meta_connect
and delta_area_color.
The 5,21,10 ... values are stored in the constants:
#define MAX_DILAT 5 #define MAX_ERODE 21 /* 4 or 5 */ #define MOY_DILAT 5 /* for delta_moyo */ /* must MOY_ERODE <= MAX_ERODE if MOY_DILAT != MAX_DILAT*/ #define MOY_ERODE 10 /* number of dilation for area ownership, must be <= MAX_DILAT */ #define OWNER_DILAT 4
As we have seen, 5 dilations/21 erosions produces GNU Go's image of territory. These values are determined by the following considerations:
the public functions are :
int delta_terri(int ti, int tj, int color)
- test the ti tj move as regards territorial evaluation. This evaluation take care of captures, but no komi is added. The returned value is the difference in territorial evaluation between terri_test and first call to
make_moyo()the evaluation is for "color - OTHER_COLOR".- Tested values are cached, if different patterns test the same ti tj, no extra computation is needed. Note: this function is not really used in GNU Go : future usage could be for a end game module, or for displaying who has the lead in the game.
int diff_terri(int ti, int tj, int color)
wrapper for : delta_terri(..,color)+delta_terri(..,other_color)
int terri_color(int m,int n)
returns the color (WHITE,BLACK,EMPTY) of the m,n intersection, as seen by the 5/21 algorithm. This is a public access to already computed values during make_moyo().
int delta_terri_color(int ti,int tj, int color, int m, int n)
returns the color(WHITE,BLACK,EMPTY)of them,nintersection, as seen by the 5/21 algorithm, after a test move inti,tj. The values of this function are computed and cached during thedelta_terri()evaluation. Calling this function also computes and cachedelta_terri(). (See Note about cachingdelta_*_color()functions.)
extern variables :int terri_eval[3]computed once bymake_moyo()terri_eval[WHITE]: white territoryterri_eval[BLACK]: black territoryterri_eval[0]: difference in territory (color - other_color)int terri_test[3]computed bydelta_terri()terri_test[WHITE]: territory evaluation fromdelta_terri()for BLACKterri_test[BLACK]: territory evaluation fromdelta_terri()for WHITEterri_test[0]: return ofdelta_terri(), difference in territorial evaluation betweenterri_test()and first call tomake_moyo().
Sample: b marks black's estimated territory (X), w
or White (O).
White to play : a move to J11 will bring +7 territorial balance.
A B C D E F G H J K L M N 13 b b b b . . . . . . . . . 13 12 b b b X b . . . . . . . . 12 11 b b b b b . . . . . O . . 11 10 b b b X b . . . . . . . . 10 9 b b b b . . . . . . X . . 9 8 b b X b . . . . . . . . . 8 White territory 22 7 b b b . . . . . . . . . . 7 6 . b b . . . . . . . . . . 6 Black territory 30 5 . . b . . . . . . . O . . 5 4 . . . X . . . . w w w w w 4 3 . . . . . . O w w O w w w 3 2 . . . . . . . w w w w w w 2 1 . . . . . . . w w w w w w 1 A B C D E F G H J K L M N
delta_terri :
20 21 20 19 11 10 10 8 7 6 3 4 3 23 23 21 X 12 11 13 10 8 6 3 3 4 25 26 25 22 10 11 8 8 7 6 O 5 5 24 26 27 X 9 8 8 5 5 2 3 7 7 25 27 26 13 10 7 7 7 5 4 X 11 8 23 25 X 12 10 9 6 8 5 6 5 10 5 21 19 18 13 11 11 11 10 6 5 5 4 5 14 14 14 13 11 12 13 7 5 2 2 2 2 14 12 11 11 12 11 7 5 2 0 O 1 1 11 10 9 X 9 5 4 2 0 -1 -1 -1 1 9 8 14 7 4 3 O -1 -1 O -1 -1 -1 8 7 6 7 6 2 1 -1 -1 -1 -1 -1 -1 5 4 5 4 3 2 1 0 -1 -1 -1 -1 -1
5 dilations and 10 erode give a value we call MOYO. Moyo has an
advantage over territory (5/21) since it permits immediate
computation of the value of a move. It is intended to be used in
conjunction with some patterns as an helper. The value 5 and 10 are
empiric, other could have a similar effect : 4/8, 5/9 , etc... Using
5 dilation permit to use some common results with territorial
evaluation 5/21. The moyo evaluation does not count prisonners nor
komi, but takes in account dragon DEAD stones.
the public functions are :
int delta_moyo(int ti, int tj, int color)
- test the ti tj move as regards moyo evaluation. The returned value is the difference in territorial evaluation between moyo_test and first call to make_moyo() the evaluation is for "color - OTHER_COLOR".
- Tested values are cached, if different patterns test the same ti tj, no extra computation is needed.
int diff_moyo(int ti, int tj, int color)
wrapper for : delta_moyo(..,color) + delta_moyo(..,other_color)
int moyo_color(int m,int n)
returns the color (WHITE,BLACK,EMPTY) of the m,n intersection, as seen by the 5/10 algorithm. This is a public access to already computed values during make_moyo().
int delta_moyo_color(int ti,int tj, int color, int m, int n)
returns the color (WHITE,BLACK,EMPTY) of the m,n intersection, as seen by the 5/10 algorithm, after a test move in ti,tj. The values of this function are NOT cached during the delta_moyo() evaluation. But calling this function caches his result for future call, and also computes and cachedelta_moyo(ti,tj,color). (See note about cachingdelta_*_color()functions.)
extern variables :int moyo_eval[3]is computed once bymake_moyo()moyo_eval[WHITE]: white moyo evaluationmoyo_eval[BLACK]: black moyo evaluationmoyo_eval[0]: difference in moyo (color - other_color)int moyo_test[3]is computed by delta_moyo for testing one movemoyo_test[WHITE]: white moyo evaluation fromdelta_moyo()moyo_test[BLACK]: ...moyo_test[0]: return ofdelta_moyo(), difference in moyo between test moyo and first moyo evaluation (color - other_color)
Example: white to play. A move at F4 would increase moyo balance by 20 points for white.
A B C D E F G H J K L M N 13 b b b b b b b b b b . . . 13 12 b b b b b b b b b b . . . 12 11 b b b b X b b b b b . . . 11 10 b b X b b b b b b X . . . 10 9 b b b b b b . . . . . . . 9 8 b b b b b . . . . . O w . 8 White territory 18 7 . . b X b . . . . . w w w 7 6 . . . . . . . . . w w w w 6 Black territory 32 5 . . . . . . . . . w w w w 5 4 . . w O w . . . w w w w w 4 W/B moyo 36/50 : -14 3 . . w w w w . . w w O w w 3 2 . . . w . . . . . w w w w 2 1 . . . . . . . . . w w w w 1 A B C D E F G H J K L M N
delta_moyo :
15 17 19 23 24 26 21 21 18 19 15 11 9 18 20 20 24 29 29 24 23 20 21 20 14 8 17 23 19 16 X 26 33 31 21 19 25 14 8 16 20 X 15 16 35 34 32 29 X 13 10 5 16 16 18 15 16 17 23 39 19 7 4 4 2 15 16 13 29 17 25 24 20 12 6 O 0 0 14 16 17 X 23 23 21 18 14 6 1 0 0 20 13 13 13 16 19 31 14 11 7 3 0 0 17 16 6 8 9 25 25 23 8 5 2 -1 0 13 14 12 O 17 20 21 19 17 3 2 -1 -1 11 11 9 22 13 17 17 17 16 14 O -1 -1 11 9 21 20 21 13 16 15 14 12 12 -1 -1 9 21 20 20 20 21 13 14 12 12 12 12 -1
This algorithm finds areas of influence, something bigger than classical moyo, with light connection between stones. This tool is intended to find weak and strong groups very early in the game. Currently it is used as an helper to find moves who cut ot connect these areas at a large scale. This module of GNU Go will probably evolve.
The first use will be to test if a tested move will :
The public functions are :
int area_stone(int m,int n)
int area_space(int m,int n)
int area_color(int m,int n)
these functions return the number of stones, empty spaces and the color
of the area around the m n intersection. They are just wrapper function
to get data already stored in tables computed by make_moyo().
int area_tag(int m,int n)
void set_area_tag(int m,int n,int tag)
these funtions (currently unused) are wrappers to access to a tag value associated with an area (for example his weakness).
int meta_connect(int ti, int tj,int color)
Test one move(ti, tj)for its effect upon area--if the number of distinct areas of each color changes, we can detect some of these events:meta_connect returns 15 point for each connection and 10 point for each cut. The objective is to give GNU Go the ability to lauch early attacks on weak groups, and connect his own groups. Note: the area ownership algorithm is a little more complex than 5/21 or 5/10, for two reasons: we need to correctly analyse the connection of two areas by a secure kosumi stone, and the sum of areas is computed by recursive functions.
- cut one opponent group in two (without creating an isolated stone)
- meta-connect two groups of player color
int delta_area_color(int ti,int tj, int color, int m, int n)
returns the color (WHITE,BLACK,EMPTY) of the(m, n)intersection, as seen by the 4/0 algorithm, after a test move in(ti,tj). The values of this function are NOT cached during the meta_connect() evaluation. But calling this function caches his result for future call, and also computes and cachemeta_connect(ti,tj,color). (See note about cachingdelta_*_color()functions.)
The values for cutting/connecting can be changed (all this need tuning):
/* number of bonus points for each group connected and opponent group cut */ #define GR_BONUS_CONNECT 15 #define GR_BONUS_CUT 10
Sample:
The 'b' black area are changed to '-' for readibility. A white move at K5 got 25 points : this means that meta_connect thinks it would separate the J3 stone from K10, and connect the white stones together:
A B C D E F G H J K L M N 13 . . - - . w w . - - - . . 13 12 . - - - . w w . - - - - . 12 11 - - - - . w w . - - - - - 11 10 - - - X . O w . - X - - - 10 9 - - - - . w w . - - - - - 9 8 - - X - - w w . - - - - . 8 White territory 2 7 - - - - - w w . - - w w . 7 6 - - - . . w . - - w w w w 6 Black territory 4 5 . . . w w w - - - w w w w 5 4 w w w w w w - - - w O w w 4 W/B moyo 19/24 : -5 3 w w w O w w - - X - w w w 3 2 w w w w w w - - - - w w w 2 1 . w w w w w - - - - w w . 1 A B C D E F G H J K L M N
area 2 A11: color B, 2 stone 28 spaces area 4 A4: color W, 2 stone 39 spaces area 9 G5: color B, 2 stone 46 spaces area 11 K6: color W, 1 stone 21 spaces
meta_connect :
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . O . 10 10 X . . . . . . . . . 10 10 25 25 10 . . . . X . . 10 10 25 25 25 25 10 . . . . . 10 10 10 25 25 25 25 25 . . . . . . 10 25 25 25 25 25 10 . . . . . . . 25 25 25 25 10 . . . . . . . . . 25 25 10 O . . . . . O . . . . X . . . . . . . . . . . . 15 . . . . . . . . . . . 15 15 15 . . .
After white K5, black played G3, now playing in the center could connect all white forces.
A B C D E F G H J K L M N 13 . . - - . w w . - - - . . 13 12 . - - - . w w . - - - - . 12 11 - - - - . w w . - - - - - 11 10 - - - X . O w . - X - - - 10 9 - - - - . w w . - - - - - 9 8 - - X - - w w . - - - - . 8 White territory 1 7 - - - - - w . w w w w w . 7 6 - - - . . . - w w w w w w 6 Black territory 4 5 . . . w w - - w w O w w w 5 4 w w w w w - - - - w O w w 4 W/B moyo 17/26 : -9 3 w w w O w - X - X - w w w 3 2 w w w w w - - - - - w w w 2 1 . w w w w - - - - - w w . 1 A B C D E F G H J K L M N
area 2 A11: color B, 2 stone 28 spaces area 4 A4: color W, 1 stone 20 spaces area 8 F13: color W, 1 stone 12 spaces area 9 F5: color B, 2 stone 20 spaces area 12 H7: color W, 2 stone 27 spaces area 13 J13: color B, 1 stone 25 spaces
meta_connect :
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 . . . . . . . . X . O 15 15 15 X . . . . . . . 15 30 15 15 15 15 15 . . . . X 15 30 30 30 15 15 15 15 . . . . 15 30 30 30 30 30 15 15 15 . . . . 15 30 30 30 30 30 15 15 . . . . . . 15 30 30 30 30 15 O . . . . . . . 15 30 30 15 . . O . . . . . O . 15 X 10 X . . . . . . . . . . . . . . . . . . . . . . . . 15 . . . . .
Dragon SAFETY is a modification of the dragon STATUS that takes into account the weakness of groups, as found by this algoritm.
Weak dragons with dragon[m][n].status == UNKNOWN
are tagged by
dragon[m][n].safety = CRITICAL
These are defined as having 2 or more stones with between 0 and 20 points of area, computed using the 4/0 algorithm.
Function:
int number_weak(int color): returns the number of weak groups
found for one color.
(experimental) the use of search_big_move function aim to evaluate the value of moves by an empiric rule. Then, if the move proposed by genmove() got a lower priority, the big_move is played. Use option -p fearless to select it.
int very_big_move[3]
public variable, contains the best territorial move found, value and position.
void search_big_move(int ti, int tj, int color, int val)
evaluate a proposed move, and keep it if it's the bigger found current evaluation rule :dt * 0.9 + 15 + val * 0.7, wherevalis the value of the move as proposed byshapes()and other modules, anddtisdiff_terri(ti,tj,color).
This 3 functions use the same goban stack for storing their results. The stack size is :
#define COLOR_STACK_SIZE 70 static goban_t boardstack[COLOR_STACK_SIZE];
This is intentionally left low to minimise memory usage. When the stack is full, the older values are suppressed when a new need of storage come. (the stored values are available during one "movenum" turn)
delta_terri(ti,tj,color) uses a stack level, available for
further delta_terri_color(ti,tj,color,?,?) call.
delta_moyo() (and meta_connect) are often called, they do not store
their result in this stack every time--only when the delta_*_color() is
called.
Beware: all dead groups are considered as removed for these functions !
A database of patterns is supplied in patterns.db These are ascii representations, of the form:
Pattern EB115 ??o| sente hane ?Oo| XX*| ...| ?.?| :8,50,0,O,5,5,5,0,0,sente_hane_helper
where O marks a friendly stone, X marks enemy stones,
. 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 right in this example is the edge of
the board itself--this is an edge pattern. Corners can also be
indicated. So this pattern describes a hane on the first line. The
o makes sure that it would not be in atari immediately, though
the matcher can check for this automatically (see class). 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 importance. Optionally, a
function called a "helper" can be provided to assist the matcher in
deciding the worth of the move, and a simple measure of the influence
of nearby stones can be factored in. In this case, there is a helper,
the sente_hane_helper, which may be found in helpers.c. Most patterns
do not require a helper, and this field is filled with NULL.
The matcher searches the board for places where this layout appears on the board, and chooses the highest scoring pattern.
After the pattern, some supplementary information in the format:
:trfno, patwt, assistance, classification,
obonus, xbonus, splitbonus, minrand, maxrand, 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.) patwt is the numerical pattern
value - if there is a helper function (see below), it is the maximum
weight it can return.
The assistance attribute reflects the fact that a pattern may have different values depending on external circumstances. For example, a pattern to connect is less important where I am powerful, but more important where my opponent is powerful. There are two different methods of assistance, wind assistance (see Wind Assistance) and moyo assistance (see Moyo Assistance).
The classification scheme is as follows : a sequence of zero or more of the following characters, each with a different meaning.
s:
no checking is done. This is appropriate for sacrifice patterns. Otherwise, the matcher requires that the stone played cannot be trivially captured.
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 is classified as ALIVE or UNKNOWN.
o:
It is checked that every friendly (O) stone of the pattern
belongs to a dragon which is classified as DEAD or UNKNOWN.
X:
It is checked that every opponent (X) stone of the pattern
belongs to a dragon which is classified as ALIVE or UNKNOWN.
x:
It is checked that every opponent (X) stone of the pattern
belongs to a dragon which is classified as DEAD or UNKNOWN
A:
If it is found that anXstone at(m,n)of the pattern can be captured (worm[m][n].attacki != 0) then the move at*is tried. If it is found to attack the stone,worm[m][n].attackis set to equal*. This means that the attacker will later use this move to attack the stone.
D:
If it is found that anOstone at(m,n)of the pattern can be captured (worm[m][n].attacki != 0) then the move at * is tried. If it is found to defend the stone,worm[m][n].defendis set to equal*. This means that the defender will later use this move to defend the stone.
C:
If two distinctOdragons occur in the pattern, the pattern is given the minimum of theconnection_valueand the return value of the pattern.
B:
If two distinctXdragons occur in the pattern, the pattern is given the minimum of theconnection_valueand the return value of the pattern.
L:
Match the pattern and run the helper, even if the weight is less than that of the largest pattern found already. This is appropriate for patterns whose significance is in the side effects of the helpers.
One common classification is OX (which rejects pattern if
either sides stones are dead). The string - may be used as a
placeholder. (In fact any characters other than the above and ,
are ignored.)
o and O could conceivably appear in a class, meaning it
applies only to UNKNOWN. Similarly X and x could
be used together.
Some care must be taken with the A and D classes. If
more than one worm that can be attacked or defended is present in the
pattern, only one of them, arbitrarily chosen, will be found.
The classes B and C can be used together. If both
connection values are greater than 0, the pattern is given a combined
value which is the larger of them plus a fraction of the smaller one.
The values obtained for the B and C classes are further
limited by the sum of the primary pattern weight (patwt) and the
assistance value. The bonuses described below are applied after this
limitation.
The field obonus is a bonus which is added when the pattern contains
any dragon of color O with dragon[m][n].safety != 0.
This means that the dragon has size at least 2 and between 0 and 20
points of area, computed by the Bouzy 4/0 algorithm. Similarly the
xbonus is added when the pattern contains at least one weak X dragon.
The field splitbonus is a bonus which is added when the move splits opponent dragons on a large scale or joins own dragons in the same manner (see Moyo).
To avoid playing the same moves each game, minrand and maxrand specifies a random adjustment of the move value, uniformly distributed between minrand and maxrand, inclusively. This feature is primarily used for fuseki moves, where the choice of exact moves is a matter of inspiration anyway.
helper_fn is the name of a C function which will be invoked
to assist in the evaluation of the pattern. It will be passed
the co-ordinates on the board of the pattern element marked *,
the rotation of the pattern which has been matched,
and the color of the piece for whom the move is being considered.
(O in the key above). Facilities are provided for navigating
around the pattern taking the rotation into account.
Usually a pattern will only contribute a move if its value is
large enough to outweigh all other moves which have been
found. There is an exception to this, however. If the
pattern classification string contains a D, the pattern
is a defensive one. If an O string is found in the pattern
which can be captured, and if the move at * defends it,
then the point of defense (worm[m][n].defendi, worm[m][n].defendj)
is moved to *. This means that even if the pattern has small
value, the defensive move will be remembered later when
defender() is run.
Another exception is patterns with a classification string containing
an A. These patterns are offensive ones. If an X string is found
in the pattern which can be captured but also defended, and if the move at
* also attacks it, then the point of attack (worm[m][n].attacki,
worm[m][n].attackj) is moved to *. This means that even if the pattern
has small value, the offensive move will be remembered later when attacker()
is run. Notice that this means that the suggested move will never find an
attack that wasn't found otherwise, but it can be used to capture enemy stones
more efficiently or with better shape than the move attacker() would have
found unassisted.
Helper functions can be provided to assist the matcher in weighing up
the importance of a move. 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, a
transformation number is supplied. This number can be passed to a
utility function offset() with the relative co-ordinates in the
original, untransformed pattern. This function will return the actual
board co-ordinates to use for the indicated stone.
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 defend_bamboo_helper. This begins with a comment:
/* ?X? ?X? O.O ObO O.* Oat */
The image on the left is the actual pattern. On the right we've taken this image and added letters to label (ti, tj), (ai, aj) and (bi, bj). Of course t is always at *, the point where GNU Go will move if the pattern is adopted.
int
defend_bamboo_helper (ARGS)
{
int ai, aj, bi, bj;
int tval=0;
int other=OTHER_COLOR(color);
OFFSET(0, -1, ai, aj);
OFFSET(-1, -1, bi, bj);
if (strategic_distance_to(other, ti, tj)>10)
return (0); /* solid connection is better */
if (TRYMOVE(bi, bj, other)) {
if (TRYMOVE(ai, aj, color)) {
if (safe_move(ti, tj, other))
tval=COMPUTE_SCORE;
popgo();
}
popgo();
}
return (tval);
}
The OFFSETs tell GNU Go the positions of the two stones at a=(ai,aj)
and b=(bi,bj). The correctness of the coordinates (relative to
t=*=(ti,tj)) can be confirmed by consulting the diagram in the
prefatory comment. The macro TRYMOVE invokes the function trymove(),
ARGS supplies standard arguments to the helper, and COMPUTE_SCORE
assigns the value of the pattern (see Pattern Attributes).
The pattern is subjected to two tests. First, the strategic_distance to X (see Dragon) must not be too great. The rationale behind this test is that if the strategic distance is great, then simply making a solid connection probably secures one point more territory. On the other hand if the strategic distance is small, the region in question may not be secure territory, and the bamboo joint is often better.
Hand-coding helpers such as this one is a powerful tool but not always needed. The same functionality can often be obtained more easily using an autohelper (see Autohelpers).
Wind assistance, wind(ucutoff, uvalue, mycutoff, myvalue), is
based on the power of the stones in a neighborhood of the considered
move. My power (mypower) and your power (upower) are
measured by the function testwind(). The actual value of the
wind assistance is given by the formula:
To calculate a color's power near the point *, we sum 6-d)
where d is the distance of a stone to *, where the sum
is over all stones of the given color with d<6.
upower and ucutoff must have the same sign, as must
mypower and mycutoff. In practice we have mostly used
positive values for these parameters. We have always given uvalue and
myvalue the value 1 or in rare instances 2.
For example
"connect if invaded" OX.. .*.O .?.? :8,55,wind(20,1,0,0),-,0,0,0,NULL
These represent additional biases to the score for the influence of
nearby stones. The first pair are a multiplier and a cutoff for enemy
stones, and the second for friendly stones. The actual weight
(computed in the function compute_score()) is given by the
formula:
uvalue*min(upower,abs(ucutoff)) + myvalue*min(mypower,abs(mycutoff)).
Typically uvalue (if nonzero) would have the value 1, meaning that the score increases by 1 for each increase in upower, up to a maximum of ucutoff, after which it does not increase. Thus in this example, the value of the pattern can increase up to 75, becoming more valuable when the opponent becomes strong in the area. This is a good feature for patterns which help the safety of our group.
Moyo assistance, moyo(moyocutoff, moyovalue), is based on an
estimation of "moyo" (see Moyo).
In practice this is a combination of territory and influence for both
players. The function delta_moyo() computes the difference in
moyo between the current position and after the move has been
made. The actual value of the moyo assistance is given by the formula:
moyovalue*min(deltamoyo,moyocutoff)
Since the pattern database decides GNU Go's personality to a very great extent, much time can be devoted to "tuning" it. 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 if its maximum possible contribution is smaller than a
pattern already found. This makes the program less efficient, but then
you can see how much you must increase a pattern value in order to
`promote' a better move over the move actually chosen.
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 sgf 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 pattern matcher. If bad moves are being proposed, one
may modify a pattern to exclude it, or reduce the value of the
pattern. If important moves are not proposed at all, you may have
found a gap in the pattern database, and you can add a pattern. If the
right move is proposed but with too low a score, this may be a sign
that you should adjust its weight upwards. It is almost always best to
make the *minimum* adjustment needed to correct the bad behavior.
If you decide to add a pattern, give some thought to adding the
pattern in exactly the right generality by putting ? at
irrelevant locations, and by using the o and x options.
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.
Pattern weights exceeding 99 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 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.
Alternatively, you can use the CGoban tools to delete all moves after
and including the one you want to study, and then load without the
-L option.
If a pattern is contributing a bad move, you can adjust its weight downward, or you you can adjust the weight of a pattern which is contributing a good move up. If no pattern is contributing the move that you think should be made, then you may add a pattern.
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 changing the value of
seed in main.c to a fixed nonzero integer. If seed==0, then GNU
Go will play a different game each time.
In addition to the hand-written helper functions in helpers.c there
can be automatic helper functions. These are briefly described in
the pattern database and compiled into C source which goes into
patterns.c.
The "pattern compiler" is based on the idea of constraint diagrams and expressions. To give an example, one pattern consists of a pair of diagrams:
Pattern ED54 |oOOX maybe capture corner |..XO |.*XO |..?? +---- :8,85,0,s,10,0,0,0,0,NULL |obbX |..Aa |.*Aa |..?? +---- ;(lib(A)<=4) && (lib(a)>=lib(A)-1) && (lib(b)>=lib(A)) ;&& (!dead(A)||attack(a))
The first diagram and the colon line has exactly the same interpretation as usual. The diagram below and the semicolon line(s) are optional and can only be used to reject the pattern given above. Note that some strings now have labels which are referred to in the constraint.
Only strings for which we have constraints need be labeled. Labels may
be any letter except OoXxt. To make the database consistent and easy to
read it is our convention that X strings should be upper-case
and O strings lower-case, but the implementation does not
enforce this. Neither does it require that all stones in a string be
labeled (it goes with the first appearance) but it is good practice to
do so anyway.
The constraint expression is transformed by mkpat into an
automatically generated helper function (there is a new field in the
pattern struct, so it does not conflict with the old helper). lib(x)
can be regarded as a macro which is expanded by mkpat into
worm[xi][xj].liberties. The resulting expression must be valid C code,
otherwise the generated patterns.c won't compile. In principle any
code can be written on the line but to keep the database maintainable
we should restrict ourselves to boolean and arithmetic expressions,
which anyone should be able to understand and write with no more than
a little trouble. If the expression evaluates to true the pattern is
accepted by the autohelper, if false it is rejected. If there are
multiple semicolon lines for the same pattern, these are concatenated
before generating the code.
lib(x) lib2(x) lib3(x) lib4(x)
Number of first, second, third, and fourth order liberties of a worm respectively (see Dragon).
xlib(x) olib(x)
The number of liberties that an enemy or own stone, respectively, would obtain if played 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) alive(x) unknown(x) critical(x) dead(x)
Status of a dragon. status(x) returns an integer that can have
the values ALIVE, UNKNOWN, CRITICAL, or
DEAD. The four other functions returns true if the dragon has
the corresponding status and false otherwise (see Dragon).
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 (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.
cutstone(x) returns worm[x].cutstone, which can be 0, 1,
or 2 (see Dragon).
weak(x)
True for a dragon with safety==CRITICAL.
attack(x) defend(x)
These give the 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 own 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.
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.
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.
The pattern code in GNU Go 2.6 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 2.6, the ascii patterns.db file is precompiled into tables (see patterns.h) by a standalone program mkpat.c, and the resulting file patterns.c is 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.
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, f=e, h=g - b=a, c=d, e=f, g=i \ e=a, g=c, f=b, h=d / h=a, f=c, g=b, e=d 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,f,d,g,.... and choose
first 2 for X and -, the first 4 for |, -,
/, and \, and all 8 for non-symmetrical patterns.
i) An entry in the pattern header states whether the anchor is an X or an O. This helps performance, since all transformations can be rejected at once if the anchor stone does not match. (Ideally, we could just define that the anchor is always O or always X, but some patterns contain no O's and some contain no X's.)
ii) The pattern header contains the size of the pattern (ie the co-ordinates of the top left and bottom right elements) relative to the anchor. This allows the pattern can be rejected quickly if there is not room for the pattern to fit around the anchor stone in a given orientation (ie it is too near the edge of the board). The bounding box information must first be transformed like the elements before it can be tested, and after transforming, we need to work out where the top-left and bottom-right corners are.
iii) The edge constraints are implemented by notionally padding the pattern with rows or columns of '?' until it is exactly 19 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
iv) The elements in a pattern are sorted so that non-space elements are checked before space elements. It is hoped that, for most of the game, more squares are empty, and so the pattern can be more quickly rejected doing it this way.
v) The patterns themselves are sorted by decreasing maximum-weight, which is the maximum value the pattern can take, taking weight and wind assistance into account. For this to work, the weight stored for patterns with helpers must be the maximum which the helper can return. As a hint, to simplify maintenance, the helper can access the stored weight from the pattern structure passed in.
vi) The actual tests are performed using an 'and-compare' sequence. Each board position is a 2-bit quantity. %00 for empty, %01 for O, %10 for X. We can test for an exact match by and-ing with %11 (no-op), then comparing with 0, 1 or 2. The test for 'o' is the same as a test for 'not-X', ie not %10. So and with %01 should give 0 if it matches. Similarly 'x' is a test that bit 0 is not set.
This is a compile time option. By editing the makefile, you can use this faster code to match patterns. The only disadvantage to using this code is that it might be harder to understand and debug.
As described in (vi), the comparisons between pattern and board are performed as 2-bit bitwise operations. Therefore they can be performed in paralled, 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 (vi) 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 in files
in patterns/ called hoshi.sgf, komoku.sgf,
sansan.sgf, mokuhadzushi.sgf and takamoku.sgf.
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 an A and the value
given by a comment.
The joseki compiler is able to generate a constraint line in the
.db. The square symbol is a shortcut for oarea(), the
triangle is xarea() and the circle is
(!oarea()&&!xarea()) = an empty area.
The delimiter between value and classification in the SGF
comment must be ;, for example:
81; D
Spaces and \n may be omitted.
These features are experimental and are currently not used in the joseki files.
The patterns in patterns/conn.db are compiled separately
from the other patterns. When a B pattern is found, a cutting
point is set in the worm data structure and make eye space marginal for the
connection inhibiting entries of the pattern. If it is a C pattern,
amalgamate the dragons in the pattern.
The process of visualizing potential moves done by you and your opponent to learn the result of different moves is called "reading".
In GNU Go, this 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.
Many of the reading functions make use of null pointers.
For example, a call to attack(i, j, &ai, &aj) will return
1 if the string at (i, j) can be captured, 2 or 3 if it
can be attacked with ko, and 0 if it is safe. The point of attack
(in case it is vulnerable) is returned in (ai, aj). However
many times we do not care about the point of attack. In this case,
we can substitute a null pointer: attack(i, j, NULL, NULL).
Depth of reading is controlled by a parameter depth. This
has a default value DEPTH (in liberty.h), which is
set to 14 in the distribution, but it may also be set at the
command line using the -D 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.
Currently the reading code does not try to defend a string by
attacking a boundary string with more than two liberties. Because
of this restriction, it can make oversights. A symptom of this is
two adjacent strings, each having three or four liberties, each
classified as DEAD. To resolve such situations, a function
small_semeai() (in engine/semeai.c) looks for such
pairs of strings and corrects their classification.
The backfill_depth is a similar variable with a default 10. Below this depth, GNU Go will try "backfilling" to capture stones. For example in this situation:
.OOOOOO. on the edge of the board, O can capture X but OOXXXXXO in order to do so he has to first play at a in .aObX.XO preparation for making the atari at b. This is -------- called backfilling.
Backfilling is only tried with stackp <= backfill_depth. The
parameter backfill_depth may be set using the -B
option.
The fourlib_depth is a parameter with a default of only 5.
Below this depth, GNU Go will try to attack strings with
four liberties. The fourlib_depth may be set using the
-F option.
The parameter ko_depth is a similar cutoff. If
stackp<ko_depth, the reading code will make experiments
involving taking a ko even if it is not legal to do so (i.e., it
is hypothesized that a remote ko threat is made and answered
before continuation). This parameter may be set using the
-K option.
The reading functions generally return 1 for success, and 0 for failure. If the result depends on ko, they return 2 or 3. A return code of 2 means that the attack or defense is successful provided the attacker or defender is willing to ignore a ko threat; a return code of 3 means the attack or defense is successful provided the player can come up with a sufficiently large ko threat.
A partial list of the functions in reading.c:
int attack(int m, int n, int *i, int *j):
The basic functionattack(m, n, *i, *j)determines if the string at(m, n)can be attacked, and if so,(*i, *j)returns the attacking move, unless*iand*jare null pointers. (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. Returns 2 or 3 if the result depends on ko: returns 2 if the attack succeeds provided attacker is willing to ignore any ko threat. Returns 3 if attack succeeds provided attacker has a ko threat which must be answered.
find_defense(int m, int n, int *i, int *j):
The functionfind_defense(m, n, *i, *j)attempts to find a move that will save the string at(m,n). It returns true if such a move is found, with(*i, *j)the location of the saving move (unless(*i, *j)are null pointers). It is not checked that tenuki defends, so this may give an erroneous answer if!attack(m,n). Returns 2 or 3 if the result depends on ko. Returns 2 if the string can be defended provided (color) is willing to ignore any ko threat. Returns 3 if (color) has a ko threat which must be answered.
safe_move(int i, int j, int color) :
The functionsafe_move(i, j, color)checks whether a move at(i, j)is 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.
The next few functions are essentially special cases of attack
and find_defense. They are coded individually.
attack2(int m, int n, int *i, int *j) :
Determine whether a string with 2 liberties can
be captured. Usage is similar to attack.
attack3(int m, int n, int *i, int *j) :
Determine whether a string with 3 liberties can
be captured. Usage is similar to attack.
attack4(int m, int n, int *i, int *j) :
Determine whether a string with 4 liberties can
be captured. Usage is similar to attack.
defend1(int m, int n, int *i, int *j) :
Determine whether a string with 1 liberty can be
rescued. Usage is similar to find_defense.
defend2() :
Determine whether a string with 2 liberties can be
rescued. Usage is similar to find_defense.
defend3() :
Determine whether a string with 3 liberties can be
rescued. Usage is similar to find_defense.
find_cap2() :
If(m,n)points to a string with 2 liberties,find_cap2(m,n,&i,&j)looks for a configuration:O. .*whereOis an element of the string in question. It tries the move at*and returns true this move captures the string, leaving(i,j)pointing to *.
chainlinks(int m, int n, int *adj,
int adji[MAXCHAIN], int adjj[MAXCHAIN], int adjsize[MAXCHAIN],
int adjlib[MAXCHAIN]):
Find the CHAIN surrounding a string. This is the set of adjacent strings of the opposite color. The functionchainlinks()returns (inadji,adjjarrays) these strings surrounding the group at(i, j). Ifstackp <= depth, these are sorted by size (largest first). The size and number of liberties of each string are returned inadjsizeandadjlib.
break_chain(int si, int sj, int *i, int *j, int *k, int *l):
The functionbreak_chain(si, sj, *i, *j, *k, *l)returns 1 if part of some surrounding string is in atari, and if capturing this string results in a live string at(si, sj). Returns 2 if the capturing string can be taken (as in a snapback), or the the saving move depends on ignoring a ko threat; Returns 3 if the saving move requires making a ko threat and winning the ko. The pointers(i,j), if not NULL, are left pointing to the appropriate defensive move. The pointers(k,l), if not NULL, are left pointing to the boundary string which is in atari.
break_chain2(int si, int sj, int *i, int *j):
The functionbreak_chain2(si, sj, *i, *j)returns 1 if there is a string in the surrounding chain having exactly two liberties whose attack leads to the rescue of(si, sj). Then *i, *j points to the location of the attacking move. Returns 2 if the attacking stone can be captured, 1 if it cannot.
snapback(snapback(int si, int sj, int i, int j, int color):
The functionsnapback(si, sj, i, j, color)considers a move by color at(i, j)and returns true if the move is a snapback. Algorithm: It removes dead pieces of the other color, then returns 1 if the stone at(si, sj)has <2 liberties. The purpose of this test is to avoid snapbacks. The locations(i, j)and(si,sj)may be either same or different. Also returns 1 if the move at(i, j)is illegal, with the trace message "ko violation" which is the only way I think this could happen. It is not a snapback if the capturing stone can be recaptured on its own, e.g.XXOOOOO X*XXXXO -------HereOcapturing at*is in atari, but this is not a snapback. Use with caution: you may want to condition the test on the string being captured not being a singleton. For exampleXXXOOOOOOOO XO*XXXXXXXO -----------is rejected as a snapback, yetOcaptures more than it gives up.
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 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().
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 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 # 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 sgf_decidestring run tbreak attack continue jt $arg0 end # restart, jump to a particular defense variation define dvar delete tbreak sgf_decidestring run tbreak attack continue finish next 3 jt $arg0 end
Here are some common utility functions from engine/utils.c.
int pushgo()
Pushes the position onto the stack.
int popgo()
Pops the movestack.
int trymove(int i, int j, int color, const char *message, int k, int l)
Returns true if(i,j)is a legal move for color. In that case, it pushes the move 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 at(k,l)if these are not(-1,-1). Use like this:if (trymove(i, j, color, [message], k, l)) { ... popgo(); }
int TRY_MOVE()
Wrapper around trymove which suppresses*messageand(k,l). Used inhelpers.c
tryko(int i, int j, int color, const char *message)
Pushes the position onto the stack, and makes a move at(i,j)ofcolor. 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.
dump_stack(void)
Handy for debugging the reading code under GDB. Prints the move stack.
vgprintf(FILE* outputfile, const char *fmt, va_list ap)
This function underpins all theTRACEandDEBUGstuff. Accepts%c,%dand%sas usual. But it also accepts%m, which takes TWO integers and writes a move NASTY BODGE:%oat start means outdent (ie cancel indent).
void TRACE(const char *fmt, ...)
Basic tracing function. Variants RTRACE, etc. are documented in the source.
int legal(int i, int j, int color)
Returns true if(i,j)is legal forcolor.
int count(int i, int j, int color, char mx[MAX_BOARD][MAX_BOARD], int maxlib, char mark)
Count liberties of color piece at location(i, j)and return value in global variablelib(which is also the return value of the function). Return size of connected component insize. Ifk<lib, then(libi[k],libj[k])points to one of the liberties of the string. FIXME: We should get rid of these global variables. This function is usually called with a stone ofcolorat(i,j). It may also be called with(i,j)EMPTY. If this is the case, the function (essentially) places a stone of (color) on the board and does the calculation.
void change_dragon_status(int x, int y, int status)
Change the status of the dragon at (x,y).
void change_defense(int ai, int aj, int ti, int tj)
Moves the point of defense of(ai, aj)to(ti, tj). FIXME: At present can only set defend_code equal to 1 or 0.
void change_attack(int ai, int aj, int ti, int tj)
Moves the point of attack of the worm at(ai, aj)to(ti, tj). FIXME: At present can only set attack_code equal to 1 or 0.
int connection_value(int ai, int aj, int bi, int bj, int ti, int tj)
This important function assigns a value to the connection of two dragons.
The move at (ti,tj) is the connecting move. It is checked whether
this move will result in a dragon having two eyes.
int cut_possible(int i, int j, int color)
Returns true if color can cut at(i,j). This information is collected byfind_cuts(), using theBpatterns in the connections database.
int does_attack(int ti, int tj, int ai, int aj)
Returns true if the move at(ti, tj)attacks(ai, aj). This means that it captures the string, and that(ai, aj)is not already dead. As currently written, this function assumesstackp==0, though this could be easily changed.
int does_defend(int ti, int tj, int ai, int aj)
Returns true if the move at(ti, tj)defends(ai, aj). This means that it defends the string, and that(ai, aj)can be captured if no defense is made. As currently written, this function assumesstackp==0, though this could be easily changed.
int find_lunch(int m, int n, int *wi, int *wj, int *ai, int *aj)
Looks for a worm adjoining the string at(m,n)which can be easily captured. Whether or not it can be defended doesn't matter (see Dragon). Returns the location of the string in(*wi, *wj), and the location of the attacking move in(*ai, *aj).
int is_ko(int i, int j, int color)
Return true if the move(i,j)bycoloris a ko capture (whether capture is a legal ko capture on this move or not).
int singleton(int i, int j)
Return true if (i,j) is an isolated stone.
int confirm_safety(int i, int j, int color, int value)
This important function will detect some blunders. Returns 1 if a move bycolorat(i,j)does not diminish the safety of any worm, nor tend to rescue inadvertantly an opponent stone.
Endgame moves are generated just like any other move by GNU Go. In fact, the concept of endgame does not exist explicitly, but we can consider the endgame to be reached when the move values generally have decreased to about 20 and the endgame patterns come into play. This is typically fairly late, when most of the remaining plays are worth a few points in gote.
It should be noted that GNU Go currently makes no attempt whatsoever to play a theoretically perfect endgame. Instead the goal is just to play a decent, although maybe somewhat passive, endgame. What this means is primarily to play the small endgame moves in roughly the right order.
The endgame is implemented by a number of patterns in
patterns.db, classified as EE, edge endgame, or CE, center
endgame. In order to play the endgame moves in the right
order, the patterns should be valued according to a
pessimistic estimation of the size of the move. If the move
is gote or reverse sente, it should have a value given by
the table below.
Value Size
1 Fill dame, i.e. 0 points gote.
2 Fill or take an unimportant ko, 1/2 point gote.
3 1 point gote.
4 1 1/2 point gote, typically two stage unimportant ko
or 1 point gote with a followup of one more point
gote.
5 2 points gote or 1 point reverse sente.
7 3 points gote.
10 4 points gote or 2 points reverse sente.
15 About 6 points gote or 3 points reverse sente.
20 At least 8 points gote or at least 4 points reverse
sente.
Small sente moves should be valued at least 5, with the exact value depending on the size of the followup move. Most sente moves are not considered as endgame moves by GNU Go, neither are larger gote or reverse sente moves. A minimal double sente move should at least have value 10, but in most cases they should be played before the endgame.
Pattern CE6 X? push in *O :8,1,0,0,0,0,OX,0,NULL
A move generated from this pattern may be worth one or more points, e.g. in the position
XXXO ..*O XXXO
where it is required that all stones are alive and it is assumed that the empty points would be territory for X with a stone at *. It could, however, also be applied in a position like
XXXO .X*O XXXO
where it only fills a dame. Hence the value of the pattern is no more than 1. To get a larger value for a move in the position above, we need to have a more specific pattern that is guaranteed to be worth at least one point gote, e.g.
Pattern CE6b X? push in *O 1 points gote :8,3,0,OX,0,0,0,0,0,NULL X? aO ;marginal_eye(a)
By taking help of the eye space evaluation we can know for certain that this move is worth at least one point.
the --mode test option of gnugo allows for testing of moves.
generated moves are tested against annotations and actual moves
/* ANNOTATION PROPERTIES: * Circle: Good Move * Triangle: OK move * Square: Bad move (Mark too... cgoban writes MA instead of SQ) * Move that was made: considered good unless annotated (BM, TE) */
The regression directory contains an example test-tree.sgf which shows
how the testing works. Look at it with your favorite editor, then run it
through the test to see how it performs.
A sample test run:
gnugo --mode test --testmode annotation --infile test-tree.sgf --quiet
attack(): Reading Basics
attack2(): Reading Basics
attack3(): Reading Basics
attack4(): Reading Basics
break_chain(): Reading Basics
break_chain2(): Reading Basics
chainlinks(): Reading Basics
defend1(): Reading Basics
defend2(int m, int n, int *i, int *j): Reading Basics
defend3(int m, int n, int *i, int *j): Reading Basics
dump_stack(void): Utility Functions
find_cap2(): Reading Basics
find_defense() :: Reading Basics
hashnode_new_result(): Hash Organization
hashtable_enter_position(): Hash Organization
hashtable_search(): Hash Organization
int confirm_safety(int i, int j, int color, int value): Utility Functions
int connection_value(int ai, int aj, int bi, int bj, int ti, int tj): Utility Functions
int count(int i, int j, int color, char mx[MAX_BOARD][MAX_BOARD], int maxlib, char mark): Utility Functions
int cut_possible(int i, int j, int color): Utility Functions
int does_attack(int ti, int tj, int ai, int aj): Utility Functions
int does_defend(int ti, int tj, int ai, int aj): Utility Functions
int find_lunch(int m, int n, int *wi, int *wj, int *ai, int *aj): Utility Functions
int is_ko(int i, int j, int color): Utility Functions
int legal(int i, int j, int color): Utility Functions
int popgo(): Utility Functions
int singleton(int i, int j): Utility Functions
int TRY_MOVE(): Utility Functions
int trymove(int i, int j, int color, const char *message, int k, int l): Utility Functions
pushgo(): Utility Functions
safe_move(): Reading Basics
small_semeai(): Reading Basics
snapback(): Reading Basics
tryko(int i, int j, int color, const char *message): Utility Functions
vgprintf(FILE* outputfile, const char *fmt, va_list ap): Utility Functions
void change_attack(int ai, int aj, int ti, int tj): Utility Functions
void change_defense(int ai, int aj, int ti, int tj): Utility Functions
void change_dragon_status(int x, int y, int status): Utility Functions
void TRACE(const char *fmt, ...): Utility Functions