9 struct selfatari_state
{
11 group_t groupids
[S_MAX
][4];
13 /* This is set if this move puts a group out of _all_
14 * liberties; we need to watch out for snapback then. */
15 bool friend_has_no_libs
;
16 /* We may have one liberty, but be looking for one more.
17 * In that case, @needs_more_lib is id of group
18 * already providing one, don't consider it again. */
19 group_t needs_more_lib
;
20 /* ID of the first liberty, providing it again is not
22 coord_t needs_more_lib_except
;
26 examine_friendly_groups(struct board
*b
, enum stone color
, coord_t to
, struct selfatari_state
*s
)
28 for (int i
= 0; i
< s
->groupcts
[color
]; i
++) {
29 /* We can escape by connecting to this group if it's
31 group_t g
= s
->groupids
[color
][i
];
33 if (board_group_info(b
, g
).libs
== 1) {
34 if (!s
->needs_more_lib
)
35 s
->friend_has_no_libs
= true;
36 // or we already have a friend with 1 lib
40 /* Could we self-atari the group here? */
41 if (board_group_info(b
, g
).libs
> 2)
44 /* We need to have another liberty, and
45 * it must not be the other liberty of
47 int lib2
= board_group_info(b
, g
).lib
[0];
48 if (lib2
== to
) lib2
= board_group_info(b
, g
).lib
[1];
49 /* Maybe we already looked at another
50 * group providing one liberty? */
51 if (s
->needs_more_lib
&& s
->needs_more_lib
!= g
52 && s
->needs_more_lib_except
!= lib2
)
55 /* Can we get the liberty locally? */
56 /* Yes if we are route to more liberties... */
57 if (s
->groupcts
[S_NONE
] > 1)
59 /* ...or one liberty, but not lib2. */
60 if (s
->groupcts
[S_NONE
] > 0
61 && !coord_is_adjecent(lib2
, to
, b
))
64 /* ...ok, then we can still contribute a liberty
65 * later by capturing something. */
66 s
->needs_more_lib
= g
;
67 s
->needs_more_lib_except
= lib2
;
68 s
->friend_has_no_libs
= false;
75 examine_enemy_groups(struct board
*b
, enum stone color
, coord_t to
, struct selfatari_state
*s
)
77 /* We may be able to gain a liberty by capturing this group. */
78 group_t can_capture
= 0;
80 /* Examine enemy groups: */
81 for (int i
= 0; i
< s
->groupcts
[stone_other(color
)]; i
++) {
82 /* We can escape by capturing this group if it's in atari. */
83 group_t g
= s
->groupids
[stone_other(color
)][i
];
84 if (board_group_info(b
, g
).libs
> 1)
87 /* But we need to get to at least two liberties by this;
88 * we already have one outside liberty, or the group is
89 * more than 1 stone (in that case, capturing is always
91 if (s
->groupcts
[S_NONE
] > 0 || !group_is_onestone(b
, g
))
93 /* ...or, it's a ko stone, */
94 if (neighbor_count_at(b
, g
, color
) + neighbor_count_at(b
, g
, S_OFFBOARD
) == 3) {
95 /* and we don't have a group to save: then, just taking
96 * single stone means snapback! */
97 if (!s
->friend_has_no_libs
)
100 /* ...or, we already have one indirect liberty provided
101 * by another group. */
102 if (s
->needs_more_lib
|| (can_capture
&& can_capture
!= g
))
108 //fprintf(stderr, "no cap group\n");
110 if (!s
->needs_more_lib
&& !can_capture
&& !s
->groupcts
[S_NONE
]) {
111 /* We have no hope for more fancy tactics - this move is simply
112 * a suicide, not even a self-atari. */
113 //fprintf(stderr, "suicide\n");
116 /* XXX: I wonder if it makes sense to continue if we actually
117 * just !s->needs_more_lib. */
123 setup_nakade_or_snapback(struct board
*b
, enum stone color
, coord_t to
, struct selfatari_state
*s
)
125 /* There is another possibility - we can self-atari if it is
126 * a nakade: we put an enemy group in atari from the inside. */
127 /* This branch also allows eyes falsification:
128 * O O O . . (This is different from throw-in to false eye
129 * X X O O . checked below in that there is no X stone at the
130 * X . X O . right of the star point in this diagram.)
133 /* TODO: Allow to only nakade if the created shape is dead
134 * (http://senseis.xmp.net/?Nakade). */
136 /* This branch also covers snapback, which is kind of special
137 * nakade case. ;-) */
138 for (int i
= 0; i
< s
->groupcts
[stone_other(color
)]; i
++) {
139 group_t g
= s
->groupids
[stone_other(color
)][i
];
140 if (board_group_info(b
, g
).libs
!= 2)
142 /* Simple check not to re-examine the same group. */
143 if (i
> 0 && s
->groupids
[stone_other(color
)][i
] == s
->groupids
[stone_other(color
)][i
- 1])
146 /* We must make sure the other liberty of that group:
147 * (i) is an internal liberty
148 * (ii) filling it to capture our group will not gain
151 /* Let's look at the other liberty neighbors: */
152 int lib2
= board_group_info(b
, g
).lib
[0];
153 if (lib2
== to
) lib2
= board_group_info(b
, g
).lib
[1];
154 foreach_neighbor(b
, lib2
, {
155 /* This neighbor of course does not contribute
156 * anything to the enemy. */
157 if (board_at(b
, c
) == S_OFFBOARD
)
160 /* If the other liberty has empty neighbor,
161 * it must be the original liberty; otherwise,
162 * since the whole group has only 2 liberties,
163 * the other liberty may not be internal and
164 * we are nakade'ing eyeless group from outside,
165 * which is stupid. */
166 if (board_at(b
, c
) == S_NONE
) {
173 int g2
= group_at(b
, c
);
174 /* If the neighbor is of our color, it must
175 * be our group; if it is a different group,
176 * it must not be in atari. */
177 /* X X X X We will not allow play on 'a',
178 * X X a X because 'b' would capture two
179 * X O b X different groups, forming two
181 if (board_at(b
, c
) == color
) {
182 if (board_group_info(b
, group_at(b
, c
)).libs
> 1)
184 /* Our group == one of the groups
185 * we (@to) are connected to. */
187 for (j
= 0; j
< 4; j
++)
188 if (s
->groupids
[color
][j
] == g2
)
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 (s
->groupcts
[color
] == 1 && group_is_onestone(b
, s
->groupids
[color
][0])))
217 /* We would create more than 2-stone group; in that
218 * case, the liberty of our result must be lib2,
219 * indicating this really is a nakade. */
220 for (int j
= 0; j
< s
->groupcts
[color
]; j
++) {
221 group_t g2
= s
->groupids
[color
][j
];
222 assert(board_group_info(b
, g2
).libs
<= 2);
223 if (board_group_info(b
, g2
).libs
== 2) {
224 if (board_group_info(b
, g2
).lib
[0] != lib2
225 && board_group_info(b
, g2
).lib
[1] != lib2
)
228 assert(board_group_info(b
, g2
).lib
[0] == to
);
234 /* Unless we are dealing with snapback setup, we don't need to look
236 if (!s
->groupcts
[color
])
244 check_throwin(struct board
*b
, enum stone color
, coord_t to
, struct selfatari_state
*s
)
246 /* We can be throwing-in to false eye:
247 * X X X O X X X O X X X X X
248 * X . * X * O . X * O O . X
249 * # # # # # # # # # # # # # */
250 /* We cannot sensibly throw-in into a corner. */
251 if (neighbor_count_at(b
, to
, S_OFFBOARD
) < 2
252 && neighbor_count_at(b
, to
, stone_other(color
))
253 + neighbor_count_at(b
, to
, S_OFFBOARD
) == 3
254 && board_is_false_eyelike(b
, &to
, stone_other(color
))) {
255 assert(s
->groupcts
[color
] <= 1);
256 /* Single-stone throw-in may be ok... */
257 if (s
->groupcts
[color
] == 0) {
258 /* O X . There is one problem - when it's
259 * . * X actually not a throw-in!
261 foreach_neighbor(b
, to
, {
262 if (board_at(b
, c
) == S_NONE
) {
263 /* Is the empty neighbor an escape path? */
264 /* (Note that one S_NONE neighbor is already @to.) */
265 if (neighbor_count_at(b
, c
, stone_other(color
))
266 + neighbor_count_at(b
, c
, S_OFFBOARD
) < 2)
273 /* Multi-stone throwin...? */
274 assert(s
->groupcts
[color
] == 1);
275 group_t g
= s
->groupids
[color
][0];
277 assert(board_group_info(b
, g
).libs
<= 2);
278 /* Suicide is definitely NOT ok, no matter what else
280 if (board_group_info(b
, g
).libs
== 1)
283 /* In that case, we must be connected to at most one stone,
284 * or throwin will not destroy any eyes. */
285 if (group_is_onestone(b
, g
))
292 is_bad_selfatari_slow(struct board
*b
, enum stone color
, coord_t to
)
294 //fprintf(stderr, "sar check %s %s\n", stone2str(color), coord2sstr(to, b));
295 /* Assess if we actually gain any liberties by this escape route.
296 * Note that this is not 100% as we cannot check whether we are
297 * connecting out or just to ourselves. */
299 struct selfatari_state s
;
300 memset(&s
, 0, sizeof(s
));
303 foreach_neighbor(b
, to
, {
304 enum stone color
= board_at(b
, c
);
305 s
.groupids
[color
][s
.groupcts
[color
]++] = group_at(b
, c
);
308 /* We have shortage of liberties; that's the point. */
309 assert(s
.groupcts
[S_NONE
] <= 1);
311 d
= examine_friendly_groups(b
, color
, to
, &s
);
315 //fprintf(stderr, "no friendly group\n");
317 d
= examine_enemy_groups(b
, color
, to
, &s
);
321 //fprintf(stderr, "no escape\n");
323 d
= setup_nakade_or_snapback(b
, color
, to
, &s
);
327 //fprintf(stderr, "no nakade group\n");
329 d
= check_throwin(b
, color
, to
, &s
);
333 //fprintf(stderr, "no throw-in group\n");
335 /* No way to pull out, no way to connect out. This really
336 * is a bad self-atari! */
341 /* Is this ladder breaker friendly for the one who catches ladder. */
343 ladder_catcher(struct board
*b
, int x
, int y
, enum stone laddered
)
345 enum stone breaker
= board_atxy(b
, x
, y
);
346 return breaker
== stone_other(laddered
) || breaker
== S_OFFBOARD
;
350 is_border_ladder(struct board
*b
, coord_t coord
, enum stone lcolor
)
352 int x
= coord_x(coord
, b
), y
= coord_y(coord
, b
);
355 fprintf(stderr
, "border ladder\n");
356 /* Direction along border; xd is horiz. border, yd vertical. */
358 if (board_atxy(b
, x
+ 1, y
) == S_OFFBOARD
|| board_atxy(b
, x
- 1, y
) == S_OFFBOARD
)
362 /* Direction from the border; -1 is above/left, 1 is below/right. */
363 int dd
= (board_atxy(b
, x
+ yd
, y
+ xd
) == S_OFFBOARD
) ? 1 : -1;
365 fprintf(stderr
, "xd %d yd %d dd %d\n", xd
, yd
, dd
);
371 /* This is normally caught, unless we have friends both above
373 if (board_atxy(b
, x
+ xd
* 2, y
+ yd
* 2) == lcolor
374 && board_atxy(b
, x
- xd
* 2, y
- yd
* 2) == lcolor
)
376 /* ...or can't block where we need because of shortage
378 int libs1
= board_group_info(b
, group_atxy(b
, x
+ xd
- yd
* dd
, y
+ yd
- xd
* dd
)).libs
;
379 int libs2
= board_group_info(b
, group_atxy(b
, x
- xd
- yd
* dd
, y
- yd
- xd
* dd
)).libs
;
381 fprintf(stderr
, "libs1 %d libs2 %d\n", libs1
, libs2
);
382 if (libs1
< 2 && libs2
< 2)
384 if (board_atxy(b
, x
+ xd
* 2, y
+ yd
* 2) == lcolor
&& libs1
< 3)
386 if (board_atxy(b
, x
- xd
* 2, y
- yd
* 2) == lcolor
&& libs2
< 3)
391 /* This is very trivial and gets a lot of corner cases wrong.
392 * We need this to be just very fast. One important point is
393 * that we sometimes might not notice a ladder but if we do,
394 * it should always work; thus we can use this for strong
395 * negative hinting safely. */
397 is_middle_ladder(struct board
*b
, coord_t coord
, enum stone lcolor
)
399 int x
= coord_x(coord
, b
), y
= coord_y(coord
, b
);
401 /* Figure out the ladder direction */
403 xd
= board_atxy(b
, x
+ 1, y
) == S_NONE
? 1 : board_atxy(b
, x
- 1, y
) == S_NONE
? -1 : 0;
404 yd
= board_atxy(b
, x
, y
+ 1) == S_NONE
? 1 : board_atxy(b
, x
, y
- 1) == S_NONE
? -1 : 0;
408 fprintf(stderr
, "no ladder, too little space; self-atari?\n");
412 /* For given (xd,yd), we have two possibilities where to move
413 * next. Consider (-1,-1):
418 bool horiz_first
= ladder_catcher(b
, x
, y
- yd
, lcolor
); // left case
419 bool vert_first
= ladder_catcher(b
, x
- xd
, y
, lcolor
); // right case
421 /* We don't have to look at the other 'X' in the position - if it
422 * wouldn't be there, the group wouldn't be in atari. */
424 /* We do only tight ladders, not loose ladders. Furthermore,
425 * the ladders need to be simple:
427 * c O X supported . c O unsupported
430 assert(!(horiz_first
&& vert_first
));
431 if (!horiz_first
&& !vert_first
) {
432 /* TODO: In case of basic non-simple ladder, play out both variants. */
434 fprintf(stderr
, "non-simple ladder\n");
438 /* We do that below for further moves, but now initially - check
439 * that at 'c', we aren't putting any of the catching stones
441 #if 1 // this might be broken?
442 #define check_catcher_danger(b, x_, y_) do { \
443 if (board_atxy(b, (x_), (y_)) != S_OFFBOARD \
444 && board_group_info(b, group_atxy(b, (x_), (y_))).libs <= 2) { \
446 fprintf(stderr, "ladder failed - atari at the beginning\n"); \
451 check_catcher_danger(b
, x
, y
- yd
);
452 check_catcher_danger(b
, x
- xd
, y
+ yd
);
454 check_catcher_danger(b
, x
- xd
, y
);
455 check_catcher_danger(b
, x
+ xd
, y
- yd
);
457 #undef check_catcher_danger
460 #define ladder_check(xd1_, yd1_, xd2_, yd2_, xd3_, yd3_) \
461 if (board_atxy(b, x, y) != S_NONE) { \
462 /* Did we hit a stone when playing out ladder? */ \
463 if (ladder_catcher(b, x, y, lcolor)) \
464 return true; /* ladder works */ \
465 if (board_group_info(b, group_atxy(b, x, y)).lib[0] > 0) \
466 return false; /* friend that's not in atari himself */ \
468 /* No. So we are at new position. \
469 * We need to check indirect ladder breakers. */ \
471 * . x o O 1 <- only at O we can check for o at 2 \
472 * x o o x . otherwise x at O would be still deadly \
474 * We check for o and x at 1, these are vital. \
475 * We check only for o at 2; x at 2 would mean we \
476 * need to fork (one step earlier). */ \
477 coord_t c1 = coord_xy(b, x + (xd1_), y + (yd1_)); \
478 enum stone s1 = board_at(b, c1); \
479 if (s1 == lcolor) return false; \
480 if (s1 == stone_other(lcolor)) { \
481 /* One more thing - if the position at 3 is \
482 * friendly and safe, we escaped anyway! */ \
483 coord_t c3 = coord_xy(b, x + (xd3_), y + (yd3_)); \
484 return board_at(b, c3) != lcolor \
485 || board_group_info(b, group_at(b, c3)).libs < 2; \
487 enum stone s2 = board_atxy(b, x + (xd2_), y + (yd2_)); \
488 if (s2 == lcolor) return false; \
489 /* Then, can X actually "play" 1 in the ladder? */ \
490 if (neighbor_count_at(b, c1, lcolor) + neighbor_count_at(b, c1, S_OFFBOARD) >= 2) \
491 return false; /* It would be self-atari! */ \
493 #define ladder_horiz do { if (DEBUGL(6)) fprintf(stderr, "%d,%d horiz step (%d,%d)\n", x, y, xd, yd); x += xd; ladder_check(xd, 0, -2 * xd, yd, 0, yd); } while (0)
494 #define ladder_vert do { if (DEBUGL(6)) fprintf(stderr, "%d,%d vert step of (%d,%d)\n", x, y, xd, yd); y += yd; ladder_check(0, yd, xd, -2 * yd, xd, 0); } while (0)
496 if (ladder_catcher(b
, x
- xd
, y
, lcolor
))
506 board_stone_radar(struct board
*b
, coord_t coord
, int distance
)
509 coord_x(coord
, b
) - distance
,
510 coord_y(coord
, b
) - distance
,
511 coord_x(coord
, b
) + distance
,
512 coord_y(coord
, b
) + distance
514 for (int i
= 0; i
< 4; i
++)
517 else if (bounds
[i
] > board_size(b
) - 2)
518 bounds
[i
] = board_size(b
) - 2;
519 for (int x
= bounds
[0]; x
<= bounds
[2]; x
++)
520 for (int y
= bounds
[1]; y
<= bounds
[3]; y
++)
521 if (board_atxy(b
, x
, y
) != S_NONE
) {
522 /* fprintf(stderr, "radar %d,%d,%d: %d,%d (%d)\n",
523 coord_x(coord, b), coord_y(coord, b),
524 distance, x, y, board_atxy(b, x, y)); */
531 cfg_distances(struct board
*b
, coord_t start
, int *distances
, int maxdist
)
533 /* Queue for d+1 spots; no two spots of the same group
534 * should appear in the queue. */
535 #define qinc(x) (x = ((x + 1) >= board_size2(b) ? ((x) + 1 - board_size2(b)) : (x) + 1))
536 coord_t queue
[board_size2(b
)]; int qstart
= 0, qstop
= 0;
539 distances
[c
] = board_at(b
, c
) == S_OFFBOARD
? maxdist
+ 1 : -1;
542 queue
[qstop
++] = start
;
543 for (int d
= 0; d
<= maxdist
; d
++) {
544 /* Process queued moves, while setting the queue
546 int qa
= qstart
, qb
= qstop
;
548 for (int q
= qa
; q
< qb
; qinc(q
)) {
549 #define cfg_one(coord, grp) do {\
550 distances[coord] = d; \
551 foreach_neighbor (b, coord, { \
552 if (distances[c] < 0 && (!grp || group_at(b, coord) != grp)) { \
558 coord_t cq
= queue
[q
];
559 if (distances
[cq
] >= 0)
560 continue; /* We already looked here. */
561 if (board_at(b
, cq
) == S_NONE
) {
564 group_t g
= group_at(b
, cq
);
565 foreach_in_group(b
, g
) {
567 } foreach_in_group_end
;
574 if (distances
[c
] < 0)
575 distances
[c
] = maxdist
+ 1;
580 board_effective_handicap(struct board
*b
)
582 /* For very small/very large boards, we might want
583 * to account for different "base komi". */
584 float first_move
= 7.5; // point value of move on empty board
585 assert(b
->handicap
!= 1);
586 return (b
->handicap
? b
->handicap
: 1) * first_move
- b
->komi
;