Commit | Line | Data |
---|---|---|
7eeb782e AT |
1 | |
2 | This chapter is an overview of the GNU Go internals. Further | |
3 | documentation of how any one module or routine works may be found in | |
4 | later chapters or comments in the source files. | |
5 | ||
6 | GNU Go starts by trying to understand the current board position as | |
7 | good as possible. Using the information found in this first phase, and | |
8 | using additional move generators, a list of candidate moves is generated. | |
9 | Finally, each of the candidate moves is valued according to its territorial | |
10 | value (including captures or life-and-death effects), and possible | |
11 | strategical effects (such as strengthening a weak group). | |
12 | ||
13 | Note that while GNU Go does, of course, do a lot of reading to analyze | |
14 | possible captures, life and death of groups etc., it does not (yet) have | |
15 | a fullboard lookahead. | |
16 | ||
17 | @menu | |
18 | * Examining the Position:: Gathering Information | |
19 | * Move Generators:: Selecting Candidate Moves | |
20 | * Move Valuation:: Selecting the best Move | |
21 | * Detailed Sequence of Events:: Outline of @code{genmove()}. | |
22 | * Roadmap:: Description of the different files. | |
23 | * Coding Styles:: Coding conventions. | |
24 | * Navigating the Source:: Navigating the Source. | |
25 | @end menu | |
26 | ||
27 | ||
28 | @node Examining the Position | |
29 | @section Gathering Information | |
30 | ||
31 | This is by far the most important phase in the move generation. | |
32 | Misunderstanding life-and-death situations can cause gross mistakes. | |
33 | Wrong territory estimates will lead to inaccurate move valuations. | |
34 | Bad judgement of weaknesses of groups make strategic mistakes likely. | |
35 | ||
36 | This information gathering is done by the function @code{examine_position()}. | |
37 | It first calls @code{make_worms()}. | |
38 | ||
39 | Its first steps are very simple: it identifies sets of directly connected | |
40 | stones, called @dfn{worms}, and notes their sizes and their number of | |
41 | liberties. | |
42 | ||
43 | Soon after comes the most important step of the worm analysis: | |
44 | the tactical reading code (@pxref{Tactical Reading}) is called for every | |
45 | worm. It tries to read | |
46 | out which worms can be captured directly, giving up as soon as a worm | |
47 | can reach 5 liberties. If a worm can be captured, the engine of course | |
48 | looks for moves defending against this capture. Also, a lot of effort | |
49 | is made to find virtually all moves that achieve the capture or defense | |
50 | of a worm. | |
51 | ||
52 | After knowing which worms are tactically stable, we can make a first | |
53 | picture of the balance of power across the board: the @ref{Influence} | |
54 | code is called for the first time. | |
55 | ||
56 | This is to aid the next step, the analysis of dragons. By a @dfn{dragon} | |
57 | we mean a group of stones that cannot be disconnected. | |
58 | ||
59 | Naturally the first step in the responsible function @code{make_dragons()} | |
60 | is to identify these dragons, i.e. determine which worms cannot be | |
61 | disconnected from each other. This is partly done by patterns, but | |
62 | in most cases the specialized readconnect code | |
63 | @comment FIXME: Put in cross-ref here once Connection is documented | |
64 | is called. This module does a minimax search to determine whether two | |
65 | given worms can be connected with, resp. disconnected from each other. | |
66 | ||
67 | Then we compute various measures to determine how strong or weak any given | |
68 | dragon is: | |
69 | @itemize @bullet | |
70 | @item A crude estimate of the number of eyes is made. | |
71 | @item The results of the influence computations is used to see which dragons | |
72 | are adjacent to own territory or a moyo. | |
73 | @item A guess is made for the potential to escape if the dragon got | |
74 | under attack. | |
75 | @end itemize | |
76 | ||
77 | For those dragons that are considered weak, a life and death analysis | |
78 | is made (@pxref{The Owl Code}). If two dragons next to each other are found | |
79 | that are both not alive, we try to resolve this situation with the semeai | |
80 | module. | |
81 | ||
82 | For a more detailed reference of the worm and dragon analysis (and | |
83 | explanations of the data structures used to store the information), | |
84 | see @xref{Worms and Dragons}. | |
85 | ||
86 | The influence code is then called second time to make a detailed analysis | |
87 | of likely territory. Of course, the life-and-death status of dragons are | |
88 | now taken into account. | |
89 | ||
90 | The territorial results of the influence module get corrected by the break-in | |
91 | module. This specifically tries to analyze where an opponent could break | |
92 | into an alleged territory, with sequences that would be too difficult to | |
93 | see for the influence code. | |
94 | ||
95 | ||
96 | @node Move Generators | |
97 | @section Move Generators | |
98 | @cindex move generation | |
99 | @cindex move generators | |
100 | @cindex move reasons | |
101 | ||
102 | Once we have found out all about the position it is time to generate | |
103 | the best move. Moves are proposed by a number of different modules | |
104 | called @dfn{move generators}. The move generators themselves | |
105 | do not set the values of the moves, but enumerate justifications for | |
106 | them, called @dfn{move reasons}. The valuation of the moves comes | |
107 | last, after all moves and their reasons have been generated. | |
108 | ||
109 | For a list and explanation of move reasons used in GNU Go, and how they | |
110 | are evaluated, see @xref{Move Generation}. | |
111 | ||
112 | There are a couple of move generators that only extract data found in | |
113 | the previous phase, examining the position: | |
114 | ||
115 | @itemize @bullet | |
116 | @item @code{worm_reasons()} | |
117 | @findex worm_reasons | |
118 | @quotation | |
119 | Moves that have been found to capture or defend a worm are proposed as | |
120 | candidates. | |
121 | @end quotation | |
122 | ||
123 | @item @code{owl_reasons()} | |
124 | @findex owl_reasons | |
125 | @quotation | |
126 | The status of every dragon, as it has been determined by the owl code | |
127 | (@pxref{The Owl Code}) in the previous phase, is reviewed. If the status | |
128 | is critical, the killing or defending move gets a corresponding move | |
129 | reason. | |
130 | @end quotation | |
131 | ||
132 | @item @code{semeai_move_reasons()} | |
133 | @findex semeai | |
134 | @quotation | |
135 | Similarly as @code{owl_reasons}, this function proposes moves relevant | |
136 | for semeais. | |
137 | @end quotation | |
138 | ||
139 | @item @code{break_in_move_reasons()} | |
140 | @quotation | |
141 | This suggests moves that have been found to break into opponent's territory | |
142 | by the break-in module. | |
143 | @end quotation | |
144 | @end itemize | |
145 | ||
146 | The following move generators do additional work: | |
147 | ||
148 | @itemize @bullet | |
149 | ||
150 | @item @code{fuseki()} | |
151 | @findex fuseki | |
152 | @quotation | |
153 | Generate a move in the early fuseki, either in an empty corner of from | |
154 | the fuseki database. | |
155 | @end quotation | |
156 | ||
157 | @item @code{shapes()} | |
158 | @findex shapes | |
159 | @quotation | |
160 | This is probably the most important move generator. | |
161 | It finds patterns from @file{patterns/patterns.db}, | |
162 | @file{patterns/patterns2.db}, @file{patterns/fuseki.db}, and the joseki | |
163 | files in the current position. Each pattern is matched in each | |
164 | of the 8 possible orientations obtainable by rotation and | |
165 | reflection. If the pattern matches, a so called "constraint" | |
166 | may be tested which makes use of reading to determine if the | |
167 | pattern should be used in the current situation. Such | |
168 | constraints can make demands on number of liberties of | |
169 | strings, life and death status, and reading out ladders, | |
170 | etc. The patterns may call helper functions, which may | |
171 | be hand coded (in @file{patterns/helpers.c}) or | |
172 | autogenerated. | |
173 | ||
174 | The patterns can be of a number of different classes | |
175 | with different goals. There are e.g. patterns which | |
176 | try to attack or defend groups, patterns which try to | |
177 | connect or cut groups, and patterns which simply try | |
178 | to make good shape. (In addition to the large pattern | |
179 | database called by @code{shapes()}, pattern matching | |
180 | is used by other modules for different tasks throughout | |
181 | the program. @xref{Patterns}, for a complete documentation | |
182 | of patterns.) | |
183 | @end quotation | |
184 | ||
185 | @item @code{combinations()} | |
186 | @findex atari_atari | |
187 | @quotation | |
188 | See if there are any combination threats or atari sequences and either | |
189 | propose them or defend against them. | |
190 | @end quotation | |
191 | ||
192 | @item @code{revise_thrashing_dragon()} | |
193 | @findex revise_thrashing_dragon | |
194 | @quotation | |
195 | This module does not directly propose move: If we are clearly ahead, | |
196 | and the last move played by the opponent is part of a dead dragon, we | |
197 | want to attack that dragon again to be on the safe side. This is done | |
198 | be setting the status of this @dfn{thrashing dragon} to unkown and | |
199 | repeating the shape move generation and move valution. | |
200 | @end quotation | |
201 | ||
202 | @item @code{endgame_shapes()} | |
203 | @findex endgame_shapes | |
204 | @quotation | |
205 | If no move is found with a value greater than 6.0, this module matches a | |
206 | set of extra patterns which are designed for the endgame. The endgame | |
207 | patterns can be found in @file{patterns/endgame.db}. | |
208 | @end quotation | |
209 | ||
210 | @item @code{revise_semeai()} | |
211 | @findex revise_semeai | |
212 | @quotation | |
213 | If no move is found, this module changes the status of opponent groups | |
214 | involved in a semeai from @code{DEAD} to @code{UNKNOWN}. After this, | |
215 | genmove runs @code{shapes} and @code{endgame_shapes} again to see if a | |
216 | new move turns up. | |
217 | @end quotation | |
218 | ||
219 | @item @code{fill_liberty()} | |
220 | @findex fill_liberty | |
221 | @quotation | |
222 | Fill a common liberty. This is only used at the end | |
223 | of the game. If necessary a backfilling or backcapturing | |
224 | move is generated. | |
225 | @end quotation | |
226 | @end itemize | |
227 | ||
228 | @node Move Valuation | |
229 | @section Move Valuation | |
230 | ||
231 | After the move generation modules have run, each proposed candidate | |
232 | move goes through a detailed valuation by the function | |
233 | @code{review_move_reasons}. This invokes some analysis to try to turn | |
234 | up other move reasons that may have been missed. | |
235 | ||
236 | The most important value of a move is its territorial effect. | |
237 | @pxref{Influence and Territory} explains in detail how this is determined. | |
238 | ||
239 | This value is modified for all move reasons that cannot be expressed | |
240 | directly in terms of territory, such as combination attacks (where it | |
241 | is not clear which of several strings will get captured), strategical | |
242 | effects, connection moves, etc. A large set heuristics is necessary | |
243 | here, e.g. to avoid duplication of such values. This is explained in | |
244 | more detail in @ref{Valuation}. | |
245 | ||
246 | ||
247 | @node Detailed Sequence of Events | |
248 | @section Detailed Sequence of Events | |
249 | ||
250 | First comes the sequence of events when | |
251 | @code{examine_position()} is run from @code{genmove()}. This | |
252 | is for reference only. | |
253 | ||
254 | @format | |
255 | @code{purge_persistent_caches()} | |
256 | @code{make_worms()}: | |
257 | @code{compute_effective_sizes()} | |
258 | @code{compute_unconditional_status()} | |
259 | @code{find_worm_attacks_and_defenses()}: | |
260 | for each attackable worm: | |
261 | set @code{worm.attack} | |
262 | @code{change_attack()} to add the attack point | |
263 | @code{find_attack_patterns()} to find a few more attacks | |
264 | for each defensible worm: | |
265 | set @code{worm.attack} | |
266 | @code{change_defense()} to add the defense point | |
267 | @code{find_defense_patterns()} to find a few more defense moves | |
268 | find additional attacks and defenses by testing all | |
269 | immediate liberties | |
270 | find higher order liberties (for each worm) | |
271 | find cutting stones (for each worm) | |
272 | improve attacks and defenses: if capturing a string defends | |
273 | another friendly string, or kills an unfriendly one, we | |
274 | add points of defense or attack. Make repairs if adjacent | |
275 | strings can both be attacked but not defended. | |
276 | find worm lunches | |
277 | find worm threats | |
278 | identify inessential worms (such as nakade stones) | |
279 | @code{compute_worm_influence()}: | |
280 | @code{find_influence_patterns()} | |
281 | @code{value_influence()} | |
282 | @code{segment_influence()} | |
283 | @code{make_dragons()}: | |
284 | @code{find_cuts()} | |
285 | @code{find_connections()} | |
286 | @code{make_domains()} (determine eyeshapes) | |
287 | @code{find_lunches()} (adjacent strings that can be captured) | |
288 | @code{find_half_and_false_eyes()} | |
289 | @code{eye_computations()}: Compute the value of each eye space. | |
290 | Store its attack and defense point. | |
291 | @code{analyze_false_eye_territory()} | |
292 | for each dragon @code{compute_dragon_genus()} | |
293 | for each dragon @code{compute_escape()} and set escape route data | |
294 | @code{resegment_initial_influence()} | |
295 | @code{compute_refined_dragon_weaknesses()} (called again after owl) | |
296 | for each dragon @code{compute_crude_status()} | |
297 | @code{find_neighbor_dragons()} | |
298 | for each dragon compute surround status | |
299 | for each weak dragon run @code{owl_attack()} and @code{owl_defend()} | |
300 | to determine points of attack and defense | |
301 | for each dragon compute dragon.status | |
302 | for each thrashing dragon compute owl threats | |
303 | for each dragon compute dragon.safety | |
304 | @code{revise_inessentiality()} | |
305 | @code{semeai()}: | |
306 | for every semeai, run @code{owl_analyze_semeai()} | |
307 | @code{find_moves_to_make_seki()} | |
308 | @code{identify_thrashing_dragons()} | |
309 | @code{compute_dragon_influence()}: | |
310 | @code{compute_influence()} | |
311 | @code{break_territories()} (@pxref{Break Ins}) | |
312 | @code{compute_refined_dragon_weaknesses()} | |
313 | @end format | |
314 | ||
315 | Now a summary of the sequence of events during the | |
316 | move generation and selection phases of @code{genmove()}, which | |
317 | take place after the information gathering phase has been completed: | |
318 | ||
319 | @format | |
320 | @code{estimate_score()} | |
321 | @code{choose_strategy()} | |
322 | @code{collect_move_reasons()}: | |
323 | @code{worm_reasons()}: for each attack and defense point add a move reason | |
324 | @code{semeai_reasons()}: for each dragon2.semeai point add a move reason | |
325 | @code{owl_reasons()}: for each owl attack and defense point add a move reason | |
326 | @code{break_in_reasons()}: for each breakin found add a move reason | |
327 | @code{fuseki()} | |
328 | @code{break_mirror_go()} | |
329 | @code{shapes()}: match patterns around the board (@pxref{Patterns Overview}) | |
330 | @code{combinations()}: look for moves with a double meaning and other tricks | |
331 | @code{find_double_threats()} | |
332 | @code{atari_atari()} | |
333 | @code{review_move_reasons()} | |
334 | if ahead and there is a thrashing dragon, consider it | |
335 | alive and reconsider the position | |
336 | @code{endgame_shapes()} | |
337 | @code{endgame()} | |
338 | if no move found yet, revisit any semeai, change status of dead opponent | |
339 | to alive, then run @code{shapes()} and @code{endgame_shapes()} again | |
340 | if no move found yet, run @code{fill_liberty()} | |
341 | @end format | |
342 | ||
343 | @node Roadmap | |
344 | @section Roadmap | |
345 | ||
346 | The GNU Go engine is contained in two directories, @file{engine/} and | |
347 | @file{patterns/}. Code related to the user interface, reading and | |
348 | writing of Smart Game Format files, and testing are found in the | |
349 | directories @file{interface/}, @file{sgf/}, and @file{regression/}. Code | |
350 | borrowed from other GNU programs is contained in @file{utils/}. That | |
351 | directory also includes some code developed within GNU Go which is not | |
352 | go specific. Documentation is in @file{doc/}. | |
353 | ||
354 | In this document we will describe some of the individual files comprising | |
355 | the engine code in @file{engine/} and @file{patterns/}. In @file{interface/} | |
356 | we mention two files: | |
357 | ||
358 | @itemize | |
359 | @item @file{gmp.c} | |
360 | @quotation | |
361 | This is the Go Modem Protocol interface (courtesy of | |
362 | William Shubert and others). This takes care of all the | |
363 | details of exchanging setup and moves with Cgoban, or any | |
364 | other driving program recognizing the Go Modem Protocol. | |
365 | @end quotation | |
366 | @item @file{main.c} | |
367 | @quotation | |
368 | This contains @code{main()}. The @file{gnugo} target is | |
369 | thus built in the @file{interface/} directory. | |
370 | @end quotation | |
371 | @end itemize | |
372 | ||
373 | @subsection Files in @file{engine/} | |
374 | ||
375 | In @file{engine/} there are the following files: | |
376 | ||
377 | @itemize @bullet | |
378 | @item @file{aftermath.c} | |
379 | @quotation | |
380 | Contains algorithms which may be called at the end of the game to generate | |
381 | moves that will generate moves to settle the position, if necessary playing | |
382 | out a position to determine exactly the status of every group on the board, | |
383 | which GNU Go can get wrong, particularly if there is a seki. This module is | |
384 | the basis for the most accurate scoring algorithm available in GNU Go. | |
385 | @end quotation | |
386 | @item @file{board.c} | |
387 | @quotation | |
388 | @findex trymove | |
389 | @findex popgo | |
390 | @findex is_legal | |
391 | This file contains code for the maintenance of the board. For example | |
392 | it contains the important function @code{trymove()} which tries a move | |
393 | on the board, and @code{popgo()} which removes it by popping the move | |
394 | stack. At the same time vital information such as the number of | |
395 | liberties for each string and their location is updated incrementally. | |
396 | @end quotation | |
397 | @item @file{breakin.c} | |
398 | @quotation | |
399 | Code to detect moves which can break into supposed territory and moves | |
400 | to prevent this. | |
401 | @end quotation | |
402 | @item @file{cache.c} and @file{cache.h} | |
403 | @quotation | |
404 | As a means of speeding up reading, computed results are cached so that | |
405 | they can be quickly reused if the same position is encountered through | |
406 | e.g. another move ordering. This is implemented using a hash table. | |
407 | @end quotation | |
408 | @item @file{clock.c} and @file{clock.h} | |
409 | @quotation | |
410 | Clock code, including code allowing GNU Go to automatically | |
411 | adjust its level in order to avoid losing on time in tournaments. | |
412 | @end quotation | |
413 | @item @file{combination.c} | |
414 | @quotation | |
415 | When something can (only) be captured through a series of ataris or | |
416 | other threats we call this a combination attack. This file contains code | |
417 | to find such attacks and moves to prevent them. | |
418 | @end quotation | |
419 | @item @file{dragon.c} | |
420 | @quotation | |
421 | This contains @code{make_dragons()}. This function is executed before | |
422 | the move-generating modules @code{shapes()} @code{semeai()} and the | |
423 | other move generators but after @code{make_worms()}. It tries to connect | |
424 | worms into dragons and collect important information about them, such as | |
425 | how many liberties each has, whether (in GNU Go's opinion) the dragon | |
426 | can be captured, if it lives, etc. | |
427 | @end quotation | |
428 | @item @file{endgame.c} | |
429 | @quotation | |
430 | Code to find certain types of endgame moves. | |
431 | @end quotation | |
432 | @item @file{filllib.c} | |
433 | @quotation | |
434 | Code to force filling of dame (backfilling if necessary) | |
435 | at the end of the game. | |
436 | @end quotation | |
437 | @item @file{fuseki.c} | |
438 | @quotation | |
439 | Generates fuseki (opening) moves from a database. Also generates moves | |
440 | in empty corners. | |
441 | @end quotation | |
442 | @item @file{genmove.c} | |
443 | @quotation | |
444 | This file contains @code{genmove()} and its supporting | |
445 | routines, particularly @code{examine_position()}. | |
446 | @end quotation | |
447 | @item @file{globals.c} | |
448 | @quotation | |
449 | This contains the principal global variables used by GNU Go. | |
450 | @end quotation | |
451 | @item @file{gnugo.h} | |
452 | @quotation | |
453 | This file contains declarations forming the public interface to | |
454 | the engine. | |
455 | @end quotation | |
456 | @item @file{hash.c} and @file{hash.h} | |
457 | @quotation | |
458 | Hashing code implementing Zobrist hashing. (@pxref{Hashing}) The code in | |
459 | @file{hash.c} provides a way to hash board positions into compact descriptions | |
460 | which can be efficiently compared. The caching code in @file{cache.c} | |
461 | makes use of the board hashes when storing and retrieving read results. | |
462 | @end quotation | |
463 | @item @file{influence.c} and @file{influence.h}. | |
464 | @quotation | |
465 | This code determines which regions of the board are under the | |
466 | influence of either player. | |
467 | (@pxref{Influence}) | |
468 | @end quotation | |
469 | @item @file{liberty.h} | |
470 | @quotation | |
471 | Header file for the engine. The name ``liberty'' connotes | |
472 | freedom (@pxref{Copying}). | |
473 | @end quotation | |
474 | @item @file{matchpat.c} | |
475 | @quotation | |
476 | This file contains the pattern matcher @code{matchpat()}, which looks for | |
477 | patterns at a particular board location. The actual patterns are in | |
478 | the @file{patterns/} directory. The function @code{matchpat()} is | |
479 | called by every module which does pattern matching, notably @code{shapes}. | |
480 | @end quotation | |
481 | @item @file{move_reasons.c} and @file{move_reasons.h} | |
482 | @quotation | |
483 | Code for keeping track of move reasons. | |
484 | @end quotation | |
485 | @item @file{movelist.c} | |
486 | @quotation | |
487 | Supporting code for lists of moves. | |
488 | @end quotation | |
489 | @item @file{optics.c} | |
490 | @quotation | |
491 | This file contains the code to recognize eye shapes, | |
492 | documented in @xref{Eyes}. | |
493 | @end quotation | |
494 | @item @file{oracle.c} | |
495 | @quotation | |
496 | Code to fork off a second GNU Go process which can be used to simulate | |
497 | reading with top level information (e.g. dragon partitioning) available. | |
498 | @end quotation | |
499 | @item @file{owl.c} | |
500 | @quotation | |
501 | This file does life and death reading. Move generation is pattern based | |
502 | and the code in @file{optics.c} is used to evaluate the eyespaces for | |
503 | vital moves and independent life. A dragon can also live by successfully | |
504 | escaping. Semeai reading along the same principles is also implemented | |
505 | in this file. | |
506 | @end quotation | |
507 | @item @file{persistent.c} | |
508 | @quotation | |
509 | Persistent cache which allows reuse of read results at a later move or | |
510 | with additional stones outside an active area, which are those | |
511 | intersections thought to affect the read result. | |
512 | @end quotation | |
513 | @item @file{printutils.c} | |
514 | @quotation | |
515 | Print utilities. | |
516 | @end quotation | |
517 | @item @file{readconnect.c} and @file{readconnect.h} | |
518 | @quotation | |
519 | This file contains code to determine whether two strings can be | |
520 | connected or disconnected. | |
521 | @end quotation | |
522 | @item @file{reading.c} | |
523 | @quotation | |
524 | This file contains code to determine whether any given | |
525 | string can be attacked or defended. @xref{Tactical Reading}, | |
526 | for details. | |
527 | @end quotation | |
528 | @item @file{semeai.c} | |
529 | @quotation | |
530 | This file contains @code{semeai()}, the module which detects dragons | |
531 | in semeai. To determine the semeai results the semeai reading in | |
532 | @file{owl.c} is used. | |
533 | @end quotation | |
534 | @item @file{sgfdecide.c} | |
535 | @quotation | |
536 | Code to generate sgf traces for various types of reading. | |
537 | @end quotation | |
538 | @item @file{shapes.c} | |
539 | @quotation | |
540 | This file contains @code{shapes()}, the module called by @code{genmove()} | |
541 | which tries to find moves which match a pattern (@pxref{Patterns}). | |
542 | @end quotation | |
543 | @item @file{showbord.c} | |
544 | @quotation | |
545 | This file contains @code{showboard()}, which draws an ASCII | |
546 | representation of the board, depicting dragons (stones | |
547 | with same letter) and status (color). This was the | |
548 | primary interface in GNU Go 1.2, but is now a debugging | |
549 | aid. | |
550 | @end quotation | |
551 | @item @file{surround.c} | |
552 | @quotation | |
553 | Code to determine whether a dragon is surrounded and to find moves to | |
554 | surround with or break out with. | |
555 | @end quotation | |
556 | @item @file{utils.c} | |
557 | @quotation | |
558 | An assortment of utilities, described in greater detail below. | |
559 | @end quotation | |
560 | @item @file{value_moves.c} | |
561 | @quotation | |
562 | This file contains the code which assigns values to every move | |
563 | after all the move reasons are generated. It also tries to generate | |
564 | certain kinds of additional move reasons. | |
565 | @end quotation | |
566 | @item @file{worm.c} | |
567 | @quotation | |
568 | This file contains @code{make_worms()}, code which is run at the | |
569 | beginning of each move cycle, before the code in @file{dragon.c}, to | |
570 | determine the attributes of every string. These attributes are things | |
571 | like liberties, wether the string can be captured (and how), etc | |
572 | @end quotation | |
573 | @end itemize | |
574 | ||
575 | @subsection Files in @file{patterns/} | |
576 | ||
577 | The directory @file{patterns/} contains files related to pattern matching. | |
578 | Currently there are several types of patterns. A partial list: | |
579 | ||
580 | @itemize @bullet | |
581 | @item move generation patterns in @file{patterns.db} and @file{patterns2.db} | |
582 | @item move generation patterns in files @file{hoshi.db} etc. which are | |
583 | automatically build from the files @file{hoshi.sgf} etc. These comprise | |
584 | our small Joseki library. | |
585 | @item patterns in @file{owl_attackpats.db}, @file{owl_defendpats.db} | |
586 | and @file{owl_vital_apats.db}. These generate moves for the owl | |
587 | code (@pxref{The Owl Code}). | |
588 | @item Connection patterns in @file{conn.db} (@pxref{Connections Database}) | |
589 | @item Influence patterns in @file{influence.db} and @file{barriers.db} | |
590 | (@pxref{Influence}) | |
591 | @item eye patterns in @file{eyes.db} (@pxref{Eyes}). | |
592 | @end itemize | |
593 | ||
594 | The following list contains, in addition to distributed source files | |
595 | some intermediate automatically generated files such as @file{patterns.c}. | |
596 | These are C source files produced by "compiling" various pattern | |
597 | databases, or in some cases (such as @file{hoshi.db}) themselves | |
598 | automatically generated pattern databases produced by "compiling" | |
599 | joseki files in Smart Game Format. | |
600 | ||
601 | @itemize @bullet | |
602 | ||
603 | @item @file{conn.db} | |
604 | @quotation | |
605 | Database of connection patterns. | |
606 | @end quotation | |
607 | ||
608 | @item @file{conn.c} | |
609 | @quotation | |
610 | Automatically generated file, containing connection | |
611 | patterns in form of struct arrays, compiled by @command{mkpat} | |
612 | from @file{conn.db}. | |
613 | @end quotation | |
614 | ||
615 | @item @file{eyes.c} | |
616 | @quotation | |
617 | Automatically generated file, containing eyeshape | |
618 | patterns in form of struct arrays, compiled by @command{mkpat} | |
619 | from @file{eyes.db}. | |
620 | @end quotation | |
621 | ||
622 | @item @file{eyes.h} | |
623 | @quotation | |
624 | Header file for @file{eyes.c}. | |
625 | @end quotation | |
626 | ||
627 | @item @file{eyes.db} | |
628 | @quotation | |
629 | Database of eyeshape patterns. @xref{Eyes}, for | |
630 | details. | |
631 | @end quotation | |
632 | ||
633 | @item @file{helpers.c} | |
634 | @quotation | |
635 | These are helper functions to assist in evaluating | |
636 | moves by matchpat. | |
637 | @end quotation | |
638 | ||
639 | @item @file{hoshi.sgf} | |
640 | @quotation | |
641 | Smart Game Format file containing 4-4 point openings | |
642 | @end quotation | |
643 | ||
644 | @item @file{hoshi.db} | |
645 | @quotation | |
646 | Automatically generated database of 4-4 point opening | |
647 | patterns, make by compiling @file{hoshi.sgf} | |
648 | @end quotation | |
649 | ||
650 | @item @file{joseki.c} | |
651 | @quotation | |
652 | Joseki compiler, which takes a joseki file in | |
653 | Smart Game Format, and produces a pattern database. | |
654 | @end quotation | |
655 | ||
656 | @item @file{komoku.sgf} | |
657 | @quotation | |
658 | Smart Game Format file containing 3-4 point openings | |
659 | @end quotation | |
660 | ||
661 | @item @file{komoku.db} | |
662 | @quotation | |
663 | Automatically generated database of 3-4 point opening | |
664 | patterns, make by compiling @file{komoku.sgf} | |
665 | @end quotation | |
666 | ||
667 | @item @file{mkeyes.c} | |
668 | @quotation | |
669 | Pattern compiler for the eyeshape databases. This | |
670 | program takes @file{eyes.db} as input and produces @file{eyes.c} | |
671 | as output. | |
672 | @end quotation | |
673 | ||
674 | @item @file{mkpat.c} | |
675 | @quotation | |
676 | Pattern compiler for the move generation and connection | |
677 | databases. Takes the file @file{patterns.db} together with | |
678 | the autogenerated Joseki pattern files @file{hoshi.db}, @file{komoku.db}, | |
679 | @file{sansan.db}, @file{mokuhadzushi.db}, @file{takamoku.db} and produces | |
680 | @file{patterns.c}, or takes @file{conn.db} and produces @file{conn.c}. | |
681 | @end quotation | |
682 | ||
683 | @item @file{mokuhazushi.sgf} | |
684 | @quotation | |
685 | Smart Game Format file containing 5-3 point openings | |
686 | @end quotation | |
687 | ||
688 | @item @file{mokuhazushi.db} | |
689 | @quotation | |
690 | Pattern database compiled from mokuhadzushi.sgf | |
691 | @end quotation | |
692 | ||
693 | @item @file{sansan.sgf} | |
694 | @quotation | |
695 | Smart Game Format file containing 3-3 point openings | |
696 | @end quotation | |
697 | ||
698 | @item @file{sansan.db} | |
699 | @quotation | |
700 | Pattern database compiled from @file{sansan.sgf} | |
701 | @end quotation | |
702 | ||
703 | @item @file{takamoku.sgf} | |
704 | @quotation | |
705 | Smart Game Format file containing 5-4 point openings | |
706 | @end quotation | |
707 | ||
708 | @item @file{takamoku.db} | |
709 | @quotation | |
710 | Pattern database compiled from takamoku.sgf. | |
711 | @end quotation | |
712 | ||
713 | @item @file{patterns.c} | |
714 | @quotation | |
715 | Pattern data, compiled from patterns.db by mkpat. | |
716 | @end quotation | |
717 | ||
718 | @item @file{patterns.h} | |
719 | @quotation | |
720 | Header file relating to the pattern databases. | |
721 | @end quotation | |
722 | ||
723 | @item @file{patterns.db} and @file{patterns2.db} | |
724 | @quotation | |
725 | These contain pattern databases in human readable form. | |
726 | @end quotation | |
727 | ||
728 | @end itemize | |
729 | ||
730 | ||
731 | @node Coding Styles | |
732 | @section Coding styles and conventions | |
733 | ||
734 | @subsection Coding Conventions | |
735 | ||
736 | Please follow the coding conventions at: | |
737 | @url{http://www.gnu.org/prep/standards_toc.html} | |
738 | ||
739 | Please preface every function with a brief description | |
740 | of its usage. | |
741 | ||
742 | Please help to keep this Texinfo documentation up-to-date. | |
743 | ||
744 | @subsection Tracing | |
745 | ||
746 | A function @code{gprintf()} is provided. It is a cut-down | |
747 | @code{printf}, supporting only @code{%c}, @code{%d}, | |
748 | @code{%s}, and without field widths, etc. It does, however, | |
749 | add some useful facilities: | |
750 | ||
751 | @itemize @bullet | |
752 | @item @code{%m} | |
753 | @quotation | |
754 | Takes two parameters, and displays a formatted board co-ordinate. | |
755 | @end quotation | |
756 | @item indentation | |
757 | @quotation | |
758 | Trace messages are automatically indented to reflect | |
759 | the current stack depth, so it is clear during read-ahead | |
760 | when it puts a move down or takes one back. | |
761 | @end quotation | |
762 | @item "outdent" | |
763 | @quotation As a workaround, @code{%o} at the beginning of the | |
764 | format string suppresses the indentation. | |
765 | @end quotation | |
766 | @end itemize | |
767 | ||
768 | Normally @code{gprintf()} is wrapped in one of the following: | |
769 | ||
770 | @code{TRACE(fmt, ...)}: | |
771 | @quotation | |
772 | Print the message if the 'verbose' variable > 0. | |
773 | (verbose is set by @command{-t} on the command line) | |
774 | @end quotation | |
775 | ||
776 | @code{DEBUG(flags, fmt, ...)}: | |
777 | @quotation | |
778 | While @code{TRACE} is intended to afford an overview | |
779 | of what GNU Go is considering, @code{DEBUG} allows occasional | |
780 | in depth study of a module, usually needed when something | |
781 | goes wrong. @code{flags} is one of the @code{DEBUG_*} symbols in | |
782 | @file{engine/gnugo.h}. The @code{DEBUG} macro tests to | |
783 | see if that bit is set in the @code{debug} variable, and prints | |
784 | the message if it is. The debug variable is set using the | |
785 | @command{-d} command-line option. | |
786 | @end quotation | |
787 | ||
788 | The variable @code{verbose} controls the tracing. It | |
789 | can equal 0 (no trace), 1, 2, 3 or 4 for increasing | |
790 | levels of tracing. You can set the trace level at | |
791 | the command line by @option{-t} for @code{verbose=1}, | |
792 | @option{-t -t} for @code{verbose=2}, etc. But in | |
793 | practice if you want more verbose tracing than level | |
794 | 1 it is better to use GDB to reach the point where | |
795 | you want the tracing; you will often find that the | |
796 | variable @code{verbose} has been temporarily set to zero | |
797 | and you can use the GDB command @command{set var verbose=1} | |
798 | to turn the tracing back on. | |
799 | ||
800 | @subsection Assertions | |
801 | ||
802 | Related to tracing are assertions. Developers are strongly encouraged | |
803 | to pepper their code with assertions to ensure that data structures | |
804 | are as they expect. For example, the helper functions make assertions | |
805 | about the contents of the board in the vicinity of the move they | |
806 | are evaluating. | |
807 | ||
808 | @code{ASSERT()} is a wrapper around the standard C @code{assert()} | |
809 | function. In addition to the test, it takes an extra pair of parameters | |
810 | which are the co-ordinates of a "relevant" board position. If an | |
811 | assertion fails, the board position is included in the trace output, and | |
812 | @code{showboard()} and @code{popgo()} are called to unwind and display | |
813 | the stack. | |
814 | ||
815 | @subsection FIXME | |
816 | @cindex FIXME | |
817 | ||
818 | We have adopted the convention of putting the word FIXME | |
819 | in comments to denote known bugs, etc. | |
820 | ||
821 | @node Navigating the Source | |
822 | @section Navigating the Source | |
823 | ||
824 | If you are using Emacs, you may find it fast and convenient to use | |
825 | Emacs' built-in facility for navigating the source. Switch to the | |
826 | root directory @file{gnugo-3.6/} and execute the command: | |
827 | ||
828 | @example | |
829 | find . -print|grep "\.[ch]$" | xargs etags | |
830 | @end example | |
831 | ||
832 | This will build a file called @file{gnugo-3.6/TAGS}. Now to | |
833 | find any GNU Go function, type @command{M-.} and enter the | |
834 | command which you wish to find, or just @command{RET} if | |
835 | the cursor is at the name of the function sought. | |
836 | ||
837 | The first time you do this you will be prompted for the location | |
838 | of the TAGS table. Enter the path to @file{gnugo-3.6/TAGS}, and | |
839 | henceforth you will be able to find any function with a minimum | |
840 | of keystrokes. | |
841 | ||
842 | ||
843 | ||
844 |