This is gnugo.info, produced by makeinfo version 4.11 from gnugo.texi. INFO-DIR-SECTION GNU games START-INFO-DIR-ENTRY * GNU Go: (gnugo). The GNU Go program END-INFO-DIR-ENTRY  File: gnugo.info, Node: The Owl Code, Next: Combinations, Up: Pattern Based Reading 12.1 The Owl Code ================= The life and death code in `optics.c', described elsewhere (*note Eyes::), works reasonably well as long as the position is in a "terminal position", which we define to be one where there are no moves left which can expand the eye space, or limit it. In situations where the dragon is surrounded, yet has room to thrash around a bit making eyes, a simple application of the graph-based analysis will not work. Instead, a bit of reading is needed to reach a terminal position. The defender tries to expand his eyespace, the attacker to limit it, and when neither finds an effective move, the position is evaluated. We call this type of life and death reading "Optics With Limit-negotiation" (OWL). The module which implements it is in `engine/owl.c'. There are two reasonably small databases `patterns/owl_defendpats.db' and `patterns/owl_attackpats.db' of expanding and limiting moves. The code in `owl.c' generates a small move tree, allowing the attacker only moves from `owl_attackpats.db', and the defender only moves from `owl_defendpats.db'. In addition to the moves suggested by patterns, vital moves from the eye space analysis are also tested. A third database, `owl_vital_apats.db' includes patterns which override the eyespace analysis done by the optics code. Since the eyeshape graphs ignore the complications of shortage of liberties and cutting points in the surrounding chains, the static analysis of eyespace is sometimes wrong. The problem is when the optics code says that a dragon definitely has 2 eyes, but it isn't true due to shortage of liberties, so the ordinary owl patterns never get into play. In such situations `owl_vital_apats.db' is the only available measure to correct mistakes by the optics. Currently the patterns in `owl_vital_apats.db' are only matched when the level is 9 or greater. The owl code is tuned by editing these three pattern databases, principally the first two. A node of the move tree is considered `terminal' if no further moves are found from `owl_attackpats.db' or `owl_defendpats.db', or if the function `compute_eyes_pessimistic()' reports that the group is definitely alive. At this point, the status of the group is evaluated. The functions `owl_attack()' and `owl_defend()', with usage similar to `attack()' and `find_defense()', make use of the owl pattern databases to generate the move tree and decide the status of the group. The function `compute_eyes_pessimistic()' used by the owl code is very conservative and only feels certain about eyes if the eyespace is completely closed (i.e. no marginal vertices). The maximum number of moves tried at each node is limited by the parameter `MAX_MOVES' defined at the beginning of `engine/owl.c'. The most most valuable moves are tried first, with the following restrictions: * If `stackp > owl_branch_depth' then only one move is tried per variation. * If `stackp > owl_reading_depth' then the reading terminates, and the situation is declared a win for the defender (since deep reading may be a sign of escape). * If the node count exceeds `owl_node_limit', the reading also terminates with a win for the defender. * Any pattern with value 99 is considered a forced move: no other move is tried, and if two such moves are found, the function returns false. This is only relevant for the attacker. * Any pattern in `patterns/owl_attackpats.db' and `patterns/owl_defendpats.db' with value 100 is considered a win: if such a pattern is found by `owl_attack' or `owl_defend', the function returns true. This feature must be used most carefully. The functions `owl_attack()' and `owl_defend()' may, like `attack()' and `find_defense()', return an attacking or defending move through their pointer arguments. If the position is already won, `owl_attack()' may or may not return an attacking move. If it finds no move of interest, it will return `PASS', that is, `0'. The same goes for `owl_defend()'. When `owl_attack()' or `owl_defend()' is called, the dragon under attack is marked in the array `goal'. The stones of the dragon originally on the board are marked with goal=1; those added by `owl_defend()' are marked with goal=2. If all the original strings of the original dragon are captured, `owl_attack()' considers the dragon to be defeated, even if some stones added later can make a live group. Only dragons with small escape route are studied when the functions are called from `make_dragons()'. The owl code can be conveniently tested using the `--decide-owl LOCATION' option. This should be used with `-t' to produce a useful trace, `-o' to produce an SGF file of variations produced when the life and death of the dragon at LOCATION is checked, or both. `--decide-position' performs the same analysis for all dragons with small escape route.  File: gnugo.info, Node: Combinations, Prev: The Owl Code, Up: Pattern Based Reading 12.2 Combination reading ======================== It may happen that no single one of a set of worms can be killed, yet there is a move that guarantees that at least one can be captured. The simplest example is a double atari. The purpose of the code in `combination.c' is to find such moves. For example, consider the following situation: +--------- |....OOOOX |....OOXXX |..O.OXX.. |.OXO.OX.. |.OX..OO.. |.XXOOOXO. |..*XXOX.. |....XOX.. |.XX..X... |X........ Every `X' stone in this position is alive. However the move at `*' produces a position in which at least one of four strings will get captured. This is a _combination_. The driving function is called `atari_atari' because typically a combination involves a sequence of ataris culminating in a capture, though sometimes the moves involved are not ataris. For example in the above example, the first move at `*' is _not_ an atari, though after `O' defends the four stones above, a sequence of ataris ensues resulting in the capture of some string. Like the owl functions `atari_atari' does pattern-based reading. The database generating the attacking moves is `aa_attackpats.db'. One danger with this function is that the first atari tried might be irrelevant to the actual combination. To detect this possibility, once we've found a combination, we mark that first move as forbidden, then try again. If no combination of the same size or larger turns up, then the first move was indeed essential. * `void combinations(int color)' Generate move reasons for combination attacks and defenses against them. This is one of the move generators called from genmove(). * `int atari_atari(int color, int *attack_move, char defense_moves[BOARDMAX], int save_verbose)' Look for a combination for `color'. For the purpose of the move generation, returns the size of the smallest of the worms under attack. * `int atari_atari_confirm_safety(int color, int move, int *defense, int minsize, const char saved_dragons[BOARDMAX], const char saved_worms[BOARDMAX])' Tries to determine whether a move is a blunder. Wrapper around atari_atari_blunder_size. Check whether a combination attack of size at least `minsize' appears after move at `move' has been made. The arrays `saved_dragons[]' and `saved_worms[]' should be one for stones belonging to dragons or worms respectively, which are supposedly saved by `move'. * `int atari_atari_blunder_size(int color, int move, int *defense, const char safe_stones[BOARDMAX])' This function checks whether any new combination attack appears after move at (move) has been made, and returns its size (in points). `safe_stones' marks which of our stones are supposedly safe after this move.  File: gnugo.info, Node: Influence, Next: Monte Carlo Go, Prev: Pattern Based Reading, Up: Top 13 Influence Function ********************* * Menu: * Influential Concepts:: Conceptual Outline of Influence * Territory and Moyo:: Territory, Moyo and Area * Influence Usage:: Where influence gets used in the engine * Influence and Territory:: Influence and Territory * Territorial Details:: Details of the Territory Valuation * The Influence Core:: The Core of the Influence Function * The Influence Algorithm:: The algorithm of `accumlate_influence()' * Permeability:: Permeability * Escape:: Escape * Break Ins:: Break Ins * Surrounded Dragons:: Surrounded Dragons * Influential Patterns:: Patterns used by the Influence module * Influential Display:: Colored display and debugging of influence * Influence Tuning:: Influence tuning with view.pike  File: gnugo.info, Node: Influential Concepts, Next: Territory and Moyo, Up: Influence 13.1 Conceptual Outline of Influence ==================================== We define call stones "lively" if they cannot be tactically attacked, or if they have a tactical defense and belong to the player whose turn it is. Similarly, stones that cannot be strategically attacked (in the sense of the life-and-death analysis), or that have a strategical defense and belong to the player to move, are called "alive". If we want to use the influence function before deciding the strategical status, all lively stones count as alive. Every alive stone on the board works as an influence source, with influence of its color radiating outwards in all directions. The strength of the influence declines exponentially with the distance from the source. Influence can only flow unhindered if the board is empty, however. All lively stones (regardless of color) act as influence barriers, as do connections between enemy stones that can't be broken through. For example the one space jump counts as a barrier unless either of the stones can be captured. Notice that it doesn't matter much if the connection between the two stones can be broken, since in that case there would come influence from both directions anyway. From the influence of both colors we compute a territorial value between -1.0 and +1.0 for each intersection, which can be seen as the likely hood of it becoming territory for either color. In order to avoid finding bogus territory, we add extra influence sources at places where an invasion can be launched, e.g. at 3-3 under a handicap stone, in the middle of wide edge extensions and in the center of large open spaces anywhere. Similarly we add extra influence sources where intrusions can be made into what otherwise looks as solid territory, e.g. monkey jumps. These intrusions depend on whose turn we assume it to be. All these extra influence sources, as well as connections, are controlled by a pattern database, which consists of the two files patterns/influence.db and patterns/barriers.db. The details are explained in *note Influential Patterns::.  File: gnugo.info, Node: Territory and Moyo, Next: Influence Usage, Prev: Influential Concepts, Up: Influence 13.2 Territory, Moyo and Area ============================= Using the influence code, empty regions of the board are partitioned in three ways. A vertex may be described as White or Black's "territory", "moyo" or "area". The functions `whose_territory()', `whose_moyo()' and `whose_area()' will return a color, or EMPTY if it belongs to one player or the other in one of these classifications. * Territory Those parts of the board which are expected to materialize as actual points for one player or the other at the end of the game are considered "territory". * Moyo Those parts of the board which are either already territory or more generally places where a territory can easily materialize if the opponent neglects to reduce are considered "moyo". "moyo". * Area Those parts of the board where one player or the other has a stronger influence than his opponent are considered "area". Generally territory is moyo and moyo is area. To get a feeling for these concepts, load an sgf file in a middle game position with the option `-m 0x0180' and examine the resulting diagrams (*note Influential Display::).  File: gnugo.info, Node: Influence Usage, Next: Influence and Territory, Prev: Territory and Moyo, Up: Influence 13.3 Where influence gets used in the engine ============================================ The information obtained from the influence computation is used in a variety of places in the engine, and the influence module is called several times in the process of the move generation. The details of the influence computation vary according to the needs of the calling function. After GNU Go has decided about the tactical stability of strings, the influence module gets called the first time. Here all lively stones act as an influence source of default strength 100. The result is stored in the variables `initial_influence' and `initial_opposite_influence', and it is used as an important information for guessing the strength of dragons. For example, a dragon that is part of a moyo of size 25 is immediately considered alive. For dragons with a smaller moyo size, a life-and-death analysis will be done by the owl code (see *note Pattern Based Reading::). A dragon with a moyo size of only 5 will be considered weak, even if the owl code has decided that it cannot be killed. As a tool for both the owl code and the strength estimate of dragons, an "escape" influence gets computed for each dragon (*note Escape::). Once all dragons have been evaluated, the influence module is called again and the variables `initial_influence' and `initial_opposite_influence' get overwritten. Of course, the dragon status', which are available now, are taken into account. Stones belonging to a dead dragon will not serve as an influence source, and the strengths of other stones get adjusted according to the strength of their respective dragon. The result of this run is the most important tool for move evaluation. All helper functions of patterns as explained in *note Patterns:: that refer to influence results (e. g. `olib(*)' etc.) actually use these results. Further, `initial_influence' serves as the reference for computing the territorial value of a move. That is, from the influence strengths stored in `initial_influence', a territory value is assigned to each intersection. This value is supposed to estimate the likelyhood that this intersection will become white or black territory. Then, for each move that gets considered in the function `value_moves', the influence module is called again via the function `compute_move_influence' to assess the likely territorial balance after this move, and the result is compared with the state before that move. An additional influence computation is done in order to compute the followup value of a move. Some explainations are in *note Territorial Details::. Some of the public functions from `influence.c' which are used throughout the engine are listed in *note Influence Utilities::.  File: gnugo.info, Node: Influence and Territory, Next: Territorial Details, Prev: Influence Usage, Up: Influence 13.4 Influence and Territory ============================ In this section we consider how the influence function is used to estimate territory in the function `estimate_territorial_value()'. A move like `*' by `O' below is worth one point: OXXX. OX.XX O*a.X OX.XX OXXX. This is evaluated by the influence function in the following way: We first assign territory under the assumption that X moves first in all local positions in the original position; then we reassing territory, again under the assumption that `X' moves first in all local positions, but after we let `O' make the move at `*'. These two territory assignments are compared and the difference gives the territorial value of the move. Technically, the assumption that `X' plays first everywhere is implemented via an asymmetric pattern database in `barriers.db'. What exactly is a safe connection that stops hostile influence from passing through is different for `O' and `X'; of course such a connection has to be tighter for stones with color `O'. Also, additional intrusion influence sources are added for `X' in places where `X' stones have natural followup moves. In this specific example above, the asymmetry (before any move has been made) would turn out as follows: If `X' is in turn to move, the white influence would get stopped by a barrier at `*', leaving 4 points of territory for `X'. However, if `O' was next to move, then a followup move for the white stones at the left would be assumed in the form of an extra ("intrusion") influence source at `*'. This would get stopped at `a', leaving three points of territory. Returning to the valuation of a move by `O' at `*', we get a value of 1 for the move at `*'. However, of course this move is sente once it is worth playing, and should therefore (in miai counting) be awarded an effective value of 2. Hence we need to recognize the followup value of a move. GNU Go 3.0 took care of this by using patterns in `patterns.db' that enforced an explicit followup value. Versions from 3.2 on instead compute a seperate followup influence to each move considered. In the above example, an intrusion source will be added at `a' as a followup move to `*'. This destroys all of Black's territory and hence gives a followup value of 3. The pattern based followup value are still needed at some places, however. To give another example, consider this position where we want to estimate the value of an `O' move at `*': OOOXXX ..OX.. ..OX.. ...*.. ------ Before the move we assume `X' moves first in the local position (and that `O' has to connect), which gives territory like this (lower case letter identify territory for each player): OOOXXX ooOXxx o.OXxx o...xx ------ Then we let `O' make the move at `*' and assume `X' moves first again next. The territory then becomes (`X' is also assumed to have to connect): OOOXXX ooOXxx ooOX.x oo.O.x ------ We see that this makes a difference in territory of 4, which is what influence_delta_territory() should report. Then again, we have followup value, and here also a reverse followup value. The reverse followup value, which in this case will be so high that the move is treated as reverse sente, is added by an explicit pattern. Other sources for followup or reverse followup values are threats to capture a rescue a string of stones. See the code and comments in the function `value_move_reaons' for how followup and reverse followup values are used to adjust the effective move value. To give an example of territorial value where something is captured, consider the `O' move at `*' here, XXXXXXXO X.OOOOXO X.O..O*O -------- As before we first let the influence function determine territory assuming X moves first, i.e. with a captured group: XXXXXXXO XxyyyyXO Xxyxxy.O -------- Here `y' indicates `X' territory + captured stone, i.e. these count for two points. After the `O' move at `*' we instead get XXXXXXXO X.OOOOXO X.OooOOO -------- and we see that `X' has 16 territory fewer and `O' has two territory more, for a total difference of 18 points. That the influence function counts the value of captured stones was introduced in GNU Go 3.2. Previously this was instead done using the effective_size heuristic. The effective size is the number of stones plus the surrounding empty spaces which are closer to this string or dragon than to any other stones. Here the `O' string would thus have effective size 6 (number of stones) + 2 (interior eye) + 2*0.5 (the two empty vertices to the left of the string, split half each with the surrounding X string) + 1*0.33 (the connection point, split between three strings) = 9.33. As noted this value was doubled, giving 18.67 which is reasonably close to the correct value of 18. The effective size heuristic is still used in certain parts of the move valuation where we can't easily get a more accurate value from the influence function (e. g. attacks depending on a ko, attack threats). Note that this section only describes the territorial valuation of a move. Apart from that, GNU Go uses various heuristics in assigning a strategical value (weakening and strengthening of other stones on the board) to a move. Also, the influence function isn't quite as well tuned as the examples above may seem to claim. But it should give a fairly good idea of how the design is intended. Another matter is that so far we have only considered the change in secure territory. GNU Go 3.2 and later versions use a revised heuristic, which is explained in the next section, to assign probable territory to each player.  File: gnugo.info, Node: Territorial Details, Next: The Influence Core, Prev: Influence and Territory, Up: Influence 13.5 Details of the Territory Valuation ======================================= This section explains how GNU Go assigns a territorial value to an intersection once the white and black influence have been computed. The intention is that an intersection that has a chance of xx% of becoming white territory is counted as 0.xx points of territory for white, and similar for black. The algorithm in the function `new_value_territory' goes roughly as follows: If `wi' is the white influence at a point, and `bi' the black influence, then ` value = ( (wi-bi)/ (wi+bi) )^3' (positive values indicates likley white territory, negative stand for black territory) turns out to be very simple first guess that is still far off, but reasonable enough to be useful. This value is then suspect a number of corrections. Assume that this first guess resulted in a positive value. If both `bi' and `wi' are small, it gets reduced. What exactly is "small" depends on whether the intersection is close to a corner or an edge of the board, since it is easier to claim territory in the corner than in the center. Then the value at each intersection is degraded to the minimum value of its neighbors. This can be seen as a second implementation of the proverb saying that there is no territory in the center of the board. This step substantially reduces the size of spheres of territory that are open at several sides. Finally, there are a number of patterns that explicitly forbid GNU Go to count territory at some intersections. This is used e. g. for false eyes that will eventually have to be filled in. Also, points for prisoners are added. To fine tune this scheme, some revisions have been made to the influence computations that are relevant for territorial evaluation. This includes a reduced default attenuation and some revised pattern handling.  File: gnugo.info, Node: The Influence Core, Next: The Influence Algorithm, Prev: Territorial Details, Up: Influence 13.6 The Core of the Influence Function ======================================= The basic influence radiation process can efficiently be implemented as a breadth first search for adjacent and more distant points, using a queue structure. Influence barriers can be found by pattern matching, assisted by reading through constraints and/or helpers. Wall structures, invasion points and intrusion points can be found by pattern matching as well. When influence is computed, the basic idea is that there are a number of influence sources on the board, whose contributions are summed to produce the influence values. For the time being we can assume that the living stones on the board are the influence sources, although this is not the whole story. The function `compute_influence()' contains a loop over the board, and for each influence source on the board, the function `accumulate_influence()' is called. This is the core of the influence function. Before we get into the details, this is how the influence field from a single isolated influence source of strength 100 turns out (with an attenuation of 3.0): 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 2 3 2 1 0 0 0 0 0 1 3 5 11 5 3 1 0 0 0 1 2 5 16 33 16 5 2 1 0 0 1 3 11 33 X 33 11 3 1 0 0 1 2 5 16 33 16 5 2 1 0 0 0 1 3 5 11 5 3 1 0 0 0 0 0 1 2 3 2 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 These values are in reality floating point numbers but have been rounded down to the nearest integer for presentation. This means that the influence field does not stop when the numbers become zeroes. Internally `accumulate_influence()' starts at the influence source and spreads influence outwards by means of a breadth first propagation, implemented in the form of a queue. The order of propagation and the condition that influence only is spread outwards guarantee that no intersection is visited more than once and that the process terminates. In the example above, the intersections are visited in the following order: + + + + + + + + + + + + 78 68 66 64 63 65 67 69 79 + + 62 46 38 36 35 37 39 47 75 + + 60 34 22 16 15 17 23 43 73 + + 58 32 14 6 3 7 19 41 71 + + 56 30 12 2 0 4 18 40 70 + + 57 31 13 5 1 8 20 42 72 + + 59 33 21 10 9 11 24 44 74 + + 61 45 28 26 25 27 29 48 76 + + 77 54 52 50 49 51 53 55 80 + + + + + + + + + + + + The visitation of intersections continues in the same way on the intersections marked '`+' and further outwards. In a real position there will be stones and tight connections stopping the influence from spreading to certain intersections. This will disrupt the diagram above, but the main property of the propagation still remains, i.e. no intersection is visited more than once and after being visited no more influence will be propagated to the intersection.  File: gnugo.info, Node: The Influence Algorithm, Next: Permeability, Prev: The Influence Core, Up: Influence 13.7 The Influence Algorithm ============================ Let `(m, n)' be the coordinates of the influence source and `(i, j)' the coordinates of a an intersection being visited during propagation, using the same notation as in the `accumulate_influence()' function. Influence is now propagated to its eight closest neighbors, including the diagonal ones, according to the follow scheme: For each of the eight directions `(di, dj)', do: 1. Compute the scalar product `di*(i-m) + dj*(j-n)' between the vectors `(di,dj)' and `(i,j) - (m,n)' 2. If this is negative or zero, the direction is not outwards and we continue with the next direction. The exception is when we are visiting the influence source, i.e. the first intersection, when we spread influence in all directions anyway. 3. If `(i+di, j+dj)' is outside the board or occupied we also continue with the next direction. 4. Let S be the strength of the influence at `(i, j)'. The influence propagated to `(i+di, j+dj)' from this intersection is given by `P*(1/A)*D*S', where the three different kinds of damping are: * The permeability `P', which is a property of the board intersections. Normally this is one, i.e. unrestricted propagation, but to stop propagation through e.g. one step jumps, the permeability is set to zero at such intersections through pattern matching. This is further discussed below. * The attenuation `A', which is a property of the influence source and different in different directions. By default this has the value 3 except diagonally where the number is twice as much. By modifying the attenuation value it is possible to obtain influence sources with a larger or a smaller effective range. * The directional damping `D', which is the squared cosine of the angle between `(di,dj)' and `(i,j) - (m,n)'. The idea is to stop influence from "bending" around an interfering stone and get a continuous behavior at the right angle cutoff. The choice of the squared cosine for this purpose is rather arbitrary, but has the advantage that it can be expressed as a rational function of `m', `n', `i', `j', `di', and `dj', without involving any trigonometric or square root computations. When we are visiting the influence source we let by convention this factor be one. Influence is typically contributed from up to three neighbors "between" this intersection and the influence source. These values are simply added together. As pointed out before, all contributions will automatically have been made before the intersection itself is visited. When the total influence for the whole board is computed by `compute_influence()', `accumulate_influence()' is called once for each influence source. These invocations are totally independent and the influence contributions from the different sources are added together.  File: gnugo.info, Node: Permeability, Next: Escape, Prev: The Influence Algorithm, Up: Influence 13.8 Permeability ================= The permeability at the different points is initially one at all empty intersections and zero at occupied intersections. To get a useful influence function we need to modify this, however. Consider the following position: |...... |OOOO.. |...O.. |...a.X ('a' empty intersection) |...O.. |...OOO |.....O +------ The corner is of course secure territory for `O' and clearly the `X' stone has negligible effect inside this position. To stop `X' influence from leaking into the corner we use pattern matching (pattern Barrier1/Barrier2 in `barriers.db') to modify the permeability for `X' at this intersection to zero. `O' can still spread influence through this connection. Another case that needs to be mentioned is how the permeability damping is computed for diagonal influence radiation. For horizontal and vertical radiation we just use the permeability (for the relevant color) at the intersection we are radiating from. In the diagonal case we additionally multiply with the maximum permeability at the two intersections we are trying to squeeze between. The reason for this can be found in the diagram below: |...X |...X |OO.. |Oda. |..O. |.bc. |..O. |..O. +---- +---- We don't want `X' influence to be spread from `a' to `b', and since the permeability at both c and d is zero, the rule above stops this.  File: gnugo.info, Node: Escape, Next: Break Ins, Prev: Permeability, Up: Influence 13.9 Escape =========== One application of the influence code is in computing the `dragon.escape_route' field. This is computed by the function `compute_escape()' as follows. First, every intersection is assigned an escape value, ranging between 0 and 4, depending on the influence value of the opposite color. The `escape_route' field is modified by the code in `surround.c' (*note Surrounded Dragons::). It is divided by two for weakly surrounded dragons, and set to zero for surrounded ones. In addition to assiging an escape value to empty vertices, we also assign an escape value to friendly dragons. This value can range from 0 to 6 depending on the status of the dragon, with live dragons having value 6. Then we sum the values of the resulting influence escape values over the intersections (including friendly dragons) at distance 4, that is, over those intersections which can be joined to the dragon by a path of length 4 (and no shorter path) not passing adjacent to any unfriendly dragon. In the following example, we sum the influence escape value over the four vertices labelled '4'. . . . . . . . . . . . . . . . . . . . . . . . X . . O . . . . . X . . O . . X . . . . . O . . X . 2 . 4 . O X . . . . . . . . X . . 1 1 2 3 4 . X O . O . . . . O X O 1 O 1 2 3 4 O X O . O . . . . . X O 1 O 1 . 4 . . X O . . . X . O O X O 1 . . X . . O . . . X . . . . . . 1 . X . . . . . X . . . . X . . . X . . . . X . . . . . . . . . . . . . . . . . . . . . Since the dragon is trying to reach safety, the reader might wonder why `compute_influence()' is called with the opposite color of the dragon contemplating escape. To explain this point, we first remind the reader why there is a color parameter to `compute_influence()'. Consider the following example position: ...XX... OOO..OOO O......O O......O -------- Whether the bottom will become O territory depends on who is in turn to play. This is implemented with the help of patterns in barriers.db, so that X influence is allowed to leak into the bottom if X is in turn to move but not if O is. There are also "invade" patterns which add influence sources in sufficiently open parts of the board which are handled differently depending on who is in turn to move. In order to decide the territorial value of an O move in the third line gap above, influence is first computed in the original position with the opponent (i.e. X) in turn to move. Then the O stone is played to give: ...XX... OOO.OOOO O......O O......O -------- Now influence is computed once more, also this time with X in turn to move. The difference in territory (as computed from the influence values) gives the territorial value of the move. Exactly how influence is computed for use in the escape route estimation is all ad hoc. But it makes sense to assume the opponent color in turn to move so that the escape possibilities aren't overestimated. After we have made a move in the escape direction it is after all the opponent's turn. The current escape route mechanism seems good enough to be useful but is not completely reliable. Mostly it seems to err on the side of being too optimistic.  File: gnugo.info, Node: Break Ins, Next: Surrounded Dragons, Prev: Escape, Up: Influence 13.10 Break Ins =============== The code in `breakin.c' break-ins into territories that require deeper tactical reading and are thus impossible to detect for the influence module. It gets run after the influence module and revises its territory valuations. The break-in code makes use of two public functions in `readconnect.c', * int break_in(int str, const char goal[BOARDMAX], int *move) Returns WIN if `str' can connect to the area `goal[]' (which may or may not contain stones), if the string's owner gets the first move. * int block_off(int str, const char goal[BOARDMAX], int *move) Returns WIN if `str' cannot connect to the area `goal[]' (which may or may not contain stones), if the other color moves first. These functions are public front ends to their counterparts `recursive_break_in' and `recursive_block_off', which call each other recursively. The procedure is as follows: We look at all big (>= 10) territory regions as detected by the influence code. Using the computation of connection distances from readconnect.c, we compute all nearby vertices of this territory. We look for the closest safe stones belonging to the opponent. For each such string `str' we call * `break_in(str, territory)' if the opponent is assumed to be next to move, * `block_off(str, territory)' if the territory owner is next. If the break in is successful resp. the blocking unsuccessful, we shrink the territory, and see whether the opponent can still break in. We repeat this until the territory is shrunk so much that the opponent can no longer reach it. To see the break in code in action run GNU Go on the file `regression/games/break_in.sgf' with the option `-d0x102000'. Among the traces you will find: Trying to break in from D7 to: E9 (1) F9 (1) G9 (1) E8 (1) F8 (1) G8 (1) H8 (1) G7 (1) H7 (1) J7 (1) H6 (1) J6 (1) H5 (1) J5 (1) H4 (1) J4 (1) H3 (1) J3 (1) H2 (1) J2 (1) block_off D7, result 0 PASS (355, 41952 nodes, 0.73 seconds) E9 (1) F9 (1) G9 (1) E8 (1) F8 (1) G8 (1) H8 (1) G7 (1) H7 (1) J7 (1) H6 (1) J6 (1) H5 (1) J5 (1) H4 (1) J4 (1) H3 (1) J3 (1) H2 (1) J2 (1) B:F4 Erasing territory at E8 -b. Erasing territory at G3 -b. Now trying to break to smaller goal: F9 (1) G9 (1) F8 (1) G8 (1) H8 (1) G7 (1) H7 (1) J7 (1) H6 (1) J6 (1) H5 (1) J5 (1) H4 (1) J4 (1) H3 (1) J3 (1) H2 (1) J2 (1) This means that the function `break_in' is called with the goal marked 'a' in the following diagram. The code attempts to find out whether it is possible to connect into this area from the string at `D7'. A B C D E F G H J 9 . . . . a a a . . 9 8 . . . . a a a a . 8 7 . . . X O O a a a 7 6 . . . X X X O a a 6 5 . . . . + . . a a 5 4 . . . X . . O a a 4 3 . . . . X . . a a 3 2 . . . . . . O a a 2 1 . . . . . . . . . 1 A B C D E F G H J A breakin is found, so the goal is shrunk by removing `E9' and `J2', then break_in is called again. In order to see what reading is actually done in order to do this break in, you may load GNU Go in gtp mode, then issue the commands: loadsgf break_in.sgf = black start_sgftrace = break_in D7 E9 F9 G9 E8 F8 G8 H8 G7 H7 J7 H6 J6 H5 J5 H4 J4 H3 J3 H2 J2 = 1 E8 finish_sgftrace vars.sgf = start_sgftrace = break_in D7 F9 G9 F8 G8 H8 G7 H7 J7 H6 J6 H5 J5 H4 J4 H3 J3 H2 J2 = 1 G7 finish_sgftrace vars1.sgf This will produce two sgf files containing the variations caused by these calls to the breakin code. The second file, `vars1.sgf' will contain quite a few variations. The break in code makes a list of break ins which are found. When it is finished, the function `add_expand_territory_move' is called for each break in, adding a move reason. The break in code is slow, and only changes a few moves by the engine per game. Nevertheless we believe that it contributes substantially to the strength of the program. The break in code is enabled by default in GNU Go 3.6 at level 10, and disabled at level 9. In fact, this is the *only* difference between levels 9 and 10 in GNU Go 3.6.  File: gnugo.info, Node: Surrounded Dragons, Next: Influential Patterns, Prev: Break Ins, Up: Influence 13.11 Surrounded Dragons ======================== When is a dragon surrounded? As has been pointed out by Bruce Wilcox, the geometric lines connecting groups of the opposite color are often important. It is very hard to prevent the escape of this `O' dragon: .......... .....O.... .X.......X .X...O...X .......... .......... ---------- On the other hand, this dragon is in grave danger: .......... .......... .X.......X .....O.... .X.......X .X...O...X .......... .......... ---------- The difference between these two positions is that in the first, the `O' dragon crosses the line connecting the top two `X' stones. Code in `surround.c' implements a test for when a dragon is surrounded. The idea is to compute the convex hull of the _surround set_, that is, the set stones belonging to unfriendly neighbor dragons. If the dragon is contained within that hull. If it is, it is said to be _surrounded_. In practice this scheme is modified slightly. The implementation uses various algorithms to compute distances and hostile stones are discarded from the surround set when a pair other hostile ones can be found which makes the considered one useless. For example, in the following position the bottom `O' stone would get discarded. O.X.O ..... .O.O. ..... ..O.. Also, points are added to the surround set below stones on the second and third lines. This should account for the edge being a natural barrier. In order to compute distances between corners of the convex hull a sorting by angle algorithm has been implemented. If the distance between a pair enclosing stones is large, the surround status gets decreased to `WEAKLY_SURROUNDED', or even 0 for very large ones. The sorting by angle must be explained. A small diagram will probably help : .O.O. O...O ..X.. O...O .O.O. The sorting algorithm will generate this: .4.5. 3...6 ..X.. 2...7 .1.8. That is, the points are sorted by ascending order of the measure of the angle S-G-O, where S is SOUTH, G the (approximated) gravity center of the goal, and O the position of the considered hostile stones. The necessity of such sorting appears when one tries to measure distances between enclosing stones without sorting them, just by using directly the existing left and right corners arrays. In some positions, the results will be inconsistent. Imagine, for example a position where for instance the points 1,2,3,4,6 and 7 were in the left arrary, leaving only 5 and 8 in the right array. Because of the large distance between 5 and 8, the dragon would have declared weak surrounded or not surrounded at all. Such cases are rare but frequent enough to require the angle sorting. The following position: O.X.O ..... .O.O. This is "more" surrounded than the following position: O.XXXXXX.O .......... .O......O. In the second case, the surround status would be lowered to `WEAKLY_SURROUNDED'. The surround code is used to modify the escape_route field in the dragon2 data array. When a dragon is WEAKLY_SURROUNDED, the escape_route is divided by 2. If the dragon is SURROUNDED, escape_route is simply set to 0.  File: gnugo.info, Node: Influential Patterns, Next: Influential Display, Prev: Surrounded Dragons, Up: Influence 13.12 Patterns used by the Influence module =========================================== This section explains the details of the pattern databases used for the influence computation. First, we have the patterns in `influence.db', which get matched symmetrically for both colors. * `E' These patterns add extra influence sources close to some shapes like walls. This tries to reflect their extra strength. These patterns are not used in the influence computations relevant for territory valuations, but they are useful for getting a better estimate of strengths of groups. * `I' These patterns add extra influence sources at typical invasion points. Usually they are of small strength. If they additionally have the class `s', the extra influence source is added for both colors. Otherwise, only the player assumed to be next to move gets the benefit. The patterns in `barriers.db' get matched only for `O' being the player next to move. * `A' Connections between `X' stones that stop influence of `O'. They have to be tight enough that `O' cannot break through, even though he is allowed to move first. * `D' Connections between `O' stones that stop influence of `X'. The stones involved can be more loosely connected than those in `A' patterns. * `B' These indicate positions of followup moves for the `O' stone marked with `Q' in the pattern. They are used to reduce the territory e. g. where a monkey jump is possible. Also, they are used in the computation of the followup influence, if the `Q' stone was the move played (or a stone saved by the move played). * `t' These patterns indicate intersections where one color will not be able to get territory, for example in a false eye. The points are set with a call to the helper non_oterritory or non_xterritory in the action of the pattern. The intrusion patterns (`B') are more powerful than the description above might suggest. They can be very helpful in identifying weak shapes (by adding an intrusion source for the opponent where he can break through). A negative inference for this is that a single bad `B' pattern, e. g. one that has a wrong constraint, typically causes 5 to 10 `FAIL's in the regression test suite. Influence Patterns can have autohelper constraints as usual. As for the constraint attributes, there are (additionally to the usual ones `O', `o', `X' and `x'), attributes `Y' and `FY'. A pattern marked with `Y' will only be used in the influence computations relevant for the territory valuation, while `FY' patterns only get used in the other influence computations. The action of an influence pattern is at the moment only used for non-territory patterns as mentioned above, and as a workaround for a problem with `B' patterns in the followup influence. To see why this workaround is necessary, consider the follwoing situation: ..XXX .a*.O .X.O. ..XXO (Imagine that there is `X' territory on the left.) The move by `O' at `*' has a natural followup move at `a'. So, in the computation of the followup influence for `*', there would be an extra influence source for `O' at `a' which would destroy a lot of black territory on the left. This would give a big followup value, and in effect the move `*' would be treated as sente. But of course it is gote, since `X' will answer at `a', which both stops the possible intrusion and threatens to capture `*'. This situation is in fact quite common. Hence we need an additional constraint that can tell when an intrusion pattern can be used in followup influence. This is done by misusing the action line: An additional line >return ; gets added to the pattern. The `condition' should be true if the intrusion cannot be stopped in sente. In the above example, the relevant intrusion pattern will have an action line of the form >return (!xplay_attack(a,b)); where `b' refers to the stone at `*'. In fact, almost all followup-specific constraints look similar to this.  File: gnugo.info, Node: Influential Display, Next: Influence Tuning, Prev: Influential Patterns, Up: Influence 13.13 Colored display and debugging of influence ================================================ There are various ways to obtain detailed information about the influence computations. Colored diagrams showing influence are possible from a colored xterm or rxvt window. There are two options controlling when to generate diagrams: * `-m 0x08' or `-m 8' Show diagrams for the initial influence computation. This is done twice, the first time before `make_dragons()' is run and the second time after. The difference is that dead dragons are taken into account the second time. Tactically captured worms are taken into account both times. * `--debug-influence LOCATION' Show influence diagrams after the move at the given location. An important limitation of this option is that it's only effective for moves that the move generation is considering. The other options control which diagrams should be generated in these situations. You have to specify at least one of the options above and at least one of the options below to generate any output. * The options below must be combined with one of the two previous ones, or the diagram will not be printed. For example to print the influence diagram, you may combine 0x08 and 0x010, and use the option `-m 0x018'.* * `-m 0x010' or `-m 16' Show colored display of territory/moyo/area regions. - territory: cyan - moyo: yellow - area: red This feature is very useful to get an immediate impression of the influence regions as GNU Go sees them. * `-m 0x20' or `-m 32' Show numerical influence values for white and black. These come in two separate diagrams, the first one for white, the second one for black. Notice that the influence values are represented by floats and thus have been rounded in these diagrams. * `-m 0x40' or `-m 64' This generates two diagrams showing the permeability for black and white influence on the board. * `-m 0x80' or `-m 128' This shows the strength of the influence sources for black and white across the board. You will see sources at each lively stone (with strength depending on the strength of this stone), and sources contributed by patterns. * `-m 0x100' or `-m 256' This shows the attenuation with which the influence sources spread influence across the board. Low attenuation indicates far-reaching influence sources. * `-m 0x200' or `-m 512' This shows the territory valuation of GNU Go. Each intersection is shown with a value between -1.0 and +1.0 (or -2 resp. +2 if there is a dead stone on this intersection). Positive values indicate territory for white. A value of -0.5 thus indicates a point where black has a 50% chance of getting territory. Finally, there is the debug option `-d 0x1' which turns on on `DEBUG_INFLUENCE'. This gives a message for each influence pattern that gets matched. Unfortunately, these are way too many messages making it tedious to navigate the output. However, if you discover an influence source with `-m 0x80' that looks wrong, the debug output can help you to quickly find out the responsible pattern.  File: gnugo.info, Node: Influence Tuning, Prev: Influential Display, Up: Influence 13.14 Influence Tuning with `view.pike' ======================================= A useful program in the regression directory is `view.pike'. To run it, you need Pike, which you may download from `http://pike.ida.liu.se/'. The test case `endgame:920' fails in GNU Go 3.6. We will explain how to fix it. Start by firing up view.pike on testcase endgame:920, e.g. by running `pike view.pike endgame:920' in the regression directory. We see from the first view of move values that filling dame at P15 is valued highest with 0.17 points while the correct move at C4 is valued slightly lower with 0.16. The real problem is of course that C4 is worth a full point and thus should be valued about 1.0. Now click on C4 to get a list of move reasons and move valuation information. Everything looks okay except that change in territory is 0.00 rather than 1.00 as it ought to be. We can confirm this by choosing the "delta territory for..." button and again clicking C4. Now B5 should have been marked as one point of change in territory, but it's not. Next step is to enter the influence debug tool. Press the "influence" button, followed by "black influence, dragons known," and "territory value." This shows the expected territory if black locally moves first everywhere (thus "black influence"). Here we can see that B5 is incorrectly considered as 1.0 points of white territory. We can compare this with the territory after a white move at C4 (still assuming that black locally moves first everywhere after that) by pressing "after move influence for..." and clicking C4. This looks identical, as expected since delta territory was 0, but here it is correct that B5 is 1.0 points of territory for white. The most straightforward solution to this problem is to add a non-territory pattern, saying that white can't get territory on B5 if black moves first. The nonterritory patterns are in `barriers.db'. Pattern Nonterritory56 ... X.O ?O. :8,t eac XbO ?Od ;oplay_attack(a,b,c,d,d) >non_xterritory(e); In these patterns it's always assumed that `O' moves first and thus it says that `X' can't get territory at `B5' (`e' in the pattern). Now we need to be a bit careful however since after `O' plays at `a' and `X' cuts in at `b', it may well happen that `O' needs to defend around `d', allowing `X' to cut at `c', possibly making the nonterritory assumption invalid. It's difficult to do this entirely accurate, but the constraint above is fairly conservative and should guarantee that `a' is safe in most, although not all, cases.  File: gnugo.info, Node: Monte Carlo Go, Next: Libboard, Prev: Influence, Up: Top 14 Monte Carlo Go ***************** In Monte Carlo Go the engine plays random games to the end, generating moves from a pattern database within the context of the algorithm UCT (upper confidence bounds applied to trees). This algorithm allowed the program MoGo (`http://www.lri.fr/~gelly/MoGo.htm', to become the first computer program to defeat a professional while taking a 9 stone handicap (`http://senseis.xmp.net/?MoGo'). GNU Go 3.8 can play 9x9 Go with the option `--monte-carlo' using the UCT algorithm. For command line options, see *Note Invoking GNU Go::. During reading, the engine makes incremental updates of local 3x3 neighborhood, suicide status, self-atari status, and number of stones captured, for each move. GNU Go's simulations (Monte Carlo games) are pattern generated. The random playout move generation is distributed strictly proportional to move values computed by table lookup from a local context consisting of 3x3 neighborhood, opponent suicide status, own and opponent self-atari status, number of stones captured by own and opponent move, and closeness to the previous move. Let's call this local context simply "a pattern" and the table "pattern values" or simply "patterns". There are three built-in databases that you can select using the option `--mc-patterns ', where `' is one of * `mc_montegnu_classic' * `mc_mogo_classic' * `mc_uniform' The first of these is an approximation of the previous random move generation algorithm. The `mogo_classic' pattern values is an approximation of the simulation policy used by early versions of MoGo, as published in the report odification of UCT with Patterns in Monte-Carlo Go (http://hal.inria.fr/inria-00117266) RR-6062, by Sylvain Gelly, Yizao Wang, Rémi Munos, and Olivier Teytaud. The uniform pattern values is the so called "light" playout which chooses uniformly between all legal moves except single point proper eyes. If you're not satisfied with these you can also tune your own pattern values with a pattern database file and load it at runtime with `--mc-load-patterns ' adding your own pattern database. Let's start with the uniform pattern values. Those are defined by the file `patterns/mc_uniform.db', which looks like this: oOo O*O oO? :0 oOo O*O --- :0 |Oo |*O +-- :0 Patterns are always exactly 3x3 in size with the move at the center point. The symbols are the usual for GNU Go pattern databases: * move O own stone (i.e. the same color as the color to move) o own stone or empty X opponent stone x opponent stone or empty ? own stone, opponent stone, or empty | vertical edge - horizontal edge + corner There's also a new symbol: % own stone, opponent stone, empty, or edge After the pattern comes a line starting with a colon. In all these patterns it says that the pattern has a move value of 0, i.e. must not be played. Unmatched patterns have a default value of 1. When all move values are zero for both players, the playout will stop. Including the three patterns above is important because otherwise the playouts would be likely to go on indefinitely, or as it actually happens be terminated at a hard-coded limit of 600 moves. Also place these patterns at the top of the database because when multiple patterns match, the first one is used, regardless of the values. When using only these patterns you will probably notice that it plays rather heavy, trying hard to be solidly connected. This is because uniform playouts are badly biased with a high probability of non-solid connections being cut apart. To counter this you could try a pattern like ?X? O*O x.? :20,near to increase the probability that the one-point jump is reinforced when threatened. Here we added the property "near", which means that the pattern only applies if the previous move was played "near" this move. Primarily "near" means within the surrounding 3x3 neighborhood but it also includes certain cases of liberties of low-liberty strings adjacent to the previous move, e.g. the move to extend out of an atari created by the previous move. You have to read the source to find out the exact rules for nearness. We could also be even more specific and say ?X? O*O x.? :20,near,osafe,xsafe to exclude the cases where this move is a self atari (osafe) or would be a self-atari for the opponent (xsafe). It may also be interesting to see the effect of capturing stones. A catch-all pattern for captures would be ?X% ?*% %%% :10,ocap1,osafe :20,ocap2 :30,ocap3 where we have used multiple colon lines to specify different move values depending on the number of captured stones; value 10 for a single captured stone, value 20 for two captured stones, and value 30 for three or more captured stones. Here we also excluded self-atari moves in the case of 1 captured stone in order to avoid getting stuck in triple-ko in the playouts (there's no superko detection in the playouts). The full set of pattern properties is as follows: `near' The move is "near" the previous move. `far' The move is not "near" the previous move. `osafe' The move is not a self-atari. `ounsafe' The move is a self-atari. `xsafe' The move would not be a self-atari for the opponent. `xunsafe' The move would be a self-atari for the opponent. `xsuicide' The move would be suicide for the opponent `xnosuicide' The move would not be suicide for the opponent. `ocap0' The move captures zero stones. `ocap1' The move captures one stone. `ocap2' The move captures two stones. `ocap3' The move captures three or more stones. `ocap1+' The move captures one or more stones. `ocap1-' The move captures at most one stone. `ocap2+' The move captures two or more stones. `ocap2-' The move captures at most two stones. `xcap0' An opponent move would capture zero stones. `xcap1' An opponent move would capture one stone. `xcap2' An opponent move would capture two stones. `xcap3' An opponent move would capture three or more stones. `xcap1+' An opponent move would capture one or more stones. `xcap1-' An opponent move would capture at most one stone. `xcap2+' An opponent move would capture two or more stones. `xcap2-' An opponent move would capture at most two stones. These can be combined arbitrarily but all must be satisfied for the pattern to take effect. If contradictory properties are combined, the pattern will never match. 14.0.1 Final Remarks -------------------- * Move values are unsigned 32-bit integers. To avoid overflow in computations it is highly recommended to keep the values below 10000000 or so. * There is no speed penalty for having lots of patterns in the database. The average time per move is approximately constant (slightly dependent on how often stones are captured or become low on liberties) and the time per game mostly depends on the average game length. * For more complex pattern databases, see `patterns/mc_montegnu_classic.db' and `patterns/mc_mogo_classic.db'. Nobody really knows how to tune the random playouts to get as strong engine as possible. Please play with this and report any interesting findings, especially if you're able to make it substantially stronger than the `montegnu_classic' patterns.  File: gnugo.info, Node: Libboard, Next: SGF, Prev: Monte Carlo Go, Up: Top 15 The Board Library ******************** * Menu: * Board Data Structures:: Board Data Structures * The Board Array:: One-dimensional board array * Incremental Board:: Incremental board data structures * Some Board Functions:: Explanation of some board functions The foundation of the GNU Go engine is a library of very efficient routines for handling go boards. This board library, called `libboard', can be used for those programs that only need a basic go board but no AI capability. One such program is `patterns/joseki.c', which compiles joseki pattern databases from SGF files. If you want to use the board library in your own program, you need all the .c-files listed under libboard_SOURCES in engine/Makefile.am, and the files in the directories sgf/ and utils/. Then you should include engine/board.h in your code. The library consists of the following files: * `board.h' The public interface to the board library. * `board.c' The basic board code. It uses incremental algorithms for keeping track of strings and liberties on the go board. * `boardlib.c' This contains all global variable of the board library. * `hash.c' Code for hashing go positions. * `sgffile.c' Implementation of output file in SGF format. * `printutils.c' Utilities for printing go boards and other things. To use the board library, you must include `liberty.h' just like when you use the whole engine, but of course you cannot use all the functions declared in it, i.e. the functions that are part of the engine, but not part of the board library. You must link your application with `libboard.a'.  File: gnugo.info, Node: Board Data Structures, Next: The Board Array, Up: Libboard 15.1 Board Data structures ========================== The basic data structures of the board correspond tightly to the `board_state' struct described in *Note The Board State::. They are all stored in global variables for efficiency reasons, the most important of which are: int board_size; Intersection board[MAXSIZE]; int board_ko_pos; float komi; int white_captured; int black_captured; Hash_data hashdata; The description of the `Position' struct is applicable to these variables also, so we won't duplicate it here. All these variables are globals for performance reasons. Behind these variables, there are a number of other private data structures. These implement incremental handling of strings, liberties and other properties (*note Incremental Board::). The variable `hashdata' contains information about the hash value for the current position (*note Hashing::). These variables should never be manipulated directly, since they are only the front end for the incremental machinery. They can be read, but should only be written by using the functions described in the next section. If you write directly to them, the incremental data structures will become out of sync with each other, and a crash is the likely result.  File: gnugo.info, Node: The Board Array, Next: Incremental Board, Prev: Board Data Structures, Up: Libboard 15.2 The Board Array ==================== GNU Go represents the board in a one-dimensional array called `board'. For some purposes a two dimensional indexing of the board by parameters `(i,j)' might be used. The `board' array includes out-of-board markers around the board. To make the relation to the old two-dimensional board representation clear, this figure shows how the 1D indices correspond to the 2D indices when MAX_BOARD is 7. j -1 0 1 2 3 4 5 6 i +---------------------------------- -1| 0 1 2 3 4 5 6 7 0| 8 9 10 11 12 13 14 15 1| 16 17 18 19 20 21 22 23 2| 24 25 26 27 28 29 30 31 3| 32 33 34 35 36 37 38 39 4| 40 41 42 43 44 45 46 47 5| 48 49 50 51 52 53 54 55 6| 56 57 58 59 60 61 62 63 7| 64 65 66 67 68 69 70 71 72 To convert between a 1D index `pos' and a 2D index `(i,j)', the macros `POS', `I', and `J' are provided, defined as below: #define POS(i, j) ((MAX_BOARD + 2) + (i) * (MAX_BOARD + 1) + (j)) #define I(pos) ((pos) / (MAX_BOARD + 1) - 1) #define J(pos) ((pos) % (MAX_BOARD + 1) - 1) All 1D indices not corresponding to points on the board have the out of board marker value `GRAY'. Thus if `board_size' and `MAX_BOARD' both are 7, this looks like j -1 0 1 2 3 4 5 6 i +---------------------------------- -1| # # # # # # # # 0| # . . . . . . . 1| # . . . . . . . 2| # . . . . . . . 3| # . . . . . . . 4| # . . . . . . . 5| # . . . . . . . 6| # . . . . . . . 7| # # # # # # # # # The indices marked `#' have value `GRAY'. If `MAX_BOARD' is 7 and `board_size' is only 5: j -1 0 1 2 3 4 5 6 i +---------------------------------- -1| # # # # # # # # 0| # . . . . . # # 1| # . . . . . # # 2| # . . . . . # # 3| # . . . . . # # 4| # . . . . . # # 5| # # # # # # # # 6| # # # # # # # # 7| # # # # # # # # # Navigation on the board is done by the `SOUTH', `WEST', `NORTH', and `EAST' macros, #define NS (MAX_BOARD + 1) #define WE 1 #define SOUTH(pos) ((pos) + NS) #define WEST(pos) ((pos) - 1) #define NORTH(pos) ((pos) - NS) #define EAST(pos) ((pos) + 1) There are also shorthand macros `SW', `NW', `NE', `SE', `SS', `WW', `NN', `EE' for two step movements. Any movement from a point on the board to an adjacent or diagonal vertex is guaranteed to produce a valid index into the board array, and the color found is GRAY if it is not on the board. To do explicit tests for out of board there are two macros #define ON_BOARD(pos) (board[pos] != GRAY) #define ON_BOARD1(pos) (((unsigned) (pos) < BOARDSIZE) && board[pos] != GRAY) where the first one should be used in the algorithms and the second one is useful for assertion tests. The advantage of a one-dimensional board array is that it gives a significant performance advantage. We need only one variable to determine a board position, which means that many functions need less arguments. Also, often one computation is sufficient for 1D-coordinate where we would need two with two 2D-coordinates: If we, for example, want to have the coordinate of the upper right of `pos', we can do this with `NORTH(EAST(pos))' instead of `(i+1, j-1)'. *Important*: The 2D coordinate `(-1,-1)', which is used for pass and sometimes to indicate no point, maps to the 1D coordinate `0', not to `-1'. Instead of a plain `0', use one of the macros `NO_MOVE' or `PASS_MOVE'. A loop over multiple directions is straightforwardly written: for (k = 0; k < 4; k++) { int d = delta[k]; do_something(pos + d); } The following constants are useful for loops over the entire board and allocation of arrays with a 1-1 mapping to the board. #define BOARDSIZE ((MAX_BOARD + 2) * (MAX_BOARD + 1) + 1) #define BOARDMIN (MAX_BOARD + 2) #define BOARDMAX (MAX_BOARD + 1) * (MAX_BOARD + 1) `BOARDSIZE' is the actual size of the 1D board array, `BOARDMIN' is the first index corresponding to a point on the board, and `BOARDMAX' is one larger than the last index corresponding to a point on the board. Often one wants to traverse the board, carrying out some function at every vertex. Here are two possible ways of doing this: int m, n; for (m = 0; m < board_size; m++) for (n = 0; n < board_size; n++) { do_something(POS(m, n)); } Or: int pos; for (pos = BOARDMIN; pos < BOARDMAX; pos++) { if (ON_BOARD(pos)) do_something(pos); }  File: gnugo.info, Node: Incremental Board, Next: Some Board Functions, Prev: The Board Array, Up: Libboard 15.3 Incremental Board data structures ====================================== In addition to the global board state, the algorithms in `board.c' implement a method of incremental updates that keeps track of the following information for each string: * The color of the string. * Number of stones in the string. * Origin of the string, i.e. a canonical reference point, defined to be the stone with smallest 1D board coordinate. * A list of the stones in the string. * Number of liberties. * A list of the liberties. If there are too many liberties the list is truncated. * The number of neighbor strings. * A list of the neighbor strings. The basic data structure is struct string_data { int color; /* Color of string, BLACK or WHITE */ int size; /* Number of stones in string. */ int origin; /* Coordinates of "origin", i.e. */ /* "upper left" stone. */ int liberties; /* Number of liberties. */ int libs[MAX_LIBERTIES]; /* Coordinates of liberties. */ int neighbors; /* Number of neighbor strings */ int neighborlist[MAXCHAIN]; /* List of neighbor string numbers. */ int mark; /* General purpose mark. */ }; struct string_data string[MAX_STRINGS]; It should be clear that almost all information is stored in the `string' array. To get a mapping from the board coordinates to the `string' array we have static int string_number[BOARDMAX]; which contains indices into the `string' array. This information is only valid at nonempty vertices, however, so it is necessary to first verify that `board[pos] != EMPTY'. The `string_data' structure does not include an array of the stone coordinates. This information is stored in a separate array: static int next_stone[BOARDMAX]; This array implements cyclic linked lists of stones. Each vertex contains a pointer to another (possibly the same) vertex. Starting at an arbitrary stone on the board, following these pointers should traverse the entire string in an arbitrary order before coming back to the starting point. As for the 'string_number' array, this information is invalid at empty points on the board. This data structure has the good properties of requiring fixed space (regardless of the number of strings) and making it easy to add a new stone or join two strings. Additionally the code makes use of some work variables: static int ml[BOARDMAX]; static int liberty_mark; static int string_mark; static int next_string; static int strings_initialized = 0; The `ml' array and `liberty_mark' are used to "mark" liberties on the board, e.g. to avoid counting the same liberty twice. The convention is that if `ml[pos]' has the same value as `liberty_mark', then `pos' is marked. To clear all marks it suffices to increase the value of `liberty_mark', since it is never allowed to decrease. The same relation holds between the `mark' field of the `string_data' structure and `string_mark'. Of course these are used for marking individual strings. `next_string' gives the number of the next available entry in the `string' array. Then `strings_initialized' is set to one when all data structures are known to be up to date. Given an arbitrary board position in the `board' array, this is done by calling `incremental_board_init()'. It is not necessary to call this function explicitly since any other function that needs the information does this if it has not been done. The interesting part of the code is the incremental update of the data structures when a stone is played and subsequently removed. To understand the strategies involved in adding a stone it is necessary to first know how undoing a move works. The idea is that as soon as some piece of information is about to be changed, the old value is pushed onto a stack which stores the value and its address. The stack is built from the following structures: struct change_stack_entry { int *address; int value; }; struct change_stack_entry change_stack[STACK_SIZE]; int change_stack_index; and manipulated with the macros BEGIN_CHANGE_RECORD() PUSH_VALUE(v) POP_MOVE() Calling `BEGIN_CHANGE_RECORD()' stores a null pointer in the address field to indicate the start of changes for a new move. As mentioned earlier `PUSH_VALUE()' stores a value and its corresponding address. Assuming that all changed information has been duly pushed onto the stack, undoing the move is only a matter of calling `POP_MOVE()', which simply assigns the values to the addresses in the reverse order until the null pointer is reached. This description is slightly simplified because this stack can only store 'int' values and we need to also store changes to the board. Thus we have two parallel stacks where one stores `int' values and the other one stores `Intersection' values. When a new stone is played on the board, first captured opponent strings, if any, are removed. In this step we have to push the board values and the `next_stone' pointers for the removed stones, and update the liberties and neighbor lists for the neighbors of the removed strings. We do not have to push all information in the 'string' entries of the removed strings however. As we do not reuse the entries they will remain intact until the move is pushed and they are back in use. After this we put down the new stone and get three distinct cases: 1. The new stone is isolated, i.e. it has no friendly neighbor. 2. The new stone has exactly one friendly neighbor. 3. The new stone has at least two friendly neighbors. The first case is easiest. Then we create a new string by using the number given by `next_string' and increasing this variable. The string will have size one, `next_stone' points directly back on itself, the liberties can be found by looking for empty points in the four directions, possible neighbor strings are found in the same way, and those need also to remove one liberty and add one neighbor. In the second case we do not create a new string but extend the neighbor with the new stone. This involves linking the new stone into the cyclic chain, if needed moving the origin, and updating liberties and neighbors. Liberty and neighbor information also needs updating for the neighbors of the new stone. In the third case finally, we need to join already existing strings. In order not to have to store excessive amounts of information, we create a new string for the new stone and let it assimilate the neighbor strings. Thus all information about those can simply be left around in the 'string' array, exactly as for removed strings. Here it becomes a little more complex to keep track of liberties and neighbors since those may have been shared by more than one of the joined strings. Making good use of marks it all becomes rather straightforward anyway. The often used construction pos = FIRST_STONE(s); do { ... pos = NEXT_STONE(pos); } while (!BACK_TO_FIRST_STONE(s, pos)); traverses the stones of the string with number `s' exactly once, with `pos' holding the coordinates. In general `pos' is used as board coordinate and `s' as an index into the `string' array or sometimes a pointer to an entry in the `string' array.  File: gnugo.info, Node: Some Board Functions, Prev: Incremental Board, Up: Libboard 15.4 Some Board Functions ========================= *Reading*, often called *search* in computer game theory, is a fundamental process in GNU Go. This is the process of generating hypothetical future boards in order to determine the answer to some question, for example "can these stones live." Since these are hypothetical future positions, it is important to be able to undo them, ultimately returning to the present board. Thus a move stack is maintained during reading. When a move is tried, by the function `trymove', or its variant `tryko'. This function pushes the current board on the stack and plays a move. The stack pointer `stackp', which keeps track of the position, is incremented. The function `popgo()' pops the move stack, decrementing `stackp' and undoing the last move made. Every successful `trymove()' must be matched with a `popgo()'. Thus the correct way of using this function is: if (trymove(pos, color, ... )) { ... [potentially lots of code here] popgo(); } In case the move is a ko capture, the legality of the capture is subject to the komaster scheme (*note Ko::). * `int trymove(int pos, int color, const char *message)' Returns true if `(pos)' is a legal move for `color'. In that case, it pushes the board on the stack and makes the move, incrementing `stackp'. If the reading code is recording reading variations (as with `--decide-string' or with `-o'), the string `*message' will be inserted in the SGF file as a comment. The comment will also refer to the string at `str' if this is not `0'. The value of `str' can be NO_MOVE if it is not needed but otherwise the location of `str' is included in the comment. * `int tryko(int pos, int color, const char *message)' `tryko()' pushes the position onto the stack, and makes a move `pos' of `color'. The move is allowed even if it is an illegal ko capture. It is to be imagined that `color' has made an intervening ko threat which was answered and now the continuation is to be explored. Return 1 if the move is legal with the above caveat. Returns zero if it is not legal because of suicide. * `void popgo()' Pops the move stack. This function must (eventually) be called after a succesful `trymove' or `tryko' to restore the board position. It undoes all the changes done by the call to `trymove/tryko' and leaves the board in the same state as it was before the call. *NOTE*: If `trymove/tryko' returns `0', i.e. the tried move was not legal, you must *not* call `popgo'. * `int komaster_trymove(int pos, int color, const char *message, int str, int *is_conditional_ko, int consider_conditional_ko)' Variation of `trymove'/`tryko' where ko captures (both conditional and unconditional) must follow a komaster scheme (*note Ko::). As you see, `trymove()' plays a move which can be easily retracted (with `popgo()') and it is call thousands of times per actual game move as GNU Go analyzes the board position. By contrast the function `play_move()' plays a move which is intended to be permanent, though it is still possible to undo it if, for example, the opponent retracts a move. * `void play_move(int pos, int color)' Play a move. If you want to test for legality you should first call `is_legal()'. This function strictly follows the algorithm: 1. Place a stone of given color on the board. 2. If there are any adjacent opponent strings without liberties, remove them and increase the prisoner count. 3. If the newly placed stone is part of a string without liberties, remove it and increase the prisoner count. In spite of the name "permanent move", this move can (usually) be unplayed by `undo_move()', but it is significantly more costly than unplaying a temporary move. There are limitations on the available move history, so under certain circumstances the move may not be possible to unplay at a later time. * `int undo_move(int n)' Undo `n' permanent moves. Returns 1 if successful and 0 if it fails. If `n' moves cannot be undone, no move is undone. Other board functions are documented in *Note Board Utilities::.  File: gnugo.info, Node: SGF, Next: DFA, Prev: Libboard, Up: Top 16 Handling SGF trees in memory ******************************* "SGF" - Smart Game Format - is a file format which is used for storing game records for a number of different games, among them chess and go. The format is a framework with special adaptions to each game. This is not a description of the file format standard. Too see the exact definition of the file format, see `http://www.red-bean.com/sgf/'. GNU Go contains a library to handle go game records in the SGF format in memory and to read and write SGF files. This library - `libsgf.a' - is in the `sgf' subdirectory. To use the SGF routines, include the file `sgftree.h'. Each game record is stored as a tree of "nodes", where each node represents a state of the game, often after some move is made. Each node contains zero or more "properties", which gives meaning to the node. There can also be a number of "child nodes" which are different variations of the game tree. The first child node is the main variation. Here is the definition of `SGFNode', and `SGFProperty', the data structures which are used to encode the game tree. typedef struct SGFProperty_t { struct SGFProperty_t *next; short name; char value[1]; } SGFProperty; typedef struct SGFNode_t { SGFProperty *props; struct SGFNode_t *parent; struct SGFNode_t *child; struct SGFNode_t *next; } SGFNode; Each node of the SGF tree is stored in an `SGFNode' struct. It has a pointer to a linked list of properties (see below) called `props'. It also has a pointer to a linked list of children, where each child is a variation which starts at this node. The variations are linked through the `next' pointer and each variation continues through the `child' pointer. Each and every node also has a pointer to its parent node (the `parent' field), except the top node whose parent pointer is `NULL'. An SGF property is encoded in the `SGFPoperty' struct. It is linked in a list through the `next' field. A property has a `name' which is encoded in a short int. Symbolic names of properties can be found in `sgf_properties.h'. Some properties also have a value, which could be an integer, a floating point value, a character or a string. These values can be accessed or set through special functions. 16.1 The SGFTree datatype ========================= Sometimes we just want to record an ongoing game or something similarly simple and not do any sofisticated tree manipulation. In that case we can use the simplified interface provided by `SGFTree' below. typedef struct SGFTree_t { SGFNode *root; SGFNode *lastnode; } SGFTree; An `SGFTree' contains a pointer to the root node of an SGF tree and a pointer to the node that we last accessed. Most of the time this will be the last move of an ongoing game. Most of the functions which manipulate an `SGFTree' work exactly like their `SGFNode' counterparts, except that they work on the current node of the tree. All the functions below that take arguments `tree' and `node' will work on: 1. `node' if non-`NULL' 2. `tree->lastnode' if non-`NULL' 3. The current end of the game tree. in that order.  File: gnugo.info, Node: API, Next: GTP, Prev: Utility Functions, Up: Top 17 Application Programmers Interface to GNU Go ********************************************** If you want to write your own interface to GNU Go, or if you want to create a go application using the GNU Go engine, this chapter is of interest to you. First an overview: GNU Go consists of two parts: the GNU Go engine and a program (user interface) which uses this engine. These are linked together into one binary. The current program implements the following user modes: * An interactive board playable on ASCII terminals * solo play - GNU Go plays against itself * replay - a mode which lets the user investigate moves in an existing SGF file. * GMP - Go Modem Protocol, a protocol for automatic play between two computers. * GTP - Go Text Protocol, a more general go protocol, *note GTP::. The GNU Go engine can be used in other applications. For example, supplied with GNU Go is another program using the engine, called `debugboard', in the directory `interface/debugboard/'. The program debugboard lets the user load SGF files and can then interactively look at different properties of the position such as group status and eye status. The purpose of this Chapter is to show how to interface your own program such as `debugboard' with the GNU Go engine. Figure 1 describes the structure of a program using the GNU Go engine. +-----------------------------------+ | | | Go application | | | +-----+----------+------+ | | | | | | | | Game | | | | | handling | | | | | | | | | +----+-----+ | | | SGF | Move | | | handling | generation | | | | | | +----------+------------+-----------+ | | | Board handling | | | +-----------------------------------+ Figure 1: The structure of a program using the GNU Go engine The foundation is a library called `libboard.a' which provides efficient handling of a go board with rule checks for moves, with incremental handling of connected strings of stones and with methods to efficiently hash go positions. On top of this, there is a library which helps the application use Smart Game Format (SGF) files, with complete handling of game trees in memory and in files. This library is called `libsgf.a' The main part of the code within GNU Go is the move generation library which given a position generates a move. This part of the engine can also be used to manipulate a go position, add or remove stones, do tactical and strategic reading and to query the engine for legal moves. These functions are collected into `libengine.a'. The game handling code helps the application programmer keep tracks of the moves in a game. Games can be saved to SGF files and then later be read back again. These are also within `libengine.a'. The responsibility of the application is to provide the user with a user interface, graphical or not, and let the user interact with the engine. * Menu: * Getting Started:: How to use the engine in your program * Basic Data Structures:: Basic Data Structures in the Engine * The Board State:: The board_state `struct' * Positional Functions:: Functions which manipulate a Position  File: gnugo.info, Node: Getting Started, Next: Basic Data Structures, Up: API 17.1 How to use the engine in your own program: getting started =============================================================== To use the GNU Go engine in your own program you must include the file `gnugo.h'. This file describes the whole public API. There is another file, `liberty.h', which describes the internal interface within the engine. If you want to make a new module within the engine, e.g. for suggesting moves you will have to include this file also. In this section we will only describe the public interface. Before you do anything else, you have to call the function `init_gnugo()'. This function initializes everything within the engine. It takes one parameter: the number of megabytes the engine can use for the internal hash table. In addition to this the engine will use a few megabytes for other purposes such as data describing groups (liberties, life status, etc), eyes and so on.  File: gnugo.info, Node: Basic Data Structures, Next: The Board State, Prev: Getting Started, Up: API 17.2 Basic Data Structures in the Engine ======================================== There are some basic definitions in gnugo.h which are used everywhere. The most important of these are the numeric declarations of colors. Each intersection on the board is represented by one of these: color value EMPTY 0 WHITE 1 BLACK 2 There is a macro, `OTHER_COLOR(color)' which can be used to get the other color than the parameter. This macro can only be used on `WHITE' or `BLACK', but not on `EMPTY'. GNU Go uses two different representations of the board, for most purposes a one-dimensional one, but for a few purposes a two dimensional one (*note Libboard::). The one-dimensional board was introduced before GNU Go 3.2, while the two-dimensional board dates back to the ancestral program written by Man Lung Li before 1995. The API still uses the two-dimensional board, so the API functions have not changed much since GNU Go 3.0.  File: gnugo.info, Node: The Board State, Next: Positional Functions, Prev: Basic Data Structures, Up: API 17.3 The board_state struct =========================== A basic data structure in the engine is the `board_state' struct. This structure is internal to the engine and is defined in `liberty.h'. typedef unsigned char Intersection; struct board_state { int board_size; Intersection board[BOARDSIZE]; int board_ko_pos; int black_captured; int white_captured; Intersection initial_board[BOARDSIZE]; int initial_board_ko_pos; int initial_white_captured; int initial_black_captured; int move_history_color[MAX_MOVE_HISTORY]; int move_history_pos[MAX_MOVE_HISTORY]; int move_history_pointer; float komi; int move_number; }; Here `Intersection' stores `EMPTY', `WHITE' or `BLACK'. It is currently defined as an `unsigned char' to make it reasonably efficient in both storage and access time. The board state contains an array of `Intersection''s representing the board. The move history is contained in the struct. Also contained in the struct is the location of a ko (`EMPTY') if the last move was not a ko capture, the komi, the number of captures, and corresponding data for the initial position at the beginning of the move history.  File: gnugo.info, Node: Positional Functions, Prev: The Board State, Up: API 17.4 Functions which manipulate a Position ========================================== All the functions in the engine that manipulate Positions have names prefixed by `gnugo_'. These functions still use the two-dimensional representation of the board (*note The Board Array::). Here is a complete list, as prototyped in `gnugo.h': * `void init_gnugo(float memory)' Initialize the gnugo engine. This needs to be called once only. * `void gnugo_clear_board(int boardsize)' Clear the board. * `void gnugo_set_komi(float new_komi)' Set the komi. * `void gnugo_add_stone(int i, int j, int color)' Place a stone on the board * `void gnugo_remove_stone(int i, int j)' Remove a stone from the board * `int gnugo_is_pass(int i, int j)' Return true if (i,j) is PASS_MOVE * `void gnugo_play_move(int i, int j, int color)' Play a move and start the clock * `int gnugo_undo_move(int n)' Undo n permanent moves. Returns 1 if successful and 0 if it fails. If n moves cannot be undone, no move is undone. * `int gnugo_play_sgfnode(SGFNode *node, int to_move)' Perform the moves and place the stones from the SGF node on the board. Return the color of the player whose turn it is to move. * `int gnugo_play_sgftree(SGFNode *root, int *until, SGFNode **curnode)' Play the moves in ROOT UNTIL movenumber is reached. Return the color of the player whose turn it is to move. * `int gnugo_is_legal(int i, int j, int color)' Interface to `is_legal()'. * `int gnugo_is_suicide(int i, int j, int color)' Interface to `is_suicide()'. * `int gnugo_placehand(int handicap)' Interface to placehand. Sets up handicap pieces and returns the number of placed handicap stones. * `void gnugo_recordboard(SGFNode *root)' Interface to `sgffile_recordboard()' * `int gnugo_sethand(int handicap, SGFNode *node)' Interface to placehand. Sets up handicap stones and returns the number of placed handicap stones, updating the sgf file * `float gnugo_genmove(int *i, int *j, int color, int *resign)' Interface to `genmove()'. * `int gnugo_attack(int m, int n, int *i, int *j)' Interface to `attack()'. * `int gnugo_find_defense(int m, int n, int *i, int *j)' Interface to `find_defense()'. * `void gnugo_who_wins(int color, FILE *outfile)' Interface to `who_wins()'. * `float gnugo_estimate_score(float *upper, float *lower)' Put upper and lower score estimates into `*upper', `*lower' and return the average. A positive score favors white. In computing the upper bound, `CRITICAL' dragons are awarded to white; in computing the lower bound, they are awarded to black. * `void gnugo_examine_position(int color, int how_much)' Interface to `examine_position'. * `int gnugo_get_komi()' Report the komi. * `void gnugo_get_board(int b[MAX_BOARD][MAX_BOARD])' Place the board into the `b' array. * `int gnugo_get_boardsize()' Report the board size. * `int gnugo_get_move_number()' Report the move number. 17.5 Game handling ================== The functions (in *note Positional Functions::) are all that are needed to create a fully functional go program. But to make the life easier for the programmer, there is a small set of functions specially designed for handling ongoing games. The data structure describing an ongoing game is the `Gameinfo'. It is defined as follows: typedef struct { int handicap; int to_move; /* whose move it currently is */ SGFTree game_record; /* Game record in sgf format. */ int computer_player; /* BLACK, WHITE, or EMPTY (used as BOTH) */ char outfilename[128]; /* Trickle file */ FILE *outfile; } Gameinfo; The meaning of `handicap' should be obvious. `to_move' is the color of the side whose turn it is to move. The SGF tree `game_record' is used to store all the moves in the entire game, including a header node which contains, among other things, komi and handicap. If one or both of the opponents is the computer, the field `computer_player' is used. Otherwise it can be ignored. GNU Go can use a trickle file to continuously save all the moves of an ongoing game. This file can also contain information about internal state of the engine such as move reasons for various locations or move valuations. The name of this file should be stored in `outfilename' and the file pointer to the open file is stored in `outfile'. If no trickle file is used, `outfilename[0]' will contain a null character and `outfile' will be set to `NULL'. 17.5.1 Functions which manipulate a Gameinfo -------------------------------------------- All the functions in the engine that manipulate Gameinfos have names prefixed by `gameinfo_'. Here is a complete list, as prototyped in `gnugo.h': * `void gameinfo_clear(Gameinfo *ginfo, int boardsize, float komi)' Initialize the `Gameinfo' structure. * `void gameinfo_print(Gameinfo *ginfo)' Print a gameinfo. * `void gameinfo_load_sgfheader(Gameinfo *gameinfo, SGFNode *head)' Reads header info from sgf structure and sets the appropriate variables. * `void gameinfo_play_move(Gameinfo *ginfo, int i, int j, int color)' Make a move in the game. Return 1 if the move was legal. In that case the move is actually done. Otherwise return 0. * `int gameinfo_play_sgftree_rot(Gameinfo *gameinfo, SGFNode *head, const char *untilstr, int orientation)' Play the moves in an SGF tree. Walk the main variation, actioning the properties into the playing board. Returns the color of the next move to be made. Head is an sgf tree. Untilstr is an optional string of the form either 'L12' or '120' which tells it to stop playing at that move or move number. When debugging, this is the location of the move being examined. * `int gameinfo_play_sgftree(Gameinfo *gameinfo, SGFNode *head, const char *untilstr)' Same as previous function, using standard orientation.  File: gnugo.info, Node: Utility Functions, Next: API, Prev: DFA, Up: Top 18 Utility Functions ******************** In this Chapter, we document some of the utilities which may be called from the GNU Go engine. * Menu: * General Utilities:: Utilities from `engine/utils.c' * Print Utilities:: Utilities from `engine/printutils.c' * Board Utilities:: Utilities from `engine/board.c' * Influence Utilities:: Utilities from `engine/influence.c'  File: gnugo.info, Node: General Utilities, Next: Print Utilities, Up: Utility Functions 18.1 General Utilities ====================== Utility functions from `engine/utils.c'. Many of these functions underlie autohelper functions (*note Autohelper Functions::). * `void change_dragon_status(int dr, int status)' Change the status of all the stones in the dragon at `dr'. * `int defend_against(int move, int color, int apos)' Check whether a move at `move' stops the enemy from playing at (apos). * `int cut_possible(int pos, int color)' Returns true if `color' can cut at `pos', or if connection through `pos' is inhibited. This information is collected by `find_cuts()', using the B patterns in the connections database. * `int does_attack(int move, int str)' returns true if the move at `move' attacks `str'. This means that it captures the string, and that `str' is not already dead. * `int does_defend(int move, int str)' `does_defend(move, str)' returns true if the move at `move' defends `str'. This means that it defends the string, and that `str' can be captured if no defense is made. * `int somewhere(int color, int last_move, ...)' Example: `somewhere(WHITE, 2, apos, bpos, cpos)'. Returns true if one of the vertices listed satisfies `board[pos]==color'. Here num_moves is the number of moves minus one. If the check is true the dragon is not allowed to be dead. This check is only valid if `stackp==0'. * `int visible_along_edge(int color, int apos, int bpos)' Search along the edge for the first visible stone. Start at apos and move in the direction of bpos. Return 1 if the first visible stone is of the given color. It is required that apos and bpos are at the same distance from the edge. * `int test_symmetry_after_move(int move, int color, int strict)' Is the board symmetric (or rather antisymmetric) with respect to mirroring in tengen after a specific move has been played? If the move is PASS_MOVE, check the current board. If strict is set we require that each stone is matched by a stone of the opposite color at the mirrored vertex. Otherwise we only require that each stone is matched by a stone of either color. * `int play_break_through_n(int color, int num_moves, ...)' The function `play_break_through_n()' plays a sequence of moves, alternating between the players and starting with color. After having played through the sequence, the three last coordinate pairs gives a position to be analyzed by `break_through()', to see whether either color has managed to enclose some stones and/or connected his own stones. If any of the three last positions is empty, it's assumed that the enclosure has failed, as well as the attempt to connect. If one or more of the moves to play turns out to be illegal for some reason, the rest of the sequence is played anyway, and `break_through()' is called as if nothing special happened. Like `break_through()', this function returns 1 if the attempt to break through was succesful and 2 if it only managed to cut through. * `int play_attack_defend_n(int color, int do_attack, int num_moves, ...)' * `int play_attack_defend2_n(int color, int do_attack, int num_moves, ...)' The function `play_attack_defend_n()' plays a sequence of moves, alternating between the players and starting with `color'. After having played through the sequence, the last coordinate pair gives a target to attack or defend, depending on the value of do_attack. If there is no stone present to attack or defend, it is assumed that it has already been captured. If one or more of the moves to play turns out to be illegal for some reason, the rest of the sequence is played anyway, and attack/defense is tested as if nothing special happened. Conversely, `play_attack_defend2_n()' plays a sequence of moves, alternating between the players and starting with `color'. After having played through the sequence, the two last coordinate pairs give two targets to simultaneously attack or defend, depending on the value of do_attack. If there is no stone present to attack or defend, it is assumed that it has already been captured. If one or more of the moves to play turns out to be illegal for some reason, the rest of the sequence is played anyway, and attack/defense is tested as if nothing special happened. A typical use of these functions is to set up a ladder in an autohelper and see whether it works or not. * `int play_connect_n(int color, int do_connect, int num_moves, ...)' Plays a sequence of moves, alternating between the players and starting with `color'. After having played through the sequence, the two last coordinates give two targets that should be connected or disconnected, depending on the value of do_connect. If there is no stone present to connect or disconnect, it is assumed that the connection has failed. If one or more of the moves to play turns out to be illegal for some reason, the rest of the sequence is played anyway, and connection/disconnection is tested as if nothing special happened. Ultimately the connection is decided by the functions `string_connect' and `disconnect' (*note Connection Reading::). * `void set_depth_values(int level)' It is assumed in reading a ladder if `stackp >= depth' that as soon as a bounding stone is in atari, the string is safe. Similar uses are made of the other depth parameters such as `backfill_depth' and so forth. In short, simplifying assumptions are made when `stackp' is large. Unfortunately any such scheme invites the "horizon effect," in which a stalling move is perceived as a win, by pushing the refutation past the "horizon"--the value of `stackp' in which the reading assumptions are relaxed. To avoid the depth it is sometimes necessary to increase the depth parameters. This function can be used to set the various reading depth parameters. If `mandated_depth_value' is not -1 that value is used; otherwise the depth values are set as a function of level. The parameter `mandated_depth_value' can be set at the command line to force a particular value of depth; normally it is -1. * `void modify_depth_values(int n)' Modify the various tactical reading depth parameters. This is typically used to avoid horizon effects. By temporarily increasing the depth values when trying some move, one can avoid that an irrelevant move seems effective just because the reading hits a depth limit earlier than it did when reading only on relevant moves. * `void increase_depth_values(void)' `modify_depth_values(1)'. * `void decrease_depth_values(void)' `modify_depth_values(-1)'. * `void restore_depth_values()' Sets `depth' and so forth to their saved values. * `void set_temporary_depth_values(int d, int b, int b2, int bc, int ss, int br, int f, int k)' Explicitly set the depth values. This function is currently never called. * `int confirm_safety(int move, int color, int *defense_point, char safe_stones[BOARDMAX])' Check that the move at color doesn't involve any kind of blunder, regardless of size. * `float blunder_size(int move, int color, int *defense_point, char safe_stones[BOARDMAX])' This function will detect some blunders. If the move reduces the number of liberties of an adjacent friendly string, there is a danger that the move could backfire, so the function checks that no friendly worm which was formerly not attackable becomes attackable, and it checks that no opposing worm which was not defendable becomes defendable. It returns the estimated size of the blunder, or 0.0 if nothing bad has happened. The array `safe_stones[]' contains the stones that are supposedly safe after `move'. It may be `NULL'. For use when called from `fill_liberty()', this function may optionally return a point of defense, which, if taken, will presumably make the move at `move' safe on a subsequent turn. * `int double_atari(int move, int color, float *value, char safe_stones[BOARDMAX])' Returns true if a move by (color) fits the following shape: X* (O=color) OX capturing one of the two `X' strings. The name is a slight misnomer since this includes attacks which are not necessarily double ataris, though the common double atari is the most important special case. If `safe_stones != NULL', then only attacks on stones marked as safe are tried. The value of the double atari attack is returned in value (unless value is `NULL'), and the attacked stones are marked unsafe. * `void unconditional_life(int unconditional_territory[BOARDMAX], int color)' Find those worms of the given color that can never be captured, even if the opponent is allowed an arbitrary number of consecutive moves. The coordinates of the origins of these worms are written to the worm arrays and the number of non-capturable worms is returned. The algorithm is to cycle through the worms until none remains or no more can be captured. A worm is removed when it is found to be capturable, by letting the opponent try to play on all its liberties. If the attack fails, the moves are undone. When no more worm can be removed in this way, the remaining ones are unconditionally alive. After this, unconditionally dead opponent worms and unconditional territory are identified. To find these, we continue from the position obtained at the end of the previous operation (only unconditionally alive strings remain for color) with the following steps: 1. Play opponent stones on all liberties of the unconditionally alive strings except where illegal. (That the move order may determine exactly which liberties can be played legally is not important. Just pick an arbitrary order). 2. Recursively extend opponent strings in atari, except where this would be suicide. 3. Play an opponent stone anywhere it can get two empty neighbors. (I.e. split big eyes into small ones). 4. an opponent stone anywhere it can get one empty neighbor. (I.e. reduce two space eyes to one space eyes.) Remaining opponent strings in atari and remaining liberties of the unconditionally alive strings constitute the unconditional territory. Opponent strings from the initial position placed on unconditional territory are unconditionally dead. On return, `unconditional_territory[][]' is 1 where color has unconditionally alive stones, 2 where it has unconditional territory, and 0 otherwise. * `void who_wins(int color, FILE *outfile)' Score the game and determine the winner * `void find_superstring(int str, int *num_stones, int *stones)' Find the stones of an extended string, where the extensions are through the following kinds of connections: 1. Solid connections (just like ordinary string). OO 2. Diagonal connection or one space jump through an intersection where an opponent move would be suicide or self-atari. ... O.O XOX X.X 3. Bamboo joint. OO .. OO 4. Diagonal connection where both adjacent intersections are empty. .O O. 5. Connection through adjacent or diagonal tactically captured stones. Connections of this type are omitted when the superstring code is called from reading.c, but included when the superstring code is called from owl.c * `void find_superstring_liberties(int str, int *num_libs, int *libs, int liberty_cap)' This function computes the superstring at `str' as described above, but omitting connections of type 5. Then it constructs a list of liberties of the superstring which are not already liberties of `str'. If `liberty_cap' is nonzero, only liberties of substrings of the superstring which have fewer than `liberty_cap' liberties are generated. * `void find_proper_superstring_liberties(int str, int *num_libs, int *libs, int liberty_cap)' This function is the same as find_superstring_liberties, but it omits those liberties of the string `str', presumably since those have already been treated elsewhere. If `liberty_cap' is nonzero, only liberties of substrings of the superstring which have at most `liberty_cap' liberties are generated. * `void find_superstring_stones_and_liberties(int str, int *num_stones, int *stones, int *num_libs, int *libs, int liberty_cap)' This function computes the superstring at `str' as described above, but omitting connections of type 5. Then it constructs a list of liberties of the superstring which are not already liberties of `str'. If liberty_cap is nonzero, only liberties of substrings of the superstring which have fewer than liberty_cap liberties are generated. * `void superstring_chainlinks(int str, int *num_adj, int adjs[MAXCHAIN], int liberty_cap)' analogous to chainlinks, this function finds boundary chains of the superstring at `str', including those which are boundary chains of `str' itself. If `liberty_cap != 0', only those boundary chains with `<= liberty_cap' liberties are reported. * `void proper_superstring_chainlinks(int str, int *num_adj, int adjs[MAXCHAIN], int liberty_cap)' analogous to chainlinks, this function finds boundary chains of the superstring at `str', omitting those which are boundary chains of `str' itself. If `liberty_cap != 0', only those boundary chains with `<= liberty_cap' liberties are reported. * `void start_timer(int n)' Start a timer. GNU Go has four internal timers available for assessing the time spent on various tasks. * `double time_report(int n, const char *occupation, int move, double mintime)' Report time spent and restart the timer. Make no report if elapsed time is less than mintime.  File: gnugo.info, Node: Print Utilities, Next: Board Utilities, Prev: General Utilities, Up: Utility Functions 18.2 Print Utilities ==================== Functions in `engine/printutils.c' do formatted printing similar to `printf' and its allies. The following formats are recognized: * `%c', `%d', `%f', `%s', `%x' These have their usual meaning in formatted output, printing a character, integer, float, string or hexadecimal, respectively. * `%o' `Outdent.' Normally output is indented by `2*stackp' spaces, so that the depth can be seen at a glance in traces. At the beginning of a format, this `%o' inhibits the indentation. * `%H' Print a hashvalue. * `%C' Print a color as a string. * `%m', `%2m' (synonyms) Takes 2 integers and writes a move, using the two dimensional board representation (*note The Board Array::) * `%1m' Takes 1 integers and writes a move, using the one dimensional board representation (*note The Board Array::) We list the non statically declared functions in `printutils.c'. * `void gfprintf(FILE *outfile, const char *fmt, ...)' Formatted output to `outfile'. * `int gprintf(const char *fmt, ...)' Formatted output to stderr. Always returns 1 to allow use in short-circuit logical expressions. * `int mprintf(const char *fmt, ...)' Formatted output to stdout. * `DEBUG(level, fmt, args...)' If `level & debug', do formatted output to stderr. Otherwise, ignore. * `void abortgo(const char *file, int line, const char *msg, int pos)' Print debugging output in an error situation, then exit. * `const char * color_to_string(int color)' Convert a color value to a string * `const char * location_to_string(int pos)' Convert a location to a string * `void location_to_buffer(int pos, char *buf)' Convert a location to a string, writing to a buffer. * `int string_to_location(int boardsize, char *str, int *m, int *n)' Get the `(m, n)' coordinates in the standard GNU Go coordinate system from the string `str'. This means that `m' is the nth row from the top and `n' is the column. Both coordinates are between 0 and `boardsize-1', inclusive. Return 1 if ok, otherwise return 0; * `int is_hoshi_point(int m, int n)' True if the coordinate is a hoshi point. * `void draw_letter_coordinates(FILE *outfile)' Print a line with coordinate letters above the board. * `void simple_showboard(FILE *outfile)' Bare bones version of `showboard(0)'. No fancy options, no hint of color, and you can choose where to write it. The following functions are in `showbord.c'. Not all public functions in that file are listed here. * `void showboard(int xo)' Show go board. xo=0: black and white XO board for ascii game xo=1: colored dragon display xo=2: colored eye display xo=3: colored owl display xo=4: colored matcher status display * `const char * status_to_string(int status)' Convert a status value to a string. * `const char * safety_to_string(int status)' Convert a safety value to a string. * `const char * result_to_string(int result)' Convert a read result to a string  File: gnugo.info, Node: Board Utilities, Next: Influence Utilities, Prev: Print Utilities, Up: Utility Functions 18.3 Board Utilities ==================== The functions documented in this section are from `board.c'. Other functions in `board.c' are described in *Note Some Board Functions::. * `void store_board(struct board_state *state)' Save board state. * `void restore_board(struct board_state *state)' Restore a saved board state. * `void clear_board(void)' Clear the internal board. * `void dump_stack(void)' for use under GDB prints the move stack. * `void add_stone(int pos, int color)' Place a stone on the board and update the board_hash. This operation destroys all move history. * `void remove_stone(int pos)' Remove a stone from the board and update the board_hash. This operation destroys the move history. * `int is_pass(int pos)' Test if the move is a pass or not. Return 1 if it is. * `int is_legal(int pos, int color)' Determines whether the move `color' at `pos' is legal. * `int is_suicide(int pos, int color)' Determines whether the move `color' at `pos' would be a suicide. This is the case if 1. There is no neighboring empty intersection. 2. There is no neighboring opponent string with exactly one liberty. 3. There is no neighboring friendly string with more than one liberty. * `int is_illegal_ko_capture(int pos, int color)' Determines whether the move `color' at `pos' would be an illegal ko capture. * `int is_edge_vertex(int pos)' Determine whether vertex is on the edge. * `int edge_distance(int pos)' Distance to the edge. * `int is_corner_vertex(int pos)' Determine whether vertex is a corner. * `int get_komaster()' * `int get_kom_pos()' Public functions to access the variable `komaster' and `kom_pos', which are static in `board.c'. Next we come to `countlib()' and its allies, which address the problem of determining how many liberties a string has. Although `countlib()' addresses this basic question, other functions can often get the needed information more quickly, so there are a number of different functions in this family. * `int countlib(int str)' Count the number of liberties of the string at `pos'. There must be a stone at this location. * `int findlib(int str, int maxlib, int *libs)' Find the liberties of the string at `str'. This location must not be empty. The locations of up to maxlib liberties are written into `libs[]'. The full number of liberties is returned. If you want the locations of all liberties, whatever their number, you should pass `MAXLIBS' as the value for `maxlib' and allocate space for `libs[]' accordingly. * `int fastlib(int pos, int color, int ignore_captures)' Count the liberties a stone of the given color would get if played at `pos'. The intent of this function is to be as fast as possible, not necessarily complete. But if it returns a positive value (meaning it has succeeded), the value is guaranteed to be correct. Captures are ignored based if the `ignore_captures' field is nonzero. The location `pos' must be empty. The function fails if there are more than two neighbor strings of the same color. In this case, the return value is -1. Captures are handled in a very limited way, so if ignore_capture is 0, and a capture is required, it will often return -1. * `int approxlib(int pos, int color, int maxlib, int *libs)' Find the liberties a stone of the given color would get if played at `pos', ignoring possible captures of opponent stones. The location `pos' must be empty. If `libs != NULL', the locations of up to `maxlib' liberties are written into `libs[]'. The counting of liberties may or may not be halted when `maxlib' is reached. The number of liberties found is returned, which may be less than the total number of liberties if `maxlib' is small. If you want the number or the locations of all liberties, however many they are, you should pass `MAXLIBS' as the value for maxlib and allocate space for `libs[]' accordingly. * `int accuratelib(int pos, int color, int maxlib, int *libs)' Find the liberties a stone of the given color would get if played at `pos'. This function takes into consideration all captures. Its return value is exact in that sense it counts all the liberties, unless `maxlib' allows it to stop earlier. The location `pos' must be empty. If `libs != NULL', the locations of up to `maxlib' liberties are written into `libs[]'. The counting of liberties may or may not be halted when `maxlib' is reached. The number of found liberties is returned. This function guarantees that liberties which are not results of captures come first in `libs[]' array. To find whether all the liberties starting from a given one are results of captures, one may use `if (board[libs[k]] != EMPTY)' construction. If you want the number or the locations of all liberties, however many they are, you should pass `MAXLIBS' as the value for `maxlib' and allocate space for `libs[]' accordingly. Next we have some general utility functions. * `int count_common_libs(int str1, int str2)' Find the number of common liberties of the two strings. * `int find_common_libs(int str1, int str2, int maxlib, int *libs)' Find the common liberties of the two strings. The locations of up to `maxlib' common liberties are written into `libs[]'. The full number of common liberties is returned. If you want the locations of all common liberties, whatever their number, you should pass `MAXLIBS' as the value for `maxlib' and allocate space for `libs[]' accordingly. * `int have_common_lib(int str1, int str2, int *lib)' Determine whether two strings have at least one common liberty. If they do and `lib != NULL', one common liberty is returned in `*lib'. * `int countstones(int str)' Report the number of stones in a string. * `int findstones(int str, int maxstones, int *stones)' Find the stones of the string at `str'. The location must not be empty. The locations of up to maxstones stones are written into `stones[]'. The full number of stones is returned. * `int chainlinks(int str, int adj[MAXCHAIN])' This very useful function returns (in the `adj' array) the chains surrounding the string at `str'. The number of chains is returned. * `int chainlinks2(int str, int adj[MAXCHAIN], int lib)' Returns (in `adj' array) those chains surrounding the string at `str', which has exactly `lib' liberties. The number of such chains is returned. * `int chainlinks3(int str, int adj[MAXCHAIN], int lib)' Returns (in `adj' array) the chains surrounding the string at `str', which have less or equal `lib' liberties. The number of such chains is returned. * `int extended_chainlinks(int str, int adj[MAXCHAIN], int both_colors)' Returns (in the `adj' array) the opponent strings being directly adjacent to `str' or having a common liberty with `str'. The number of such strings is returned. If the both_colors parameter is true, also own strings sharing a liberty are returned. * `int find_origin(int str)' Find the origin of a string, i.e. the point with the smallest 1D board coordinate. The idea is to have a canonical reference point for a string. * `int is_self_atari(int pos, int color)' Determine whether a move by color at `pos' would be a self atari, i.e. whether it would get more than one liberty. This function returns true also for the case of a suicide move. * `int liberty_of_string(int pos, int str)' Returns true if `pos' is a liberty of the string at `str'. * `int second_order_liberty_of_string(int pos, int str)' Returns true if `pos' is a second order liberty of the string at str. * `int neighbor_of_string(int pos, int str)' Returns true if `pos' is adjacent to the string at `str'. * `int has_neighbor(int pos, int color)' Returns true if `pos' has a neighbor of `color'. * `int same_string(int str1, int str2)' Returns true if `str1' and `str2' belong to the same string. * `int adjacent_strings(int str1, int str2)' Returns true if the strings at `str1' and `str2' are adjacent. * `int is_ko(int pos, int color, int *ko_pos)' Return true if the move `pos' by `color' is a ko capture (whether capture is legal on this move or not). If so, and if `ko_pos' is not a `NULL' pointer, then `*ko_pos' returns the location of the captured ko stone. If the move is not a ko capture, `*ko_pos' is set to 0. A move is a ko capture if and only if 1. All neighbors are opponent stones. 2. The number of captured stones is exactly one. * `int is_ko_point(int pos)' Return true if `pos' is either a stone, which if captured would give ko, or if `pos' is an empty intersection adjacent to a ko stone. * `int does_capture_something(int pos, int color)' Returns 1 if at least one string is captured when color plays at `pos'. * `void mark_string(int str, char mx[BOARDMAX], char mark)' For each stone in the string at pos, set `mx' to value mark. If some of the stones in the string are marked prior to calling this function, only the connected unmarked stones starting from pos are guaranteed to become marked. The rest of the string may or may not become marked. (In the current implementation, it will.) * `int move_in_stack(int pos, int cutoff)' Returns true if at least one move has been played at pos at deeper than level `cutoff' in the reading tree. * `int stones_on_board(int color)' Return the number of stones of the indicated color(s) on the board. This only counts stones in the permanent position, not stones placed by `trymove()' or `tryko()'. Use `stones_on_board(BLACK | WHITE)' to get the total number of stones on the board.  File: gnugo.info, Node: Influence Utilities, Prev: Board Utilities, Up: Utility Functions 18.4 Utilities from `engine/influence.c' ======================================== We will only list here a portion of the public functions in `influence.c'. The influence code is invoked through the function `compute_influence' (*note Influence Usage::). It is invoked as follows. * `void compute_influence(int color, const char safe_stones[BOARDMAX], const float strength[BOARDMAX], struct influence_data *q, int move, const char *trace_message)' Compute the influence values for both colors. The caller must - set up the `board[]' state - mark safe stones with `INFLUENCE_SAFE_STONE', dead stones with 0 - mark stones newly saved by a move with `INFLUENCE_SAVED_STONE' (this is relevant if the influence_data *q is reused to compute a followup value for this move). Results will be stored in q. `move' has no effects except toggling debugging. Set it to -1 for no debug output at all (otherwise it will be controlled by the `-m' command line option). It is assumed that `color' is in turn to move. (This affects the barrier patterns (class A, D) and intrusions (class B)). Color Other functions in `influence.c' are of the nature of utilities which may be useful throughout the engine. We list the most useful ones here. * `void influence_mark_non_territory(int pos, int color)' Called from actions for `t' patterns in `barriers.db'. Marks `pos' as not being territory for `color'. * `int whose_territory(const struct influence_data *q, int pos)' Return the color of the territory at `pos'. If it's territory for neither color, `EMPTY' is returned. * `int whose_moyo(const struct influence_data *q, int pos)' Return the color who has a moyo at `pos'. If neither color has a moyo there, `EMPTY' is returned. The definition of moyo in terms of the influences is totally ad hoc. * `int whose_area(const struct influence_data *q, int pos)' Return the color who has dominating influence ("area") at `pos'. If neither color dominates the influence there, EMPTY is returned. The definition of area in terms of the influences is totally ad hoc.  File: gnugo.info, Node: GTP, Next: Regression, Prev: API, Up: Top 19 The Go Text Protocol *********************** * Menu: * The Go Text Protocol:: The Go Text Protocol * Running in GTP mode:: Running GNU Go in GTP mode * GTP applications:: GTP applications * The Metamachine:: The Metamachine * Adding new GTP commands:: Adding new GTP commands * GTP command reference:: Details on every GTP command  File: gnugo.info, Node: The Go Text Protocol, Next: Running in GTP mode, Up: GTP 19.1 The Go Text Protocol ========================= GNU Go 3.0 introduced a new interface, the Go Text Protocol, abbreviated GTP. The intention was to make an interface that is better suited for machine-machine communication than the ascii interface and simpler, more powerful, and more flexible than the Go Modem Protocol. There are two versions of the protocol. Version 1 was used with GNU Go 3.0 and 3.2. GNU Go 3.4 and later versions use protocol version 2. The specification of GTP version 2 is available at `http://www.lysator.liu.se/~gunnar/gtp/'. GNU Go 3.4 is the reference implementation for GTP version 2, but all but the most common commands are to be regarded as private extensions of the protocol. The GTP has a variety of applications. For GNU Go the first use was in regression testing (*note Regression::), followed by communication with the NNGS go server and for automated test games against itself and other programs. Now there are also many graphical user interfaces available supporting GTP, as well as bridges to other Go servers than NNGS.  File: gnugo.info, Node: Running in GTP mode, Next: GTP applications, Prev: The Go Text Protocol, Up: GTP 19.2 Running GNU Go in GTP mode =============================== To start GNU Go in GTP mode, simply invoke it with the option `--mode gtp'. You will not get a prompt or any other output to start with but GNU Go is silently waiting for GTP commands. A sample GTP session may look as follows: virihaure 462% ./gnugo --mode gtp 1 boardsize 7 =1 2 clear_board =2 3 play black D5 =3 4 genmove white =4 C3 5 play black C3 ?5 illegal move 6 play black E3 =6 7 showboard =7 A B C D E F G 7 . . . . . . . 7 6 . . . . . . . 6 5 . . + X + . . 5 4 . . . + . . . 4 3 . . O . X . . 3 2 . . . . . . . 2 WHITE (O) has captured 0 stones 1 . . . . . . . 1 BLACK (X) has captured 0 stones A B C D E F G 8 quit =8 Commands are given on a single line, starting by an optional identity number, followed by the command name and its arguments. If the command is successful, the response starts by an equals sign (`='), followed by the identity number of the command (if any) and then the result. In this example all results were empty strings except for command 4 where the answer was the white move at C3, and command 7 where the result was a diagram of the current board position. The response ends by two consecutive newlines. Failing commands are signified by a question mark (`?') instead of an equals sign, as in the response to command 5. The detailed specification of the protocol can be found at `http://www.lysator.liu.se/~gunnar/gtp/'. The available commands in GNU Go may always be listed using the command `list_commands'. They are also documented in *Note GTP command reference::.  File: gnugo.info, Node: GTP applications, Next: The Metamachine, Prev: Running in GTP mode, Up: GTP 19.3 GTP applications ===================== GTP is an asymmetric protocol involving two parties which we call controller and engine. The controller sends all commands and the engine only responds to these commands. GNU Go implements the engine end of the protocol. With the source code of GNU Go is also distributed a number of applications implementing the controller end. Among the most interesting of these are: * `regression/regress.awk' Script to run regressions. The script sends GTP commands to set up and evaluate positions to the engine and then analyzes the responses from the engine. More information about GTP based regression testing can be found in the regression chapter (*note Regression::). * `regression/regress.pl' Perl script to run regressions, giving output which together with the CGI script `regression/regress.plx' generates HTML views of the regressions. * `regression/regress.pike' Pike script to run regressions. More feature-rich and powerful than `regress.awk'. * `regression/view.pike' Pike script to examine a single regression testcase through a graphical board. This gives an easy way to inspect many of the GNU Go internals. * `interface/gtp_examples/twogtp' Perl script to play two engines against each other. The script essentially sets up both engines with desired boardsize, handicap, and komi, then relays moves back and forth between the engines. * `interface/gtp_examples/twogtp-a' An alternative Perl implementation of twogtp. * `interface/gtp_examples/twogtp.py' Implementation of twogtp in Python. Has more features than the Perl variants. * `interface/gtp_examples/twogtp.pike' Implementation of twogtp in Pike. Has even more features than the Python variant. * `interface/gtp_examples/2ptkgo.pl' Variation of twogtp which includes a graphical board. More GTP applications, including bridges to go servers and graphical user interfaces, are listed at `http://www.lysator.liu.se/~gunnar/gtp/'.  File: gnugo.info, Node: The Metamachine, Next: Adding new GTP commands, Prev: GTP applications, Up: GTP 19.4 The Metamachine ==================== An interesting application of the GTP is the concept of using GNU Go as an "Oracle" that can be consulted by another process. This could be another computer program that asks GNU Go to generate future board positions, then evaluate them. David Doshay at the University of California at Santa Cruz has done interesting experiments with a parallel engine, known as SlugGo, that is based on GNU Go. These are described in `http://lists.gnu.org/archive/html/gnugo-devel/2004-08/msg00060.html'. The "Metamachine" experiment is a more modest approach using the GTP to communicate with a GNU Go process that is used as an oracle. The following scheme is used. * The GNU Go "oracle" is asked to generate its top moves using the GTP `top_moves' commands. * Both moves are tried and `estimate_score' is called from the resulting board position. * The higher scoring position is selected as the engine's move. This scheme does not produce a stronger engine, but it is suggestive, and the SlugGo experiment seems to show that a more elaborate scheme along the same lines could produce a stronger engine. Two implementations are distributed with GNU Go. Both make use of `fork' and `pipe' system calls, so they require a Unix-like environment. The Metamachine has been tested under GNU/Linux. *Important:* If the Metamachine terminates normally, the GNU Go process will be killed. However there is a danger that something will go wrong. When you are finished running the Metamachine, it is a good idea to run `ps -A|grep gnugo' or `ps -aux|grep gnugo' to make sure there are no unterminated processes. (If there are, just kill them.) 19.4.1 The Standalone Metamachine --------------------------------- In `interface/gtp_examples/metamachine.c' is a standalone implementation of the Metamachine. Compile it with `cc -o metamachine metamachine.c' and run it. It forks a `gnugo' process with which it communicates through the GTP, to use as an oracle. The following scheme is followed: stdin pipe a GTP client ----> Metamachine -----> GNU Go <---- <----- stdout pipe b Most commands issued by the client are passed along verbatim to GNU Go by the Metamachine. The exception is gg_genmove, which is intercepted then processed differently, as described above. The client is unaware of this, and only knows that it issued a gg_genmove command and received a reply. Thus to the the Metamachine appears as an ordinary GTP engine. Usage: no arguments gives normal GTP behavior. `metamachine --debug' sends diagnostics to stderr. 19.4.2 GNU Go as a Metamachine ------------------------------ Alternatively, you may compile GNU Go with the configure option `--enable-metamachine'. This causes the file `oracle.c' to be compiled, which contains the Metamachine code. This has no effect on the engine unless you run GNU Go with the runtime option `--metamachine'. Thus you must use both the configure and the runtime option to get the Metamachine. This method is better than the standalone program since you have access to GNU Go's facilities. For example, you can run the Metamachine with CGoban or in Ascii mode this way. You can get traces by adding the command line `-d0x1000000'. In debugging the Metamachine, a danger is that any small oversight in designing the program can cause the forked process and the controller to hang, each one waiting for a response from the other. If this seems to happen it is useful to know that you can attach `gdb' to a running process and find out what it is doing.  File: gnugo.info, Node: Adding new GTP commands, Next: GTP command reference, Prev: The Metamachine, Up: GTP 19.5 Adding new GTP commands ============================ The implementation of GTP in GNU Go is distributed over three files, `interface/gtp.h', `interface/gtp.c', and `interface/play_gtp.c'. The first two implement a small library of helper functions which can be used also by other programs. In the interest of promoting the GTP they are licensed with minimal restrictions (*note GTP License::). The actual GTP commands are implemented in `play_gtp.c', which has knowledge about the engine internals. To see how a simple but fairly typical command is implemented we look at `gtp_countlib()' (a GNU Go private extension command): static int gtp_countlib(char *s) { int i, j; if (!gtp_decode_coord(s, &i, &j)) return gtp_failure("invalid coordinate"); if (BOARD(i, j) == EMPTY) return gtp_failure("vertex must not be empty"); return gtp_success("%d", countlib(POS(i, j))); } The arguments to the command are passed in the string `s'. In this case we expect a vertex as argument and thus try to read it with `gtp_decode_coord()' from `gtp.c'. A correctly formatted response should start with either `=' or `?', followed by the identity number (if one was sent), the actual result, and finally two consecutive newlines. It is important to get this formatting correct since the controller in the other end relies on it. Naturally the result itself cannot contain two consecutive newlines but it may be split over several lines by single newlines. The easiest way to generate a correctly formatted response is with one of the functions `gtp_failure()' and `gtp_success()', assuming that their formatted output does not end with a newline. Sometimes the output is too complex for use with gtp_success, e.g. if we want to print vertices, which gtp_success() does not support. Then we have to fall back to the construction in e.g. `gtp_genmove()': static int gtp_genmove(char *s) { [...] gtp_start_response(GTP_SUCCESS); gtp_print_vertex(i, j); return gtp_finish_response(); } Here `gtp_start_response()' writes the equal sign and the identity number while `gtp_finish_response()' adds the final two newlines. The next example is from `gtp_list_commands()': static int gtp_list_commands(char *s) { int k; UNUSED(s); gtp_start_response(GTP_SUCCESS); for (k = 0; commands[k].name != NULL; k++) gtp_printf("%s\n", commands[k].name); gtp_printf("\n"); return GTP_OK; } As we have said, the response should be finished with two newlines. Here we have to finish up the response ourselves since we already have one newline in place from the last command printed in the loop. In order to add a new GTP command to GNU Go, the following pieces of code need to be inserted in `play_gtp.c': 1. A function declaration using the `DECLARE' macro in the list starting at line 68. 2. An entry in the `commands[]' array starting at line 200. 3. An implementation of the function handling the command. Useful helper functions in `gtp.c'/`gtp.h' are: * `gtp_printf()' for basic formatted printing. * `gtp_mprintf()' for printing with special format codes for vertices and colors. * `gtp_success()' and `gtp_failure()' for simple responses. * `gtp_start_response()' and `gtp_end_response()' for more complex responses. * `gtp_print_vertex()' and `gtp_print_vertices()' for printing one or multiple vertices. * `gtp_decode_color()' to read in a color from the command arguments. * `gtp_decode_coord()' to read in a vertex from the command arguments. * `gtp_decode_move()' to read in a move, i.e. color plus vertex, from the command arguments.  File: gnugo.info, Node: GTP command reference, Prev: Adding new GTP commands, Up: GTP 19.6 GTP command reference ========================== This section lists the GTP commands implemented in GNU Go along with some information about each command. Each entry in the list has the following fields: * Function: What this command does. * Arguments: What other information, if any, this command requires. Typical values include "none" or "vertex" or "integer" (there are others). * Fails: Circumstances which cause this command to fail. * Returns: What is displayed after the "=" and before the two newlines. Typical values include "nothing" or "a move coordinate" or some status string (there are others). * Status: How this command relates to the standard GTP version 2 commands. If nothing else is specified it is a GNU Go private extension. Without further ado, here is the big list (in no particular order). Note: if new commands are added by editing `interface/play_gtp.c' this list could become incomplete. You may rebuild this list in `doc/gtp-commands.texi' with the command `make gtp-commands' in the `doc/' directory. This may require GNU sed. * quit: Quit Arguments: none Fails: never Returns: nothing Status: GTP version 2 standard command. * protocol_version: Report protocol version. Arguments: none Fails: never Returns: protocol version number Status: GTP version 2 standard command. * name: Report the name of the program. Arguments: none Fails: never Returns: program name Status: GTP version 2 standard command. * version: Report the version number of the program. Arguments: none Fails: never Returns: version number Status: GTP version 2 standard command. * boardsize: Set the board size to NxN and clear the board. Arguments: integer Fails: board size outside engine's limits Returns: nothing Status: GTP version 2 standard command. * query_boardsize: Find the current boardsize Arguments: none Fails: never Returns: board_size * clear_board: Clear the board. Arguments: none Fails: never Returns: nothing Status: GTP version 2 standard command. * orientation: Set the orienation to N and clear the board Arguments: integer Fails: illegal orientation Returns: nothing * query_orientation: Find the current orientation Arguments: none Fails: never Returns: orientation * komi: Set the komi. Arguments: float Fails: incorrect argument Returns: nothing Status: GTP version 2 standard command. * get_komi: Get the komi Arguments: none Fails: never Returns: Komi * black: Play a black stone at the given vertex. Arguments: vertex Fails: invalid vertex, illegal move Returns: nothing Status: Obsolete GTP version 1 command. * playwhite: Play a white stone at the given vertex. Arguments: vertex Fails: invalid vertex, illegal move Returns: nothing Status: Obsolete GTP version 1 command. * play: Play a stone of the given color at the given vertex. Arguments: color, vertex Fails: invalid vertex, illegal move Returns: nothing Status: GTP version 2 standard command. * fixed_handicap: Set up fixed placement handicap stones. Arguments: number of handicap stones Fails: invalid number of stones for the current boardsize Returns: list of vertices with handicap stones Status: GTP version 2 standard command. * place_free_handicap: Choose free placement handicap stones and put them on the board. Arguments: number of handicap stones Fails: invalid number of stones Returns: list of vertices with handicap stones Status: GTP version 2 standard command. * set_free_handicap: Put free placement handicap stones on the board. Arguments: list of vertices with handicap stones Fails: board not empty, bad list of vertices Returns: nothing Status: GTP version 2 standard command. * get_handicap: Get the handicap Arguments: none Fails: never Returns: handicap * loadsgf: Load an sgf file, possibly up to a move number or the first occurence of a move. Arguments: filename + move number, vertex, or nothing Fails: missing filename or failure to open or parse file Returns: color to play Status: GTP version 2 standard command. * color: Return the color at a vertex. Arguments: vertex Fails: invalid vertex Returns: "black", "white", or "empty" * list_stones: List vertices with either black or white stones. Arguments: color Fails: invalid color Returns: list of vertices * countlib: Count number of liberties for the string at a vertex. Arguments: vertex Fails: invalid vertex, empty vertex Returns: Number of liberties. * findlib: Return the positions of the liberties for the string at a vertex. Arguments: vertex Fails: invalid vertex, empty vertex Returns: Sorted space separated list of vertices. * accuratelib: Determine which liberties a stone of given color will get if played at given vertex. Arguments: move (color + vertex) Fails: invalid color, invalid vertex, occupied vertex Returns: Sorted space separated list of liberties * accurate_approxlib: Determine which liberties a stone of given color will get if played at given vertex. Arguments: move (color + vertex) Fails: invalid color, invalid vertex, occupied vertex Returns: Sorted space separated list of liberties Supposedly identical in behavior to the above function and can be retired when this is confirmed. * is_legal: Tell whether a move is legal. Arguments: move Fails: invalid move Returns: 1 if the move is legal, 0 if it is not. * all_legal: List all legal moves for either color. Arguments: color Fails: invalid color Returns: Sorted space separated list of vertices. * captures: List the number of captures taken by either color. Arguments: color Fails: invalid color Returns: Number of captures. * last_move: Return the last move. Arguments: none Fails: no previous move known Returns: Color and vertex of last move. * move_history: Print the move history in reverse order Arguments: none Fails: never Returns: List of moves played in reverse order in format: color move (one move per line) * invariant_hash: Return the rotation/reflection invariant board hash. Arguments: none Fails: never Returns: Invariant hash for the board as a hexadecimal number. * invariant_hash_for_moves: Return the rotation/reflection invariant board hash obtained by playing all the possible moves for the given color. Arguments: color Fails: invalid color Returns: List of moves + invariant hash as a hexadecimal number, one pair of move + hash per line. * trymove: Play a stone of the given color at the given vertex. Arguments: move (color + vertex) Fails: invalid color, invalid vertex, illegal move Returns: nothing * tryko: Play a stone of the given color at the given vertex, allowing illegal ko capture. Arguments: move (color + vertex) Fails: invalid color, invalid vertex, illegal move Returns: nothing * popgo: Undo a trymove or tryko. Arguments: none Fails: stack empty Returns: nothing * clear_cache: clear the caches. Arguments: none. Fails: never. Returns: nothing. * attack: Try to attack a string. Arguments: vertex Fails: invalid vertex, empty vertex Returns: attack code followed by attack point if attack code nonzero. * attack_either: Try to attack either of two strings Arguments: two vertices Fails: invalid vertex, empty vertex Returns: attack code against the strings. Guarantees there exists a move which will attack one of the two with attack_code, but does not return the move. * defend: Try to defend a string. Arguments: vertex Fails: invalid vertex, empty vertex Returns: defense code followed by defense point if defense code nonzero. * does_attack: Examine whether a specific move attacks a string tactically. Arguments: vertex (move), vertex (dragon) Fails: invalid vertex, empty vertex Returns: attack code * does_defend: Examine whether a specific move defends a string tactically. Arguments: vertex (move), vertex (dragon) Fails: invalid vertex, empty vertex Returns: attack code * ladder_attack: Try to attack a string strictly in a ladder. Arguments: vertex Fails: invalid vertex, empty vertex Returns: attack code followed by attack point if attack code nonzero. * increase_depths: Increase depth values by one. Arguments: none Fails: never Returns: nothing * decrease_depths: Decrease depth values by one. Arguments: none Fails: never Returns: nothing * owl_attack: Try to attack a dragon. Arguments: vertex Fails: invalid vertex, empty vertex Returns: attack code followed by attack point if attack code nonzero. * owl_defend: Try to defend a dragon. Arguments: vertex Fails: invalid vertex, empty vertex Returns: defense code followed by defense point if defense code nonzero. * owl_threaten_attack: Try to attack a dragon in 2 moves. Arguments: vertex Fails: invalid vertex, empty vertex Returns: attack code followed by the two attack points if attack code nonzero. * owl_threaten_defense: Try to defend a dragon with 2 moves. Arguments: vertex Fails: invalid vertex, empty vertex Returns: defense code followed by the 2 defense points if defense code nonzero. * owl_does_attack: Examine whether a specific move attacks a dragon. Arguments: vertex (move), vertex (dragon) Fails: invalid vertex, empty vertex Returns: attack code * owl_does_defend: Examine whether a specific move defends a dragon. Arguments: vertex (move), vertex (dragon) Fails: invalid vertex, empty vertex Returns: defense code * owl_connection_defends: Examine whether a connection defends involved dragons. Arguments: vertex (move), vertex (dragon1), vertex (dragon2) Fails: invalid vertex, empty vertex Returns: defense code * defend_both: Try to defend both of two strings Arguments: two vertices Fails: invalid vertex, empty vertex Returns: defend code for the strings. Guarantees there exists a move which will defend both of the two with defend_code, but does not return the move. * owl_substantial: Determine whether capturing a string gives a living dragon Arguments: vertex Fails: invalid vertex, empty vertex Returns: 1 if dragon can live, 0 otherwise * analyze_semeai: Analyze a semeai Arguments: dragona, dragonb Fails: invalid vertices, empty vertices Returns: semeai defense result, semeai attack result, semeai move * analyze_semeai_after_move: Analyze a semeai after a move have been made. Arguments: color, vertex, dragona, dragonb Fails: invalid vertices Returns: semeai defense result, semeai attack result, semeai move * tactical_analyze_semeai: Analyze a semeai, not using owl Arguments: dragona, dragonb Fails: invalid vertices, empty vertices Returns: status of dragona, dragonb assuming dragona moves first * connect: Try to connect two strings. Arguments: vertex, vertex Fails: invalid vertex, empty vertex, vertices of different colors Returns: connect result followed by connect point if successful. * disconnect: Try to disconnect two strings. Arguments: vertex, vertex Fails: invalid vertex, empty vertex, vertices of different colors Returns: disconnect result followed by disconnect point if successful. * break_in: Try to break from string into area. Arguments: vertex, vertices Fails: invalid vertex, empty vertex. Returns: result followed by break in point if successful. * block_off: Try to block string from area. Arguments: vertex, vertices Fails: invalid vertex, empty vertex. Returns: result followed by block point if successful. * eval_eye: Evaluate an eye space Arguments: vertex Fails: invalid vertex Returns: Minimum and maximum number of eyes. If these differ an attack and a defense point are additionally returned. If the vertex is not an eye space or not of unique color, a single -1 is returned. * dragon_status: Determine status of a dragon. Arguments: optional vertex Fails: invalid vertex, empty vertex Returns: status ("alive", "critical", "dead", or "unknown"), attack point, defense point. Points of attack and defense are only given if the status is critical. If no vertex is given, the status is listed for all dragons, one per row in the format "A4: alive". FIXME: Should be able to distinguish between life in seki and independent life. Should also be able to identify ko. * same_dragon: Determine whether two stones belong to the same dragon. Arguments: vertex, vertex Fails: invalid vertex, empty vertex Returns: 1 if the vertices belong to the same dragon, 0 otherwise * unconditional_status: Determine the unconditional status of a vertex. Arguments: vertex Fails: invalid vertex Returns: unconditional status ("undecided", "alive", "dead", "white_territory", "black_territory"). Occupied vertices can be undecided, alive, or dead. Empty vertices can be undecided, white territory, or black territory. * combination_attack: Find a move by color capturing something through a combination attack. Arguments: color Fails: invalid color Returns: Recommended move, PASS if no move found * combination_defend: If color can capture something through a combination attack, list moves by the opponent of color to defend against this attack. Arguments: color Fails: invalid color Returns: Recommended moves, PASS if no combination attack found. * aa_confirm_safety: Run atari_atari_confirm_safety(). Arguments: move, optional int Fails: invalid move Returns: success code, if failure also defending move * genmove_black: Generate and play the supposedly best black move. Arguments: none Fails: never Returns: a move coordinate or "PASS" Status: Obsolete GTP version 1 command. * genmove_white: Generate and play the supposedly best white move. Arguments: none Fails: never Returns: a move coordinate or "PASS" Status: Obsolete GTP version 1 command. * genmove: Generate and play the supposedly best move for either color. Arguments: color to move Fails: invalid color Returns: a move coordinate or "PASS" (or "resign" if resignation_allowed) Status: GTP version 2 standard command. * reg_genmove: Generate the supposedly best move for either color. Arguments: color to move Fails: invalid color Returns: a move coordinate (or "PASS") Status: GTP version 2 standard command. * gg_genmove: Generate the supposedly best move for either color. Arguments: color to move, optionally a random seed Fails: invalid color Returns: a move coordinate (or "PASS") This differs from reg_genmove in the optional random seed. * restricted_genmove: Generate the supposedly best move for either color from a choice of allowed vertices. Arguments: color to move, allowed vertices Fails: invalid color, invalid vertex, no vertex listed Returns: a move coordinate (or "PASS") * kgs-genmove_cleanup: Generate and play the supposedly best move for either color, not passing until all dead opponent stones have been removed. Arguments: color to move Fails: invalid color Returns: a move coordinate (or "PASS") Status: KGS specific command. A similar command, but possibly somewhat different, will likely be added to GTP version 3 at a later time. * level: Set the playing level. Arguments: int Fails: incorrect argument Returns: nothing * undo: Undo one move Arguments: none Fails: If move history is too short. Returns: nothing Status: GTP version 2 standard command. * gg-undo: Undo a number of moves Arguments: optional int Fails: If move history is too short. Returns: nothing * time_settings: Set time allowance Arguments: int main_time, int byo_yomi_time, int byo_yomi_stones Fails: syntax error Returns: nothing Status: GTP version 2 standard command. * time_left: Report remaining time Arguments: color color, int time, int stones Fails: syntax error Returns: nothing Status: GTP version 2 standard command. * final_score: Compute the score of a finished game. Arguments: Optional random seed Fails: never Returns: Score in SGF format (RE property). Status: GTP version 2 standard command. * final_status: Report the final status of a vertex in a finished game. Arguments: Vertex, optional random seed Fails: invalid vertex Returns: Status in the form of one of the strings "alive", "dead", "seki", "white_territory", "black_territory", or "dame". * final_status_list: Report vertices with a specific final status in a finished game. Arguments: Status in the form of one of the strings "alive", "dead", "seki", "white_territory", "black_territory", or "dame". An optional random seed can be added. Fails: missing or invalid status string Returns: Vertices having the specified status. These are split with one string on each line if the vertices are nonempty (i.e. for "alive", "dead", and "seki"). Status: GTP version 2 standard command. However, "dame", "white_territory", and "black_territory" are private extensions. * estimate_score: Estimate the score Arguments: None Fails: never Returns: upper and lower bounds for the score * experimental_score: Estimate the score, taking into account which player moves next Arguments: Color to play Fails: Invalid color Returns: Score. This function generates a move for color, then adds the value of the move generated to the value of the position. Critical dragons are awarded to the opponent since the value of rescuing a critical dragon is taken into account in the value of the move generated. * reset_life_node_counter: Reset the count of life nodes. Arguments: none Fails: never Returns: nothing Note: This function is obsolete and only remains for backwards compatibility. * get_life_node_counter: Retrieve the count of life nodes. Arguments: none Fails: never Returns: number of life nodes Note: This function is obsolete and only remains for backwards compatibility. * reset_owl_node_counter: Reset the count of owl nodes. Arguments: none Fails: never Returns: nothing * get_owl_node_counter: Retrieve the count of owl nodes. Arguments: none Fails: never Returns: number of owl nodes * reset_reading_node_counter: Reset the count of reading nodes. Arguments: none Fails: never Returns: nothing * get_reading_node_counter: Retrieve the count of reading nodes. Arguments: none Fails: never Returns: number of reading nodes * reset_trymove_counter: Reset the count of trymoves/trykos. Arguments: none Fails: never Returns: nothing * get_trymove_counter: Retrieve the count of trymoves/trykos. Arguments: none Fails: never Returns: number of trymoves/trykos * reset_connection_node_counter: Reset the count of connection nodes. Arguments: none Fails: never Returns: nothing * get_connection_node_counter: Retrieve the count of connection nodes. Arguments: none Fails: never Returns: number of connection nodes * test_eyeshape: Test an eyeshape for inconsistent evaluations Arguments: Eyeshape vertices Fails: Bad vertices Returns: Failure reports on stderr. * analyze_eyegraph: Compute an eyevalue and vital points for an eye graph Arguments: Eyeshape encoded in string Fails: Bad eyeshape, analysis failed Returns: Eyevalue, vital points * cputime: Returns elapsed CPU time in seconds. Arguments: none Fails: never Returns: Total elapsed (user + system) CPU time in seconds. * showboard: Write the position to stdout. Arguments: none Fails: never Returns: nothing Status: GTP version 2 standard command. * dump_stack: Dump stack to stderr. Arguments: none Fails: never Returns: nothing * initial_influence: Return information about the initial influence function. Arguments: color to move, what information Fails: never Returns: Influence data formatted like: 0.51 1.34 3.20 6.60 9.09 8.06 1.96 0.00 0.00 0.45 1.65 4.92 12.19 17.47 15.92 4.03 0.00 0.00 . . . 0.00 0.00 0.00 0.00 0.00 100.00 75.53 41.47 23.41 The available choices of information are: white_influence (float) black_influence (float) white_strength (float) black_strength (float) white_attenuation (float) black_attenuation (float) white_permeability (float) black_permeability (float) territory_value (float) influence_regions (int) non_territory (int) The encoding of influence_regions is as follows: 4 white stone 3 white territory 2 white moyo 1 white area 0 neutral -1 black area -2 black moyo -3 black territory -4 black stone * move_influence: Return information about the influence function after a move. Arguments: move, what information Fails: never Returns: Influence data formatted like for initial_influence. * move_probabilities: List probabilities of each move being played (when non-zero). If no previous genmove command has been issued, the result of this command will be meaningless. Arguments: none Fails: never Returns: Move, probabilty pairs, one per row. * move_uncertainty: Return the number of bits of uncertainty in the move. If no previous genmove command has been issued, the result of this command will be meaningless. Arguments: none Fails: never Returns: bits of uncertainty * followup_influence: Return information about the followup influence after a move. Arguments: move, what information Fails: never Returns: Influence data formatted like for initial_influence. * worm_data: Return the information in the worm data structure. Arguments: optional vertex Fails: never Returns: Worm data formatted like: A19: color black size 10 effective_size 17.83 origin A19 liberties 8 liberties2 15 liberties3 10 liberties4 8 attack PASS attack_code 0 lunch B19 defend PASS defend_code 0 cutstone 2 cutstone2 0 genus 0 inessential 0 B19: color white . . . inessential 0 C19: ... If an intersection is specified, only data for this one will be returned. * worm_stones: List the stones of a worm Arguments: the location, "BLACK" or "WHITE" Fails: if called on an empty or off-board location Returns: list of stones * worm_cutstone: Return the cutstone field in the worm data structure. Arguments: non-empty vertex Fails: never Returns: cutstone * dragon_data: Return the information in the dragon data structure. Arguments: optional intersection Fails: never Returns: Dragon data formatted in the corresponding way to worm_data. * dragon_stones: List the stones of a dragon Arguments: the location Fails: if called on an empty or off-board location Returns: list of stones * eye_data: Return the information in the eye data structure. Arguments: color, vertex Fails: never Returns: eye data fields and values, one pair per row * half_eye_data: Return the information in the half eye data structure. Arguments: vertex Fails: never Returns: half eye data fields and values, one pair per row * start_sgftrace: Start storing moves executed during reading in an sgf tree in memory. Arguments: none Fails: never Returns: nothing Warning: You had better know what you're doing if you try to use this command. * finish_sgftrace: Finish storing moves in an sgf tree and write it to file. Arguments: filename Fails: never Returns: nothing Warning: You had better know what you're doing if you try to use this command. * printsgf: Dump the current position as a static sgf file to filename, or as output if filename is missing or "-" Arguments: optional filename Fails: never Returns: nothing if filename, otherwise the sgf * tune_move_ordering: Tune the parameters for the move ordering in the tactical reading. Arguments: MOVE_ORDERING_PARAMETERS integers Fails: incorrect arguments Returns: nothing * echo: Echo the parameter Arguments: string Fails: never Returns: nothing * echo_err: Echo the parameter to stdout AND stderr Arguments: string Fails: never Returns: nothing * help: List all known commands Arguments: none Fails: never Returns: list of known commands, one per line Status: GTP version 2 standard command. * known_command: Tell whether a command is known. Arguments: command name Fails: never Returns: "true" if command exists, "false" if not Status: GTP version 2 standard command. * report_uncertainty: Turn uncertainty reports from owl_attack and owl_defend on or off. Arguments: "on" or "off" Fails: invalid argument Returns: nothing * get_random_seed: Get the random seed Arguments: none Fails: never Returns: random seed * set_random_seed: Set the random seed Arguments: integer Fails: invalid data Returns: nothing * advance_random_seed: Advance the random seed by a number of games. Arguments: integer Fails: invalid data Returns: New random seed. * is_surrounded: Determine if a dragon is surrounded Arguments: vertex (dragon) Fails: invalid vertex, empty vertex Returns: 1 if surrounded, 2 if weakly surrounded, 0 if not * does_surround: Determine if a move surrounds a dragon Arguments: vertex (move), vertex (dragon) Fails: invalid vertex, empty (dragon, nonempty (move) Returns: 1 if (move) surrounds (dragon) * surround_map: Report the surround map for dragon at a vertex Arguments: vertex (dragon), vertex (mapped location) Fails: invalid vertex, empty dragon Returns: value of surround map at (mapped location), or -1 if dragon not surrounded. * set_search_diamond: limit search, and establish a search diamond Arguments: pos Fails: invalid value Returns: nothing * reset_search_mask: unmark the entire board for limited search Arguments: none Fails: never Returns: nothing * limit_search: sets the global variable limit_search Arguments: value Fails: invalid arguments Returns: nothing * set_search_limit: mark a vertex for limited search Arguments: position Fails: invalid arguments Returns: nothing * draw_search_area: Draw search area. Writes to stderr. Arguments: none Fails: never Returns: nothing  File: gnugo.info, Node: Regression, Next: Copying, Prev: GTP, Up: Top 20 Regression testing ********************* The standard purpose of regression testing is to avoid getting the same bug twice. When a bug is found, the programmer fixes the bug and adds a test to the test suite. The test should fail before the fix and pass after the fix. When a new version is about to be released, all the tests in the regression test suite are run and if an old bug reappears, this will be seen quickly since the appropriate test will fail. The regression testing in GNU Go is slightly different. A typical test case involves specifying a position and asking the engine what move it would make. This is compared to one or more correct moves to decide whether the test case passes or fails. It is also stored whether a test case is expected to pass or fail, and deviations in this status signify whether a change has solved some problem and/or broken something else. Thus the regression tests both include positions highlighting some mistake being done by the engine, which are waiting to be fixed, and positions where the engine does the right thing, where we want to detect if a change breaks something. * Menu: * Regression Testing:: Regression Testing in GNU Go * Test Suites:: Test Suites * Running the Regressions:: Running the Regression Tests * Running regress.pike:: Running regress.pike * Viewing with Emacs:: Viewing tests with Emacs * HTML Views:: HTML Views  File: gnugo.info, Node: Regression Testing, Next: Test Suites, Up: Regression 20.1 Regression testing in GNU Go ================================= Regression testing is performed by the files in the `regression/' directory. The tests are specified as GTP commands in files with the suffix `.tst', with corresponding correct results and expected pass/fail status encoded in GTP comments following the test. To run a test suite the shell scripts `test.sh', `eval.sh', and `regress.sh' can be used. There are also Makefile targets to do this. If you `make all_batches' most of the tests are run. The Pike script `regress.pike' can also be used to run all tests or a subset of the tests. Game records used by the regression tests are stored in the directory `regression/games/' and its subdirectories.  File: gnugo.info, Node: Test Suites, Next: Running the Regressions, Prev: Regression Testing, Up: Regression 20.2 Test suites ================ The regression tests are grouped into suites and stored in files as GTP commands. A part of a test suite can look as follows: # Connecting with ko at B14 looks best. Cutting at D17 might be # considered. B17 (game move) is inferior. loadsgf games/strategy25.sgf 61 90 gg_genmove black #? [B14|D17] # The game move at P13 is a suicidal blunder. loadsgf games/strategy25.sgf 249 95 gg_genmove black #? [!P13] loadsgf games/strategy26.sgf 257 100 gg_genmove black #? [M16]* Lines starting with a hash sign, or in general anything following a hash sign, are interpreted as comments by the GTP mode and thus ignored by the engine. GTP commands are executed in the order they appear, but only those on numbered lines are used for testing. The comment lines starting with `#?' are magical to the regression testing scripts and indicate correct results and expected pass/fail status. The string within brackets is matched as a regular expression against the response from the previous numbered GTP command. A particular useful feature of regular expressions is that by using `|' it is possible to specify alternatives. Thus `B14|D17' above means that if either `B14' or `D17' is the move generated in test case 90, it passes. There is one important special case to be aware of. If the correct result string starts with an exclamation mark, this is excluded from the regular expression but afterwards the result of the matching is negated. Thus `!P13' in test case 95 means that any move except `P13' is accepted as a correct result. In test case 100, the brackets on the `#?' line is followed by an asterisk. This means that the test is expected to fail. If there is no asterisk, the test is expected to pass. The brackets may also be followed by a `&', meaning that the result is ignored. This is primarily used to report statistics, e.g. how many tactical reading nodes were spent while running the test suite.  File: gnugo.info, Node: Running the Regressions, Next: Running regress.pike, Prev: Test Suites, Up: Regression 20.3 Running the Regression Tests ================================= `./test.sh blunder.tst' runs the tests in `blunder.tst' and prints the results of the commands on numbered lines, which may look like: 1 E5 2 F9 3 O18 4 B7 5 A4 6 E4 7 E3 8 A3 9 D9 10 J9 11 B3 12 C6 13 C6 This is usually not very informative, however. More interesting is `./eval.sh blunder.tst' which also compares the results above against the correct ones in the test file and prints a report for each test on the form: 1 failed: Correct '!E5', got 'E5' 2 failed: Correct 'C9|H9', got 'F9' 3 PASSED 4 failed: Correct 'B5|C5|C4|D4|E4|E3|F3', got 'B7' 5 PASSED 6 failed: Correct 'D4', got 'E4' 7 PASSED 8 failed: Correct 'B4', got 'A3' 9 failed: Correct 'G8|G9|H8', got 'D9' 10 failed: Correct 'G9|F9|C7', got 'J9' 11 failed: Correct 'D4|E4|E5|F4|C6', got 'B3' 12 failed: Correct 'D4', got 'C6' 13 failed: Correct 'D4|E4|E5|F4', got 'C6' The result of a test can be one of four different cases: * `passed': An expected pass This is the ideal result. * `PASSED': An unexpected pass This is a result that we are hoping for when we fix a bug. An old test case that used to fail is now passing. * `failed': An expected failure The test failed but this was also what we expected, unless we were trying to fix the particular mistake highlighted by the test case. These tests show weaknesses of the GNU Go engine and are good places to search if you want to detect an area which needs improvement. * `FAILED': An unexpected failure This should nominally only happen if something is broken by a change. However, sometimes GNU Go passes a test, but for the wrong reason or for a combination of wrong reasons. When one of these reasons is fixed, the other one may shine through so that the test suddenly fails. When a test case unexpectedly fails, it is necessary to make a closer examination in order to determine whether a change has broken something. If you want a less verbose report, `./regress.sh . blunder.tst' does the same thing as the previous command, but only reports unexpected results. The example above is compressed to 3 unexpected PASS! 5 unexpected PASS! 7 unexpected PASS! For convenience the tests are also available as makefile targets. For example, `make blunder' runs the tests in the blunder test suite by executing `eval.sh blunder.tst'. `make all_batches' runs all test suites in a sequence using the `regress.sh' script.  File: gnugo.info, Node: Running regress.pike, Next: Viewing with Emacs, Prev: Running the Regressions, Up: Regression 20.4 Running regress.pike ========================= A more powerful way to run regressions is with the script `regress.pike'. This requires that you have Pike (`http://pike.ida.liu.se') installed. Executing `./regress.pike' without arguments will run all testsuites that `make all_batches' would run. The difference is that unexpected results are reported immediately when they have been found (instead of after the whole file has been run) and that statistics of time consumption and node usage is presented for each test file and in total. To run a single test suite do e.g. `./regress.pike nicklas3.tst' or `./regress.pike nicklas3'. The result may look like: nicklas3 2.96 614772 3322 469 Total nodes: 614772 3322 469 Total time: 2.96 (3.22) Total uncertainty: 0.00 The numbers here mean that the test suite took 2.96 seconds of processor time and 3.22 seconds of real time. The consumption of reading nodes was 614772 for tactical reading, 3322 for owl reading, and 469 for connection reading. The last line relates to the variability of the generated moves in the test suite, and 0 means that none was decided by the randomness contribution to the move valuation. Multiple testsuites can be run by e.g. `./regress.pike owl ld_owl owl1'. It is also possible to run a single testcase, e.g. `./regress.pike strategy:6', a number of testcases, e.g. `./regress.pike strategy:6,23,45', a range of testcases, e.g. `./regress.pike strategy:13-15' or more complex combinations e.g. `./regress.pike strategy:6,13-15,23,45 nicklas3:602,1403'. There are also command line options to choose what engine to run, what options to send to the engine, to turn on verbose output, and to use a file to specify which testcases to run. Run `./regress.pike --help' for a complete and up to date list of options.  File: gnugo.info, Node: Viewing with Emacs, Next: HTML Views, Prev: Running regress.pike, Up: Regression 20.5 Viewing tests with Emacs ============================= To get a quick regression view, you may use the graphical display mode available with Emacs (*note Emacs::). You will want the cursor in the regression buffer when you enter `M-x gnugo', so that GNU Go opens in the correct directory. A good way to be in the right directory is to open the window of the test you want to investigate. Then you can cut and past GTP commands directly from the test to the minibuffer, using the `:' command from Emacs. Although Emacs mode does not have a coordinate grid, you may get an ascii board with the coordinate grid using `: showboard' command.  File: gnugo.info, Node: HTML Views, Prev: Viewing with Emacs, Up: Regression 20.6 HTML Regression Views ========================== Extremely useful HTML Views of the regression tests may be produced using two perl scripts `regression/regress.pl' and `regression/regress.plx'. 1. The driver program (regress.pl) which: * Runs the regression tests, invoking GNU Go. * Captures the trace output, board position, and pass/fail status, sgf output, and dragon status information. 2. The interface to view the captured output (regress.plx) which: * Never invokes GNU Go. * Displays the captured output in helpful formats (i.e. HTML). 20.6.1 Setting up the HTML regression Views ------------------------------------------- There are many ways configuring Apache to permit CGI scripts, all of them are featured in Apache documentation, which can be found at `http://httpd.apache.org/docs/2.0/howto/cgi.html' Below you will find one example. This documentation assumes an Apache 2.0 included in Fedora Core distribution, but it should be fairly close to the config for other distributions. First, you will need to configure Apache to run CGI scripts in the directory you wish to serve the html views from. In `/etc/httpd/conf/httpd.conf' there should be a line: `DocumentRoot "/var/www/html"' Search for a line `', where `/path/to/directory' is the same as provided in `DocumentRoot', then add `ExecCGI' to list of `Options'. The whole section should look like: ... Options ... ExecCGI ... This allows CGI scripts to be executed in the directory used by regress.plx. Next, you need to tell Apache that `.plx' is a CGI script ending. Your `httpd.conf' file should contain a line: `AddHandler cgi-script ...' If there isn't already, add it; add `.plx' to the list of extensions, so line should look like: `AddHandler cgi-script ... .plx' You will also need to make sure you have the necessary modules loaded to run CGI scripts; mod_cgi and mod_mime should be sufficient. Your `httpd.conf' should have the relevant `LoadModule cgi_module modules/mod_cgi.so' and `LoadModule mime_module modules/mod_mime.so' lines; uncomment them if necessary. Next, you need to put a copy of `regress.plx' in the `DocumentRoot' directory `/var/www/html' or it subdirectories where you plan to serve the html views from. You will also need to install the Perl module GD (`http://search.cpan.org/dist/GD/'), available from CPAN. Finally, run `regression/regress.pl' to create the xml data used to generate the html views (to do all regression tests run `regression/regress.pl -a 1'); then, copy the `html/' directory to the same directory as `regress.plx' resides in. At this point, you should have a working copy of the html regression views. Additional notes for Debian users: The Perl GD module can be installed by `apt-get install libgd-perl'. It may suffice to add this to the apache2 configuration: Options +ExecCGI AddHandler cgi-script .plx RedirectMatch ^/regression$ /regression/regress.plx and then make a link from `/var/www/regression' to the GNU Go regression directory. The `RedirectMatch' statement is only needed to set up a shorter entry URL.  File: gnugo.info, Node: Copying, Next: Concept Index, Prev: Regression, Up: Top Appendix A Copying ****************** The program GNU Go is distributed under the terms of the GNU General Public License (GPL). Its documentation is distributed under the terms of the GNU Free Documentation License (GFDL). * Menu: * GPL:: The GNU General Public License * GFDL:: The GNU Free Documentation License * GTP License:: The Go Text Protocol License  File: gnugo.info, Node: GPL, Next: GFDL, Prev: Copying, Up: Copying A.1 GNU GENERAL PUBLIC LICENSE ============================== Version 3, 29 June 2007 Copyright (C) 2007 Free Software Foundation, Inc. Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed. Preamble ======== The GNU General Public License is a free, copyleft license for software and other kinds of works. The licenses for most software and other practical works are designed to take away your freedom to share and change the works. By contrast, the GNU General Public License is intended to guarantee your freedom to share and change all versions of a program-to make sure it remains free software for all its users. We, the Free Software Foundation, use the GNU General Public License for most of our software; it applies also to any other work released this way by its authors. You can apply it to your programs, too. When we speak of free software, we are referring to freedom, not price. Our General Public Licenses are designed to make sure that you have the freedom to distribute copies of free software (and charge for them if you wish), that you receive source code or can get it if you want it, that you can change the software or use pieces of it in new free programs, and that you know you can do these things. To protect your rights, we need to prevent others from denying you these rights or asking you to surrender the rights. Therefore, you have certain responsibilities if you distribute copies of the software, or if you modify it: responsibilities to respect the freedom of others. For example, if you distribute copies of such a program, whether gratis or for a fee, you must pass on to the recipients the same freedoms that you received. You must make sure that they, too, receive or can get the source code. And you must show them these terms so they know their rights. Developers that use the GNU GPL protect your rights with two steps: (1) assert copyright on the software, and (2) offer you this License giving you legal permission to copy, distribute and/or modify it. For the developers' and authors' protection, the GPL clearly explains that there is no warranty for this free software. For both users' and authors' sake, the GPL requires that modified versions be marked as changed, so that their problems will not be attributed erroneously to authors of previous versions. Some devices are designed to deny users access to install or run modified versions of the software inside them, although the manufacturer can do so. This is fundamentally incompatible with the aim of protecting users' freedom to change the software. The systematic pattern of such abuse occurs in the area of products for individuals to use, which is precisely where it is most unacceptable. Therefore, we have designed this version of the GPL to prohibit the practice for those products. If such problems arise substantially in other domains, we stand ready to extend this provision to those domains in future versions of the GPL, as needed to protect the freedom of users. Finally, every program is threatened constantly by software patents. States should not allow patents to restrict development and use of software on general-purpose computers, but in those that do, we wish to avoid the special danger that patents applied to a free program could make it effectively proprietary. To prevent this, the GPL assures that patents cannot be used to render the program non-free. The precise terms and conditions for copying, distribution and modification follow. TERMS AND CONDITIONS 0. DEFINITIONS "This License" refers to version 3 of the GNU General Public License. "Copyright" also means copyright-like laws that apply to other kinds of works, such as semiconductor masks. "The Program" refers to any copyrightable work licensed under this License. Each licensee is addressed as "you". "Licensees" and "recipients" may be individuals or organizations. To "modify" a work means to copy from or adapt all or part of the work in a fashion requiring copyright permission, other than the making of an exact copy. The resulting work is called a "modified version" of the earlier work or a work "based on" the earlier work. A "covered work" means either the unmodified Program or a work based on the Program. To "propagate" a work means to do anything with it that, without permission, would make you directly or secondarily liable for infringement under applicable copyright law, except executing it on a computer or modifying a private copy. Propagation includes copying, distribution (with or without modification), making available to the public, and in some countries other activities as well. To "convey" a work means any kind of propagation that enables other parties to make or receive copies. Mere interaction with a user through a computer network, with no transfer of a copy, is not conveying. An interactive user interface displays "Appropriate Legal Notices" to the extent that it includes a convenient and prominently visible feature that (1) displays an appropriate copyright notice, and (2) tells the user that there is no warranty for the work (except to the extent that warranties are provided), that licensees may convey the work under this License, and how to view a copy of this License. If the interface presents a list of user commands or options, such as a menu, a prominent item in the list meets this criterion. 1. SOURCE CODE The "source code" for a work means the preferred form of the work for making modifications to it. "Object code" means any non-source form of a work. A "Standard Interface" means an interface that either is an official standard defined by a recognized standards body, or, in the case of interfaces specified for a particular programming language, one that is widely used among developers working in that language. The "System Libraries" of an executable work include anything, other than the work as a whole, that (a) is included in the normal form of packaging a Major Component, but which is not part of that Major Component, and (b) serves only to enable use of the work with that Major Component, or to implement a Standard Interface for which an implementation is available to the public in source code form. A "Major Component", in this context, means a major essential component (kernel, window system, and so on) of the specific operating system (if any) on which the executable work runs, or a compiler used to produce the work, or an object code interpreter used to run it. The "Corresponding Source" for a work in object code form means all the source code needed to generate, install, and (for an executable work) run the object code and to modify the work, including scripts to control those activities. However, it does not include the work's System Libraries, or general-purpose tools or generally available free programs which are used unmodified in performing those activities but which are not part of the work. For example, Corresponding Source includes interface definition files associated with source files for the work, and the source code for shared libraries and dynamically linked subprograms that the work is specifically designed to require, such as by intimate data communication or control flow between those subprograms and other parts of the work. The Corresponding Source need not include anything that users can regenerate automatically from other parts of the Corresponding Source. The Corresponding Source for a work in source code form is that same work. 2. BASIC PERMISSIONS All rights granted under this License are granted for the term of copyright on the Program, and are irrevocable provided the stated conditions are met. This License explicitly affirms your unlimited permission to run the unmodified Program. The output from running a covered work is covered by this License only if the output, given its content, constitutes a covered work. This License acknowledges your rights of fair use or other equivalent, as provided by copyright law. You may make, run and propagate covered works that you do not convey, without conditions so long as your license otherwise remains in force. You may convey covered works to others for the sole purpose of having them make modifications exclusively for you, or provide you with facilities for running those works, provided that you comply with the terms of this License in conveying all material for which you do not control copyright. Those thus making or running the covered works for you must do so exclusively on your behalf, under your direction and control, on terms that prohibit them from making any copies of your copyrighted material outside their relationship with you. Conveying under any other circumstances is permitted solely under the conditions stated below. Sublicensing is not allowed; section 10 makes it unnecessary. 3. PROTECTING USERS' LEGAL RIGHTS FROM ANTI-CIRCUMVENTION LAW No covered work shall be deemed part of an effective technological measure under any applicable law fulfilling obligations under article 11 of the WIPO copyright treaty adopted on 20 December 1996, or similar laws prohibiting or restricting circumvention of such measures. When you convey a covered work, you waive any legal power to forbid circumvention of technological measures to the extent such circumvention is effected by exercising rights under this License with respect to the covered work, and you disclaim any intention to limit operation or modification of the work as a means of enforcing, against the work's users, your or third parties' legal rights to forbid circumvention of technological measures. 4. CONVEYING VERBATIM COPIES You may convey verbatim copies of the Program's source code as you receive it, in any medium, provided that you conspicuously and appropriately publish on each copy an appropriate copyright notice; keep intact all notices stating that this License and any non-permissive terms added in accord with section 7 apply to the code; keep intact all notices of the absence of any warranty; and give all recipients a copy of this License along with the Program. You may charge any price or no price for each copy that you convey, and you may offer support or warranty protection for a fee. 5. CONVEYING MODIFIED SOURCE VERSIONS You may convey a work based on the Program, or the modifications to produce it from the Program, in the form of source code under the terms of section 4, provided that you also meet all of these conditions: a) The work must carry prominent notices stating that you modified it, and giving a relevant date. b) The work must carry prominent notices stating that it is released under this License and any conditions added under section 7. This requirement modifies the requirement in section 4 to "keep intact all notices". c) You must license the entire work, as a whole, under this License to anyone who comes into possession of a copy. This License will therefore apply, along with any applicable section 7 additional terms, to the whole of the work, and all its parts, regardless of how they are packaged. This License gives no permission to license the work in any other way, but it does not invalidate such permission if you have separately received it. d) If the work has interactive user interfaces, each must display Appropriate Legal Notices; however, if the Program has interactive interfaces that do not display Appropriate Legal Notices, your work need not make them do so. A compilation of a covered work with other separate and independent works, which are not by their nature extensions of the covered work, and which are not combined with it such as to form a larger program, in or on a volume of a storage or distribution medium, is called an "aggregate" if the compilation and its resulting copyright are not used to limit the access or legal rights of the compilation's users beyond what the individual works permit. Inclusion of a covered work in an aggregate does not cause this License to apply to the other parts of the aggregate. 6. CONVEYING NON-SOURCE FORMS You may convey a covered work in object code form under the terms of sections 4 and 5, provided that you also convey the machine-readable Corresponding Source under the terms of this License, in one of these ways: a) Convey the object code in, or embodied in, a physical product (including a physical distribution medium), accompanied by the Corresponding Source fixed on a durable physical medium customarily used for software interchange. b) Convey the object code in, or embodied in, a physical product (including a physical distribution medium), accompanied by a written offer, valid for at least three years and valid for as long as you offer spare parts or customer support for that product model, to give anyone who possesses the object code either (1) a copy of the Corresponding Source for all the software in the product that is covered by this License, on a durable physical medium customarily used for software interchange, for a price no more than your reasonable cost of physically performing this conveying of source, or (2) access to copy the Corresponding Source from a network server at no charge. c) Convey individual copies of the object code with a copy of the written offer to provide the Corresponding Source. This alternative is allowed only occasionally and noncommercially, and only if you received the object code with such an offer, in accord with subsection 6b. d) Convey the object code by offering access from a designated place (gratis or for a charge), and offer equivalent access to the Corresponding Source in the same way through the same place at no further charge. You need not require recipients to copy the Corresponding Source along with the object code. If the place to copy the object code is a network server, the Corresponding Source may be on a different server (operated by you or a third party) that supports equivalent copying facilities, provided you maintain clear directions next to the object code saying where to find the Corresponding Source. Regardless of what server hosts the Corresponding Source, you remain obligated to ensure that it is available for as long as needed to satisfy these requirements. e) Convey the object code using peer-to-peer transmission, provided you inform other peers where the object code and Corresponding Source of the work are being offered to the general public at no charge under subsection 6d. A separable portion of the object code, whose source code is excluded from the Corresponding Source as a System Library, need not be included in conveying the object code work. A "User Product" is either (1) a "consumer product", which means any tangible personal property which is normally used for personal, family, or household purposes, or (2) anything designed or sold for incorporation into a dwelling. In determining whether a product is a consumer product, doubtful cases shall be resolved in favor of coverage. For a particular product received by a particular user, "normally used" refers to a typical or common use of that class of product, regardless of the status of the particular user or of the way in which the particular user actually uses, or expects or is expected to use, the product. A product is a consumer product regardless of whether the product has substantial commercial, industrial or non-consumer uses, unless such uses represent the only significant mode of use of the product. "Installation Information" for a User Product means any methods, procedures, authorization keys, or other information required to install and execute modified versions of a covered work in that User Product from a modified version of its Corresponding Source. The information must suffice to ensure that the continued functioning of the modified object code is in no case prevented or interfered with solely because modification has been made. If you convey an object code work under this section in, or with, or specifically for use in, a User Product, and the conveying occurs as part of a transaction in which the right of possession and use of the User Product is transferred to the recipient in perpetuity or for a fixed term (regardless of how the transaction is characterized), the Corresponding Source conveyed under this section must be accompanied by the Installation Information. But this requirement does not apply if neither you nor any third party retains the ability to install modified object code on the User Product (for example, the work has been installed in ROM). The requirement to provide Installation Information does not include a requirement to continue to provide support service, warranty, or updates for a work that has been modified or installed by the recipient, or for the User Product in which it has been modified or installed. Access to a network may be denied when the modification itself materially and adversely affects the operation of the network or violates the rules and protocols for communication across the network. Corresponding Source conveyed, and Installation Information provided, in accord with this section must be in a format that is publicly documented (and with an implementation available to the public in source code form), and must require no special password or key for unpacking, reading or copying. 7. ADDITIONAL TERMS "Additional permissions" are terms that supplement the terms of this License by making exceptions from one or more of its conditions. Additional permissions that are applicable to the entire Program shall be treated as though they were included in this License, to the extent that they are valid under applicable law. If additional permissions apply only to part of the Program, that part may be used separately under those permissions, but the entire Program remains governed by this License without regard to the additional permissions. When you convey a copy of a covered work, you may at your option remove any additional permissions from that copy, or from any part of it. (Additional permissions may be written to require their own removal in certain cases when you modify the work.) You may place additional permissions on material, added by you to a covered work, for which you have or can give appropriate copyright permission. Notwithstanding any other provision of this License, for material you add to a covered work, you may (if authorized by the copyright holders of that material) supplement the terms of this License with terms: a) Disclaiming warranty or limiting liability differently from the terms of sections 15 and 16 of this License; or b) Requiring preservation of specified reasonable legal notices or author attributions in that material or in the Appropriate Legal Notices displayed by works containing it; or c) Prohibiting misrepresentation of the origin of that material, or requiring that modified versions of such material be marked in reasonable ways as different from the original version; or d) Limiting the use for publicity purposes of names of licensors or authors of the material; or e) Declining to grant rights under trademark law for use of some trade names, trademarks, or service marks; or f) Requiring indemnification of licensors and authors of that material by anyone who conveys the material (or modified versions of it) with contractual assumptions of liability to the recipient, for any liability that these contractual assumptions directly impose on those licensors and authors. All other non-permissive additional terms are considered "further restrictions" within the meaning of section 10. If the Program as you received it, or any part of it, contains a notice stating that it is governed by this License along with a term that is a further restriction, you may remove that term. If a license document contains a further restriction but permits relicensing or conveying under this License, you may add to a covered work material governed by the terms of that license document, provided that the further restriction does not survive such relicensing or conveying. If you add terms to a covered work in accord with this section, you must place, in the relevant source files, a statement of the additional terms that apply to those files, or a notice indicating where to find the applicable terms. Additional terms, permissive or non-permissive, may be stated in the form of a separately written license, or stated as exceptions; the above requirements apply either way. 8. TERMINATION You may not propagate or modify a covered work except as expressly provided under this License. Any attempt otherwise to propagate or modify it is void, and will automatically terminate your rights under this License (including any patent licenses granted under the third paragraph of section 11). However, if you cease all violation of this License, then your license from a particular copyright holder is reinstated (a) provisionally, unless and until the copyright holder explicitly and finally terminates your license, and (b) permanently, if the copyright holder fails to notify you of the violation by some reasonable means prior to 60 days after the cessation. Moreover, your license from a particular copyright holder is reinstated permanently if the copyright holder notifies you of the violation by some reasonable means, this is the first time you have received notice of violation of this License (for any work) from that copyright holder, and you cure the violation prior to 30 days after your receipt of the notice. Termination of your rights under this section does not terminate the licenses of parties who have received copies or rights from you under this License. If your rights have been terminated and not permanently reinstated, you do not qualify to receive new licenses for the same material under section 10. 9. ACCEPTANCE NOT REQUIRED FOR HAVING COPIES You are not required to accept this License in order to receive or run a copy of the Program. Ancillary propagation of a covered work occurring solely as a consequence of using peer-to-peer transmission to receive a copy likewise does not require acceptance. However, nothing other than this License grants you permission to propagate or modify any covered work. These actions infringe copyright if you do not accept this License. Therefore, by modifying or propagating a covered work, you indicate your acceptance of this License to do so. 10. AUTOMATIC LICENSING OF DOWNSTREAM RECIPIENTS Each time you convey a covered work, the recipient automatically receives a license from the original licensors, to run, modify and propagate that work, subject to this License. You are not responsible for enforcing compliance by third parties with this License. An "entity transaction" is a transaction transferring control of an organization, or substantially all assets of one, or subdividing an organization, or merging organizations. If propagation of a covered work results from an entity transaction, each party to that transaction who receives a copy of the work also receives whatever licenses to the work the party's predecessor in interest had or could give under the previous paragraph, plus a right to possession of the Corresponding Source of the work from the predecessor in interest, if the predecessor has it or can get it with reasonable efforts. You may not impose any further restrictions on the exercise of the rights granted or affirmed under this License. For example, you may not impose a license fee, royalty, or other charge for exercise of rights granted under this License, and you may not initiate litigation (including a cross-claim or counterclaim in a lawsuit) alleging that any patent claim is infringed by making, using, selling, offering for sale, or importing the Program or any portion of it. 11. PATENTS A "contributor" is a copyright holder who authorizes use under this License of the Program or a work on which the Program is based. The work thus licensed is called the contributor's "contributor version". A contributor's "essential patent claims" are all patent claims owned or controlled by the contributor, whether already acquired or hereafter acquired, that would be infringed by some manner, permitted by this License, of making, using, or selling its contributor version, but do not include claims that would be infringed only as a consequence of further modification of the contributor version. For purposes of this definition, "control" includes the right to grant patent sublicenses in a manner consistent with the requirements of this License. Each contributor grants you a non-exclusive, worldwide, royalty-free patent license under the contributor's essential patent claims, to make, use, sell, offer for sale, import and otherwise run, modify and propagate the contents of its contributor version. In the following three paragraphs, a "patent license" is any express agreement or commitment, however denominated, not to enforce a patent (such as an express permission to practice a patent or covenant not to sue for patent infringement). To "grant" such a patent license to a party means to make such an agreement or commitment not to enforce a patent against the party. If you convey a covered work, knowingly relying on a patent license, and the Corresponding Source of the work is not available for anyone to copy, free of charge and under the terms of this License, through a publicly available network server or other readily accessible means, then you must either (1) cause the Corresponding Source to be so available, or (2) arrange to deprive yourself of the benefit of the patent license for this particular work, or (3) arrange, in a manner consistent with the requirements of this License, to extend the patent license to downstream recipients. "Knowingly relying" means you have actual knowledge that, but for the patent license, your conveying the covered work in a country, or your recipient's use of the covered work in a country, would infringe one or more identifiable patents in that country that you have reason to believe are valid. If, pursuant to or in connection with a single transaction or arrangement, you convey, or propagate by procuring conveyance of, a covered work, and grant a patent license to some of the parties receiving the covered work authorizing them to use, propagate, modify or convey a specific copy of the covered work, then the patent license you grant is automatically extended to all recipients of the covered work and works based on it. A patent license is "discriminatory" if it does not include within the scope of its coverage, prohibits the exercise of, or is conditioned on the non-exercise of one or more of the rights that are specifically granted under this License. You may not convey a covered work if you are a party to an arrangement with a third party that is in the business of distributing software, under which you make payment to the third party based on the extent of your activity of conveying the work, and under which the third party grants, to any of the parties who would receive the covered work from you, a discriminatory patent license (a) in connection with copies of the covered work conveyed by you (or copies made from those copies), or (b) primarily for and in connection with specific products or compilations that contain the covered work, unless you entered into that arrangement, or that patent license was granted, prior to 28 March 2007. Nothing in this License shall be construed as excluding or limiting any implied license or other defenses to infringement that may otherwise be available to you under applicable patent law. 12. NO SURRENDER OF OTHERS' FREEDOM If conditions are imposed on you (whether by court order, agreement or otherwise) that contradict the conditions of this License, they do not excuse you from the conditions of this License. If you cannot convey a covered work so as to satisfy simultaneously your obligations under this License and any other pertinent obligations, then as a consequence you may not convey it at all. For example, if you agree to terms that obligate you to collect a royalty for further conveying from those to whom you convey the Program, the only way you could satisfy both those terms and this License would be to refrain entirely from conveying the Program. 13. USE WITH THE GNU AFFERO GENERAL PUBLIC LICENSE Notwithstanding any other provision of this License, you have permission to link or combine any covered work with a work licensed under version 3 of the GNU Affero General Public License into a single combined work, and to convey the resulting work. The terms of this License will continue to apply to the part which is the covered work, but the special requirements of the GNU Affero General Public License, section 13, concerning interaction through a network will apply to the combination as such. 14. REVISED VERSIONS OF THIS LICENSE The Free Software Foundation may publish revised and/or new versions of the GNU General Public License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. Each version is given a distinguishing version number. If the Program specifies that a certain numbered version of the GNU General Public License "or any later version" applies to it, you have the option of following the terms and conditions either of that numbered version or of any later version published by the Free Software Foundation. If the Program does not specify a version number of the GNU General Public License, you may choose any version ever published by the Free Software Foundation. If the Program specifies that a proxy can decide which future versions of the GNU General Public License can be used, that proxy's public statement of acceptance of a version permanently authorizes you to choose that version for the Program. Later license versions may give you additional or different permissions. However, no additional obligations are imposed on any author or copyright holder as a result of your choosing to follow a later version. 15. DISCLAIMER OF WARRANTY THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. 16. LIMITATION OF LIABILITY. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MODIFIES AND/OR CONVEYS THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. 17. INTERPRETATION OF SECTIONS 15 AND 16 If the disclaimer of warranty and limitation of liability provided above cannot be given local legal effect according to their terms, reviewing courts shall apply local law that most closely approximates an absolute waiver of all civil liability in connection with the Program, unless a warranty or assumption of liability accompanies a copy of the Program in return for a fee. How to Apply These Terms to your New Programs ============================================= If you develop a new program, and you want it to be of the greatest possible use to the public, the best way to achieve this is to make it free software which everyone can redistribute and change under these terms. To do so, attach the following notices to the program. It is safest to attach them to the start of each source file to most effectively state the exclusion of warranty; and each file should have at least the "copyright" line and a pointer to where the full notice is found. Copyright (C) This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . Also add information on how to contact you by electronic and paper mail. If the program does terminal interaction, make it output a short notice like this when it starts in an interactive mode: Copyright (C) This program comes with ABSOLUTELY NO WARRANTY; for details type `show w'. This is free software, and you are welcome to redistribute it under certain conditions; type `show c' for details. The hypothetical commands `show w' and `show c' should show the appropriate parts of the General Public License. Of course, your program's commands might be different; for a GUI interface, you would use an "about box". You should also get your employer (if you work as a programmer) or school, if any, to sign a "copyright disclaimer" for the program, if necessary. For more information on this, and how to apply and follow the GNU GPL, see . The GNU General Public License does not permit incorporating your program into proprietary programs. If your program is a subroutine library, you may consider it more useful to permit linking proprietary applications with the library. If this is what you want to do, use the GNU Lesser General Public License instead of this License. But first, please read .  File: gnugo.info, Node: GFDL, Next: GTP License, Prev: GPL, Up: Copying A.2 GNU FREE DOCUMENTATION LICENSE ================================== Version 1.3, 3 November 2008 Copyright (C) 2000, 2001, 2002, 2007, 2008 Free Software Foundation, Inc. `http://fsf.org/' Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed. 0. PREAMBLE The purpose of this License is to make a manual, textbook, or other functional and useful document "free" in the sense of freedom: to assure everyone the effective freedom to copy and redistribute it, with or without modifying it, either commercially or noncommercially. Secondarily, this License preserves for the author and publisher a way to get credit for their work, while not being considered responsible for modifications made by others. This License is a kind of "copyleft", which means that derivative works of the document must themselves be free in the same sense. It complements the GNU General Public License, which is a copyleft license designed for free software. We have designed this License in order to use it for manuals for free software, because free software needs free documentation: a free program should come with manuals providing the same freedoms that the software does. But this License is not limited to software manuals; it can be used for any textual work, regardless of subject matter or whether it is published as a printed book. We recommend this License principally for works whose purpose is instruction or reference. 1. APPLICABILITY AND DEFINITIONS This License applies to any manual or other work, in any medium, that contains a notice placed by the copyright holder saying it can be distributed under the terms of this License. Such a notice grants a world-wide, royalty-free license, unlimited in duration, to use that work under the conditions stated herein. The "Document", below, refers to any such manual or work. Any member of the public is a licensee, and is addressed as "you". You accept the license if you copy, modify or distribute the work in a way requiring permission under copyright law. A "Modified Version" of the Document means any work containing the Document or a portion of it, either copied verbatim, or with modifications and/or translated into another language. A "Secondary Section" is a named appendix or a front-matter section of the Document that deals exclusively with the relationship of the publishers or authors of the Document to the Document's overall subject (or to related matters) and contains nothing that could fall directly within that overall subject. (Thus, if the Document is in part a textbook of mathematics, a Secondary Section may not explain any mathematics.) The relationship could be a matter of historical connection with the subject or with related matters, or of legal, commercial, philosophical, ethical or political position regarding them. The "Invariant Sections" are certain Secondary Sections whose titles are designated, as being those of Invariant Sections, in the notice that says that the Document is released under this License. If a section does not fit the above definition of Secondary then it is not allowed to be designated as Invariant. The Document may contain zero Invariant Sections. If the Document does not identify any Invariant Sections then there are none. The "Cover Texts" are certain short passages of text that are listed, as Front-Cover Texts or Back-Cover Texts, in the notice that says that the Document is released under this License. A Front-Cover Text may be at most 5 words, and a Back-Cover Text may be at most 25 words. A "Transparent" copy of the Document means a machine-readable copy, represented in a format whose specification is available to the general public, that is suitable for revising the document straightforwardly with generic text editors or (for images composed of pixels) generic paint programs or (for drawings) some widely available drawing editor, and that is suitable for input to text formatters or for automatic translation to a variety of formats suitable for input to text formatters. A copy made in an otherwise Transparent file format whose markup, or absence of markup, has been arranged to thwart or discourage subsequent modification by readers is not Transparent. An image format is not Transparent if used for any substantial amount of text. A copy that is not "Transparent" is called "Opaque". Examples of suitable formats for Transparent copies include plain ASCII without markup, Texinfo input format, LaTeX input format, SGML or XML using a publicly available DTD, and standard-conforming simple HTML, PostScript or PDF designed for human modification. Examples of transparent image formats include PNG, XCF and JPG. Opaque formats include proprietary formats that can be read and edited only by proprietary word processors, SGML or XML for which the DTD and/or processing tools are not generally available, and the machine-generated HTML, PostScript or PDF produced by some word processors for output purposes only. The "Title Page" means, for a printed book, the title page itself, plus such following pages as are needed to hold, legibly, the material this License requires to appear in the title page. For works in formats which do not have any title page as such, "Title Page" means the text near the most prominent appearance of the work's title, preceding the beginning of the body of the text. The "publisher" means any person or entity that distributes copies of the Document to the public. A section "Entitled XYZ" means a named subunit of the Document whose title either is precisely XYZ or contains XYZ in parentheses following text that translates XYZ in another language. (Here XYZ stands for a specific section name mentioned below, such as "Acknowledgements", "Dedications", "Endorsements", or "History".) To "Preserve the Title" of such a section when you modify the Document means that it remains a section "Entitled XYZ" according to this definition. The Document may include Warranty Disclaimers next to the notice which states that this License applies to the Document. These Warranty Disclaimers are considered to be included by reference in this License, but only as regards disclaiming warranties: any other implication that these Warranty Disclaimers may have is void and has no effect on the meaning of this License. 2. VERBATIM COPYING You may copy and distribute the Document in any medium, either commercially or noncommercially, provided that this License, the copyright notices, and the license notice saying this License applies to the Document are reproduced in all copies, and that you add no other conditions whatsoever to those of this License. You may not use technical measures to obstruct or control the reading or further copying of the copies you make or distribute. However, you may accept compensation in exchange for copies. If you distribute a large enough number of copies you must also follow the conditions in section 3. You may also lend copies, under the same conditions stated above, and you may publicly display copies. 3. COPYING IN QUANTITY If you publish printed copies (or copies in media that commonly have printed covers) of the Document, numbering more than 100, and the Document's license notice requires Cover Texts, you must enclose the copies in covers that carry, clearly and legibly, all these Cover Texts: Front-Cover Texts on the front cover, and Back-Cover Texts on the back cover. Both covers must also clearly and legibly identify you as the publisher of these copies. The front cover must present the full title with all words of the title equally prominent and visible. You may add other material on the covers in addition. Copying with changes limited to the covers, as long as they preserve the title of the Document and satisfy these conditions, can be treated as verbatim copying in other respects. If the required texts for either cover are too voluminous to fit legibly, you should put the first ones listed (as many as fit reasonably) on the actual cover, and continue the rest onto adjacent pages. If you publish or distribute Opaque copies of the Document numbering more than 100, you must either include a machine-readable Transparent copy along with each Opaque copy, or state in or with each Opaque copy a computer-network location from which the general network-using public has access to download using public-standard network protocols a complete Transparent copy of the Document, free of added material. If you use the latter option, you must take reasonably prudent steps, when you begin distribution of Opaque copies in quantity, to ensure that this Transparent copy will remain thus accessible at the stated location until at least one year after the last time you distribute an Opaque copy (directly or through your agents or retailers) of that edition to the public. It is requested, but not required, that you contact the authors of the Document well before redistributing any large number of copies, to give them a chance to provide you with an updated version of the Document. 4. MODIFICATIONS You may copy and distribute a Modified Version of the Document under the conditions of sections 2 and 3 above, provided that you release the Modified Version under precisely this License, with the Modified Version filling the role of the Document, thus licensing distribution and modification of the Modified Version to whoever possesses a copy of it. In addition, you must do these things in the Modified Version: A. Use in the Title Page (and on the covers, if any) a title distinct from that of the Document, and from those of previous versions (which should, if there were any, be listed in the History section of the Document). You may use the same title as a previous version if the original publisher of that version gives permission. B. List on the Title Page, as authors, one or more persons or entities responsible for authorship of the modifications in the Modified Version, together with at least five of the principal authors of the Document (all of its principal authors, if it has fewer than five), unless they release you from this requirement. C. State on the Title page the name of the publisher of the Modified Version, as the publisher. D. Preserve all the copyright notices of the Document. E. Add an appropriate copyright notice for your modifications adjacent to the other copyright notices. F. Include, immediately after the copyright notices, a license notice giving the public permission to use the Modified Version under the terms of this License, in the form shown in the Addendum below. G. Preserve in that license notice the full lists of Invariant Sections and required Cover Texts given in the Document's license notice. H. Include an unaltered copy of this License. I. Preserve the section Entitled "History", Preserve its Title, and add to it an item stating at least the title, year, new authors, and publisher of the Modified Version as given on the Title Page. If there is no section Entitled "History" in the Document, create one stating the title, year, authors, and publisher of the Document as given on its Title Page, then add an item describing the Modified Version as stated in the previous sentence. J. Preserve the network location, if any, given in the Document for public access to a Transparent copy of the Document, and likewise the network locations given in the Document for previous versions it was based on. These may be placed in the "History" section. You may omit a network location for a work that was published at least four years before the Document itself, or if the original publisher of the version it refers to gives permission. K. For any section Entitled "Acknowledgements" or "Dedications", Preserve the Title of the section, and preserve in the section all the substance and tone of each of the contributor acknowledgements and/or dedications given therein. L. Preserve all the Invariant Sections of the Document, unaltered in their text and in their titles. Section numbers or the equivalent are not considered part of the section titles. M. Delete any section Entitled "Endorsements". Such a section may not be included in the Modified Version. N. Do not retitle any existing section to be Entitled "Endorsements" or to conflict in title with any Invariant Section. O. Preserve any Warranty Disclaimers. If the Modified Version includes new front-matter sections or appendices that qualify as Secondary Sections and contain no material copied from the Document, you may at your option designate some or all of these sections as invariant. To do this, add their titles to the list of Invariant Sections in the Modified Version's license notice. These titles must be distinct from any other section titles. You may add a section Entitled "Endorsements", provided it contains nothing but endorsements of your Modified Version by various parties--for example, statements of peer review or that the text has been approved by an organization as the authoritative definition of a standard. You may add a passage of up to five words as a Front-Cover Text, and a passage of up to 25 words as a Back-Cover Text, to the end of the list of Cover Texts in the Modified Version. Only one passage of Front-Cover Text and one of Back-Cover Text may be added by (or through arrangements made by) any one entity. If the Document already includes a cover text for the same cover, previously added by you or by arrangement made by the same entity you are acting on behalf of, you may not add another; but you may replace the old one, on explicit permission from the previous publisher that added the old one. The author(s) and publisher(s) of the Document do not by this License give permission to use their names for publicity for or to assert or imply endorsement of any Modified Version. 5. COMBINING DOCUMENTS You may combine the Document with other documents released under this License, under the terms defined in section 4 above for modified versions, provided that you include in the combination all of the Invariant Sections of all of the original documents, unmodified, and list them all as Invariant Sections of your combined work in its license notice, and that you preserve all their Warranty Disclaimers. The combined work need only contain one copy of this License, and multiple identical Invariant Sections may be replaced with a single copy. If there are multiple Invariant Sections with the same name but different contents, make the title of each such section unique by adding at the end of it, in parentheses, the name of the original author or publisher of that section if known, or else a unique number. Make the same adjustment to the section titles in the list of Invariant Sections in the license notice of the combined work. In the combination, you must combine any sections Entitled "History" in the various original documents, forming one section Entitled "History"; likewise combine any sections Entitled "Acknowledgements", and any sections Entitled "Dedications". You must delete all sections Entitled "Endorsements." 6. COLLECTIONS OF DOCUMENTS You may make a collection consisting of the Document and other documents released under this License, and replace the individual copies of this License in the various documents with a single copy that is included in the collection, provided that you follow the rules of this License for verbatim copying of each of the documents in all other respects. You may extract a single document from such a collection, and distribute it individually under this License, provided you insert a copy of this License into the extracted document, and follow this License in all other respects regarding verbatim copying of that document. 7. AGGREGATION WITH INDEPENDENT WORKS A compilation of the Document or its derivatives with other separate and independent documents or works, in or on a volume of a storage or distribution medium, is called an "aggregate" if the copyright resulting from the compilation is not used to limit the legal rights of the compilation's users beyond what the individual works permit. When the Document is included in an aggregate, this License does not apply to the other works in the aggregate which are not themselves derivative works of the Document. If the Cover Text requirement of section 3 is applicable to these copies of the Document, then if the Document is less than one half of the entire aggregate, the Document's Cover Texts may be placed on covers that bracket the Document within the aggregate, or the electronic equivalent of covers if the Document is in electronic form. Otherwise they must appear on printed covers that bracket the whole aggregate. 8. TRANSLATION Translation is considered a kind of modification, so you may distribute translations of the Document under the terms of section 4. Replacing Invariant Sections with translations requires special permission from their copyright holders, but you may include translations of some or all Invariant Sections in addition to the original versions of these Invariant Sections. You may include a translation of this License, and all the license notices in the Document, and any Warranty Disclaimers, provided that you also include the original English version of this License and the original versions of those notices and disclaimers. In case of a disagreement between the translation and the original version of this License or a notice or disclaimer, the original version will prevail. If a section in the Document is Entitled "Acknowledgements", "Dedications", or "History", the requirement (section 4) to Preserve its Title (section 1) will typically require changing the actual title. 9. TERMINATION You may not copy, modify, sublicense, or distribute the Document except as expressly provided under this License. Any attempt otherwise to copy, modify, sublicense, or distribute it is void, and will automatically terminate your rights under this License. However, if you cease all violation of this License, then your license from a particular copyright holder is reinstated (a) provisionally, unless and until the copyright holder explicitly and finally terminates your license, and (b) permanently, if the copyright holder fails to notify you of the violation by some reasonable means prior to 60 days after the cessation. Moreover, your license from a particular copyright holder is reinstated permanently if the copyright holder notifies you of the violation by some reasonable means, this is the first time you have received notice of violation of this License (for any work) from that copyright holder, and you cure the violation prior to 30 days after your receipt of the notice. Termination of your rights under this section does not terminate the licenses of parties who have received copies or rights from you under this License. If your rights have been terminated and not permanently reinstated, receipt of a copy of some or all of the same material does not give you any rights to use it. 10. FUTURE REVISIONS OF THIS LICENSE The Free Software Foundation may publish new, revised versions of the GNU Free Documentation License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. See `http://www.gnu.org/copyleft/'. Each version of the License is given a distinguishing version number. If the Document specifies that a particular numbered version of this License "or any later version" applies to it, you have the option of following the terms and conditions either of that specified version or of any later version that has been published (not as a draft) by the Free Software Foundation. If the Document does not specify a version number of this License, you may choose any version ever published (not as a draft) by the Free Software Foundation. If the Document specifies that a proxy can decide which future versions of this License can be used, that proxy's public statement of acceptance of a version permanently authorizes you to choose that version for the Document. 11. RELICENSING "Massive Multiauthor Collaboration Site" (or "MMC Site") means any World Wide Web server that publishes copyrightable works and also provides prominent facilities for anybody to edit those works. A public wiki that anybody can edit is an example of such a server. A "Massive Multiauthor Collaboration" (or "MMC") contained in the site means any set of copyrightable works thus published on the MMC site. "CC-BY-SA" means the Creative Commons Attribution-Share Alike 3.0 license published by Creative Commons Corporation, a not-for-profit corporation with a principal place of business in San Francisco, California, as well as future copyleft versions of that license published by that same organization. "Incorporate" means to publish or republish a Document, in whole or in part, as part of another Document. An MMC is "eligible for relicensing" if it is licensed under this License, and if all works that were first published under this License somewhere other than this MMC, and subsequently incorporated in whole or in part into the MMC, (1) had no cover texts or invariant sections, and (2) were thus incorporated prior to November 1, 2008. The operator of an MMC Site may republish an MMC contained in the site under CC-BY-SA on the same site at any time before August 1, 2009, provided the MMC is eligible for relicensing. ADDENDUM: How to use this License for your documents ==================================================== To use this License in a document you have written, include a copy of the License in the document and put the following copyright and license notices just after the title page: Copyright (C) YEAR YOUR NAME. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled ``GNU Free Documentation License''. If you have Invariant Sections, Front-Cover Texts and Back-Cover Texts, replace the "with...Texts." line with this: with the Invariant Sections being LIST THEIR TITLES, with the Front-Cover Texts being LIST, and with the Back-Cover Texts being LIST. If you have Invariant Sections without Cover Texts, or some other combination of the three, merge those two alternatives to suit the situation. If your document contains nontrivial examples of program code, we recommend releasing these examples in parallel under your choice of free software license, such as the GNU General Public License, to permit their use in free software.  File: gnugo.info, Node: GTP License, Prev: GFDL, Up: Copying A.3 The Go Text Protocol License ================================ In order to facilitate the use of the Go Text Protocol, the two files `gtp.c' and `gtp.h' are licensed under the following terms. Copyright 2001 by the Free Software Foundation. Permission is hereby granted, free of charge, to any person obtaining a copy of this file `gtp.x', to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, provided that the above copyright notice(s) and this permission notice appear in all copies of the Software and that both the above copyright notice(s) and this permission notice appear in supporting documentation. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. Except as contained in this notice, the name of a copyright holder shall not be used in advertising or otherwise to promote the sale, use or other dealings in this Software without prior written authorization of the copyright holder.  File: gnugo.info, Node: Concept Index, Next: Functions Index, Prev: Copying, Up: Top Concept Index ************* [index] * Menu: * aa_confirm_safety: GTP command reference. (line 492) * accurate_approxlib: GTP command reference. (line 207) * accuratelib: GTP command reference. (line 200) * adjacent dragons: Dragons. (line 145) * advance_random_seed: GTP command reference. (line 960) * all_legal: GTP command reference. (line 223) * amalgamation of worms into dragons: Amalgamation. (line 6) * analyze_eyegraph: GTP command reference. (line 710) * analyze_semeai: GTP command reference. (line 400) * analyze_semeai_after_move: GTP command reference. (line 406) * API: API. (line 26) * area: Territory and Moyo. (line 6) * ascii description of shapes: Patterns Overview. (line 27) * ascii interface: Ascii. (line 6) * ascii mode: Invoking GNU Go. (line 336) * attack: GTP command reference. (line 288) * attack shapes database: Patterns Overview. (line 6) * attack_either: GTP command reference. (line 294) * autohelper actions: Autohelper Actions. (line 6) * Autohelpers: Autohelpers and Constraints. (line 6) * automaton: DFA. (line 29) * black: GTP command reference. (line 111) * block_off: GTP command reference. (line 437) * board_state: The Board State. (line 6) * boardsize: GTP command reference. (line 63) * break_in: GTP command reference. (line 431) * cache: Invoking GNU Go. (line 119) * cache-size: Invoking GNU Go. (line 119) * captures: GTP command reference. (line 229) * CGoban: CGoban. (line 6) * clear_board: GTP command reference. (line 77) * clear_cache: GTP command reference. (line 284) * color: GTP command reference. (line 175) * color (dragon): Dragons. (line 98) * colored display <1>: Dragons in Color. (line 6) * colored display: Colored Display. (line 6) * combination_attack: GTP command reference. (line 479) * combination_defend: GTP command reference. (line 485) * command line options: Invoking GNU Go. (line 6) * connect: GTP command reference. (line 419) * connection shapes database <1>: Connections Database. (line 6) * connection shapes database: Patterns Overview. (line 6) * connections: Connection. (line 6) * connections database: Connections Database. (line 6) * corner matcher: Corner Matcher. (line 6) * countlib: GTP command reference. (line 187) * cputime: GTP command reference. (line 717) * cutting stone: Worms. (line 124) * cutting stone, potential: Worms. (line 133) * data structures: Basic Data Structures. (line 6) * debugging on a graphical board: view.pike. (line 6) * debugging options: Invoking GNU Go. (line 415) * Debugging the reading code: Debugging. (line 6) * decide-dragon: Decide dragon. (line 6) * decide-string: Decide string. (line 6) * decrease_depths: GTP command reference. (line 334) * defence shapes database: Patterns Overview. (line 6) * defend: GTP command reference. (line 302) * defend_both: GTP command reference. (line 385) * depth: Invoking GNU Go. (line 242) * Depth of reading: Tactical Reading. (line 6) * description of shapes: Patterns Overview. (line 27) * dfa: DFA. (line 29) * dfa.c: DFA. (line 29) * dfa.h: DFA. (line 29) * disconnect: GTP command reference. (line 425) * distance from liberty to dragon: Worms. (line 109) * does_attack: GTP command reference. (line 308) * does_defend: GTP command reference. (line 315) * does_surround: GTP command reference. (line 972) * dragon: Worms and Dragons. (line 27) * dragon escape_route: Dragons. (line 207) * dragon genus: Dragons. (line 213) * dragon lunch: Dragons. (line 230) * dragon number: Dragons. (line 100) * dragon origin: Dragons. (line 104) * dragon safety: Dragons. (line 176) * dragon size: Dragons. (line 112) * dragon status: Dragons. (line 131) * dragon weakness: Dragons. (line 199) * dragon_data: GTP command reference. (line 854) * dragon_status: GTP command reference. (line 452) * dragon_stones: GTP command reference. (line 860) * dragons: Dragons. (line 6) * draw_search_area: GTP command reference. (line 1008) * dump_stack: GTP command reference. (line 731) * echo: GTP command reference. (line 913) * echo_err: GTP command reference. (line 919) * editing pattern database: Editing Patterns. (line 6) * editing patterns: Editing Patterns. (line 6) * effective size: Dragons. (line 116) * effective size (worm): Worms. (line 48) * eliminate the randomness: Tuning. (line 155) * emacs mode: Emacs. (line 6) * escape_route: Dragons. (line 207) * estimate_score: GTP command reference. (line 621) * eval_eye: GTP command reference. (line 444) * experimental_score: GTP command reference. (line 626) * eye shapes database: Patterns Overview. (line 6) * eye space display: Colored Display. (line 48) * eye_data: GTP command reference. (line 866) * false eye: Half Eyes. (line 6) * fast pattern matching: DFA. (line 29) * final_score: GTP command reference. (line 589) * final_status: GTP command reference. (line 597) * final_status_list: GTP command reference. (line 605) * findlib: GTP command reference. (line 193) * finish_sgftrace: GTP command reference. (line 889) * finite state automaton: DFA. (line 29) * fixed_handicap: GTP command reference. (line 135) * FIXME: Coding Styles. (line 83) * followup_influence: GTP command reference. (line 799) * format of the pattern database: Patterns Overview. (line 27) * formatted printing: Print Utilities. (line 6) * GDB <1>: Debugging. (line 30) * GDB: GTP and GDB techniques. (line 6) * generation of helper functions: Autohelpers and Constraints. (line 6) * genmove: GTP command reference. (line 512) * genmove_black: GTP command reference. (line 496) * genmove_white: GTP command reference. (line 504) * genus: Dragons. (line 213) * genus (worm): Worms. (line 155) * get_connection_node_counter: GTP command reference. (line 697) * get_handicap: GTP command reference. (line 160) * get_komi: GTP command reference. (line 105) * get_life_node_counter: GTP command reference. (line 646) * get_owl_node_counter: GTP command reference. (line 661) * get_random_seed: GTP command reference. (line 948) * get_reading_node_counter: GTP command reference. (line 673) * get_trymove_counter: GTP command reference. (line 685) * gg-undo: GTP command reference. (line 571) * gg_genmove: GTP command reference. (line 529) * GMP: GMP and GTP. (line 6) * GNU Go's GDB commands: Debugging. (line 82) * go position: Hash Calculation. (line 10) * grid optimization: Details. (line 6) * GTP <1>: GTP and GDB techniques. (line 6) * GTP: GMP and GTP. (line 6) * GTP command reference: GTP command reference. (line 6) * half eye: Half Eyes. (line 6) * half_eye_data: GTP command reference. (line 872) * Hash node: Hash Organization. (line 8) * Hashing of positions: Hashing. (line 6) * help: GTP command reference. (line 925) * helper functions in pattern matching: Helper Functions. (line 6) * how GNU Go learns new joseki: Joseki Compiler. (line 6) * How to debug the reading code: Debugging. (line 6) * implementation of pattern matching <1>: Corner Matcher. (line 6) * implementation of pattern matching: PM Implementation. (line 6) * increase_depths: GTP command reference. (line 328) * inessential string: Worms. (line 165) * initial_influence: GTP command reference. (line 737) * installation: GNU/Linux and Unix. (line 6) * invariant_hash: GTP command reference. (line 248) * invariant_hash_for_moves: GTP command reference. (line 255) * invincible worm: Worms. (line 178) * invoking GNU Go: Invoking GNU Go. (line 6) * is_legal: GTP command reference. (line 217) * is_surrounded: GTP command reference. (line 966) * jago: Other Clients. (line 6) * joseki <1>: Corner Matcher. (line 6) * joseki: Joseki Compiler. (line 6) * kgs-genmove_cleanup: GTP command reference. (line 544) * known_command: GTP command reference. (line 933) * komi: GTP command reference. (line 97) * ladder_attack: GTP command reference. (line 322) * last_move: GTP command reference. (line 235) * level <1>: GTP command reference. (line 557) * level: Invoking GNU Go. (line 225) * level of play: Invoking GNU Go. (line 25) * liberties (worm): Worms. (line 74) * liberties, higher order (worm): Worms. (line 74) * licence, documentation (GFDL): GFDL. (line 3) * licence, program (GPL): GPL. (line 3) * limit_search: GTP command reference. (line 996) * list_stones: GTP command reference. (line 181) * loadsgf: GTP command reference. (line 166) * lunch: Dragons. (line 230) * lunch (worm): Worms. (line 114) * matchpat.c: DFA. (line 29) * Monte Carlo Go: Monte Carlo Go. (line 6) * move generation: Move Generators. (line 6) * move generators: Move Generators. (line 6) * move reasons <1>: Move Reasons. (line 6) * move reasons: Move Generators. (line 6) * move_history: GTP command reference. (line 241) * move_influence: GTP command reference. (line 776) * move_probabilities: GTP command reference. (line 783) * move_uncertainty: GTP command reference. (line 791) * moyo: Territory and Moyo. (line 6) * name: GTP command reference. (line 47) * neighbor dragons: Dragons. (line 145) * orientation: GTP command reference. (line 85) * origin (worm): Worms. (line 58) * output file: Output File. (line 6) * owl_attack: GTP command reference. (line 340) * owl_attack_certain: Dragons. (line 296) * owl_attack_code: Dragons. (line 291) * owl_attack_point: Dragons. (line 286) * owl_connection_defends: GTP command reference. (line 378) * owl_defend: GTP command reference. (line 346) * owl_defense_certain: Dragons. (line 314) * owl_defense_code: Dragons. (line 309) * owl_defense_point: Dragons. (line 305) * owl_does_attack: GTP command reference. (line 366) * owl_does_defend: GTP command reference. (line 372) * owl_second_attack_point: Dragons. (line 301) * owl_second_defense_point: Dragons. (line 319) * owl_substantial: GTP command reference. (line 393) * owl_threaten_attack: GTP command reference. (line 352) * owl_threaten_defense: GTP command reference. (line 359) * pattern attributes: Pattern Classification. (line 6) * pattern database <1>: DFA. (line 29) * pattern database: Patterns Overview. (line 6) * pattern matching <1>: DFA. (line 29) * pattern matching: Patterns Overview. (line 6) * pattern matching optimization: Details. (line 6) * pattern overview: Patterns Overview. (line 6) * pattern.c: Patterns Overview. (line 6) * pattern.h: Patterns Overview. (line 6) * persistent cache: Persistent Cache. (line 6) * place_free_handicap: GTP command reference. (line 143) * play: GTP command reference. (line 127) * playwhite: GTP command reference. (line 119) * popgo: GTP command reference. (line 277) * position: Hash Calculation. (line 10) * position struct: Basic Data Structures. (line 6) * potential cutting stone: Worms. (line 133) * printsgf: GTP command reference. (line 899) * product: DFA. (line 29) * protocol_version: GTP command reference. (line 39) * qGo: Other Clients. (line 6) * quarry: Other Clients. (line 6) * query_boardsize: GTP command reference. (line 71) * query_orientation: GTP command reference. (line 91) * quit: GTP command reference. (line 33) * Read result: Hash Organization. (line 8) * Reading code: Tactical Reading. (line 6) * Reading code debugging tools: Debugging. (line 6) * reading DEPTH: Tactical Reading. (line 6) * Reading optimisation: Hashing. (line 6) * Reading process: Tactical Reading. (line 6) * reading return codes: Reading Basics. (line 51) * reading shadow: Persistent Cache. (line 50) * reading.c <1>: Reading Basics. (line 122) * reading.c: Tactical Reading. (line 6) * reading.h: Tactical Reading. (line 6) * reg_genmove: GTP command reference. (line 521) * report_uncertainty: GTP command reference. (line 941) * reset_connection_node_counter: GTP command reference. (line 691) * reset_life_node_counter: GTP command reference. (line 637) * reset_owl_node_counter: GTP command reference. (line 655) * reset_reading_node_counter: GTP command reference. (line 667) * reset_search_mask: GTP command reference. (line 990) * reset_trymove_counter: GTP command reference. (line 679) * restricted_genmove: GTP command reference. (line 537) * return codes: Reading Basics. (line 51) * same_dragon: GTP command reference. (line 464) * scoring: Scoring. (line 6) * semeai: Dragons. (line 254) * semeai_attack_certain: Dragons. (line 254) * semeai_attack_point: Dragons. (line 254) * semeai_defense_certain: Dragons. (line 254) * semeai_defense_point: Dragons. (line 254) * set_free_handicap: GTP command reference. (line 152) * set_random_seed: GTP command reference. (line 954) * set_search_diamond: GTP command reference. (line 984) * set_search_limit: GTP command reference. (line 1002) * SGF (Smart Game Format): SGF Support. (line 6) * SGF files in memory: SGF. (line 6) * shape attributes: Pattern Classification. (line 6) * showboard: GTP command reference. (line 723) * Smart Game Format: SGF Support. (line 6) * Speedup of reading process: Hashing. (line 6) * start_sgftrace: GTP command reference. (line 879) * string: Worms and Dragons. (line 27) * superstring: General Utilities. (line 249) * surround: Dragons. (line 238) * surround_map: GTP command reference. (line 979) * surround_size: Dragons. (line 238) * surround_status: Dragons. (line 238) * symmetry and transformations: Symmetry & transformations. (line 6) * symmetry and transformations of shapes: Symmetry & transformations. (line 6) * tactical_analyze_semeai: GTP command reference. (line 413) * teaching josekis to GNU Go: Joseki Compiler. (line 6) * territory: Territory and Moyo. (line 6) * test_eyeshape: GTP command reference. (line 704) * The Go Modem Protocol and Go Text Protocol: GMP and GTP. (line 6) * the joseki compiler: Joseki Compiler. (line 6) * time_left: GTP command reference. (line 583) * time_settings: GTP command reference. (line 576) * timers: General Utilities. (line 328) * traces: Traces. (line 6) * Transposition table: Hashing. (line 6) * Trying hypothetical moves: Tactical Reading. (line 6) * tryko: GTP command reference. (line 270) * trymove: GTP command reference. (line 264) * tune_move_ordering: GTP command reference. (line 906) * tuning GNU Go: Traces. (line 6) * tuning the pattern database: Tuning. (line 6) * tuning the shapes database: Tuning. (line 6) * UCT algorithm: Monte Carlo Go. (line 6) * unconditional_status: GTP command reference. (line 470) * undo: GTP command reference. (line 564) * Usage of the stack in reading: Tactical Reading. (line 6) * version: GTP command reference. (line 55) * weakness: Dragons. (line 199) * worm <1>: Worms. (line 6) * worm: Worms and Dragons. (line 27) * worm_cutstone: GTP command reference. (line 847) * worm_data: GTP command reference. (line 806) * worm_stones: GTP command reference. (line 841) * Zobrist hashing algorithm: Hashing. (line 6)