9 #include "tactics/selfatari.h"
12 struct selfatari_state
{
14 group_t groupids
[S_MAX
][4];
15 coord_t groupneis
[S_MAX
][4];
17 /* This is set if this move puts a group out of _all_
18 * liberties; we need to watch out for snapback then. */
19 bool friend_has_no_libs
;
20 /* We may have one liberty, but be looking for one more.
21 * In that case, @needs_more_lib is id of group
22 * already providing one, don't consider it again. */
23 group_t needs_more_lib
;
24 /* ID of the first liberty, providing it again is not
26 coord_t needs_more_lib_except
;
30 three_liberty_suicide(struct board
*b
, group_t g
, enum stone color
, coord_t to
, struct selfatari_state
*s
)
32 /* If a group has three liberties, by playing on one of
33 * them it is possible to kill the group clumsily. Check
34 * against that condition: "After our move, the opponent
35 * can unconditionally capture the group."
39 * O O O O O O O X X O O O O O O v-v- ladder
40 * O X X X X X O . O X X X X X O . . . O O
41 * O X ! . ! X O . O X ! . ! O . O X X . O
42 * O X X X X X O # # # # # # # # O O O O O */
44 /* Extract the other two liberties. */
45 coord_t other_libs
[2];
46 bool other_libs_adj
[2];
47 for (int i
= 0, j
= 0; i
< 3; i
++) {
48 coord_t lib
= board_group_info(b
, g
).lib
[i
];
50 other_libs_adj
[j
] = coord_is_adjecent(lib
, to
, b
);
51 other_libs
[j
++] = lib
;
55 /* Make sure this move is not useful by gaining liberties,
56 * splitting the other two liberties (quite possibly splitting
57 * 3-eyespace!) or connecting to a different group. */
58 if (immediate_liberty_count(b
, to
) - (other_libs_adj
[0] || other_libs_adj
[1]) > 0)
60 assert(!(other_libs_adj
[0] && other_libs_adj
[1]));
61 if (s
->groupcts
[color
] > 1)
64 /* Playing on the third liberty might be useful if it enables
65 * capturing some group. */
66 for (int i
= 0; i
< s
->groupcts
[stone_other(color
)]; i
++)
67 if (board_group_info(b
, s
->groupids
[stone_other(color
)][i
]).libs
<= 2)
71 /* Okay. This looks like a pretty dangerous situation. The
72 * move looks useless, it definitely converts us to a 2-lib
73 * group. But we still want to play it e.g. if it takes off
74 * liberties of some unconspicous enemy group, and of course
75 * also at the game end to leave just single-point eyes. */
78 fprintf(stderr
, "3-lib danger\n");
80 /* Therefore, the final suicidal test is: (After filling this
81 * liberty,) when opponent fills liberty [0], playing liberty
82 * [1] will not help the group, or vice versa. */
83 bool other_libs_neighbors
= coord_is_adjecent(other_libs
[0], other_libs
[1], b
);
84 for (int i
= 0; i
< 2; i
++) {
85 int null_libs
= other_libs_neighbors
+ other_libs_adj
[i
];
86 if (board_is_one_point_eye(b
, other_libs
[1 - i
], color
)) {
87 /* The other liberty is an eye, happily go ahead.
88 * There are of course situations where this will
89 * take off semeai liberties, but without this check,
90 * many terminal endgame plays will be messed up. */
93 if (immediate_liberty_count(b
, other_libs
[i
]) - null_libs
> 1) {
94 /* Gains liberties. */
95 /* TODO: Check for ladder! */
99 foreach_neighbor(b
, other_libs
[i
], {
100 if (board_at(b
, c
) == color
101 && group_at(b
, c
) != g
102 && board_group_info(b
, group_at(b
, c
)).libs
> 1) {
103 /* Can connect to a friend. */
104 /* TODO: > 2? But maybe the group can capture
105 * a neighbor! But then better let it do that
110 /* If we can capture a neighbor, better do it now
111 * before wasting a liberty. So no need to check. */
112 /* Ok, the last liberty has no way to get out. */
114 fprintf(stderr
, "3-lib dangerous: %s\n", coord2sstr(other_libs
[i
], b
));
122 examine_friendly_groups(struct board
*b
, enum stone color
, coord_t to
, struct selfatari_state
*s
)
124 for (int i
= 0; i
< s
->groupcts
[color
]; i
++) {
125 /* We can escape by connecting to this group if it's
127 group_t g
= s
->groupids
[color
][i
];
129 if (board_group_info(b
, g
).libs
== 1) {
130 if (!s
->needs_more_lib
)
131 s
->friend_has_no_libs
= true;
132 // or we already have a friend with 1 lib
136 /* Could we self-atari the group here? */
137 if (board_group_info(b
, g
).libs
> 2) {
138 if (board_group_info(b
, g
).libs
== 3
139 && three_liberty_suicide(b
, g
, color
, to
, s
))
144 /* We need to have another liberty, and
145 * it must not be the other liberty of
147 int lib2
= board_group_other_lib(b
, g
, to
);
148 /* Maybe we already looked at another
149 * group providing one liberty? */
150 if (s
->needs_more_lib
&& s
->needs_more_lib
!= g
151 && s
->needs_more_lib_except
!= lib2
)
154 /* Can we get the liberty locally? */
155 /* Yes if we are route to more liberties... */
156 if (s
->groupcts
[S_NONE
] > 1)
158 /* ...or one liberty, but not lib2. */
159 if (s
->groupcts
[S_NONE
] > 0
160 && !coord_is_adjecent(lib2
, to
, b
))
163 /* ...ok, then we can still contribute a liberty
164 * later by capturing something. */
165 s
->needs_more_lib
= g
;
166 s
->needs_more_lib_except
= lib2
;
167 s
->friend_has_no_libs
= false;
174 examine_enemy_groups(struct board
*b
, enum stone color
, coord_t to
, struct selfatari_state
*s
)
176 /* We may be able to gain a liberty by capturing this group. */
177 group_t can_capture
= 0;
179 /* Examine enemy groups: */
180 for (int i
= 0; i
< s
->groupcts
[stone_other(color
)]; i
++) {
181 /* We can escape by capturing this group if it's in atari. */
182 group_t g
= s
->groupids
[stone_other(color
)][i
];
183 if (board_group_info(b
, g
).libs
> 1)
186 /* But we need to get to at least two liberties by this;
187 * we already have one outside liberty, or the group is
188 * more than 1 stone (in that case, capturing is always
190 if (s
->groupcts
[S_NONE
] > 0 || !group_is_onestone(b
, g
))
192 /* ...or, it's a ko stone, */
193 if (neighbor_count_at(b
, g
, color
) + neighbor_count_at(b
, g
, S_OFFBOARD
) == 3) {
194 /* and we don't have a group to save: then, just taking
195 * single stone means snapback! */
196 if (!s
->friend_has_no_libs
)
199 /* ...or, we already have one indirect liberty provided
200 * by another group. */
201 if (s
->needs_more_lib
|| (can_capture
&& can_capture
!= g
))
208 fprintf(stderr
, "no cap group\n");
210 if (!s
->needs_more_lib
&& !can_capture
&& !s
->groupcts
[S_NONE
]) {
211 /* We have no hope for more fancy tactics - this move is simply
212 * a suicide, not even a self-atari. */
214 fprintf(stderr
, "suicide\n");
217 /* XXX: I wonder if it makes sense to continue if we actually
218 * just !s->needs_more_lib. */
224 setup_nakade_or_snapback(struct board
*b
, enum stone color
, coord_t to
, struct selfatari_state
*s
)
226 /* There is another possibility - we can self-atari if it is
227 * a nakade: we put an enemy group in atari from the inside. */
228 /* This branch also allows eyes falsification:
229 * O O O . . (This is different from throw-in to false eye
230 * X X O O . checked below in that there is no X stone at the
231 * X . X O . right of the star point in this diagram.)
234 /* TODO: Allow to only nakade if the created shape is dead
235 * (http://senseis.xmp.net/?Nakade). */
237 /* This branch also covers snapback, which is kind of special
238 * nakade case. ;-) */
239 for (int i
= 0; i
< s
->groupcts
[stone_other(color
)]; i
++) {
240 group_t g
= s
->groupids
[stone_other(color
)][i
];
241 if (board_group_info(b
, g
).libs
!= 2)
244 /* We must make sure the other liberty of that group:
245 * (i) is an internal liberty
246 * (ii) filling it to capture our group will not gain
249 /* Let's look at neighbors of the other liberty: */
250 int lib2
= board_group_other_lib(b
, g
, to
);
251 foreach_neighbor(b
, lib2
, {
252 /* This neighbor of course does not contribute
253 * anything to the enemy. */
254 if (board_at(b
, c
) == S_OFFBOARD
)
257 /* If the other liberty has empty neighbor,
258 * it must be the original liberty; otherwise,
259 * since the whole group has only 2 liberties,
260 * the other liberty may not be internal and
261 * we are nakade'ing eyeless group from outside,
262 * which is stupid. */
263 if (board_at(b
, c
) == S_NONE
) {
270 int g2
= group_at(b
, c
);
271 /* If the neighbor is of our color, it must
272 * be also a 2-lib group. If it is more,
273 * we CERTAINLY want that liberty to be played
274 * first, what if it is an alive group? If it
275 * is in atari, we want to extend from it to
276 * prevent eye-making capture. However, if it
277 * is 2-lib, it is selfatari connecting two
278 * nakade'ing groups! */
279 /* X X X X We will not allow play on 'a',
280 * X X a X because 'b' would capture two
281 * X O b X different groups, forming two
283 if (board_at(b
, c
) == color
) {
284 if (board_group_info(b
, group_at(b
, c
)).libs
== 2)
289 /* The neighbor is enemy color. It's ok if
290 * it's still the same group or this is its
292 if (g
== g2
|| board_group_info(b
, g2
).libs
== 1)
294 /* Otherwise, it must have the exact same
295 * liberties as the original enemy group. */
296 if (board_group_info(b
, g2
).libs
== 2
297 && (board_group_info(b
, g2
).lib
[0] == to
298 || board_group_info(b
, g2
).lib
[1] == to
))
304 /* Now, we must distinguish between nakade and eye
305 * falsification; we must not falsify an eye by more
306 * than two stones. */
307 if (s
->groupcts
[color
] < 1)
308 return false; // simple throw-in
309 if (s
->groupcts
[color
] == 1 && group_is_onestone(b
, s
->groupids
[color
][0])) {
310 /* More complex throw-in - we are in one of
312 * a O O O O X b O O O X c O O O X
313 * O . X . O O X . . O . X .
314 * # # # # # # # # # # # # #
315 * b is desirable here (since maybe O has no
316 * backup two eyes); a may be desirable, but
317 * is tested next in check_throwin(). c is
318 * never desirable. */
319 group_t g2
= s
->groupids
[color
][0];
320 assert(board_group_info(b
, g2
).libs
<= 2);
321 if (board_group_info(b
, g2
).libs
== 1)
323 goto next_group
; // a or c
326 /* We would create more than 2-stone group; in that
327 * case, the liberty of our result must be lib2,
328 * indicating this really is a nakade. */
329 for (int j
= 0; j
< s
->groupcts
[color
]; j
++) {
330 group_t g2
= s
->groupids
[color
][j
];
331 assert(board_group_info(b
, g2
).libs
<= 2);
332 if (board_group_info(b
, g2
).libs
== 2) {
333 if (board_group_info(b
, g2
).lib
[0] != lib2
334 && board_group_info(b
, g2
).lib
[1] != lib2
)
337 assert(board_group_info(b
, g2
).lib
[0] == to
);
343 /* Unless we are dealing with snapback setup, we don't need to look
345 if (s
->groupcts
[color
])
353 check_throwin(struct board
*b
, enum stone color
, coord_t to
, struct selfatari_state
*s
)
355 /* We can be throwing-in to false eye:
356 * X X X O X X X O X X X X X
357 * X . * X * O . X * O O . X
358 * # # # # # # # # # # # # # */
359 /* We cannot sensibly throw-in into a corner. */
360 if (neighbor_count_at(b
, to
, S_OFFBOARD
) < 2
361 && neighbor_count_at(b
, to
, stone_other(color
))
362 + neighbor_count_at(b
, to
, S_OFFBOARD
) == 3
363 && board_is_false_eyelike(b
, to
, stone_other(color
))) {
364 assert(s
->groupcts
[color
] <= 1);
365 /* Single-stone throw-in may be ok... */
366 if (s
->groupcts
[color
] == 0) {
367 /* O X . There is one problem - when it's
368 * . * X actually not a throw-in!
370 foreach_neighbor(b
, to
, {
371 if (board_at(b
, c
) == S_NONE
) {
372 /* Is the empty neighbor an escape path? */
373 /* (Note that one S_NONE neighbor is already @to.) */
374 if (neighbor_count_at(b
, c
, stone_other(color
))
375 + neighbor_count_at(b
, c
, S_OFFBOARD
) < 2)
382 /* Multi-stone throwin...? */
383 assert(s
->groupcts
[color
] == 1);
384 group_t g
= s
->groupids
[color
][0];
386 assert(board_group_info(b
, g
).libs
<= 2);
387 /* Suicide is definitely NOT ok, no matter what else
389 if (board_group_info(b
, g
).libs
== 1)
392 /* In that case, we must be connected to at most one stone,
393 * or throwin will not destroy any eyes. */
394 if (group_is_onestone(b
, g
))
401 is_bad_selfatari_slow(struct board
*b
, enum stone color
, coord_t to
)
404 fprintf(stderr
, "sar check %s %s\n", stone2str(color
), coord2sstr(to
, b
));
405 /* Assess if we actually gain any liberties by this escape route.
406 * Note that this is not 100% as we cannot check whether we are
407 * connecting out or just to ourselves. */
409 struct selfatari_state s
;
410 memset(&s
, 0, sizeof(s
));
413 foreach_neighbor(b
, to
, {
414 enum stone color
= board_at(b
, c
);
415 group_t group
= group_at(b
, c
);
417 for (int i
= 0; i
< s
.groupcts
[color
]; i
++)
418 if (s
.groupids
[color
][i
] == group
) {
423 s
.groupneis
[color
][s
.groupcts
[color
]] = c
;
424 s
.groupids
[color
][s
.groupcts
[color
]++] = group_at(b
, c
);
428 /* We have shortage of liberties; that's the point. */
429 assert(s
.groupcts
[S_NONE
] <= 1);
431 d
= examine_friendly_groups(b
, color
, to
, &s
);
436 fprintf(stderr
, "no friendly group\n");
438 d
= examine_enemy_groups(b
, color
, to
, &s
);
443 fprintf(stderr
, "no escape\n");
445 d
= setup_nakade_or_snapback(b
, color
, to
, &s
);
450 fprintf(stderr
, "no nakade group\n");
452 d
= check_throwin(b
, color
, to
, &s
);
457 fprintf(stderr
, "no throw-in group\n");
459 /* No way to pull out, no way to connect out. This really
460 * is a bad self-atari! */
466 selfatari_cousin(struct board
*b
, enum stone color
, coord_t coord
)
468 group_t groups
[4]; int groups_n
= 0;
469 foreach_neighbor(b
, coord
, {
470 enum stone s
= board_at(b
, c
);
471 if (s
!= color
) continue;
472 group_t g
= group_at(b
, c
);
473 if (board_group_info(b
, g
).libs
== 2)
474 groups
[groups_n
++] = g
;
479 group_t group
= groups
[fast_random(groups_n
)];
481 coord_t lib2
= board_group_other_lib(b
, group
, coord
);
482 if (is_bad_selfatari(b
, color
, lib2
))