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


GNU Go Documentation

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

16.3 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. Version 3.2 instead computes 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 is new 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 uses a revised heuristic, which is explained in the next section, to assign probable territory to each player.


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

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