[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] doc patch
|
From: |
Arend Bayer |
|
Subject: |
[gnugo-devel] doc patch |
|
Date: |
Sun, 29 Jun 2003 00:55:47 +0200 (CEST) |
That's the doc patch that I had mentioned.
A couple of comments on the current docs, sorted to be increasingly
polemic :-)
- incremental.texi should be part of board.texi
- "Pattern Based Reading" should be called "Life and Death Reading"
- The technical chapters on API, handling SGF trees, and the board
library should be moved more to the end.
- I still think we should kill the lists of functions, that only
reproduce the comments from the source code. Or is anyone using them
now?
- The "Move Generation" chapter still needs to be adapted to the fact
that we now have an overview chapter (I.e. kill most of the first two
pages.)
- The need of a chapter "Detailed Sequence of Events" in overview.texi
(which is not yet updated) just reflects the fact that the functions
make_worms and make_dragons are _far_ too long -- if the lengthy
loops etc. in there would be broken out into separate functions, one
could get the sequence of events immediately from looking at the
source.
The biggest gap in the docs is s.th. on readconnect.c.
Arend
- subsection on 1D board array moved to board.texi
- references to cavities in dragon amalgamation removed
- complete rewrite of first chapters of overview.texi
Index: doc/api.texi
===================================================================
RCS file: /cvsroot/gnugo/gnugo/doc/api.texi,v
retrieving revision 1.9
diff -u -p -r1.9 api.texi
--- doc/api.texi 1 Apr 2002 01:42:44 -0000 1.9
+++ doc/api.texi 28 Jun 2003 22:47:43 -0000
@@ -206,8 +206,8 @@ of the move history.
All the functions in the engine that manipulate Positions have names
prefixed by @code{gnugo_}. These functions still use the two-dimensional
-representation of the board (@pxref{The Board}). Here is a complete list, as
-prototyped in @file{gnugo.h}:
+representation of the board (@pxref{The Board Array}). Here is a complete
+list, as prototyped in @file{gnugo.h}:
@itemize
@item @code{void init_gnugo(float memory)}
Index: doc/board.texi
===================================================================
RCS file: /cvsroot/gnugo/gnugo/doc/board.texi,v
retrieving revision 1.8
diff -u -p -r1.8 board.texi
--- doc/board.texi 22 Mar 2002 08:18:32 -0000 1.8
+++ doc/board.texi 28 Jun 2003 22:47:43 -0000
@@ -1,5 +1,6 @@
@menu
* Board Data Structures:: Board Data Structures
+* The Board Array:: One-dimensional board array
* Board Setup Functions:: Board Setup Functions
* Move Functions:: Move Functions
* Status Functions:: Status Functions
@@ -56,7 +57,7 @@ functions declared in it, i.e. the funct
engine, but not part of the board library. You must link your
application with @code{libboard.a}.
address@hidden Board Data Structures, Board Setup Functions, , Libboard
address@hidden Board Data Structures, The Board Array, , Libboard
@section Board Data structures
The basic data structures of the board correspond tightly to the
@@ -94,7 +95,171 @@ section. If you write directly to them,
will become out of sync with each other, and a crash is the likely
result.
address@hidden Board Setup Functions, Move Functions, Board Data Structures,
Libboard
address@hidden The Board Array, Board Setup Functions, Board Data Structures,
Libboard
address@hidden The Board Array
+
+GNU Go represents the board in a one-dimensional array called
address@hidden For some purposes a two dimensional indexing of the
+board by parameters @code{(i,j)} might be used.
+
+The @code{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.
+
address@hidden
address@hidden
+ 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
address@hidden group
address@hidden example
+
+To convert between a 1D index @code{pos} and a 2D index @code{(i,j)},
+the macros @code{POS}, @code{I}, and @code{J} are provided, defined as
+below:
+
address@hidden
+#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)
address@hidden example
+
+All 1D indices not corresponding to points on the board have the out
+of board marker value @code{GRAY}. Thus if @code{board_size} and
address@hidden both are 7, this looks like
+
address@hidden
address@hidden
+ j -1 0 1 2 3 4 5 6
+i +----------------------------------
+-1| # # # # # # # #
+ 0| # . . . . . . .
+ 1| # . . . . . . .
+ 2| # . . . . . . .
+ 3| # . . . . . . .
+ 4| # . . . . . . .
+ 5| # . . . . . . .
+ 6| # . . . . . . .
+ 7| # # # # # # # # #
address@hidden group
address@hidden example
+
+The indices marked @samp{#} have value @code{GRAY}.
+If @code{MAX_BOARD} is 7 and @code{board_size} is only 5:
+
address@hidden
address@hidden
+ j -1 0 1 2 3 4 5 6
+i +----------------------------------
+-1| # # # # # # # #
+ 0| # . . . . . # #
+ 1| # . . . . . # #
+ 2| # . . . . . # #
+ 3| # . . . . . # #
+ 4| # . . . . . # #
+ 5| # # # # # # # #
+ 6| # # # # # # # #
+ 7| # # # # # # # # #
address@hidden group
address@hidden example
+
+Navigation on the board is done by the @code{SOUTH}, @code{WEST},
address@hidden, and @code{EAST} macros,
+
address@hidden
+#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)
address@hidden example
+
+There are also shorthand macros @code{SW}, @code{NW}, @code{NE},
address@hidden, @code{SS}, @code{WW}, @code{NN}, @code{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
+
address@hidden
+#define ON_BOARD(pos) (board[pos] != GRAY)
+#define ON_BOARD1(pos) (((unsigned) (pos) < BOARDSIZE) && board[pos] != GRAY)
address@hidden example
+
+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 @code{pos}, we can do this with
address@hidden(EAST(pos))} instead of @code{(i+1, j-1)}.
+
address@hidden: The 2D coordinate @code{(-1,-1)}, which is used for
+pass and sometimes to indicate no point, maps to the 1D coordinate
address@hidden, not to @code{-1}. Instead of a plain @code{0}, use one of the
+macros @code{NO_MOVE} or @code{PASS_MOVE}.
+
+A loop over multiple directions is straightforwardly written:
+
address@hidden
+ for (k = 0; k < 4; k++) @{
+ int d = delta[k];
+ do_something(pos + d);
+ @}
address@hidden example
+
+The following constants are useful for loops over the entire board and
+allocation of arrays with a 1-1 mapping to the board.
+
address@hidden
+#define BOARDSIZE ((MAX_BOARD + 2) * (MAX_BOARD + 1) + 1)
+#define BOARDMIN (MAX_BOARD + 2)
+#define BOARDMAX (MAX_BOARD + 1) * (MAX_BOARD + 1)
address@hidden example
+
address@hidden is the actual size of the 1D board array,
address@hidden is the first index corresponding to a point on the
+board, and @code{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:
+
address@hidden
+ int m, n;
+ for (m = 0; m < board_size; m++)
+ for (n = 0; n < board_size; n++) @{
+ do_something(POS(m, n));
+ @}
address@hidden example
+
+Or:
+
address@hidden
+ int pos;
+ for (pos = BOARDMIN; pos < BOARDMAX; pos++) @{
+ if (ON_BOARD(pos))
+ do_something(pos);
+ @}
address@hidden example
+
+
address@hidden Board Setup Functions, Move Functions, The Board Array, Libboard
@section Board Functions
These functions are all the public functions in @file{engine/board.c}.
Index: doc/dragon.texi
===================================================================
RCS file: /cvsroot/gnugo/gnugo/doc/dragon.texi,v
retrieving revision 1.10
diff -u -p -r1.10 dragon.texi
--- doc/dragon.texi 6 Aug 2002 19:04:11 -0000 1.10
+++ doc/dragon.texi 28 Jun 2003 22:47:45 -0000
@@ -24,15 +24,9 @@ two routines @code{make_worm()} and @cod
@cindex dragon
@cindex worm
@cindex string
address@hidden worm closure
-A @dfn{worm} is a maximal set of vertices on the board which are connected
-along the horizontal and vertical lines, and are of the same color,
-which can be @code{BLACK}, @code{WHITE} or @code{EMPTY}. The term
address@hidden applied to a worm means that the worm consists of empty
-(unoccupied) vertices. It does @strong{not} mean that that the worm is the
-empty set. A @dfn{string} is a nonempty worm. An empty worm is called a
address@hidden If a subset of vertices is contained in a worm, there is a
-unique worm containing it; this is its @dfn{worm closure}.
+A @dfn{worm} is a maximal set of stones on the board which are connected
+along the horizontal and vertical lines, and are of the same color.
+We often say @dfn{string} instead of worm.
A @dfn{dragon} is a union of strings of the same color which will be
treated as a unit. The dragons are generated anew at each move. If two strings
@@ -271,16 +265,9 @@ not adjacent to any opponent string whic
captured, and which has no edge liberties or second
order liberties, and which satisfies the following
further property: If the string is removed from the
-board, then the empty worm E which is the worm closure
-of the set of vertices which it occupied has
-bordercolor the opposite of the removed string. The
-empty worm E (empty, that is, as a worm of the board
-modified by removal of S) consists of the union of
-support of S together with certain other empty worms
-which we call the @dfn{boundary components} of S.
+board, then the remaining cavity only borders worms of the
+opposite color.
-The inessential strings are used in the amalgamation of
-cavities in @code{make_dragons()}.
@end quotation
@findex unconditional_life
@item @code{invincible}
@@ -357,85 +344,7 @@ similar data. Each dragon is a union of
@code{worm[]} is constant on each worm, the data in
@code{dragon[]} is constant on each dragon.
address@hidden of two worms means means in practice replacing the origin
-of one worm by the origin of the other. Amalgamation takes place in
-two stages: first, the amalgamation of empty worms (cavities) into
-empty dragons (caves); then, the amalgamation of colored worms into
-dragons.
-
address@hidden Amalgamation of cavities
address@hidden amalgamation of cavities
-
-As we have already defined it, a cavity is an empty
-worm. A cave is an empty dragon.
-
-Under certain circumstances we want to amalgamate two or
-more cavities into a single cave. This is done before we
-amalgamate strings. An example where we wish to amalgamate
-two empty strings is the following:
-
address@hidden
-
- OOOOO
- OOXXXOO
- OXaObXO
- OOXXXOO
- OOOOO
-
address@hidden example
-
-The two empty worms at a and b are to be amalgamated.
address@hidden inessential string
-
-We have already defined a string to be @dfn{inessential} if it meets a
-criterion designed to guarantee that it has no life potential unless a
-particular surrounding string of the opposite color can be killed. An
address@hidden string} is a string S of genus zero which is not a cutting
-string or potential cutting string, and which has no edge liberties or
-second order liberties (the last condition should be relaxed), and
-which satisfies the following further property: If the string is
-removed from the board, then the empty worm E which is the worm
-closure of the set of vertices which it occupied has bordercolor the
-opposite of the removed string.
-
-Thus in the previous example, after removing the inessential string at
-the center the worm closure of the center vertex consists of an empty
-worm of size 3 including a and b. The latter are the boundary
-components.
-
-The last condition in the definition of inessential worms excludes
-examples such as this:
-
address@hidden
-
- OOOO
- OXXOO
- OXX.XO
- OX.XXO
- OOXXO
- OOO
-
address@hidden example
-
-Neither of the two X strings should be considered inessential
-(together they form a live group!) and indeed after removing one of
-them the resulting space has gray bordercolor, so by this definition
-these worms are not inessential.
-
-Some strings which should by rights be considered inessential will be
-missed by this criterion.
-
-The algorithm for amalgamation of empty worms consists of amalgamating
-the boundary components of any inessential worm. The resulting dragon
-has bordercolor the opposite of the removed string.
-
-Any dragon consisting of a single cavity has bordercolor equal to that
-of the cavity.
-
address@hidden Amalgamation of strings
address@hidden amalgamation of worms into dragons
-
-Amalgamation of nonempty worms in GNU Go 3.0 proceeds as follows.
+Amalgamation of worms in GNU Go 3.0 proceeds as follows.
First we amalgamate all boundary components of an eyeshape. Thus in
the following example:
Index: doc/gnugo.texi
===================================================================
RCS file: /cvsroot/gnugo/gnugo/doc/gnugo.texi,v
retrieving revision 1.10
diff -u -p -r1.10 gnugo.texi
--- doc/gnugo.texi 12 Jan 2003 19:44:21 -0000 1.10
+++ doc/gnugo.texi 28 Jun 2003 22:47:45 -0000
@@ -15,7 +15,7 @@
@titlepage
@subtitle Documentation for the GNU Go Project
@subtitle Edition @value{EDITION}
address@hidden April, 2002
address@hidden July, 2003
@vskip 0pt plus 1filll
@image{logo-32}
@vskip 0pt plus 1filll
Index: doc/influence.texi
===================================================================
RCS file: /cvsroot/gnugo/gnugo/doc/influence.texi,v
retrieving revision 1.15
diff -u -p -r1.15 influence.texi
--- doc/influence.texi 5 Jun 2003 11:12:50 -0000 1.15
+++ doc/influence.texi 28 Jun 2003 22:47:47 -0000
@@ -391,9 +391,6 @@ propagated to the intersection.
@comment node-name, next, previous, up
@section The Core of the Influence Function
-While most of the engine uses the one dimensional board (@pxref{The Board})
-the two dimensional board is still used in @file{engine/influence.c}.
-
Let @code{(m, n)} be the coordinates of the influence source and
@code{(i, j)} the coordinates of a an intersection being visited
during propagation, using the same notation as in the
Index: doc/overview.texi
===================================================================
RCS file: /cvsroot/gnugo/gnugo/doc/overview.texi,v
retrieving revision 1.11
diff -u -p -r1.11 overview.texi
--- doc/overview.texi 5 Jun 2003 11:12:50 -0000 1.11
+++ doc/overview.texi 28 Jun 2003 22:47:48 -0000
@@ -3,262 +3,101 @@ This chapter is an overview of the GNU G
documentation of how any one module or routine works may be found in
later chapters or comments in the source files.
+GNU Go starts by trying to understand the current board position as
+good as possible. Using the information found in this first phase, and
+using additional move generators, a list of candidate moves is generated.
+Finally, each of the candidate moves is valued according to its territorial
+value (including captures or life-and-death effects), and possible
+strategical effects (such as strengthening a weak group).
+
+Note that while GNU Go does, of course, do a lot of reading to analyze
+possible captures, life and death of groups etc., it does not (yet?) have
+a fullboard lookahead.
+
@menu
-* Definitions:: Some words used in this documentation.
-* The Board:: The Board
-* Move Generation Basics:: How GNU Go generates a move.
-* Examining the Position:: What @code{examine_position()} does.
-* Sequence of Events:: Outline of @code{genmove()}.
-* Roadmap:: Description of the different files.
-* Coding Styles:: Coding conventions.
-* Navigating the Source:: Navigating the Source.
+* Examining the Position:: Gathering Information
+* Move Generators:: Selecting Candidate Moves
+* Move Valuation:: Selecting the best Move
+* Detailed Sequence of Events:: Outline of @code{genmove()}.
+* Roadmap:: Description of the different files.
+* Coding Styles:: Coding conventions.
+* Navigating the Source:: Navigating the Source.
@end menu
address@hidden Definitions, The Board, Overview, Overview
address@hidden Definitions
address@hidden worm
address@hidden dragon
address@hidden cavity
address@hidden string
address@hidden superstring
-
-A @dfn{worm} is a maximal set of vertices on the board which are connected
-along the horizontal and vertical lines, and are of the same color,
-which can be @code{BLACK}, @code{WHITE} or @code{EMPTY}. The term
address@hidden applied to a worm means that the worm consists of empty
-(unoccupied) vertices. It does @strong{not} mean that that the worm is the
-empty set. A @dfn{string} is a nonempty worm. An empty worm is called a
address@hidden If a subset of vertices is contained in a worm, there is a
unique
-worm containing it; this is its @dfn{worm closure}. (@pxref{Worms}.)
-
-A @dfn{dragon} is a union of strings of the same color which will be treated
-as a unit. If two strings are in the same dragon, it is the computer's
-working hypothesis that they will live or die together and are
-effectively connected. (@pxref{Dragons}.)
-
-A @dfn{superstring} is a less commonly used unit which is the union
-of several strings but generally smaller than a dragon. The superstring
-code is in @file{engine/utils.c}. The definition of a superstring is
-slightly different if the code is called from @file{owl.c} or from
address@hidden
-
address@hidden The Board, Move Generation Basics, Definitions, Overview
address@hidden The Board
-
-GNU Go represents the board in a one-dimensional array called
address@hidden For some purposes a two dimensional indexing of the
-board by parameters @code{(i,j)} might be used.
-
-The @code{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.
-
address@hidden
address@hidden
- 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
address@hidden group
address@hidden example
-
-To convert between a 1D index @code{pos} and a 2D index @code{(i,j)},
-the macros @code{POS}, @code{I}, and @code{J} are provided, defined as
-below:
-
address@hidden
-#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)
address@hidden example
-
-All 1D indices not corresponding to points on the board have the out
-of board marker value @code{GRAY}. Thus if @code{board_size} and
address@hidden both are 7, this looks like
-
address@hidden
address@hidden
- j -1 0 1 2 3 4 5 6
-i +----------------------------------
--1| # # # # # # # #
- 0| # . . . . . . .
- 1| # . . . . . . .
- 2| # . . . . . . .
- 3| # . . . . . . .
- 4| # . . . . . . .
- 5| # . . . . . . .
- 6| # . . . . . . .
- 7| # # # # # # # # #
address@hidden group
address@hidden example
-
-The indices marked @samp{#} have value @code{GRAY}.
-If @code{MAX_BOARD} is 7 and @code{board_size} is only 5:
-
address@hidden
address@hidden
- j -1 0 1 2 3 4 5 6
-i +----------------------------------
--1| # # # # # # # #
- 0| # . . . . . # #
- 1| # . . . . . # #
- 2| # . . . . . # #
- 3| # . . . . . # #
- 4| # . . . . . # #
- 5| # # # # # # # #
- 6| # # # # # # # #
- 7| # # # # # # # # #
address@hidden group
address@hidden example
-
-Navigation on the board is done by the @code{SOUTH}, @code{WEST},
address@hidden, and @code{EAST} macros,
-
address@hidden
-#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)
address@hidden example
-
-There are also shorthand macros @code{SW}, @code{NW}, @code{NE},
address@hidden, @code{SS}, @code{WW}, @code{NN}, @code{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
-
address@hidden
-#define ON_BOARD(pos) (board[pos] != GRAY)
-#define ON_BOARD1(pos) (((unsigned) (pos) < BOARDSIZE) && board[pos] != GRAY)
address@hidden example
-
-where the first one should be used in the algorithms and the second
-one is useful for assertion tests.
-
address@hidden: The 2D coordinate @code{(-1,-1)}, which is used for
-pass and sometimes to indicate no point, maps to the 1D coordinate
address@hidden, not to @code{-1}. Instead of a plain @code{0}, use one of the
-macros @code{NO_MOVE} or @code{PASS_MOVE}.
-
-A loop over multiple directions is straightforwardly written:
-
address@hidden
- for (k = 0; k < 4; k++) @{
- int d = delta[k];
- do_something(pos + d);
- @}
address@hidden example
-
-The following constants are useful for loops over the entire board and
-allocation of arrays with a 1-1 mapping to the board.
-
address@hidden
-#define BOARDSIZE ((MAX_BOARD + 2) * (MAX_BOARD + 1) + 1)
-#define BOARDMIN (MAX_BOARD + 2)
-#define BOARDMAX (MAX_BOARD + 1) * (MAX_BOARD + 1)
address@hidden example
-
address@hidden is the actual size of the 1D board array,
address@hidden is the first index corresponding to a point on the
-board, and @code{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:
-
address@hidden
- int m, n;
- for (m = 0; m < board_size; m++)
- for (n = 0; n < board_size; n++) @{
- do_something(POS(m, n));
- @}
address@hidden example
-
-Or:
-
address@hidden
- int pos;
- for (pos = BOARDMIN; pos < BOARDMAX; pos++) @{
- if (ON_BOARD(pos))
- do_something(pos);
- @}
address@hidden example
address@hidden Move Generation Basics, Examining the Position, The Board,
Overview
address@hidden Examining the Position, Move Generators,, Overview
@comment node-name, next, previous, up
address@hidden Move Generation Basics
address@hidden move generation
address@hidden Gathering Information
-The engine of GNU Go takes a position and a color to move and
-generates the (supposedly) optimal move. This is done by the function
address@hidden()} in @file{engine/genmove.c}.
address@hidden genmove
-
-The move generation is done in three passes:
-
address@hidden
address@hidden Information gathering.
address@hidden Different modules propose moves.
address@hidden The values of the moves are weighted together and the best move
is selected.
address@hidden enumerate
-
address@hidden Information gathering
address@hidden examine_position
address@hidden information gathering
-
-The information gathering is done by a function @code{examine_position()},
-which will be discussed in greater detail in the next section.
-Such information could be life and death of the groups, information
-about moyos, connection of groups and so on. Information gathering is
-performed by @code{examine_position()}, which in turn calls:
+This is by far the most important phase in the move generation.
+Misunderstanding life-and-death situations can cause gross mistakes.
+Wrong territory estimates will lead to inaccurate move valuations.
+Bad judgement of weaknesses of groups make strategic mistakes likely.
+
+This information gathering is done by the function @code{examine_position()}.
+It first calls @code{make_worms()}.
+
+Its first steps are very simple: It identifies sets of directly connected
+stones--we call them @dfn{worms}--, and notes their sizes and their number of
+liberties.
+
+Soon after comes the most important step of the worm analysis:
+The tactical reading code (@pxref{Tactical Reading}) is called for every
+worm. It tries to read
+out which worms can be captured directly, giving up as soon as a worm
+can reach 5 liberties. If a worm can be captured, the engine of course
+looks for moves defending against this capture. Also, a lot of effort
+is made to find virtually all moves that achieve the capture or defense
+of a worm.
+
+After knowing which worms are tactically stable, we can make a first
+picture of the balance of power across the board: The @ref{Influence}
+code is called for the first time.
+
+This is to aid the next step, the analysis of dragons. By a @dfn{dragon}
+we mean a group of stones that cannot be disconnected.
+
+Naturally the first step in the responsible function @code{make_dragons()}
+is to identify these dragons, i.e. determine which worms cannot be
+disconnected from each other. This is partly done by patterns, but
+in most cases the specialized readconnect code (@pxref{Connections})
+is called. This module does a minimax search to determine whether two
+given worms can be connected with, resp. disconnected from each other.
+Then we compute various measures to determine how strong or weak any given
+dragon is:
@itemize @bullet
address@hidden @code{make_worms()}
address@hidden make_worms
address@hidden
-Collect information about all connected sets of stones
-(strings) and cavities. This information is stored in
-the @code{worm[]} array. (@pxref{Worms})
address@hidden quotation
address@hidden @code{compute_initial_influence()}
address@hidden compute_initial_influence
address@hidden
-Decides which areas of the board are influenced by which
-player. This function is run a second time later at
-the end of @code{make_dragons()}, since GNU Go's opinion
-about the safety of groups may change, and it is
-important to have the influence function as accurate as
-possible. @pxref{Influence}
address@hidden quotation
address@hidden @code{make_dragons()}
address@hidden make_dragons
address@hidden
-Collect information about connected strings, which are
-called dragons. Important information here is number
-of eyes, life status, and connectedness between
-string. (@pxref{Dragons}.)
address@hidden quotation
address@hidden A crude estimate of the number of eyes is made.
address@hidden The results of the influence computations is used to see which
dragons
+are adjacent to own territory or a moyo.
address@hidden A guess is made for the potential to escape if the dragon got
+under attack.
@end itemize
-A more detailed
+For those dragons that are considered weak, a life and death analysis
+is made (@pxref{The Owl Code}). If two dragons next to each other are found
+that are both not alive, we try to resolve this situation with the semeai
+module.
+
+For a more detailed reference of the worm and dragon analysis (and
+explanations of the data structures used to store the information),
+see @xref{Worms and Dragons}.
+
+The influence code is then called second time to make a detailed analysis
+of likely territory. Of course, the life-and-death status' of dragons are
+now taken into account.
+
+The territorial results of the influence module get corrected by the break-in
+module. This specifically tries to analyze where an opponent could break
+into an alleged territory, with sequences that would be too difficult to
+see for the influence code.
address@hidden Move generation in GNU Go 3.2
+
address@hidden Move Generators, Move Valuation, Examining the Position, Overview
@cindex move generation
@cindex move generators
@cindex move reasons
address@hidden Move Generators
Once we have found out all about the position it is time to generate
the best move. Moves are proposed by a number of different modules
@@ -267,30 +106,61 @@ do not set the values of the moves, but
them, called @dfn{move reasons}. The valuation of the moves comes
last, after all moves and their reasons have been generated.
-The move generators in version 3.2 are:
+For a list and explanation of move reasons used in GNU Go, and how they
+are evaluated, see @xref{Move Generation}.
+
+There are a couple of move generators that only extract data found in
+the previous phase, examining the position:
@itemize @bullet
address@hidden @code{worm_reasons()}
address@hidden worm_reasons
address@hidden
+Moves that have been found to capture or defend a worm are propsed as
+candidates.
address@hidden quotation
address@hidden @code{fuseki()}
address@hidden fuseki
address@hidden @code{owl_reasons()}
address@hidden owl_reasons
@quotation
-Generate a move in the early fuseki.
+The status of every dragon, as it has been determined by the owl code
+(@pxref{The Owl Code}) in the previous phase, is reviewed. If the status
+is critical, the killing or defending move gets a corresponding move
+reason.
@end quotation
address@hidden @code{semeai()}
address@hidden @code{semeai_move_reasons()}
@findex semeai
@quotation
-Find out if two dead groups of opposite colors are
-next to each other and, if so, try to kill the other
-group. This module will eventually be rewritten along
-the lines of the owl code.
+Similarly as @code{owl_reasons}, this function proposes moves relevant
+for semeais.
address@hidden quotation
+
address@hidden @code{break_in_move_reasons()}
address@hidden
+This suggests moves that have been found to break into opponent's territory
+by the break-in module.
address@hidden quotation
address@hidden itemize
+
+The following move generators do additional work:
+
address@hidden @bullet
+
address@hidden @code{fuseki()}
address@hidden fuseki
address@hidden
+Generate a move in the early fuseki, either in an empty corner of from
+the fuseki database.
@end quotation
@item @code{shapes()}
@findex shapes
@quotation
-Find patterns from @file{patterns/patterns.db} in
-the current position. Each pattern is matched in each
+This is probably the most important move generator.
+It finds patterns from @file{patterns/patterns.db},
address@hidden/patterns2.db}, @file{patterns/fuseki.db}, and the joseki
+files in the current position. Each pattern is matched in each
of the 8 possible orientations obtainable by rotation and
reflection. If the pattern matches, a so called "constraint"
may be tested which makes use of reading to determine if the
@@ -305,29 +175,28 @@ The patterns can be of a number of diffe
with different goals. There are e.g. patterns which
try to attack or defend groups, patterns which try to
connect or cut groups, and patterns which simply try
-to make good shape. In addition to the large pattern
+to make good shape. (In addition to the large pattern
database called by @code{shapes()}, pattern matching
is used by other modules for different tasks throughout
the program. @xref{Patterns}, for a complete documentation
-of patterns.
+of patterns.)
@end quotation
address@hidden @code{atari_atari()}
address@hidden @code{combinations()}
@findex atari_atari
@quotation
-See if there are any combination threats and either propose them or
-defend against them.
+See if there are any combination threats or atari sequences and either
+propose them or defend against them.
@end quotation
address@hidden @code{owl_reasons()}
address@hidden owl_reasons
address@hidden @code{revise_thrashing_dragon()}
address@hidden revise_thrashing_dragon
@quotation
-The Owl Code (@pxref{The Owl Code}) which has been run during
address@hidden), before @code{owl_reasons()} executes, has decided
-whether different groups can be attacked. The module @code{review_owl_reasons}
-reviews the statuses of every dragon and assigns move reasons for attack and
-defense. Unlike the other move generation modules, this one is called from
address@hidden()}.
+This module does not directly propose move: If we are clearly ahead,
+and the last move played by the opponent is part of a dead dragon, we
+want to attack that dragon again to be on the safe side. This is done
+be setting the status of this @dfn{thrashing dragon} to unkown and
+repeating the shape move generation and move valution.
@end quotation
@item @code{endgame_shapes()}
@@ -356,22 +225,32 @@ move is generated.
@end quotation
@end itemize
address@hidden Selecting the Move
address@hidden Move Valuation, Detailed Sequence of Events, Move Generators,
Overview
address@hidden Move Valuation
-After the move generation modules have run, the best ten moves
-are selected by the function @code{review_move_reasons}. This
-function also does some analysis to try to turn up other moves
-which may have been missed. The modules @code{revise_semeai()} and
address@hidden()} are only run if no good move has been
-discovered by the other modules.
+After the move generation modules have run, each proposed candidate
+move goes through a detailed valuation by the function
address@hidden This invokes some analysis to try to turn
+up other move reasons that may have been missed.
+
+The most important value of a move is its territorial effect.
address@hidden and Territory} explains in detail how this is determined.
+
+This value is modified for all move reasons that cannot be expressed
+directly in terms of territory, such as combination attacks (where it
+is not clear which of several strings will get captured), strategical
+effects, connection moves, etc. A large set heuristics is necessary
+here, e.g. to avoid duplication of such values. This is explained in
+more detail in @ref{Valuations}.
address@hidden Examining the Position, Sequence of Events, Move Generation
Basics, Overview
+
address@hidden Detailed Sequence of Events, Roadmap, Move Valuation, Overview
@comment node-name, next, previous, up
address@hidden Examining the Position
address@hidden Detailed Sequence of Events
-In this section we summarize the sequence of events when
+First comes the sequence of events when
@code{examine_position()} is run from @code{genmove()}. This
-is for reference only. Don't try to memorize it.
+is for reference only.
@format
purge persistent reading cache (@pxref{Persistent Cache})
@@ -397,7 +276,6 @@ purge persistent reading cache (@pxref{P
find higher order liberties
find cutting points (worm.cutstone)
for each worm compute the genus (@pxref{Worms})
- @code{small_semeai()}
try to improve values of worm.attack and worm.defend
try to repair situations where adjacent worms can be
both attacked and defended
@@ -453,13 +331,9 @@ purge persistent reading cache (@pxref{P
@code{compute_initial_influence()} again (@pxref{Influence})
@end format
address@hidden Sequence of Events, Roadmap, Examining the Position, Overview
address@hidden node-name, next, previous, up
address@hidden Sequence of Events
-
-In this section we summarize the sequence of events during the
+Now a summary of the sequence of events during the
move generation and selection phases of @code{genmove()}, which
-take place after the information gathering phase has been completed.
+take place after the information gathering phase has been completed:
@format
@code{fuseki()}
@@ -485,7 +359,7 @@ if still no move found
pass
@end format
address@hidden Roadmap, Coding Styles, Sequence of Events, Overview
address@hidden Roadmap, Coding Styles, Detailed Sequence of Events, Overview
@comment node-name, next, previous, up
@section Roadmap
@@ -869,8 +743,7 @@ format string suppresses the indentation
@end quotation
@end itemize
-A variant @code{mprintf} sends output to stderr. Normally
address@hidden()} is wrapped in one of the following:
+Normally @code{gprintf()} is wrapped in one of the following:
@code{TRACE(fmt, ...)}:
@quotation
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [gnugo-devel] doc patch,
Arend Bayer <=