14. Another approach to Moyos : Bouzy's 5/21 algorithm

14.1 Moyo history History of `moyo.c' and `score.c'

14.2 Bouzy's 5/21 algorithm Bouzy's algorithm

The file `score.c' contains alternative algorithms for the computation of Territory and Moyos. These algorithms are used in estimate_score() but apart from that are generally not used in the rest of the engine since the concepts of Territory, Moyo and Area were reimplemented using the influence code (see section 13.2 Territory, Moyo and Area). The function estimate_score(), which is the only way this code is used in the engine, could easily be replaced with a function such as influence_score() based on the influence code.

14.1 Moyo history

In GNU Go 2.6 extensive use was made of an algorithm from Bruno Bouzy's dissertation, which is available at: ftp://www.joy.ne.jp/welcome/igs/Go/computer/bbthese.ps.Z This algorithm starts with the characteristic function of the live groups on the board and performs `n' operations called dilations, then `m' operations called erosions. If n=5 and m=21 this is called the 5/21 algorithm.

The Bouzy 5/21 algorithm is interesting in that it corresponds reasonably well to the human concept of territory. This algorithm is still used in GNU Go 3.6 in the function estimate_score. Thus we associate the 5/21 algorithm with the word territory. Similarly we use words moyo and area in reference to the 5/10 and 4/0 algorithms, respectively.

The principle defect of the algorithm is that it is not tunable. The current method of estimating moyos and territory is in `influence.c' (see section 13. Influence Function). The territory, moyo and area concepts have been reimplemented using the influence code.

The Bouzy algorithm is briefly reimplemented in the file `scoring.c' and is used by GNU Go 3.6 in estimating the score.

Not all features of the old `moyo.c' from GNU Go 2.6 were reimplemented--particularly the deltas were not--but the reimplementation may be more readable.

14.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 :