[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

4. GNU Go engine overview

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

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.

4.1 Gathering Information  
4.2 Move Generators  Selecting Candidate Moves
4.3 Move Valuation  Selecting the best Move
4.4 Detailed Sequence of Events  Outline of genmove().
4.5 Roadmap  Description of the different files.
4.6 Coding styles and conventions  Coding conventions.
4.7 Navigating the Source  


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

4.1 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--we call them 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 section 11. 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 13. Influence Function 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:

For those dragons that are considered weak, a life and death analysis is made (see section 12.1 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 See section 7. 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.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

4.2 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 See section 6. Move generation.

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

The following move generators do additional work:


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

4.3 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 section 13.4 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 6.4 Valuation of suggested moves.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

4.4 Detailed Sequence of Events

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

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

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:

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


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

4.5 Roadmap

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

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


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

4.5.1 Files in `engine/'

In `engine/' there are the following files:


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

4.5.2 Files in `patterns/'

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

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


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

4.6 Coding styles and conventions


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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

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.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

4.6.4 FIXME

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


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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

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

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

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


[ << ] [ >> ]           [Top] [Contents] [Index] [ ? ]

This document was generated by Martin Godisch on February, 17 2004 using texi2html