Updated README: Equal sign not required with `--mode` flag.

[sgk-go] / doc / reading.texi

@cindex Reading code
@cindex Reading process
@cindex Trying hypothetical moves
@cindex Usage of the stack in reading
@cindex reading DEPTH
@cindex Depth of reading
@cindex reading.c
@cindex reading.h

The process of visualizing potential moves done by you and your
opponent to learn the result of different moves is called
"reading". GNU Go does three distinct types of reading: @dfn{tactical
reading} which typically is concerned with the life and death of
individual strings, @dfn{Owl reading} which is concerned
with the life and death of dragons, and @dfn{connection reading}.
In this Chapter, we document
the tactical reading code, which is in @file{engine/reading.c}.

@menu
* Reading Basics::               Reading Basics
* Hashing::                      Hashing of positions
* Persistent Cache::             Persistent Reading Cache
* Ko::                           Ko handling
* A Ko Example::                 A Ko Example
* Another Ko Example::           Another Ko Example
* Alternate Komaster Schemes::   Alternate Komaster Schemes
* Superstrings::                 Superstrings
* Debugging::                    Debugging the reading code
* Connection Reading::           Connection Reading
@end menu

@node Reading Basics
@section Reading Basics

What we call @emph{Tactical Reading} is the analysis whether there is
a direct capture of a single string, or whether there is a move to prevent
such a direct capture.

If the reading module finds out that the string can get captured, this
answer should (usually) be trusted. However, if it says it can be defended,
this does not say as much. It is often the case that such a string has
no chance to make a life, but that it cannot be captured within the
horizon (and the cutoff heuristics) of the tactical reading.

The tactical reading is done by the functions in @file{engine/reading.c}.
It is a minimax search that declares win for the attacker once he can
physically take the string off board, whereas the defense is considered
successful when the string has sufficiently many liberties. A string with
five liberties is always considered alive. At higher depth within the
search tree even fewer liberties cause GNU Go to give up the attack,
@xref{depthparams}.

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

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

@subsection Organization of the reading code

The function @code{do_attack} and @code{do_find_defense} are wrappers
themselves and call @code{attack1}, @code{attack2}, @code{attack3} or
@code{attack4} resp.  @code{defend1}, @code{defend1}, @code{defend1}
or @code{defend1} depending on the number of liberties.

These are fine-tuned to generate and try out the moves in an efficient
order. They generate a few moves themselves (mostly direct liberties
of the string), and then call helper functions called @code{..._moves} 
which suggest less obvious moves. Which of these functions get called
depends on the number of liberties and of the current search depth.

@subsection Return Codes
@anchor{Return Codes}
@cindex return codes
@cindex reading return codes

The return codes of the reading (and owl) functions and owl can
be @code{0}, @code{KO_B}, @code{KO_A} or @code{WIN}. Each reading
function determines whether a particular player (assumed to have the
move) can solve a specific problem, typically attacking or defending
a string.

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

@anchor{Experimental Owl Extension}
If GNU Go is compiled with the configure option
@option{--enable-experimental-owl-ext} then the owl functions also have
possible return codes of @code{GAIN} and @code{LOSS}. A code of @code{GAIN}
means that the attack (or defense) does not succeed, but that in the process
of trying to attack or defend, an opponent's worm is captured. A code
of @code{LOSS} means that the attack or defense succeeds, but that another
friendly worm dies during the attack or defense.

@subsection Reading cutoff and depth parameters
@anchor{depthparams}

