Commit | Line | Data |
---|---|---|
7eeb782e AT |
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 |