[gnugo-devel] outline of experimental influence

[Arend Bayer]

On Wed, 13 Feb 2002, Daniel Bump wrote:
(Reply to private message)
> You've written previously in:
> 
> http://mail.gnu.org/pipermail/gnugo-devel/2002-January/001212.html
> http://mail.gnu.org/pipermail/gnugo-devel/2001-December/000715.html
> 
> about how the experimental influence option works. But these
> were both written before it was fully implemented and working
> well as it is now (unless it proves unacceptably slow). Any
> exposition in the list of what you've done would be welcome.

Here is a summary of what I have done. Appended below is a small first
documentation patch (moving a somewhat extended explanation of most
-m options to the influence chapter and adding an explanation of the
-m0x200 option that I introduced some weeks ago).

First of all, "experimental influence" may be a bit misleading, as the most
relevant changes only concern the territory valuation. Apart from
new_value_territory, I made only very small changes to Gunnar's code.

Lets start with new_value_territory, which assigns a territory value to
each intersection after the black and white influence have been computed.

It does so in 3 steps:
 - With diff = (white_influence - black_influence)
                / (white_influence + black_influence),
   the first approximation is diff*diff*diff. This means e.g. that if
   white has 7 times as much influence as black (which was previously the
   bordering condition for moyos), white gets 0.42 pts territory at
   that intersection.
 - Next, this gets corrected if the both influences were small. What exactly
   is "small" depends on where the intersection lies: the minimal influence
   needed to claim territory is defined as 6 in the corner, 15 on edge
   points, 31 on third line and 55 in the center (the formula is interpolated
   between some set values, details are in comments in influence.c; the
   exact values may still change)
 - Now the value at each intersection computed so far (first_guess[i][j] in
   the code) is reduced to the minimum of the values of itself and its
   neighbors. However, neighbors that have permeability 0.0 for opponents
   influence are ignored, and such with reduced permeability are only 
   allowed to give a reduced correction.
   
The 3rd steps greatly reduces "territories" e.g. in the center that are
open in several directions. The second step is also important so that
regions of black influence with very little white influence do not yet
get counted as quasi-territory for black.

Changes to the influence computation:
 - Most important, I reduced the DEFAULT_ATTENUATION from 3.0 to 2.4, and
   the DEFUALT_ATTENUATION accordingly. This was both more consistent with
   my personal judgement, and seemed to give more plausible result for
   the territory valuation. Note that the exact value of the attenuation
   is now a bit more important than before, as it does matter whether
   white's influence is 10 or 20 times as strong as black's.
 - The enhance patterns are ignored. (This does not make a very big
   difference, but it seems to make results a bit more consistent. Also,
   walls automatically get some improved effect due to the reduced
   attenuation.)
 - Intrusion ("B") patterns may get reduced in value (They are, together
   with asymmetric barriers, the source for the asymmetry of the influence
   function, i.e. its dependence on the color to move). This is the case if
   the sum of the intrusion values caused by a single stone would be greater
   than its own strength.
   
Finally, to each move influence an additional followup influence is
computed. This works as follows:
 - All B patterns that contain the move played (or any stone saved by this
   move) get matched.
 - Such a pattern gets rejected if the opponent can prevent the intrusion
   in sente.
 - Then these strengths are accumulated and the resulting influence is
   simply added to the values in move_influence. The difference in
   territorial valuation to the move_influence is reported to value_moves
   where it is stored in move[pos].infl_followup_value and treated the
   same way as other followup values.
   
This makes almost all followup patterns redundant that do not contain
capturing a stone etc. So these are in experimental influence mode now.

This should sum up what I've done unless I have forgotten s.th.

Arend


Index: doc/analyze.texi
===================================================================
RCS file: /cvsroot/gnugo/gnugo/doc/analyze.texi,v
retrieving revision 1.4
diff -u -r1.4 analyze.texi
--- doc/analyze.texi    3 Jan 2002 20:08:57 -0000       1.4
+++ doc/analyze.texi    13 Feb 2002 16:48:21 -0000
@@ -319,8 +319,8 @@
 The option @option{-m @var{level}} can give colored displays of the
 various quantities which are computed in @file{engine/moyo.c}.
 
-The moyos found by GNU Go can be displayed from an xterm or rxvt window or
-from the Linux console using the @option{-m} option. This takes a parameter:
+The regions found by Bouzy's algorithm explained in @xref{Moyo} can be
+displayed with the following options:
 
 @example
 