Depth of reading is controlled by the parameters @code{depth}
and @code{branch_depth}. The @code{depth} has a default value
@code{DEPTH} (in @file{liberty.h}), which is set to 16 in the
distribution, but it may also be set at the command line using
the @option{-D} or @option{--depth} option.  If @code{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 @code{stackp > depth}, GNU Go assumes that as
soon as the string can get 3 liberties it is alive. This
assumption is sufficient for reading ladders.

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

%@findex small_semeai
%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 @code{DEAD}. To resolve such situations, a function
%@code{small_semeai()} (in @file{engine/semeai.c}) looks for such
%pairs of strings and corrects their classification.

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

@example
@group

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

@end group
@end example

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

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

The parameter @code{ko_depth} is a similar cutoff. If
@code{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
@option{-K} option.

@cindex reading.c

@itemize @bullet
@item @code{int attack(int str, int *move)}
@findex attack
@quotation
Determines if the string at @code{str} can
be attacked, and if so, @code{*move} returns the attacking move,
unless @code{*movei} is a null pointer. (Use null pointers if
you are interested in the result of the attack but not the
attacking move itself.) Returns @code{WIN}, if the attack succeeds,
0 if it fails, and @code{KO_A} or @code{KO_B} if the result depends on ko
@ref{Return Codes}.
@end quotation
@findex find_defense
@item @code{find_defense(int str, int *move)}
@quotation 
Attempts to find a move that will save the string at @code{str}. It
returns true if such a move is found, with @code{*move} the location
of the saving move (unless @code{*move} is a null pointer). It is not
checked that tenuki defends, so this may give an erroneous answer if
@code{!attack(str)}.  Returns @code{KO_A} or @code{KO_B} if the
result depends on ko @xref{Return Codes}. 
@end quotation
@findex safe_move
@item @code{safe_move(int str, int color)} :
@quotation
The function @code{safe_move(str, color)} checks whether a move at
@code{str} is illegal or can immediately be captured. If @code{stackp==0}
the 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.
@end quotation
@end itemize

@node Hashing
@section Hashing of Positions

@cindex Hashing of positions
@cindex Reading optimisation
@cindex Speedup of reading process
@cindex Zobrist hashing algorithm
@cindex Transposition table

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

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

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

The hash table is created once and for all at the beginning of
the game by the function @code{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
@code{hashtable_clear()} from @code{genmove()}.

@menu
* Hash Calculation::            Calculation of the hash value
* Hash Organization::           Organization of the hash table
* Hash Structures::             Structures in @file{hash.h}
@end menu

@node Hash Calculation
@subsection Calculation of the hash value

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

@cindex go position
@cindex position

@enumerate
@item First we define a @dfn{go position}.  This positions consists of
@itemize @bullet
@item the actual board, i.e. the locations and colors of the stones
@item A @dfn{ko point}, if a ko is going on.  The ko point is defined as
the empty point where the last single stone was situated before
it was captured.
@end itemize

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
@code{attack3}, and it is implicit in the calling function which
player is to move.

@item For each location on the board we generate random numbers:
@itemize @bullet
@item A number which is used if there is a white stone on this location
@item A number which is used if there is a black stone on this location
@item A number which is used if there is a ko on this location
@end itemize

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

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

@node Hash Organization
@subsection Organization of the hash table

The hash table consists of 3 parts:

@cindex Hash node
@cindex Read result

@itemize @bullet
@item An area which contains so called @dfn{Hash Nodes}. Each hash node
contains:
@itemize @minus
@item A go position as defined above.
@item A computed hash value for the position
@item A pointer to Read Results (see below)
@item A pointer to another hash node.
@end itemize

@item An area with so called Read Results.  These are used to store
which function was called in the go position, which string was
under attack or to be defended, and the result of the reading.

Each Read Result contains: 
@itemize @minus
@item the function ID (an int between 0 and 255), the position of the
string under attack and a depth value, which is used to
determine how deep the search was when it was made, packed into
one 32 bit integer. 
@item The result of the search (a numeric value) and a position to
play to get the result packed into one 32 bit integer. 
@item A pointer to another Read Result.
@end itemize

@item An array of pointers to hash nodes.  This is the hash table
proper.

@end itemize

When the hash table is created, these 3 areas are allocated using
@code{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.

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

@findex hashtable_enter_position
@code{hashtable_enter_position()}.  

@findex 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
@code{hashnode_search()}.  If a result is found, it can be used, and
if not, a new result can be entered after a search using 
@findex hashnode_new_result
@code{hashnode_new_result()}.

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

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

@node Hash Structures
@subsection Hash Structures

The basic hash structures are declared in @file{engine/hash.h} and
@file{engine/cache.c}

@example
typedef struct hashposition_t @{
  Compacttype  board[COMPACT_BOARD_SIZE];
  int          ko_pos;
@} Hashposition;
@end example

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

@example
typedef struct @{
  Hashvalue     hashval;
  Hashposition  hashpos;
@} Hash_data;
@end example

Represents the return value of a function (@code{hashval}) and
the board state (@code{hashpos}).

@example
typedef struct read_result_t @{
  unsigned int data1;	
  unsigned int data2;

  struct read_result_t *next;
@} Read_result;
@end example

The data1 field packs into 32 bits the following fields:

@example

komaster:  2 bits (EMPTY, BLACK, WHITE, or GRAY)
kom_pos : 10 bits (allows MAX_BOARD up to 31)
routine :  4 bits (currently 10 different choices)
str1    : 10 bits
stackp  :  5 bits

@end example

The data2 field packs into 32 bits the following fields:

@example

status :   2 bits (0 free, 1 open, 2 closed)
result1:   4 bits
result2:   4 bits
move   :  10 bits
str2   :  10 bits

@end example

The @code{komaster} and @code{(kom_pos)} field are
documented in @xref{Ko}.

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

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

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

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

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

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

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

The hash table consists of three parts:

@itemize @bullet
@item The hash table proper: a number of hash buckets with collisions
being handled by a linked list.
@item The hash nodes.  These are allocated at creation time and are 
never removed or reallocated in the current implementation.
@item The results of the searches.  Since many different searches can
be done in the same position, there should be more of these than
hash nodes.
@end itemize

@node Persistent Cache
@section Persistent Reading Cache

@cindex persistent cache
@findex store_persistent_reading_cache
@findex purge_persistent_reading_cache
@findex purge_persistent_connection_cache
@findex purge_persistent_breakin_cache
@findex purge_persistent_owl_cache

@findex search_persistent_reading_cache
@findex store_persistent_reading_cache

Some calculations can be safely saved from move to move. If the
opponent's move is not close to our worm or dragon, we do not have to
reconsider the life or death of that group on the next move. So
the result is saved in a persistent cache. Persistent caches are used for
are used in the engine for several types of read results.

@itemize @bullet
@item Tactical reading
@item Owl reading
@item Connection reading
@item Breakin code
@end itemize

In this section we will discuss the persistent caching of tactical
reading but the same principles apply to the other persistent caches.

Persistent caching is an important performance feature. However it
can lead to mistakes and debugging problems---situations where GNU
Go generates the right move during debugging but plays a wrong move
during a game. If you suspect a persistent cache effect you may
try loading the sgf file with the @option{--replay} option and see if the
mistake is repeated (@pxref{Invoking GNU Go}).

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

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

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

@cindex reading shadow

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

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

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

@itemize @bullet
@item
The reading shadow and the string under attack are marked
with the character @samp{1}. We also include the successful
move, which is most often a part of the reading shadow, but
sometimes not, for example with the function @code{attack1()}.

@item
Next the reading shadow is expanded by marking strings and
empty vertices adjacent to the area marked @samp{1} with
the character @samp{2}.

@item
Next vertices adjacent to empty vertices marked @samp{2} are
labelled with the character @samp{3}.

@item
Next all vertices adjacent to previously marked vertices. These are
marked @samp{-1} instead of the more logical @samp{4} because it
is slightly faster to code this way.

@item
If the stack pointer is >0 we add the moves already played from the
moves stack with mark 4.
@end itemize

@node Ko
@section Ko Handling

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

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

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

The static reading functions, and the global functions @code{do_attack}
and @code{do_find_defense} consult parameters @code{komaster},
@code{kom_pos}, which are declared static in @file{board.c}. These mediate ko
captures to prevent the occurrence of infinite loops. During
reading, the komaster values are pushed and popped from a stack.

Normally @code{komaster} is @code{EMPTY} but it can also be
@samp{BLACK}, @samp{WHITE}, @code{GRAY_BLACK}, @code{GRAY_WHITE} or
@code{WEAK_KO}. The komaster is set to @code{color} when @code{color} makes a
conditional ko capture. In this case @code{kom_pos} is set to the location of
the captured ko stone.

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

@example

         .OX
         OX*X
        OmOX
         OO

@end example

Here if @samp{m} is the location of @code{kom_pos}, then the move at 
@samp{*} is allowed.

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

If the komaster's opponent takes a ko, then both players have taken one ko. In
this case @code{komaster} is set to @code{GRAY_BLACK} or @code{GRAY_WHITE} and
after this further ko captures are even further restricted.

If the ko at @code{kom_pos} is filled, then the komaster reverts to
@code{EMPTY}.

In detail, the komaster scheme is as follows. Color @samp{O} is to move.
This scheme is known as scheme 5 since in versions of GNU Go through
3.4, several different schemes were included.

@itemize @bullet
@item 1. Komaster is EMPTY.
@itemize @minus
@item 1a. Unconditional ko capture is allowed.
@quotation
Komaster remains EMPTY if previous move was not a ko capture.
Komaster is set to WEAK_KO if previous move was a ko capture
and kom_pos is set to the old value of board_ko_pos.
@end quotation
@item 1b) Conditional ko capture is allowed.
@quotation
Komaster is set to O and kom_pos to the location of the ko, where a stone was
just removed.
@end quotation
@end itemize
@item 2. Komaster is O:
@itemize @minus
@item 2a) Only nested ko captures are allowed. Kom_pos is moved to the
new removed stone.
@item 2b) If komaster fills the ko at kom_pos then komaster reverts to
EMPTY.
@end itemize
@item 3. Komaster is X:
@quotation
Play at kom_pos is not allowed. Any other ko capture
is allowed. If O takes another ko, komaster becomes GRAY_X.
@end quotation
@item  4. Komaster is GRAY_O or GRAY_X:
@quotation
Ko captures are not allowed. If the ko at kom_pos is
filled then the komaster reverts to EMPTY.
@end quotation
@item 5. Komaster is WEAK_KO:
@itemize @minus
@item 5a) After a non-ko move komaster reverts to EMPTY.
@item 5b) Unconditional ko capture is only allowed if it is nested ko capture.
@quotation
Komaster is changed to WEAK_X and kom_pos to the old value of
board_ko_pos.
@end quotation
@item 5c) Conditional ko capture is allowed according to the rules of 1b.
@end itemize
@end itemize

@node A Ko Example
@section A Ko Example

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

@example
  gnugo -l tripod9.sgf --decide-dragon C3 -o vars.sgf
@end example

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

@example
@group

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

@end group
@end example

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

@example
@group

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

@end group
@end example

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

@example
@group

 8 . . . . . . . .         komaster: BLACK
 7 . . O . . . . .         kom_pos: A2
 6 . . O . . . . .
 5 O O O . . . . .
 4 O X O O . . . .
 3 X . X O O O O .
 2 . X X X O . . .
 1 X O . . . . . .
   A B C D E F G H

@end group
@end example

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

@example
@group

 8 . . . . . . . .         komaster: GRAY
 7 . . O . . . . .         kom_pos: B4
 6 . . O . . . . .
 5 O O O . . . . .
 4 O . O O . . . .
 3 X O X O O O O .
 2 . X X X O . . .
 1 X O . . . . . .
   A B C D E F G H

@end group
@end example

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


@node Another Ko Example
@section Another Ko Example

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

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

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

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

@example
gnugo -l ko5.sgf --quiet --decide-string L1 -o vars.sgf
@end example

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

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

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

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


@node Alternate Komaster Schemes
@section Alternate Komaster Schemes

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

@subsection Essentially the 2.7.232 scheme.

@itemize @bullet
@item Komaster is EMPTY.
@itemize @minus
@item Unconditional ko capture is allowed. Komaster remains EMPTY.
@item Conditional ko capture is allowed. Komaster is set to O and
@code{kom_pos} to the location of the ko, where a stone was
just removed.
@end itemize
@item Komaster is O:
@itemize @minus
@item Conditional ko capture is not allowed.
@item Unconditional ko capture is allowed. Komaster parameters unchanged.
@end itemize
@item Komaster is X:
@itemize @minus
@item Conditional ko capture is not allowed.
@item Unconditional ko capture is allowed except for a move at 
@code{kom_pos}. Komaster parameters unchanged.
@end itemize
@end itemize

