File: READING

package info (click to toggle)
gnugo 2.4-2
  • links: PTS
  • area: main
  • in suites: potato
  • size: 1,816 kB
  • ctags: 1,828
  • sloc: ansic: 22,091; tcl: 401; sh: 376; makefile: 202
file content (323 lines) | stat: -rw-r--r-- 11,315 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
			       READING

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

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 
                  liberties

 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 
                  liberties

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


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
    contains:
     - 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
    proper.

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

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
hashnode_new_result().

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.

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 name] 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 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) 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:

'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

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