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


GNU Go Documentation

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

17.2 Bouzy's 5/21 algorithm

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

2 dilations :

 
            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/4 :

 
          3     5     3 
          
      2  136    8    136   2          
           
          3     5     3
          
3/5 :

 
          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