@subsection Revised 2.7.232 version

@itemize @bullet
@item Komaster is EMPTY.
@itemize @minus
@item Unconditional ko capture is allowed. Komaster remains EMPTY.
@item Conditional ko capture is allowed. Komaster is set to @samp{O} and
@code{kom_pos} to the location of the ko, where a stone was
just removed.
@end itemize
@item Komaster is @samp{O}:
@itemize @minus
@item Ko capture (both kinds) is allowed only if after playing the move,
@code{is_ko(kom_pos, X)} returns false. In that case, 
@code{kom_pos} is updated to the new ko position, i.e. the stone
captured by this move.
@end itemize
@item Komaster is @samp{X}:
@itemize @minus
@item Conditional ko capture is not allowed.
@item Unconditional ko capture is allowed except for a move at 
@code{kom_pos}. Komaster parameters unchanged.
@end itemize
@end itemize

@node Superstrings
@section Superstrings

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

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

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

@node Debugging
@section Debugging the reading code

@cindex How to debug the reading code
@cindex Debugging the reading code
@cindex Reading code debugging tools

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 @option{--decidestring} option. This may
be run with or without an output file.

Simply running 

@example

@command{gnugo -t -l [input file name] -L [movenumber] --decidestring [location]}

@end example

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

If we add @option{-o @var{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.

@cindex GDB

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 @file{reading.c} without optimization,
edit @file{engine/Makefile} to remove the string @code{-O2} from
the file, touch @file{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 @option{--hash 0}. You should get the same
result. (If you do not, please send us a bug report.) Don't
run @option{--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 @option{-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.

@example

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

@end example

@noindent
will then jump to the location in question. 

Actually the attack variations and defense variations are numbered
separately. (But @code{find_defense()} is only run if @code{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.

@example

(gdb) avar 17

@end example

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

@example

(gdb) dvar 17

@end example

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

@example

@cindex GNU Go's GDB commands 

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

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

# this command displays the stack

define dump
set dump_stack()
end

# display the name of the move in ascii

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

# display the all information about a dragon

define dragon
set ascii_report_dragon("$arg0")
end

define worm
set ascii_report_worm("$arg0")
end

# move to the next variation

define nv
tbreak trymove
continue
finish
next
end

# move forward to a particular variation

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

# restart, jump to a particular attack variation

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

# restart, jump to a particular defense variation

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

@end example

@node Connection Reading
@section Connection Reading

GNU Go does reading to determine if strings can be connected.  The algorithms
for this are in @file{readconnect.c}. As with the reading code, the connection
code is not pattern based.

The connection code is invoked by the engine through the functions:

@itemize
@item @code{int string_connect(int str1, int str2, int *move)}
@findex string_connect
@quotation
Returns @code{WIN} if @code{str1} and @code{str2} can be connected. 
@end quotation
@item @code{int disconnect(int str1, int str2, int *move)}
@findex disconnect
@quotation
Returns @code{WIN} if @code{str1} and @code{str2} can be disconnected. 
@end quotation
@end itemize

To see the connection code in action, you may try the
following example.

@example
gnugo --quiet -l connection3.sgf --decide-connection M3/N7 -o vars.sgf
@end example

(The file @file{connection3.sgf} is in @file{regression/games}.)
Examine the sgf file produced by this to see what kind of reading
is done by the functions @code{string_connect()} and
@code{string_disconnect()}, which are called by the function
@code{decide_connection}. 

One use of the connection code is used is through the autohelper macros
@code{oplay_connect}, @code{xplay_connect}, @code{oplay_disconnect} and
@code{xplay_disconnect} which are used in the connection databases.