The process of visualizing potential moves done by you and your
opponent to find out what the result of different moves will be is
called "reading". In GNU Go, this is done by the functions in
src/reading.c. Each of these functions have a separate goal to
fill, and they call each other recursively to carry out the
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
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.
The backfill_depth is a similar variable with default 7. 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<depth. The backfill
depth may be set using the -B parameter.
Some of the functions in reading.c are:
attack() : Determines whether a string can be captured. Looks
for ladders and nets. Capable of reading in some
detail. If stackp exceeds the parameter depth it
tries fewer moves --- reading beyond this depth
it will find ladders but will miss many nets.
find_defense() : Looks for a defensive move to defend a string.
Called by genmove
safe_move() : Determines whether a move results in a string
which cannot be captured by any of the variations
considered by attack.
readlad1() : Read out a ladder attack on a group with one liberty
readlad2() : Read out a ladder attack on a group with two
savestone2() : Try to rescue a string with 2 liberties
basicnet3() : Try to capture a string with three liberties
find_cap2() : Try a capping attack (geta) on a group with two
savestone3() : Try to rescue a string with 3 liberties
chainlinks() : Find the CHAIN surrounding a string. This is the
set of adjacent strings of the opposite color.
break_chain() : Looks for a string in the chain surrounding a
given string which is in atari.
break_chain2() : Looks for a string in the chain surrounding a
given string which can be captured. Unlike
break_chain, it tries attacks on strings
which may have more than one liberty.
snapback() : see if a potential capture is actually a snapback.
HASHING OF POSITIONS
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
occurance that a previously checked position is rechecked, often
within the same search but from a different branch in the recursion
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 / 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 / defence 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
Calculation of the hash value
The hash algorithm is called Zorbrist hashing, and seems to be a
standard technique for go and chess programming. I have not read
Zorbrists initial article, so my implementation might work differently
in some areas. The algorithm as used by us works as follows:
1. First we define a GO POSITION. This positions consists of
- the actual board, i.e. the locations and colors of the stones
- A 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.
- The color to move (white / black)
2. For each location on the board we generate random numbers:
- A number which is used if there is a white stone on this location
- A number which is used if there is a black stone on this location
- A number which is used if there is a ko on this location
Additionally we also generate a random number to use if it is
whites turn to move and one to use if it is blacks turn to move.
These random numbers are generated once at initialization time and
then used throughout the life time of the hash table.
3. The hash key for a position is the XOR of all the random numbers
which is applicable for the position (white stones, black stones,
ko position and the color to move).
Organization of the hash table
This text documents the hash table as it looked when it was introduced
in version 2.3.70.
The hash table consists of 3 parts:
- An area which contains so called Hash Nodes. Each hash node
- A go position as defined above.
- A computed hash value for the position
- A pointer to Read Results (see below)
- A pointer to another hash node.
- 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:
- 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.
- The result of the search (a numeric value) and a position to
play to get the result packed into one 32 bit integer.
- A pointer to another Read Result.
- An array of pointers to hash nodes. This is the hash table
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 allocating 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 it was newly
When a function wants to use the hash table, it looks up the current
position using hashtable_search(). If it doesn't already exist there,
it can enter it 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
Hash nodes which hash to the same position in the hash table
(collisions) form a simple linked list. Read results which is created
for the same position, but by different functions and different
attacked / 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.
DEBUGGING THE READING CODE
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.
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 name] GNU Go will produce an output
file with all variations considered. The variations are numbered
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 src/Makefile to remove the -O2 from CFLAGS, touch
src/reading.c and make.
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) 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:
'dump' will print the move stack.
'nv' moves to the next variation
'ascii i j' converts (i,j) to ascii
############### .gdbinit file ###############
# this command displays the stack
# display the name of the move in ascii
# move to the next variation
# move forward to a particular variation
while (count_variations < $arg0)
# restart, jump to a particular attack variation
# restart, jump to a particular defense variation