@@ -329,25 +329,18 @@
     1       0x01         ascii printing of territorial evaluation (5/21)
     2       0x02         ascii printing of moyo evaluation (5/10)
     4       0x04         ascii printing of area (4/0)
-    8       0x08         print initial moyo influence
-   16       0x10         print influence
-   32       0x20         numeric influence
-   64       0x40         moyo strength
-  128       0x80         moyo attenuation
-
 @end example
 
-The first three options are somewhat superceded because these
-data are no longer used by the engine.
-
address@hidden
-These options can be combined by adding the levels. Levels
-16, 32, 64 and 128 don't do much unless you also specify level 8. 
-Thus one might use the hexadecimal option @option{-m0x018} if you 
-want to see the influence function displayed graphically.
+These data are today only used in the score estimation. 
 
address@hidden, for the first three items.
-
address@hidden Display}, for the last five items.
+The rest of the engine uses instead the new influence algorithm explained
+in @xref{Influence}.  To get a colored display of the influence regions
+found by this module, use @option{-m 0x18} to see the initial influence,
+and e.g. @option{-m 0x10 --debug-influence D5} to see the influence
+after having made the move D5. There are various other options available
+for numerical displays influence; for a detailed description see
address@hidden Display}.
 
address@hidden
+These options can be combined by adding the levels.
 
Index: doc/influence.texi
===================================================================
RCS file: /cvsroot/gnugo/gnugo/doc/influence.texi,v
retrieving revision 1.4
diff -u -r1.4 influence.texi
--- doc/influence.texi  23 Nov 2001 17:47:39 -0000      1.4
+++ doc/influence.texi  13 Feb 2002 16:48:25 -0000
@@ -551,8 +551,11 @@
 @comment  node-name,  next,  previous,  up
 @section Colored display and debugging of influence
 
-It is possible to obtain colored diagrams showing influence from
-a colored xterm or rxvt window.
+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:
 
 @itemize @bullet
 @item @option{-m 0x08} or @option{-m 8}
@@ -563,6 +566,19 @@
 second time. Tactically captured worms are taken into account both
 times. 
 @end quotation
address@hidden @option{--debuginfluence @var{location}}
address@hidden
+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.
address@hidden quotation
address@hidden itemize
+
+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.
+
address@hidden @bullet
 @item @option{-m 0x010} or @option{-m 16}.
 @quotation
 Show colored display of territory/moyo/area regions.
@@ -571,8 +587,8 @@
 @item moyo: yellow
 @item area: red
 @end itemize
-Use either with @option{-m 0x8} (i.e. use @option{-m 0x18}) or
-with @option{--debuginfluence}.
+This feature is very useful to get an immediate impression of the influence
+regions as GNU Go sees them.
 @end quotation
 @item @option{-m 0x20} or @option{-m 32}.
 @quotation
@@ -580,26 +596,39 @@
 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.
-Use either with @option{-m 0x8} (i.e. use @option{-m 0x28}) or
-with @option{--debuginfluence}.
 @end quotation
address@hidden @option{--debuginfluence @var{location}}
address@hidden @option{-m 0x40} or @option{-m 64}.
 @quotation
-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.
+This generates two diagrams showing the permeability for black and white
+influence on the board.
 @end quotation
address@hidden @option{-d 0x20}
address@hidden @option{-m 0x80} or @option{-m 128}.
 @quotation
-Turn on @code{DEBUG_INFLUENCE}. This gives tons of messages from the pattern
-matching performed by the influence code. Too many to be really
-useful, unfortunately.
+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.
address@hidden quotation
address@hidden @option{-m 0x100} or @option{-m 256}.
address@hidden
+This shows the attenuation with which the influence sources spread
+influence across the board. Low attenuation indicates far-reaching
+influence sources.
address@hidden quotation
address@hidden @option{-m 0x200} or @option{-m 512}.
address@hidden
+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.
 @end quotation
 @end itemize
 
-Notice that you need to activate at least one of @option{-m 0x8} or
address@hidden, and at least one of @option{-m 0x10} and
address@hidden 0x20}, to get any diagrams at all. The first two determine when 
to
-print diagrams while the last two determine what diagrams to print.
-
+Finally, there is the debug option @option{-d 0x1} which turns on
+on @code{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 @option{-m 0x80} that looks wrong, the debug output can
+help you to quickly find out the responsible pattern.