www.delorie.com/gnu/docs/gnugo/gnugo_192.html   search  
 
Buy GNU books!


GNU Go Documentation

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

16.5 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.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003