9 #include "tactics/selfatari.h"
12 struct selfatari_state
{
14 group_t groupids
[S_MAX
][4];
16 /* This is set if this move puts a group out of _all_
17 * liberties; we need to watch out for snapback then. */
18 bool friend_has_no_libs
;
19 /* We may have one liberty, but be looking for one more.
20 * In that case, @needs_more_lib is id of group
21 * already providing one, don't consider it again. */
22 group_t needs_more_lib
;
23 /* ID of the first liberty, providing it again is not
25 coord_t needs_more_lib_except
;
29 examine_friendly_groups(struct board
*b
, enum stone color
, coord_t to
, struct selfatari_state
*s
)
31 for (int i
= 0; i
< s
->groupcts
[color
]; i
++) {
32 /* We can escape by connecting to this group if it's
34 group_t g
= s
->groupids
[color
][i
];
36 if (board_group_info(b
, g
).libs
== 1) {
37 if (!s
->needs_more_lib
)
38 s
->friend_has_no_libs
= true;
39 // or we already have a friend with 1 lib
43 /* Could we self-atari the group here? */
44 if (board_group_info(b
, g
).libs
> 2)
47 /* We need to have another liberty, and
48 * it must not be the other liberty of
50 int lib2
= board_group_other_lib(b
, g
, to
);
51 /* Maybe we already looked at another
52 * group providing one liberty? */
53 if (s
->needs_more_lib
&& s
->needs_more_lib
!= g
54 && s
->needs_more_lib_except
!= lib2
)
57 /* Can we get the liberty locally? */
58 /* Yes if we are route to more liberties... */
59 if (s
->groupcts
[S_NONE
] > 1)
61 /* ...or one liberty, but not lib2. */
62 if (s
->groupcts
[S_NONE
] > 0
63 && !coord_is_adjecent(lib2
, to
, b
))
66 /* ...ok, then we can still contribute a liberty
67 * later by capturing something. */
68 s
->needs_more_lib
= g
;
69 s
->needs_more_lib_except
= lib2
;
70 s
->friend_has_no_libs
= false;
77 examine_enemy_groups(struct board
*b
, enum stone color
, coord_t to
, struct selfatari_state
*s
)
79 /* We may be able to gain a liberty by capturing this group. */
80 group_t can_capture
= 0;
82 /* Examine enemy groups: */
83 for (int i
= 0; i
< s
->groupcts
[stone_other(color
)]; i
++) {
84 /* We can escape by capturing this group if it's in atari. */
85 group_t g
= s
->groupids
[stone_other(color
)][i
];
86 if (board_group_info(b
, g
).libs
> 1)
89 /* But we need to get to at least two liberties by this;
90 * we already have one outside liberty, or the group is
91 * more than 1 stone (in that case, capturing is always
93 if (s
->groupcts
[S_NONE
] > 0 || !group_is_onestone(b
, g
))
95 /* ...or, it's a ko stone, */
96 if (neighbor_count_at(b
, g
, color
) + neighbor_count_at(b
, g
, S_OFFBOARD
) == 3) {
97 /* and we don't have a group to save: then, just taking
98 * single stone means snapback! */
99 if (!s
->friend_has_no_libs
)
102 /* ...or, we already have one indirect liberty provided
103 * by another group. */
104 if (s
->needs_more_lib
|| (can_capture
&& can_capture
!= g
))
111 fprintf(stderr
, "no cap group\n");
113 if (!s
->needs_more_lib
&& !can_capture
&& !s
->groupcts
[S_NONE
]) {
114 /* We have no hope for more fancy tactics - this move is simply
115 * a suicide, not even a self-atari. */
117 fprintf(stderr
, "suicide\n");
120 /* XXX: I wonder if it makes sense to continue if we actually
121 * just !s->needs_more_lib. */
127 setup_nakade_or_snapback(struct board
*b
, enum stone color
, coord_t to
, struct selfatari_state
*s
)
129 /* There is another possibility - we can self-atari if it is
130 * a nakade: we put an enemy group in atari from the inside. */
131 /* This branch also allows eyes falsification:
132 * O O O . . (This is different from throw-in to false eye
133 * X X O O . checked below in that there is no X stone at the
134 * X . X O . right of the star point in this diagram.)
137 /* TODO: Allow to only nakade if the created shape is dead
138 * (http://senseis.xmp.net/?Nakade). */
140 /* This branch also covers snapback, which is kind of special
141 * nakade case. ;-) */
142 for (int i
= 0; i
< s
->groupcts
[stone_other(color
)]; i
++) {
143 group_t g
= s
->groupids
[stone_other(color
)][i
];
144 if (board_group_info(b
, g
).libs
!= 2)
146 /* Simple check not to re-examine the same group. */
147 if (i
> 0 && s
->groupids
[stone_other(color
)][i
] == s
->groupids
[stone_other(color
)][i
- 1])
150 /* We must make sure the other liberty of that group:
151 * (i) is an internal liberty
152 * (ii) filling it to capture our group will not gain
155 /* Let's look at neighbors of the other liberty: */
156 int lib2
= board_group_other_lib(b
, g
, to
);
157 foreach_neighbor(b
, lib2
, {
158 /* This neighbor of course does not contribute
159 * anything to the enemy. */
160 if (board_at(b
, c
) == S_OFFBOARD
)
163 /* If the other liberty has empty neighbor,
164 * it must be the original liberty; otherwise,
165 * since the whole group has only 2 liberties,
166 * the other liberty may not be internal and
167 * we are nakade'ing eyeless group from outside,
168 * which is stupid. */
169 if (board_at(b
, c
) == S_NONE
) {
176 int g2
= group_at(b
, c
);
177 /* If the neighbor is of our color, it must
178 * be also a 2-lib group. If it is more,
179 * we CERTAINLY want that liberty to be played
180 * first, what if it is an alive group? If it
181 * is in atari, we want to extend from it to
182 * prevent eye-making capture. However, if it
183 * is 2-lib, it is selfatari connecting two
184 * nakade'ing groups! */
185 /* X X X X We will not allow play on 'a',
186 * X X a X because 'b' would capture two
187 * X O b X different groups, forming two
189 if (board_at(b
, c
) == color
) {
190 if (board_group_info(b
, group_at(b
, c
)).libs
== 2)
195 /* The neighbor is enemy color. It's ok if
196 * it's still the same group or this is its
198 if (g
== g2
|| board_group_info(b
, g2
).libs
== 1)
200 /* Otherwise, it must have the exact same
201 * liberties as the original enemy group. */
202 if (board_group_info(b
, g2
).libs
== 2
203 && (board_group_info(b
, g2
).lib
[0] == to
204 || board_group_info(b
, g2
).lib
[1] == to
))
210 /* Now, we must distinguish between nakade and eye
211 * falsification; we must not falsify an eye by more
212 * than two stones. */
213 if (s
->groupcts
[color
] < 1)
214 return false; // simple throw-in
215 if (s
->groupcts
[color
] == 1 && group_is_onestone(b
, s
->groupids
[color
][0])) {
216 /* More complex throw-in - we are in one of
218 * a O O O O X b O O O X c O O O X
219 * O . X . O O X . . O . X .
220 * # # # # # # # # # # # # #
221 * b is desirable here (since maybe O has no
222 * backup two eyes); a may be desirable, but
223 * is tested next in check_throwin(). c is
224 * never desirable. */
225 group_t g2
= s
->groupids
[color
][0];
226 assert(board_group_info(b
, g2
).libs
<= 2);
227 if (board_group_info(b
, g2
).libs
== 1)
229 goto next_group
; // a or c
232 /* We would create more than 2-stone group; in that
233 * case, the liberty of our result must be lib2,
234 * indicating this really is a nakade. */
235 for (int j
= 0; j
< s
->groupcts
[color
]; j
++) {
236 group_t g2
= s
->groupids
[color
][j
];
237 assert(board_group_info(b
, g2
).libs
<= 2);
238 if (board_group_info(b
, g2
).libs
== 2) {
239 if (board_group_info(b
, g2
).lib
[0] != lib2
240 && board_group_info(b
, g2
).lib
[1] != lib2
)
243 assert(board_group_info(b
, g2
).lib
[0] == to
);
249 /* Unless we are dealing with snapback setup, we don't need to look
251 if (s
->groupcts
[color
])
259 check_throwin(struct board
*b
, enum stone color
, coord_t to
, struct selfatari_state
*s
)
261 /* We can be throwing-in to false eye:
262 * X X X O X X X O X X X X X
263 * X . * X * O . X * O O . X
264 * # # # # # # # # # # # # # */
265 /* We cannot sensibly throw-in into a corner. */
266 if (neighbor_count_at(b
, to
, S_OFFBOARD
) < 2
267 && neighbor_count_at(b
, to
, stone_other(color
))
268 + neighbor_count_at(b
, to
, S_OFFBOARD
) == 3
269 && board_is_false_eyelike(b
, to
, stone_other(color
))) {
270 assert(s
->groupcts
[color
] <= 1);
271 /* Single-stone throw-in may be ok... */
272 if (s
->groupcts
[color
] == 0) {
273 /* O X . There is one problem - when it's
274 * . * X actually not a throw-in!
276 foreach_neighbor(b
, to
, {
277 if (board_at(b
, c
) == S_NONE
) {
278 /* Is the empty neighbor an escape path? */
279 /* (Note that one S_NONE neighbor is already @to.) */
280 if (neighbor_count_at(b
, c
, stone_other(color
))
281 + neighbor_count_at(b
, c
, S_OFFBOARD
) < 2)
288 /* Multi-stone throwin...? */
289 assert(s
->groupcts
[color
] == 1);
290 group_t g
= s
->groupids
[color
][0];
292 assert(board_group_info(b
, g
).libs
<= 2);
293 /* Suicide is definitely NOT ok, no matter what else
295 if (board_group_info(b
, g
).libs
== 1)
298 /* In that case, we must be connected to at most one stone,
299 * or throwin will not destroy any eyes. */
300 if (group_is_onestone(b
, g
))
307 is_bad_selfatari_slow(struct board
*b
, enum stone color
, coord_t to
)
310 fprintf(stderr
, "sar check %s %s\n", stone2str(color
), coord2sstr(to
, b
));
311 /* Assess if we actually gain any liberties by this escape route.
312 * Note that this is not 100% as we cannot check whether we are
313 * connecting out or just to ourselves. */
315 struct selfatari_state s
;
316 memset(&s
, 0, sizeof(s
));
319 foreach_neighbor(b
, to
, {
320 enum stone color
= board_at(b
, c
);
321 s
.groupids
[color
][s
.groupcts
[color
]++] = group_at(b
, c
);
324 /* We have shortage of liberties; that's the point. */
325 assert(s
.groupcts
[S_NONE
] <= 1);
327 d
= examine_friendly_groups(b
, color
, to
, &s
);
332 fprintf(stderr
, "no friendly group\n");
334 d
= examine_enemy_groups(b
, color
, to
, &s
);
339 fprintf(stderr
, "no escape\n");
341 d
= setup_nakade_or_snapback(b
, color
, to
, &s
);
346 fprintf(stderr
, "no nakade group\n");
348 d
= check_throwin(b
, color
, to
, &s
);
353 fprintf(stderr
, "no throw-in group\n");
355 /* No way to pull out, no way to connect out. This really
356 * is a bad self-atari! */
362 selfatari_cousin(struct board
*b
, enum stone color
, coord_t coord
)
364 group_t groups
[4]; int groups_n
= 0;
365 foreach_neighbor(b
, coord
, {
366 enum stone s
= board_at(b
, c
);
367 if (s
!= color
) continue;
368 group_t g
= group_at(b
, c
);
369 if (board_group_info(b
, g
).libs
== 2)
370 groups
[groups_n
++] = g
;
375 group_t group
= groups
[fast_random(groups_n
)];
377 coord_t lib2
= board_group_other_lib(b
, group
, coord
);
378 if (is_bad_selfatari(b
, color
, lib2
))