| 1 | |
| 2 | @menu |
| 3 | * Moyo history:: History of @file{moyo.c} and @file{score.c} |
| 4 | * Bouzy:: Bouzy's algorithm |
| 5 | @end menu |
| 6 | |
| 7 | The file @file{score.c} contains alternative algorithms for the |
| 8 | computation of Territory and Moyos. These algorithms are used in |
| 9 | @code{estimate_score()} but apart from that are generally |
| 10 | @strong{not} used in the rest of the engine since the concepts of |
| 11 | Territory, Moyo and Area were reimplemented using the influence |
| 12 | code (@pxref{Territory and Moyo}). The function @code{estimate_score()}, |
| 13 | which is the only way this code is used in the engine, could |
| 14 | easily be replaced with a function such as |
| 15 | @code{influence_score()} based on the influence code. |
| 16 | |
| 17 | @node Moyo history |
| 18 | @section Moyo history |
| 19 | |
| 20 | In GNU Go 2.6 extensive use was made of an algorithm from |
| 21 | Bruno Bouzy's dissertation, which is available at: |
| 22 | @url{ftp://www.joy.ne.jp/welcome/igs/Go/computer/bbthese.ps.Z} |
| 23 | This algorithm starts with the characteristic function of the |
| 24 | live groups on the board and performs @samp{n} operations |
| 25 | called dilations, then @samp{m} operations called erosions. |
| 26 | If n=5 and m=21 this is called the 5/21 algorithm. |
| 27 | |
| 28 | The Bouzy 5/21 algorithm is interesting in that it corresponds |
| 29 | reasonably well to the human concept of territory. This |
| 30 | algorithm is still used in GNU Go 3.6 in the function |
| 31 | @code{estimate_score}. Thus we associate the 5/21 algorithm |
| 32 | with the word @dfn{territory}. Similarly we use words |
| 33 | @dfn{moyo} and @dfn{area} in reference to the 5/10 |
| 34 | and 4/0 algorithms, respectively. |
| 35 | |
| 36 | The principle defect of the algorithm is that it is not |
| 37 | tunable. The current method of estimating moyos and territory |
| 38 | is in @file{influence.c} (@pxref{Influence}). The territory, |
| 39 | moyo and area concepts have been reimplemented using the |
| 40 | influence code. |
| 41 | |
| 42 | The Bouzy algorithm is briefly reimplemented in the file |
| 43 | @file{scoring.c} and is used by GNU Go 3.6 in estimating |
| 44 | the score. |
| 45 | |
| 46 | Not all features of the old @file{moyo.c} from |
| 47 | GNU Go 2.6 were reimplemented---particularly the deltas were |
| 48 | not---but the reimplementation may be more readable. |
| 49 | |
| 50 | @node Bouzy |
| 51 | @section Bouzy's 5/21 algorithm |
| 52 | |
| 53 | Bouzy's algorithm was inspired by prior work of Zobrist and ideas from |
| 54 | computer vision for determining territory. This algorithm is based on two |
| 55 | simple operations, DILATION and EROSION. Applying dilation 5 times and erosion |
| 56 | 21 times determines the territory. |
| 57 | |
| 58 | To get a feeling for the algorithm, take a position in the early |
| 59 | middle game and try the colored display using the @option{-m 1} option |
| 60 | in an RXVT window. The regions considered territory by this algorithm |
| 61 | tend to coincide with the judgement of a strong human player. |
| 62 | |
| 63 | Before running the algorithm, dead stones (@code{dragon.status==0}) |
| 64 | must be "removed." |
| 65 | |
| 66 | Referring to page 86 of Bouzy's thesis, we start with a function |
| 67 | taking a high value (ex : +128 for black, -128 for white) on stones on |
| 68 | the goban, 0 to empty intersections. We may iterate the following |
| 69 | operations: |
| 70 | |
| 71 | @dfn{dilation}: for each intersection of the goban, if the intersection |
| 72 | is @code{>= 0}, and not adjacent to a @code{< 0} one, then add to the intersection |
| 73 | the number of adjacent >0 intersections. The same for other color : if |
| 74 | the intersection is @code{<= 0}, and not adjacent to a @code{> 0} one, then subtract |
| 75 | the number of @code{< 0} intersections. |
| 76 | |
| 77 | @dfn{erosion}: for each intersection @code{> 0} (or @code{< 0}), subtract (or |
| 78 | add) the number of adjacent @code{<= 0} (or @code{>= 0}) intersection. Stop at zero. The |
| 79 | algorithm is just : 5 dilations, then 21 erosions. The number of erosions |
| 80 | should be 1+n(n-1) where n=number of dilation, since this permit to have an |
| 81 | isolated stone to give no territory. Thus the couple 4/13 also works, but it |
| 82 | is often not good, for example when there is territory on the 6th line. |
| 83 | |
| 84 | For example, let us start with a tobi. |
| 85 | |
| 86 | @example |
| 87 | |
| 88 | 128 0 128 |
| 89 | |
| 90 | @end example |
| 91 | |
| 92 | 1 dilation : |
| 93 | |
| 94 | @example |
| 95 | @group |
| 96 | |
| 97 | 1 1 |
| 98 | |
| 99 | 1 128 2 128 1 |
| 100 | |
| 101 | 1 1 |
| 102 | |
| 103 | @end group |
| 104 | @end example |
| 105 | |
| 106 | 2 dilations : |
| 107 | |
| 108 | @example |
| 109 | @group |
| 110 | |
| 111 | 1 1 |
| 112 | |
| 113 | 2 2 3 2 2 |
| 114 | |
| 115 | 1 2 132 4 132 2 1 |
| 116 | |
| 117 | 2 2 3 2 2 |
| 118 | |
| 119 | 1 1 |
| 120 | |
| 121 | @end group |
| 122 | @end example |
| 123 | |
| 124 | 3 dilations : |
| 125 | |
| 126 | @example |
| 127 | @group |
| 128 | |
| 129 | 1 1 |
| 130 | |
| 131 | 2 2 3 2 2 |
| 132 | |
| 133 | 2 4 6 6 6 4 2 |
| 134 | |
| 135 | 1 2 6 136 8 136 6 2 1 |
| 136 | |
| 137 | 2 4 6 6 6 4 2 |
| 138 | |
| 139 | 2 2 3 2 2 |
| 140 | |
| 141 | 1 1 |
| 142 | |
| 143 | @end group |
| 144 | @end example |
| 145 | |
| 146 | and so on... |
| 147 | |
| 148 | Next, with the same example |
| 149 | |
| 150 | 3 dilations and 1 erosion : |
| 151 | |
| 152 | |
| 153 | @example |
| 154 | @group |
| 155 | |
| 156 | 2 2 2 |
| 157 | |
| 158 | 0 4 6 6 6 4 |
| 159 | |
| 160 | 0 2 6 136 8 136 6 2 |
| 161 | |
| 162 | 0 4 6 6 6 4 |
| 163 | |
| 164 | 2 2 2 |
| 165 | |
| 166 | @end group |
| 167 | @end example |
| 168 | |
| 169 | |
| 170 | 3 dilations and 2 erosions : |
| 171 | |
| 172 | @example |
| 173 | @group |
| 174 | |
| 175 | 1 |
| 176 | |
| 177 | 2 6 6 6 2 |
| 178 | |
| 179 | 6 136 8 136 6 |
| 180 | |
| 181 | 2 6 6 6 2 |
| 182 | |
| 183 | 1 |
| 184 | |
| 185 | @end group |
| 186 | @end example |
| 187 | |
| 188 | 3 dil. / 3 erosions : |
| 189 | |
| 190 | |
| 191 | @example |
| 192 | @group |
| 193 | |
| 194 | 5 6 5 |
| 195 | |
| 196 | 5 136 8 136 5 |
| 197 | |
| 198 | 5 6 5 |
| 199 | |
| 200 | @end group |
| 201 | @end example |
| 202 | |
| 203 | 3/4 : |
| 204 | |
| 205 | |
| 206 | @example |
| 207 | @group |
| 208 | |
| 209 | 3 5 3 |
| 210 | |
| 211 | 2 136 8 136 2 |
| 212 | |
| 213 | 3 5 3 |
| 214 | |
| 215 | @end group |
| 216 | @end example |
| 217 | |
| 218 | 3/5 : |
| 219 | |
| 220 | @example |
| 221 | @group |
| 222 | |
| 223 | 1 4 1 |
| 224 | |
| 225 | 136 8 136 |
| 226 | |
| 227 | 1 4 1 |
| 228 | |
| 229 | @end group |
| 230 | @end example |
| 231 | |
| 232 | 3/6 : |
| 233 | |
| 234 | @example |
| 235 | @group |
| 236 | |
| 237 | 3 |
| 238 | |
| 239 | 135 8 135 |
| 240 | |
| 241 | 3 |
| 242 | |
| 243 | @end group |
| 244 | @end example |
| 245 | |
| 246 | 3/7 : |
| 247 | |
| 248 | @example |
| 249 | @group |
| 250 | |
| 251 | 132 8 132 |
| 252 | |
| 253 | @end group |
| 254 | @end example |
| 255 | |
| 256 | We interpret this as a 1 point territory. |
| 257 | |