This chapter is an overview of the GNU Go internals. Further documentation of how any one module or routine works may be found in later chapters or comments in the source files.

GNU Go starts by trying to understand the current board position as good as possible. Using the information found in this first phase, and using additional move generators, a list of candidate moves is generated. Finally, each of the candidate moves is valued according to its territorial value (including captures or life-and-death effects), and possible strategical effects (such as strengthening a weak group).

Note that while GNU Go does, of course, do a lot of reading to analyze possible captures, life and death of groups etc., it does not (yet) have a fullboard lookahead.

Gathering Information
=====================

This is by far the most important phase in the move generation. Misunderstanding life-and-death situations can cause gross mistakes. Wrong territory estimates will lead to inaccurate move valuations. Bad judgement of weaknesses of groups make strategic mistakes likely.

This information gathering is done by the function examine_position(). It first calls make_worms().

Its first steps are very simple: it identifies sets of directly connected stones, called worms, and notes their sizes and their number of liberties.

Soon after comes the most important step of the worm analysis: the tactical reading code (see Tactical Reading) is called for every worm. It tries to read out which worms can be captured directly, giving up as soon as a worm can reach 5 liberties. If a worm can be captured, the engine of course looks for moves defending against this capture. Also, a lot of effort is made to find virtually all moves that achieve the capture or defense of a worm.

After knowing which worms are tactically stable, we can make a first picture of the balance of power across the board: the Influence code is called for the first time.

This is to aid the next step, the analysis of dragons. By a dragon we mean a group of stones that cannot be disconnected.

Naturally the first step in the responsible function make_dragons() is to identify these dragons, i.e. determine which worms cannot be disconnected from each other. This is partly done by patterns, but in most cases the specialized readconnect code is called. This module does a minimax search to determine whether two given worms can be connected with, resp. disconnected from each other.

Then we compute various measures to determine how strong or weak any given dragon is:

  * A crude estimate of the number of eyes is made.

  * The results of the influence computations is used to see which dragons are adjacent to own territory or a moyo.

  * A guess is made for the potential to escape if the dragon got under attack.

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

For a more detailed reference of the worm and dragon analysis (and explanations of the data structures used to store the information), see Worms and Dragons.

The influence code is then called second time to make a detailed analysis of likely territory. Of course, the life-and-death status of dragons are now taken into account.

The territorial results of the influence module get corrected by the break-in module. This specifically tries to analyze where an opponent could break into an alleged territory, with sequences that would be too difficult to see for the influence code.

Move Generators
===============

Once we have found out all about the position it is time to generate the best move. Moves are proposed by a number of different modules called move generators. The move generators themselves do not set the values of the moves, but enumerate justifications for them, called move reasons. The valuation of the moves comes last, after all moves and their reasons have been generated.

For a list and explanation of move reasons used in GNU Go, and how they are evaluated, see Move Generation.

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

  * worm_reasons()

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

  * owl_reasons()

          The status of every dragon, as it has been determined by the owl code (see The Owl Code) in the previous phase, is reviewed. If the status is critical, the killing or defending move gets a corresponding move reason.

  * semeai_move_reasons()

          Similarly as owl_reasons, this function proposes moves relevant for semeais.

  * break_in_move_reasons()

          This suggests moves that have been found to break into opponent's territory by the break-in module.

The following move generators do additional work:

  * fuseki()

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

  * shapes()

          This is probably the most important move generator. It finds patterns from patterns/patterns.db, patterns/patterns2.db, patterns/fuseki.db, and the joseki files in the current position.  Each pattern is matched in each of the 8 possible orientations obtainable by rotation and reflection. If the pattern matches, a so called "constraint" may be tested which makes use of reading to determine if the pattern should be used in the current situation.  Such constraints can make demands on number of liberties of strings, life and death status, and reading out ladders, etc. The patterns may call helper functions, which may be hand coded (in patterns/helpers.c) or autogenerated.

          The patterns can be of a number of different classes with different goals.  There are e.g. patterns which try to attack or defend groups, patterns which try to connect or cut groups, and patterns which simply try to make good shape. (In addition to the large pattern database called by shapes(), pattern matching is used by other modules for different tasks throughout the program. See Patterns, for a complete documentation of patterns.)

  * combinations()

          See if there are any combination threats or atari sequences and either propose them or defend against them.

  * revise_thrashing_dragon()

          This module does not directly propose move: If we are clearly ahead, and the last move played by the opponent is part of a dead dragon, we want to attack that dragon again to be on the safe side. This is done be setting the status of this thrashing dragon to unkown and repeating the shape move generation and move valution.

  * endgame_shapes()

          If no move is found with a value greater than 6.0, this module matches a set of extra patterns which are designed for the endgame.  The endgame patterns can be found in patterns/endgame.db.

  * revise_semeai()

          If no move is found, this module changes the status of opponent groups involved in a semeai from DEAD to UNKNOWN.  After this, genmove runs shapes and endgame_shapes again to see if a new move turns up.

  * fill_liberty()

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

