www.delorie.com/gnu/docs/gnugo/gnugo_201.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
Bouzy's algorithm was inspired by prior work of Zobrist and ideas from computer vision for determining territory. This algorithm is based on two simple operations, DILATION and EROSION. Applying dilation 5 times and erosion 21 times determines the territory.
To get a feeling for the algorithm, take a position in the early middle game and try the colored display using the `-m 1' option in an RXVT window. The regions considered territory by this algorithm tend to coincide with the judgement of a strong human player.
Before running the algorithm, dead stones (dragon.status==0
)
must be "removed."
Referring to page 86 of Bouzy's thesis, we start with a function taking a high value (ex : +128 for black, -128 for white) on stones on the goban, 0 to empty intersections. We may iterate the following operations:
dilation: for each intersection of the goban, if the intersection
is >= 0
, and not adjacent to a < 0
one, then add to the intersection
the number of adjacent >0 intersections. The same for other color : if
the intersection is <= 0
, and not adjacent to a > 0
one, then subtract
the number of < 0
intersections.
erosion: for each intersection > 0
(or < 0
), subtract (or
add) the number of adjacent <= 0
(or >= 0
) intersection. Stop at zero. The
algorithm is just : 5 dilations, then 21 erosions. The number of erosions
should be 1+n(n-1) where n=number of dilation, since this permit to have an
isolated stone to give no territory. Thus the couple 4/13 also works, but it
is often not good, for example when there is territory on the 6th line.
For example, let us start with a tobi.
128 0 128 |
1 dilation :
1 1 1 128 2 128 1 1 1 |
1 1 2 2 3 2 2 1 2 132 4 132 2 1 2 2 3 2 2 1 1 |
3 dilations :
1 1 2 2 3 2 2 2 4 6 6 6 4 2 1 2 6 136 8 136 6 2 1 2 4 6 6 6 4 2 2 2 3 2 2 1 1 |
and so on...
Next, with the same example
3 dilations and 1 erosion :
2 2 2 0 4 6 6 6 4 0 2 6 136 8 136 6 2 0 4 6 6 6 4 2 2 2 |
3 dilations and 2 erosions :
1 2 6 6 6 2 6 136 8 136 6 2 6 6 6 2 1 |
3 dil. / 3 erosions :
5 6 5 5 136 8 136 5 5 6 5 |
3 5 3 2 136 8 136 2 3 5 3 |
1 4 1 136 8 136 1 4 1 |
3/6 :
3 135 8 135 3 |
3/7 :
132 8 132 |
We interpret this as a 1 point territory.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
webmaster | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |