File: OVERVIEW

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 (482 lines) | stat: -rw-r--r-- 18,837 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
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
                           GNU GO OVERVIEW

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

                           DEFINITIONS

In this document wherever we define a concept we use CAPITAL LETTERS
for the term being defined.

A WORM is a maximal set of vertices on the board which are connected
along the horizontal and vertical lines, and are of the same color,
which can be BLACK, WHITE or EMPTY. The term EMPTY applied to a worm
means that the worm consists of empty (unoccupied) vertices. It does
NOT mean that that the worm is the empty set. A STRING is a nonempty
worm. An empty worm is called a CAVITY.  If a subset of vertices is
contained in a worm, there is a unique worm containing it; this is its
WORM CLOSURE.

A DRAGON is a union of strings of the same color which will be treated
as a unit. The dragons are recomputed. If two strings are in the
dragon, it is the computer's working hypothesis that they will live or
die together and are effectively connected.


			   MOVE GENERATION

The engine of GNU Go takes a positions and a color to move and
generates the (supposedly) optimal move.  This is done by the function
genmove() in src/genmove.c.

The move generation is done in two passes:
 1) information gathering
 2) actual move generation based on the information gathered in pass 1.


Information gathering
---------------------

First we have to collect as much information as possible about the
current position.  Such information could be life and death of the
groups, moyo status, connection of groups and so on. Information
gathering are performed by the following functions, called in this
order: 

 - make_worms	Collect information about all connected sets of stones
                (strings) and cavities.  This information is stored in
                the worm[][] array.

 - make_dragons	Collect information about connected strings, which are
		called dragons.  Important information here is number
		of eyes, life status, and connectedness between
		string. 

 - make_moyo	Calculate the "territory", "moyo" and "area" for both
		sides.  "Territory", as used here, is a somewhat
		looser term than we are used to, but in the end it
		coincides with the actual points. "Moyo" is the area
		of influence which could become territory if the other
		side does nothing about it, and "area" is weaker but
		bigger than moyo.

make_worms and make_dragons are documented more in detail in
docs/DRAGON and some algorithms in make_moyo are documented in
docs/MOYO. 


Move generation
---------------

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 move
generators with a value attached to them.  The values are compared and
the best move is picked.  If two or more moves have the same value,
one of them is picked at random.  

The move generators in version 2.4 are:

 - fuseki	Generate a move in the early fuseki. This module
                is undocumented but will be replaced by something
                better in the future.

 - semeai	Find out if two dead groups of opposite colors are
		next to each other and, if so, try to kill the other
		group. This module is probably the one in the worst
		condition currently and badly in need of improvement.

 - shapes	Match a number of patterns on the current position.
		Each pattern is matched in 8 different combinations of
		rotation and mirroring. 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 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.  See the file docs/PATTERNS for a
		complete documentation of patterns.

 - attacker	Looks for strings of the opposite color with three
		liberties or less and tries to kill them.

 - defender	Looks for strings of my color with three liberties or
		less and tries to defend them. 

 - eye_finder	Finds groups of either color which can make two eyes
		in the next move and looks for the vital point in the
		eye shapes.

 - revise_semeai If no move is found yet, change status of opponent
		 groups involved in a semeai from DEAD to UNKNOWN.

		 After this, genmove runs 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.



                         ROADMAP

The GNU Go engine is contained in two directories, src/ 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/. Documentation is in docs/.

In this document we will describe the all individual files comprising
the engine code in src/ and patterns/. In interface/ we mention one
file:

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.

In src/ there are the following files:

attdef.c    : This file contains attacker(), defender() and 
              eye_finder(), three of the move generators called by 
              genmove(). The module attacker() proposes moves which 
              attack enemy strings, while defender() proposes moves 
              which defend friendly strings. The reading necessary to 
              decide whether a string can be captured or defended is
              contained in reading.c, and has already been called
              by make_worms(). If a string can be defended, there
              may be different possible defensive moves, and some 
              of the patterns found by shapes() may move the points 
              of defense. This is the only case where data compiled 
              by make_worms() and make_dragons() is changed by a later 
              routine. Because of this feature, shapes() is called 
              before defender().           

              Also in attdef.c is eye_finder(). This module looks
              for dragons having one and a half eyes. If such a
              dragon (of either color) is found, eye_finder()
              proposes making or destroying the half eye.

dragon.c    : This contains make_worms() and make_dragons(). These
              routines are executed before the move-generating
              modules shapes(), attacker(), defender(), semeai()
              and eye_finder. They find all the worms and dragons
              and collect important information about them, such
              as how many liberties each has, whether (in GNU Go's
              opinion) the string or dragon can be captured, etc. 
              This information remains unchanged until the next
              move, with one exception: some patterns can move
              the point of defense of a friendly worm which is under 
              attack.

filllib.c   : code to force filling of dame (backfilling if necessary)
              at the end of the game.

fuseki.c    : this module generates fuseki (large scale opening)
              moves at the beginning of the game. This file is
              undocumented but will be replaced by something better
              in the future.

genmove.c   : This file contains genmove(), is the routine responsible
              for generating the next move. Opening moves are
              generated directly in this file, but it calls on
              other modules for other moves. The modules called
              by genmove are shapes() (in shapes.c), attacker()
              and defender (in attdef.c), semeai() (in semeai.c)
              and eye_finder (in attdef.c). Each module proposes
              moves, each with a value, and genmove() selects the
              one with the highest value.