Move Valuation
==============

After the move generation modules have run, each proposed candidate move goes through a detailed valuation by the function review_move_reasons. This invokes some analysis to try to turn up other move reasons that may have been missed.

The most important value of a move is its territorial effect. see Influence and Territory explains in detail how this is determined.

This value is modified for all move reasons that cannot be expressed directly in terms of territory, such as combination attacks (where it is not clear which of several strings will get captured), strategical effects, connection moves, etc.  A large set heuristics is necessary here, e.g. to avoid duplication of such values. This is explained in more detail in Valuation.

Detailed Sequence of Events
===========================

First comes the sequence of events when examine_position() is run from genmove(). This is for reference only.

     purge_persistent_caches()
     make_worms():
       compute_effective_sizes()
       compute_unconditional_status()
       find_worm_attacks_and_defenses():
         for each attackable worm:
           set worm.attack
           change_attack() to add the attack point
         find_attack_patterns() to find a few more attacks
         for each defensible worm:
           set worm.attack
           change_defense() to add the defense point
         find_defense_patterns() to find a few more defense moves
         find additional attacks and defenses by testing all
           immediate liberties
       find higher order liberties (for each worm)
       find cutting stones (for each worm)
       improve attacks and defenses: if capturing a string defends
         another friendly string, or kills an unfriendly one, we
         add points of defense or attack. Make repairs if adjacent
         strings can both be attacked but not defended.
       find worm lunches
       find worm threats
       identify inessential worms (such as nakade stones)
     compute_worm_influence():
       find_influence_patterns()
       value_influence()
       segment_influence()
     make_dragons():
       find_cuts()
       find_connections()
       make_domains() (determine eyeshapes)
       find_lunches() (adjacent strings that can be captured)
       find_half_and_false_eyes()
       eye_computations(): Compute the value of each eye space.
         Store its attack and defense point.
       analyze_false_eye_territory()
       for each dragon compute_dragon_genus()
       for each dragon compute_escape() and set escape route data
       resegment_initial_influence()
       compute_refined_dragon_weaknesses() (called again after owl)
       for each dragon compute_crude_status()
       find_neighbor_dragons()
       for each dragon compute surround status
       for each weak dragon run owl_attack() and owl_defend()
         to determine points of attack and defense
       for each dragon compute dragon.status
       for each thrashing dragon compute owl threats
       for each dragon compute dragon.safety
       revise_inessentiality()
       semeai():
         for every semeai, run owl_analyze_semeai()
         find_moves_to_make_seki()
       identify_thrashing_dragons()
       compute_dragon_influence():
         compute_influence()
         break_territories() (see Break Ins)
       compute_refined_dragon_weaknesses()

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

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

Roadmap
=======

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

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

  * gmp.c

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

  * main.c

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

Files in engine/
----------------

In engine/ there are the following files:

  * aftermath.c

          Contains algorithms which may be called at the end of the game to generate moves that will generate moves to settle the position, if necessary playing out a position to determine exactly the status of every group on the board, which GNU Go can get wrong, particularly if there is a seki. This module is the basis for the most accurate scoring algorithm available in GNU Go.

  * board.c

          This file contains code for the maintenance of the board.  For example it contains the important function trymove() which tries a move on the board, and popgo() which removes it by popping the move stack. At the same time vital information such as the number of liberties for each string and their location is updated incrementally.

  * breakin.c

          Code to detect moves which can break into supposed territory and moves to prevent this.

  * cache.c and cache.h

          As a means of speeding up reading, computed results are cached so that they can be quickly reused if the same position is encountered through e.g. another move ordering. This is implemented using a hash table.

  * clock.c and clock.h

          Clock code, including code allowing GNU Go to automatically adjust its level in order to avoid losing on time in tournaments.

  * combination.c

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

  * dragon.c

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

  * endgame.c

          Code to find certain types of endgame moves.

  * filllib.c

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

  * fuseki.c

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

  * genmove.c

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

  * globals.c

          This contains the principal global variables used by GNU Go.

  * gnugo.h

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

  * hash.c and hash.h

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

  * influence.c and influence.h.

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

  * liberty.h

          Header file for the engine. The name ``liberty'' connotes freedom (see Copying).

  * matchpat.c

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

  * move_reasons.c and move_reasons.h

          Code for keeping track of move reasons.

  * movelist.c

          Supporting code for lists of moves.

  * optics.c

          This file contains the code to recognize eye shapes, documented in see Eyes.

  * oracle.c

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

  * owl.c

          This file does life and death reading. Move generation is pattern based and the code in optics.c is used to evaluate the eyespaces for vital moves and independent life. A dragon can also live by successfully escaping. Semeai reading along the same principles is also implemented in this file.

  * persistent.c

          Persistent cache which allows reuse of read results at a later move or with additional stones outside an active area, which are those intersections thought to affect the read result.

  * printutils.c

          Print utilities.

  * readconnect.c and readconnect.h

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

  * reading.c

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

  * semeai.c

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

  * sgfdecide.c

          Code to generate sgf traces for various types of reading.

  * shapes.c

          This file contains shapes(), the module called by genmove() which tries to find moves which match a pattern (see Patterns).

  * showbord.c

          This file contains showboard(), which draws an ASCII representation of the board, depicting dragons (stones with same letter) and status (color). This was the primary interface in GNU Go 1.2, but is now a debugging aid.

  * surround.c

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

  * utils.c

          An assortment of utilities, described in greater detail below.

  * value_moves.c

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

  * worm.c

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

