Commit | Line | Data |
---|---|---|
7eeb782e AT |
1 | /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ |
2 | * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see * | |
3 | * http://www.gnu.org/software/gnugo/ for more information. * | |
4 | * * | |
5 | * Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, * | |
6 | * 2008 and 2009 by the Free Software Foundation. * | |
7 | * * | |
8 | * This program is free software; you can redistribute it and/or * | |
9 | * modify it under the terms of the GNU General Public License as * | |
10 | * published by the Free Software Foundation - version 3 or * | |
11 | * (at your option) any later version. * | |
12 | * * | |
13 | * This program is distributed in the hope that it will be useful, * | |
14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of * | |
15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * | |
16 | * GNU General Public License in file COPYING for more details. * | |
17 | * * | |
18 | * You should have received a copy of the GNU General Public * | |
19 | * License along with this program; if not, write to the Free * | |
20 | * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, * | |
21 | * Boston, MA 02111, USA. * | |
22 | \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ | |
23 | ||
24 | #include "gnugo.h" | |
25 | ||
26 | #include <stdio.h> | |
27 | #include <string.h> | |
28 | #include <stdlib.h> | |
29 | ||
30 | #include "liberty.h" | |
31 | ||
32 | /* Capture as many strings of the given color as we can. Played stones | |
33 | * are left on the board and the number of played stones is returned. | |
34 | * Strings marked in the exceptions array are excluded from capturing | |
35 | * attempts. If all non-excepted strings are successfully captured, | |
36 | * *none_invincible is set to one. Set none_invincible to NULL if you | |
37 | * don't need that information. | |
38 | */ | |
39 | static int | |
40 | capture_non_invincible_strings(int color, int exceptions[BOARDMAX], | |
41 | int *none_invincible) | |
42 | { | |
43 | int other = OTHER_COLOR(color); | |
44 | int something_captured = 1; /* To get into the first turn of the loop. */ | |
45 | int string_found = 0; | |
46 | int moves_played = 0; | |
47 | int save_moves; | |
48 | int libs[MAXLIBS]; | |
49 | int liberties; | |
50 | int pos; | |
51 | int k; | |
52 | ||
53 | while (something_captured) { | |
54 | /* Nothing captured so far in this turn of the loop. */ | |
55 | something_captured = 0; | |
56 | ||
57 | /* Is there something left to try to capture? */ | |
58 | string_found = 0; | |
59 | ||
60 | /* Visit all friendly strings on the board. */ | |
61 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
62 | if (board[pos] != color || find_origin(pos) != pos) | |
63 | continue; | |
64 | ||
65 | if (exceptions && exceptions[pos]) | |
66 | continue; | |
67 | ||
68 | string_found = 1; | |
69 | ||
70 | /* Try to capture the string at pos. */ | |
71 | liberties = findlib(pos, MAXLIBS, libs); | |
72 | save_moves = moves_played; | |
73 | for (k = 0; k < liberties; k++) { | |
74 | if (trymove(libs[k], other, "unconditional_life", pos)) | |
75 | moves_played++; | |
76 | } | |
77 | ||
78 | /* Successful if already captured or a single liberty remains. | |
79 | * Otherwise we must rewind and take back the last batch of moves. | |
80 | */ | |
81 | if (board[pos] == EMPTY) | |
82 | something_captured = 1; | |
83 | else if (findlib(pos, 2, libs) == 1) { | |
84 | /* Need to use tryko as a defense against the extreme case | |
85 | * when the only opponent liberty that is not suicide is an | |
86 | * illegal ko capture, like in this 5x5 position: | |
87 | * +-----+ | |
88 | * |.XO.O| | |
89 | * |XXOO.| | |
90 | * |X.XOO| | |
91 | * |XXOO.| | |
92 | * |.XO.O| | |
93 | * +-----+ | |
94 | */ | |
95 | int success = tryko(libs[0], other, "unconditional_life"); | |
96 | gg_assert(success); | |
97 | moves_played++; | |
98 | something_captured = 1; | |
99 | } | |
100 | else | |
101 | while (moves_played > save_moves) { | |
102 | popgo(); | |
103 | moves_played--; | |
104 | } | |
105 | } | |
106 | } | |
107 | ||
108 | if (none_invincible) | |
109 | *none_invincible = !string_found; | |
110 | ||
111 | return moves_played; | |
112 | } | |
113 | ||
114 | /* Find those worms of the given color that can never be captured, | |
115 | * even if the opponent is allowed an arbitrary number of consecutive | |
116 | * moves. The coordinates of the origins of these worms are written to | |
117 | * the worm arrays and the number of non-capturable worms is | |
118 | * returned. | |
119 | * | |
120 | * The algorithm is to cycle through the worms until none remains or | |
121 | * no more can be captured. A worm is removed when it is found to be | |
122 | * capturable, by letting the opponent try to play on all its | |
123 | * liberties. If the attack fails, the moves are undone. When no more | |
124 | * worm can be removed in this way, the remaining ones are | |
125 | * unconditionally alive. | |
126 | * | |
127 | * After this, unconditionally dead opponent worms and unconditional | |
128 | * territory are identified. This is almost, but only almost, | |
129 | * straightforward. We first present a simple but only almost correct | |
130 | * solution, then show how to patch up its deficiencies. | |
131 | * | |
132 | * - - - - - - - | |
133 | * | |
134 | * Algorithm 1, simple but slightly incorrect. | |
135 | * | |
136 | * To find unconditionally dead opponent worms and unconditional | |
137 | * territory, we continue from the position obtained at the end of the | |
138 | * previous operation (only unconditionally alive strings remain for | |
139 | * color) with the following steps: | |
140 | * | |
141 | * 1. Play opponent stones on all liberties of the unconditionally | |
142 | * alive strings except where illegal. (That the move order may | |
143 | * determine exactly which liberties can be played legally is not | |
144 | * important. Just pick an arbitrary order). | |
145 | * 2. Recursively extend opponent strings in atari, except where this | |
146 | * would be suicide. | |
147 | * 3. Play an opponent stone anywhere it can get two empty | |
148 | * neighbors. (I.e. split big eyes into small ones). | |
149 | * 4. Play an opponent stone anywhere it can get one empty | |
150 | * neighbor. (I.e. reduce two space eyes to one space eyes.) | |
151 | * | |
152 | * Remaining opponent strings in atari and remaining liberties of the | |
153 | * unconditionally alive strings constitute the unconditional | |
154 | * territory. | |
155 | * | |
156 | * Opponent strings from the initial position placed on | |
157 | * unconditional territory are unconditionally dead. | |
158 | * | |
159 | * - - - - - - - | |
160 | * | |
161 | * The deficiency with this algorithm is that a certain class of sekis | |
162 | * are considered as dead, e.g. this position: | |
163 | * | |
164 | * .OOOOO. | |
165 | * OOXXXOO | |
166 | * OXX.XXO | |
167 | * OX.O.XO | |
168 | * OX.O.XO | |
169 | * OXX.XXO | |
170 | * OOXXXOO | |
171 | * .OOOOO. | |
172 | * | |
173 | * The problem is that while removing the two O stones, X is reduced | |
174 | * to a single small eye. Still O cannot capture these stones under | |
175 | * alternating play since the eyespace is too big. | |
176 | * | |
177 | * Before discussing this seki further we make a preliminary | |
178 | * modification of the algorithm. | |
179 | * | |
180 | * - - - - - - - | |
181 | * | |
182 | * Algorithm 2. More complex but still slightly incorrect algorithm: | |
183 | * | |
184 | * 1. Run algorithm 1. | |
185 | * 2. Return to the original position. | |
186 | * 3. Capture all capturable O strings which according to algorithm 1 | |
187 | * do not belong to unconditional territory. | |
188 | * 4. Play opponent stones on all liberties of the unconditionally | |
189 | * alive strings except where illegal. (That the move order may | |
190 | * determine exactly which liberties can be played legally is not | |
191 | * important. Just pick an arbitrary order). | |
192 | * 5. Recursively extend opponent strings in atari, except where this | |
193 | * would be suicide. | |
194 | * 6. Capture all remaining capturable O strings. | |
195 | * 7. Repeat 4 and 5 once. | |
196 | * 8. Play an opponent stone anywhere it can get two empty | |
197 | * neighbors. (I.e. split big eyes into small ones). | |
198 | * 9. Play an opponent stone anywhere it can get one empty | |
199 | * neighbor. (I.e. reduce two space eyes to one space eyes.) | |
200 | * | |
201 | * Remaining opponent strings in atari and remaining liberties of the | |
202 | * unconditionally alive strings constitute the unconditional | |
203 | * territory. | |
204 | * | |
205 | * Opponent strings from the initial position placed on | |
206 | * unconditional territory are unconditionally dead. | |
207 | * | |
208 | * - - - - - - - | |
209 | * | |
210 | * We can observe that, after step 5, an X group with at least two | |
211 | * distinct eyespaces would not risk being reduced to a single small | |
212 | * eye. Similarly an X group with a capturable O string of size at | |
213 | * least three would allow the formation of two distinct small eyes | |
214 | * after being captured. Thus it is easy to see that the only X groups | |
215 | * which would live in seki but could not be transformed into | |
216 | * unconditionally alive groups would have a single eyespace with a | |
217 | * capturable O string of size at most 2. Furthermore the eyespace | |
218 | * would not be possible to subdivide. Then if the capturable string | |
219 | * would be of size 1 it would in all cases form a nakade and we would | |
220 | * not have a seki. The plausible seki positions would all be | |
221 | * reducable to the following eyeshape: | |
222 | * | |
223 | * .OOOOO. | |
224 | * OOXXXO. | |
225 | * OXX.XOO | |
226 | * OX.OXXO | |
227 | * OXXO.XO | |
228 | * OOX.XXO | |
229 | * .OXXXOO | |
230 | * .OOOOO. | |
231 | * | |
232 | * The remaining question is what effects cutting points in the X | |
233 | * group would have. For example these X groups are dead: | |
234 | * | |
235 | * .OOOOO. .OOOOO. .OOOOO. .OOOOO. ..OOOO. ..OOOO. | |
236 | * .OXXXO. .OXXXO. .OXXXO. .OXXXO. OOOXXO. OOOXXO. | |
237 | * OOX.XO. OOX.XOO OOX.XOO OOX.XOO OXX.XO. OXX.XOO | |
238 | * OX.OXOO OX.OXXO OX.OXXO OX.OXXO OX.OXOO OX.OXXO | |
239 | * OXXO.XO OXXO.XO OXXO.XO OXXO.XO OXXO.XO OXXO.XO | |
240 | * OOX.XXO OOX.XOO OOX.XXO OOX.XXO OOX.XXO OOX.XXO | |
241 | * .OXXXOO .OXXXO. .OXXOOO .OOXXOO .OXXXOO .OXXOOO | |
242 | * .OOOOO. .OOOOO. .OOOO.. ..OOOO. .OOOOO. .OOOO.. | |
243 | * | |
244 | * while these are alive in seki | |
245 | * | |
246 | * ..OOOO. .OOOO.. .OOOO.. ..OOOO. ..OOOO. | |
247 | * OOOXXO. .OXXOO. OOXXOO. .OOXXO. OOOXXO. | |
248 | * OXX.XOO OOX.XOO OXX.XOO OOX.XOO OXX.XOO | |
249 | * OX.OXXO OX.OXXO OX.OXXO OX.OXXO OX.OXXO | |
250 | * OXXO.XO OXXO.XO OOXO.XO OXXO.XO OOXO.XO | |
251 | * OOX.XXO OOX.XXO .OX.XXO OOX.XXO .OX.XXO | |
252 | * .OXXXOO .OXXXOO .OXXOOO .OXXXOO .OXXXOO | |
253 | * .OOOOO. .OOOOO. .OOOO.. ..OOOO. .OOOOO. | |
254 | * | |
255 | * The critical distinction between the dead ones and the seki ones is | |
256 | * that the stones marked a and b below, | |
257 | * | |
258 | * .OOOOO. | |
259 | * OOXXXO. | |
260 | * OXX.XOO | |
261 | * OX.ObXO | |
262 | * OXaO.XO | |
263 | * OOX.XXO | |
264 | * .OXXXOO | |
265 | * .OOOOO. | |
266 | * | |
267 | * belong to different strings for the dead groups and to the same | |
268 | * string for the seki groups. | |
269 | * | |
270 | * The trick to avoid misclassifying areas where the opponent can form | |
271 | * a seki group but not an invincible group as unconditional territory | |
272 | * is thus to detect the formation above and add a third stone to the | |
273 | * O group before the capturing in step 6 above. | |
274 | * | |
275 | * This leads to the final algorithm. | |
276 | * | |
277 | * - - - - - - - | |
278 | * | |
279 | * Algorithm 3. Final and correct algorithm: | |
280 | * | |
281 | * 1. Run algorithm 1. | |
282 | * 2. Return to the original position. | |
283 | * 3. Capture all capturable O strings which according to algorithm 1 | |
284 | * do not belong to unconditional territory. | |
285 | * 4. Play opponent stones on all liberties of the unconditionally | |
286 | * alive strings except where illegal. (That the move order may | |
287 | * determine exactly which liberties can be played legally is not | |
288 | * important. Just pick an arbitrary order). | |
289 | * 5. Recursively extend opponent strings in atari, except where this | |
290 | * would be suicide. | |
291 | * 6. Identify eyespaces of the kind described above and extend any | |
292 | * matching two-stone string with a third stone. | |
293 | * 7. Capture all remaining capturable O strings. | |
294 | * 8. Repeat 4 and 5 once. | |
295 | * 9. Play an opponent stone anywhere it can get two empty | |
296 | * neighbors. (I.e. split big eyes into small ones). | |
297 | * 10. Play an opponent stone anywhere it can get one empty | |
298 | * neighbor. (I.e. reduce two space eyes to one space eyes.) | |
299 | * | |
300 | * Remaining opponent strings in atari and remaining liberties of the | |
301 | * unconditionally alive strings constitute the unconditional | |
302 | * territory. | |
303 | * | |
304 | * Opponent strings from the initial position placed on | |
305 | * unconditional territory are unconditionally dead. | |
306 | * | |
307 | * - - - - - - - | |
308 | * | |
309 | * On return, unconditional_territory[][] is 1 where color has | |
310 | * unconditionally alive stones, 2 where it has unconditional | |
311 | * territory, and 0 otherwise. | |
312 | */ | |
313 | ||
314 | void | |
315 | unconditional_life(int unconditional_territory[BOARDMAX], int color) | |
316 | { | |
317 | int found_one; | |
318 | int other = OTHER_COLOR(color); | |
319 | int libs[MAXLIBS]; | |
320 | int liberties; | |
321 | int pos; | |
322 | int k, r; | |
323 | int moves_played; | |
324 | int potential_sekis[BOARDMAX]; | |
325 | int none_invincible; | |
326 | ||
327 | /* Initialize unconditional_territory array. */ | |
328 | memset(unconditional_territory, 0, | |
329 | sizeof(unconditional_territory[0]) * BOARDMAX); | |
330 | ||
331 | /* Find isolated two-stone strings which might be involved in the | |
332 | * kind of seki described in the comments. | |
333 | */ | |
334 | memset(potential_sekis, 0, sizeof(potential_sekis)); | |
335 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
336 | int isolated = 1; | |
337 | int stones[2]; | |
338 | int pos2; | |
339 | ||
340 | if (board[pos] != color | |
341 | || find_origin(pos) != pos | |
342 | || countstones(pos) != 2) | |
343 | continue; | |
344 | ||
345 | findstones(pos, 2, stones); | |
346 | for (k = 0; k < 2 && isolated; k++) { | |
347 | for (r = 0; r < 8 && isolated; r++) { | |
348 | pos2 = stones[k] + delta[r]; | |
349 | if (!ON_BOARD(pos2) | |
350 | || (board[pos2] == color | |
351 | && !same_string(pos, pos2))) | |
352 | isolated = 0; | |
353 | } | |
354 | } | |
355 | ||
356 | if (isolated) { | |
357 | potential_sekis[stones[0]] = 1; | |
358 | potential_sekis[stones[1]] = 1; | |
359 | } | |
360 | } | |
361 | ||
362 | moves_played = capture_non_invincible_strings(color, potential_sekis, | |
363 | &none_invincible); | |
364 | ||
365 | /* If there are no invincible strings, nothing can be unconditionally | |
366 | * settled. | |
367 | */ | |
368 | if (none_invincible) { | |
369 | /* Take back all moves. */ | |
370 | while (moves_played > 0) { | |
371 | popgo(); | |
372 | moves_played--; | |
373 | } | |
374 | return; | |
375 | } | |
376 | ||
377 | /* The strings still remaining except those marked in | |
378 | * potential_sekis[] are uncapturable. Now see which opponent | |
379 | * strings can survive. | |
380 | * | |
381 | * 1. Play opponent stones on all liberties of the unconditionally | |
382 | * alive strings except where illegal. | |
383 | */ | |
384 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
385 | if (board[pos] != color || potential_sekis[pos] || find_origin(pos) != pos) | |
386 | continue; | |
387 | ||
388 | /* Play as many liberties as we can. */ | |
389 | liberties = findlib(pos, MAXLIBS, libs); | |
390 | for (k = 0; k < liberties; k++) { | |
391 | if (trymove(libs[k], other, "unconditional_life", pos)) | |
392 | moves_played++; | |
393 | } | |
394 | } | |
395 | ||
396 | /* 2. Recursively extend opponent strings in atari, except where this | |
397 | * would be suicide. | |
398 | */ | |
399 | found_one = 1; | |
400 | while (found_one) { | |
401 | /* Nothing found so far in this turn of the loop. */ | |
402 | found_one = 0; | |
403 | ||
404 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
405 | if (board[pos] != other || countlib(pos) > 1) | |
406 | continue; | |
407 | ||
408 | /* Try to extend the string at (m, n). */ | |
409 | findlib(pos, 1, libs); | |
410 | if (trymove(libs[0], other, "unconditional_life", pos)) { | |
411 | moves_played++; | |
412 | found_one = 1; | |
413 | } | |
414 | } | |
415 | } | |
416 | ||
417 | /* Now see whether there are any significant sekis on the board. */ | |
418 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
419 | if (!potential_sekis[pos] | |
420 | || board[pos] == EMPTY | |
421 | || find_origin(pos) != pos) | |
422 | continue; | |
423 | for (r = 0; r < 4; r++) { | |
424 | int up = delta[r]; | |
425 | int right = delta[(r + 1) % 4]; | |
426 | int locally_played_moves = 0; | |
427 | if (board[pos + up] != color | |
428 | || board[pos + up + up] != EMPTY | |
429 | || board[pos - up] != EMPTY) | |
430 | continue; | |
431 | for (k = 0; k < 2; k++) { | |
432 | if (k == 1) | |
433 | right = -right; | |
434 | if (board[pos + right] != EMPTY || board[pos + up - right] != EMPTY) | |
435 | continue; | |
436 | if (board[pos - right] == EMPTY | |
437 | && trymove(pos - right, other, "unconditional_life", pos)) | |
438 | locally_played_moves++; | |
439 | if (board[pos + up + right] == EMPTY | |
440 | && trymove(pos + up + right, other, "unconditional_life", pos)) | |
441 | locally_played_moves++; | |
442 | if (board[pos - right] == other && board[pos + up + right] == other | |
443 | && same_string(pos - right, pos + up + right)) { | |
444 | /* This is a critical seki. Extend the string with one stone | |
445 | * in an arbitrary direction to break the seki. | |
446 | */ | |
447 | while (locally_played_moves > 0) { | |
448 | popgo(); | |
449 | locally_played_moves--; | |
450 | } | |
451 | trymove(pos - up, color, "unconditional_life", pos); | |
452 | moves_played++; | |
453 | break; | |
454 | } | |
455 | else { | |
456 | while (locally_played_moves > 0) { | |
457 | popgo(); | |
458 | locally_played_moves--; | |
459 | } | |
460 | } | |
461 | } | |
462 | if (countstones(pos) > 2) | |
463 | break; | |
464 | } | |
465 | } | |
466 | ||
467 | /* Capture the strings involved in potential sekis. */ | |
468 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
469 | if (!potential_sekis[pos] || board[pos] == EMPTY) | |
470 | continue; | |
471 | /* Play as many liberties as we can. */ | |
472 | liberties = findlib(pos, MAXLIBS, libs); | |
473 | for (k = 0; k < liberties; k++) { | |
474 | if (trymove(libs[k], other, "unconditional_life", pos)) | |
475 | moves_played++; | |
476 | } | |
477 | } | |
478 | ||
479 | ||
480 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
481 | int apos; | |
482 | int bpos; | |
483 | int aopen, bopen; | |
484 | int alib, blib; | |
485 | if (board[pos] != other || countlib(pos) != 2) | |
486 | continue; | |
487 | findlib(pos, 2, libs); | |
488 | apos = libs[0]; | |
489 | bpos = libs[1]; | |
490 | if (abs(I(apos) - I(bpos)) + abs(J(apos) - J(bpos)) != 1) | |
491 | continue; | |
492 | ||
493 | /* Only two liberties and these are adjacent. Play one. We want | |
494 | * to maximize the number of open liberties. In this particular | |
495 | * situation we can count this with approxlib for the opposite | |
496 | * color. If the number of open liberties is the same, we | |
497 | * maximize the total number of obtained liberties. | |
498 | * Two relevant positions: | |
499 | * | |
500 | * |XXX. | |
501 | * |OOXX |XXXXXXX | |
502 | * |O.OX |OOXOOOX | |
503 | * |..OX |..OO.OX | |
504 | * +---- +------- | |
505 | */ | |
506 | aopen = approxlib(apos, color, 4, NULL); | |
507 | bopen = approxlib(bpos, color, 4, NULL); | |
508 | alib = approxlib(apos, other, 4, NULL); | |
509 | blib = approxlib(bpos, other, 4, NULL); | |
510 | ||
511 | if (aopen > bopen || (aopen == bopen && alib >= blib)) { | |
512 | trymove(apos, other, "unconditional_life", pos); | |
513 | moves_played++; | |
514 | } | |
515 | else { | |
516 | trymove(bpos, other, "unconditional_life", pos); | |
517 | moves_played++; | |
518 | } | |
519 | } | |
520 | ||
521 | /* Identify unconditionally alive stones and unconditional territory. */ | |
522 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
523 | if (board[pos] == color && !potential_sekis[pos]) { | |
524 | unconditional_territory[pos] = 1; | |
525 | if (find_origin(pos) == pos) { | |
526 | liberties = findlib(pos, MAXLIBS, libs); | |
527 | for (k = 0; k < liberties; k++) | |
528 | unconditional_territory[libs[k]] = 2; | |
529 | } | |
530 | } | |
531 | else if (board[pos] == other && countlib(pos) == 1) { | |
532 | unconditional_territory[pos] = 2; | |
533 | findlib(pos, 1, libs); | |
534 | unconditional_territory[libs[0]] = 2; | |
535 | } | |
536 | } | |
537 | ||
538 | /* Take back all moves. */ | |
539 | while (moves_played > 0) { | |
540 | popgo(); | |
541 | moves_played--; | |
542 | } | |
543 | } | |
544 | ||
545 | ||
546 | /* By unconditional status analysis we can statically find some moves | |
547 | * which there is never any need to play. Those belong to three | |
548 | * different categories: | |
549 | * | |
550 | * 1. A move on a vertex which is already unconditional territory for | |
551 | * either color. | |
552 | * 2. A move which after having been made ends up as unconditional | |
553 | * territory for the opponent. | |
554 | * 3. If a move at vertex A makes vertex B become unconditional | |
555 | * territory, there is no need to consider a move at B, since A has | |
556 | * all the positive effects that B would have. | |
557 | * | |
558 | * Moves in categories 1 and 2 are never any better than passing and | |
559 | * often worse (with territory scoring always worse). Moves in | |
560 | * category three can be either better or worse than passing, but it's | |
561 | * always true that a move at A is at least as good as a move at B. | |
562 | * Occasionally they are identically good (A makes B unconditional | |
563 | * territory and B makes A unconditional territory) but there is never | |
564 | * any need to analyze both. | |
565 | * | |
566 | * In meaningless_black_moves[] and meaningless_white_moves[] a value | |
567 | * of -1 means it is not meaningless, 0 (NO_MOVE) means it belongs to | |
568 | * category 1 or 2, and a value greater than zero points to the | |
569 | * preferred move in category 3. | |
570 | * | |
571 | * The parameter unconditional_territory should contain the result of | |
572 | * calling unconditional_life() in the original position. Meaningless | |
573 | * moves are computed for the given color. | |
574 | */ | |
575 | void | |
576 | find_unconditionally_meaningless_moves(int unconditional_territory[BOARDMAX], | |
577 | int color) | |
578 | { | |
579 | int *meaningless_moves; | |
580 | int other = OTHER_COLOR(color); | |
581 | int friendly_unconditional[BOARDMAX]; | |
582 | int opponent_unconditional[BOARDMAX]; | |
583 | int pos; | |
584 | int pos2; | |
585 | ||
586 | gg_assert(color == BLACK || color == WHITE); | |
587 | ||
588 | if (color == BLACK) | |
589 | meaningless_moves = meaningless_black_moves; | |
590 | else | |
591 | meaningless_moves = meaningless_white_moves; | |
592 | ||
593 | /* Initialize meaningless_moves and detect moves of category 1, but | |
594 | * only for own unconditional territory. | |
595 | * | |
596 | * FIXME: We would save some time by detecting all category 1 moves | |
597 | * here but then we would need to have the initial unconditional | |
598 | * territory for the opponent as well. This can of course be done, | |
599 | * the question is how we get it in the nicest way. | |
600 | */ | |
601 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
602 | if (board[pos] == EMPTY) { | |
603 | if (unconditional_territory[pos]) | |
604 | meaningless_moves[pos] = NO_MOVE; | |
605 | else | |
606 | meaningless_moves[pos] = -1; | |
607 | } | |
608 | ||
609 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
610 | if (board[pos] != EMPTY || meaningless_moves[pos] != -1) | |
611 | continue; | |
612 | ||
613 | if (!tryko(pos, color, "find_unconditionally_meaningless_moves")) | |
614 | continue; | |
615 | ||
616 | unconditional_life(opponent_unconditional, other); | |
617 | if (opponent_unconditional[pos]) { | |
618 | /* Move of category 1 or 2. */ | |
619 | meaningless_moves[pos] = NO_MOVE; | |
620 | } | |
621 | else { | |
622 | unconditional_life(friendly_unconditional, color); | |
623 | if (friendly_unconditional[pos]) | |
624 | for (pos2 = BOARDMIN; pos2 < BOARDMAX; pos2++) | |
625 | if (board[pos2] == EMPTY | |
626 | && meaningless_moves[pos2] == -1 | |
627 | && friendly_unconditional[pos2]) { | |
628 | /* Move of category 3. */ | |
629 | meaningless_moves[pos2] = pos; | |
630 | } | |
631 | } | |
632 | ||
633 | popgo(); | |
634 | } | |
635 | ||
636 | /* Meaningless moves of category 3 may have been found in multiple | |
637 | * steps. Normalize to the final replacement move. | |
638 | */ | |
639 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
640 | if (board[pos] == EMPTY && meaningless_moves[pos] > 0) | |
641 | while (meaningless_moves[meaningless_moves[pos]] > 0) | |
642 | meaningless_moves[pos] = meaningless_moves[meaningless_moves[pos]]; | |
643 | } | |
644 | ||
645 | /* Returns 1 if the move at pos by color is meaningless and 0 | |
646 | * otherwise. When it is meaningless, *replacement_move will contain a | |
647 | * replacing move, which is NO_MOVE if passing is guaranteed to be no | |
648 | * worse than making the move. | |
649 | */ | |
650 | int | |
651 | unconditionally_meaningless_move(int pos, int color, int *replacement_move) | |
652 | { | |
653 | if (color == WHITE && meaningless_white_moves[pos] != -1) { | |
654 | *replacement_move = meaningless_white_moves[pos]; | |
655 | return 1; | |
656 | } | |
657 | if (color == BLACK && meaningless_black_moves[pos] != -1) { | |
658 | *replacement_move = meaningless_black_moves[pos]; | |
659 | return 1; | |
660 | } | |
661 | ||
662 | return 0; | |
663 | } | |
664 | ||
665 | void | |
666 | clear_unconditionally_meaningless_moves() | |
667 | { | |
668 | int pos; | |
669 | ||
670 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
671 | if (ON_BOARD(pos)) { | |
672 | meaningless_black_moves[pos] = -1; | |
673 | meaningless_white_moves[pos] = -1; | |
674 | } | |
675 | } | |
676 | ||
677 | /* Pick up antisuji and replacement move reasons found by analysis | |
678 | * of unconditional status. | |
679 | */ | |
680 | void | |
681 | unconditional_move_reasons(int color) | |
682 | { | |
683 | int replacement_move; | |
684 | int pos; | |
685 | ||
686 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
687 | if (board[pos] == EMPTY | |
688 | && unconditionally_meaningless_move(pos, color, &replacement_move)) { | |
689 | if (replacement_move == NO_MOVE) { | |
690 | TRACE("%1m unconditional antisuji.\n", pos); | |
691 | add_antisuji_move(pos); | |
692 | } | |
693 | else { | |
694 | TRACE("%1m unconditionally replaced to %1m.\n", pos, replacement_move); | |
695 | add_replacement_move(pos, replacement_move, color); | |
696 | } | |
697 | } | |
698 | } | |
699 | ||
700 | /* | |
701 | * Local Variables: | |
702 | * tab-width: 8 | |
703 | * c-basic-offset: 2 | |
704 | * End: | |
705 | */ |