hash.c      : hashing code used by for reading. See READING for
              details.

hash.h      : header file for hash.c.

liberty.h   : Header file for the whole program. 

main.c      : Miscellaneous book-keeping (parsing args, signal
              handlers, etc.) sgf file interfaces (reading and writing)
              high level game playing (collecting moves from genmove(),
              keeping track of passes, etc.) Contains very little
              knowledge about go : only that each side plays
              alternately, and that two passes marks the end of the
              game.
              
matchpat.c  : This file contains matchpat(), which looks for
              patterns at a particular board location.

moyo.c      : This file contains code to estimate territory and
              influence. See docs/MOYO for details.

reading.c   : This file contains code to determine whether any given
              string can be attacked or defended. See docs/READING
              for details.

semeai.c    : This contains semeai(), the module which tries to
              win capturing races.

sethand.c   : Initially populate the board with handicap stones.

showbord.c  : This 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.
                  
shapes.c    : This file contains shapes(), the module called by
              genmove() which tries to find moves which match a
              pattern. The pattern matcher has some sophisticated
              features described in more detail in PATTERNS. 
              Briefly, the pattern may take into account both
              friendly and opposing strength in the area, a
              string's escape potential, whether or not the
              pattern makes or breaks a valuable connection,
              whether it involves a dragon classified as dead,
              and it can also call a helper function hand
              tailored to the program which typically does some 
              further reading to decide whether the pattern is
              appropriate.

optics.c    : This contains the code to recognize eye shapes,
              documented in docs/EYES.

worm.c      : This file contains code which is run at the beginning
              of each move cycle, before the code in dragon.c, to
              determine the attributes of every string.

utils.c     : An assortment of utilities, described in greater
              detail below.


The directory patterns/ contains files related to pattern matching.
Currently search for 3 types of patterns: move generation patterns
(in patterns.db and similar files such as hoshi.db, compiled from
hoshi.sgf---see docs/PATTERNS for details); eyeshape patterns (in
eyes.db---see docs/OPTICS) and connection patterns (in conn.db, 
discussed in docs/DRAGONS). 

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.

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 docs/EYES for
              details.

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

hoshi.sgf   : Smart Go 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 Go Format, and produces a pattern database.

komoku.sgf  : Smart Go 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 patterns.db+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 Go Format file containing 5-3 point openings

mokuhazushi.db  : pattern database compiled from mokuhadzushi.sgf

sansan.sgf       : Smart Go Format file containing 3-3 point openings

sansan.db        : pattern database compiled from sansan.sgf

takamoku.sgf     : Smart Go 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 : This contains the pattern database in human
              readable form. See PATTERNS for documentation.





Utility files and routines in src/utils.c
-----------------------------------------

Only a portion of these functions are documented here. 

 legal()        : Determines whether a move is legal.

 trymove()      : Pushes the board position on the stack,
                  increments stackp, places the stone on the board if 
                  the move is legal, removes captures and increments 
                  stackp.

 pushgo()       : Pushes the board position on the stack and
                  increments stackp.

 popgo()        : Pops the stack.

 gprintf() : printf-like fn (see below under TRACING)

 TRACE, VTRACE, DEBUG ()  - see below

 abortgo()  : Wrapper around abort() which dumps the stack. Usually
              this is invoked by means of the macro ASSERT (see
              ASSERTIONS) below.


utils.c :  board utility functions :
----

 approxlib() : counts liberties, but as an optimisation, can be given
               an upper limit, above which it can stop counting.

 count() : low level helper for approxlib(), but is used by other fns

 updateboard() : place a piece on the board, remove captures, and update
                 state information (for ko)



Data Structures
---------------

The most important global variable is p[][], which is the go board.
Each element contains EMPTY, WHITE or BLACK.

The state of the board can be saved and restored using pushgo()
and popgo().

p[][] should not be written to directly. Trial moves should
be made using trymove(), which pushes the board, places the
piece, checks the move is legal, and updates the board.
popgo() undoes the move.  When a move is actually made,
updateboard() places the piece and removes prisoners.

approxlib() / count() can be called without actually placing
a piece. They report what the number of liberties would be
if a given piece was placed.

Other important data structures are dragon[][] and worm[][].
These contain information about groups of stones, whether
they are alive or dead, where they can be attacked, whether
they are cutting groups (split enemy groups), etc.

size, lib, and libi[],libj[] are global variables written
to by count() / approxlib(). They contain the size of
the group, and the number and positions of the liberties.

*NOTE* : if the count is truncated because it reaches the
limit on the number of liberties, then size and lib may
be smaller than the true value.

Other variables tend to be private to individual modules : 
half_eyes[][] is between dragon.c and halfeyes.c, stackp
is part of the stack implementation, plast[][] is part of
the ko history stuff, etc.




Coding styles and conventions
-----------------------------   
              
         
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
two 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.

As a workaround, %o at the beginning of the format string suppresses
the indentation.


gprintf() is intended to be wrapped by one of the following:


  TRACE(fmt, ...)  : print the message if the 'verbose' variable > 0.
                     (verbose is set by -t on the command line)


  VTRACE(fmt, ...) : Verbose trace, only if verbose > 1
                     (not currently used)


  DEBUG(flags, fmt, ...) : while TRACE is intended to afford an overview
                      of what GNU Go is considering, DEBUG allows occassional
                      in depth study of a module, usually needed when something
                      goes wrong. 'flags' is one of the DEBUG_* symbols in
                      liberty.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.




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.