Files in patterns/
------------------

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

  * move generation patterns in patterns.db and patterns2.db

  * move generation patterns in files hoshi.db etc. which are automatically build from the files hoshi.sgf etc. These comprise our small Joseki library.

  * patterns in owl_attackpats.db, owl_defendpats.db and owl_vital_apats.db. These generate moves for the owl code (see The Owl Code).

  * Connection patterns in conn.db (see Connections Database)

  * Influence patterns in influence.db and barriers.db (see Influence)

  * eye patterns in eyes.db (see Eyes).

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

  * conn.db

          Database of connection patterns.

  * conn.c

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

  * eyes.c

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

  * eyes.h

          Header file for eyes.c.

  * eyes.db

          Database of eyeshape patterns. See Eyes, for details.

  * helpers.c

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

  * hoshi.sgf

          Smart Game Format file containing 4-4 point openings

  * hoshi.db

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

  * joseki.c

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

  * komoku.sgf

          Smart Game Format file containing 3-4 point openings

  * komoku.db

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

  * mkeyes.c

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

  * mkpat.c

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

  * mokuhazushi.sgf

          Smart Game Format file containing 5-3 point openings

  * mokuhazushi.db

          Pattern database compiled from mokuhadzushi.sgf

  * sansan.sgf

          Smart Game Format file containing 3-3 point openings

  * sansan.db

          Pattern database compiled from sansan.sgf

  * takamoku.sgf

          Smart Game Format file containing 5-4 point openings

  * takamoku.db

          Pattern database compiled from takamoku.sgf.

  * patterns.c

          Pattern data, compiled from patterns.db by mkpat.

  * patterns.h

          Header file relating to the pattern databases.

  * patterns.db and patterns2.db

          These contain pattern databases in human readable form.

Coding styles and conventions
=============================

Coding Conventions
------------------

Please follow the coding conventions at: http://www.gnu.org/prep/standards_toc.html

Please preface every function with a brief description of its usage.

Please help to keep this Texinfo documentation up-to-date.

Tracing
-------

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

  * %m

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

  * indentation

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

  * "outdent"

          format string suppresses the indentation.

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

TRACE(fmt, ...):

     Print the message if the 'verbose' variable > 0. (verbose is set by -t on the command line)

DEBUG(flags, fmt, ...):

     While TRACE is intended to afford an overview of what GNU Go is considering, DEBUG allows occasional in depth study of a module, usually needed when something goes wrong. flags is one of the DEBUG_* symbols in engine/gnugo.h.  The DEBUG macro tests to see if that bit is set in the debug variable, and prints the message if it is.  The debug variable is set using the -d command-line option.

The variable verbose controls the tracing. It can equal 0 (no trace), 1, 2, 3 or 4 for increasing levels of tracing. You can set the trace level at the command line by -t for verbose=1, -t -t for verbose=2, etc. But in practice if you want more verbose tracing than level 1 it is better to use GDB to reach the point where you want the tracing; you will often find that the variable verbose has been temporarily set to zero and you can use the GDB command set var verbose=1 to turn the tracing back on.

Assertions
----------

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

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

FIXME
-----

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

Navigating the Source
=====================

If you are using Emacs, you may find it fast and convenient to use Emacs' built-in facility for navigating the source. Switch to the root directory gnugo-3.6/ and execute the command:

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

This will build a file called gnugo-3.6/TAGS. Now to find any GNU Go function, type M-. and enter the command which you wish to find, or just RET if the cursor is at the name of the function sought.

The first time you do this you will be prompted for the location of the TAGS table.  Enter the path to gnugo-3.6/TAGS, and henceforth you will be able to find any function with a minimum of keystrokes.