probdist_pick(): Make the ignore list pass-terminated
[pachi/json.git] / tactics.c
blob0735ee5c7be1b64b4f16339e1f1f2540be9e5c9f
1 #include <assert.h>
2 #include <stdio.h>
3 #include <stdlib.h>
5 #define DEBUG
6 #include "board.h"
7 #include "debug.h"
8 #include "tactics.h"
11 struct selfatari_state {
12 int groupcts[S_MAX];
13 group_t groupids[S_MAX][4];
15 /* This is set if this move puts a group out of _all_
16 * liberties; we need to watch out for snapback then. */
17 bool friend_has_no_libs;
18 /* We may have one liberty, but be looking for one more.
19 * In that case, @needs_more_lib is id of group
20 * already providing one, don't consider it again. */
21 group_t needs_more_lib;
22 /* ID of the first liberty, providing it again is not
23 * interesting. */
24 coord_t needs_more_lib_except;
27 static int
28 examine_friendly_groups(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
30 for (int i = 0; i < s->groupcts[color]; i++) {
31 /* We can escape by connecting to this group if it's
32 * not in atari. */
33 group_t g = s->groupids[color][i];
35 if (board_group_info(b, g).libs == 1) {
36 if (!s->needs_more_lib)
37 s->friend_has_no_libs = true;
38 // or we already have a friend with 1 lib
39 continue;
42 /* Could we self-atari the group here? */
43 if (board_group_info(b, g).libs > 2)
44 return false;
46 /* We need to have another liberty, and
47 * it must not be the other liberty of
48 * the group. */
49 int lib2 = board_group_info(b, g).lib[0];
50 if (lib2 == to) lib2 = board_group_info(b, g).lib[1];
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)
55 return false;
57 /* Can we get the liberty locally? */
58 /* Yes if we are route to more liberties... */
59 if (s->groupcts[S_NONE] > 1)
60 return false;
61 /* ...or one liberty, but not lib2. */
62 if (s->groupcts[S_NONE] > 0
63 && !coord_is_adjecent(lib2, to, b))
64 return false;
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;
73 return -1;
76 static int
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)
87 continue;
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
92 * nice!). */
93 if (s->groupcts[S_NONE] > 0 || !group_is_onestone(b, g))
94 return false;
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)
100 return false;
102 /* ...or, we already have one indirect liberty provided
103 * by another group. */
104 if (s->needs_more_lib || (can_capture && can_capture != g))
105 return false;
106 can_capture = g;
110 if (DEBUGL(6))
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. */
116 if (DEBUGL(6))
117 fprintf(stderr, "suicide\n");
118 return true;
120 /* XXX: I wonder if it makes sense to continue if we actually
121 * just !s->needs_more_lib. */
123 return -1;
126 static int
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.)
135 * X X X O O
136 * X O * . . */
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)
145 goto next_group;
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])
148 continue;
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
153 * safety */
155 /* Let's look at the other liberty neighbors: */
156 int lib2 = board_group_info(b, g).lib[0];
157 if (lib2 == to) lib2 = board_group_info(b, g).lib[1];
158 foreach_neighbor(b, lib2, {
159 /* This neighbor of course does not contribute
160 * anything to the enemy. */
161 if (board_at(b, c) == S_OFFBOARD)
162 continue;
164 /* If the other liberty has empty neighbor,
165 * it must be the original liberty; otherwise,
166 * since the whole group has only 2 liberties,
167 * the other liberty may not be internal and
168 * we are nakade'ing eyeless group from outside,
169 * which is stupid. */
170 if (board_at(b, c) == S_NONE) {
171 if (c == to)
172 continue;
173 else
174 goto next_group;
177 int g2 = group_at(b, c);
178 /* If the neighbor is of our color, it must
179 * be our group; if it is a different group,
180 * it must not be in atari. */
181 /* X X X X We will not allow play on 'a',
182 * X X a X because 'b' would capture two
183 * X O b X different groups, forming two
184 * X X X X eyes. */
185 if (board_at(b, c) == color) {
186 if (board_group_info(b, group_at(b, c)).libs > 1)
187 continue;
188 /* Our group == one of the groups
189 * we (@to) are connected to. */
190 int j;
191 for (j = 0; j < 4; j++)
192 if (s->groupids[color][j] == g2)
193 break;
194 if (j == 4)
195 goto next_group;
196 continue;
199 /* The neighbor is enemy color. It's ok if
200 * it's still the same group or this is its
201 * only liberty. */
202 if (g == g2 || board_group_info(b, g2).libs == 1)
203 continue;
204 /* Otherwise, it must have the exact same
205 * liberties as the original enemy group. */
206 if (board_group_info(b, g2).libs == 2
207 && (board_group_info(b, g2).lib[0] == to
208 || board_group_info(b, g2).lib[1] == to))
209 continue;
211 goto next_group;
214 /* Now, we must distinguish between nakade and eye
215 * falsification; we must not falsify an eye by more
216 * than two stones. */
217 if (s->groupcts[color] < 1 ||
218 (s->groupcts[color] == 1 && group_is_onestone(b, s->groupids[color][0])))
219 return false;
221 /* We would create more than 2-stone group; in that
222 * case, the liberty of our result must be lib2,
223 * indicating this really is a nakade. */
224 for (int j = 0; j < s->groupcts[color]; j++) {
225 group_t g2 = s->groupids[color][j];
226 assert(board_group_info(b, g2).libs <= 2);
227 if (board_group_info(b, g2).libs == 2) {
228 if (board_group_info(b, g2).lib[0] != lib2
229 && board_group_info(b, g2).lib[1] != lib2)
230 goto next_group;
231 } else {
232 assert(board_group_info(b, g2).lib[0] == to);
236 return false;
237 next_group:
238 /* Unless we are dealing with snapback setup, we don't need to look
239 * further. */
240 if (s->groupcts[color])
241 return -1;
244 return -1;
247 static int
248 check_throwin(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
250 /* We can be throwing-in to false eye:
251 * X X X O X X X O X X X X X
252 * X . * X * O . X * O O . X
253 * # # # # # # # # # # # # # */
254 /* We cannot sensibly throw-in into a corner. */
255 if (neighbor_count_at(b, to, S_OFFBOARD) < 2
256 && neighbor_count_at(b, to, stone_other(color))
257 + neighbor_count_at(b, to, S_OFFBOARD) == 3
258 && board_is_false_eyelike(b, to, stone_other(color))) {
259 assert(s->groupcts[color] <= 1);
260 /* Single-stone throw-in may be ok... */
261 if (s->groupcts[color] == 0) {
262 /* O X . There is one problem - when it's
263 * . * X actually not a throw-in!
264 * # # # */
265 foreach_neighbor(b, to, {
266 if (board_at(b, c) == S_NONE) {
267 /* Is the empty neighbor an escape path? */
268 /* (Note that one S_NONE neighbor is already @to.) */
269 if (neighbor_count_at(b, c, stone_other(color))
270 + neighbor_count_at(b, c, S_OFFBOARD) < 2)
271 return -1;
274 return false;
277 /* Multi-stone throwin...? */
278 assert(s->groupcts[color] == 1);
279 group_t g = s->groupids[color][0];
281 assert(board_group_info(b, g).libs <= 2);
282 /* Suicide is definitely NOT ok, no matter what else
283 * we could test. */
284 if (board_group_info(b, g).libs == 1)
285 return true;
287 /* In that case, we must be connected to at most one stone,
288 * or throwin will not destroy any eyes. */
289 if (group_is_onestone(b, g))
290 return false;
292 return -1;
295 bool
296 is_bad_selfatari_slow(struct board *b, enum stone color, coord_t to)
298 if (DEBUGL(5))
299 fprintf(stderr, "sar check %s %s\n", stone2str(color), coord2sstr(to, b));
300 /* Assess if we actually gain any liberties by this escape route.
301 * Note that this is not 100% as we cannot check whether we are
302 * connecting out or just to ourselves. */
304 struct selfatari_state s;
305 memset(&s, 0, sizeof(s));
306 int d;
308 foreach_neighbor(b, to, {
309 enum stone color = board_at(b, c);
310 s.groupids[color][s.groupcts[color]++] = group_at(b, c);
313 /* We have shortage of liberties; that's the point. */
314 assert(s.groupcts[S_NONE] <= 1);
316 d = examine_friendly_groups(b, color, to, &s);
317 if (d >= 0)
318 return d;
320 if (DEBUGL(6))
321 fprintf(stderr, "no friendly group\n");
323 d = examine_enemy_groups(b, color, to, &s);
324 if (d >= 0)
325 return d;
327 if (DEBUGL(6))
328 fprintf(stderr, "no escape\n");
330 d = setup_nakade_or_snapback(b, color, to, &s);
331 if (d >= 0)
332 return d;
334 if (DEBUGL(6))
335 fprintf(stderr, "no nakade group\n");
337 d = check_throwin(b, color, to, &s);
338 if (d >= 0)
339 return d;
341 if (DEBUGL(6))
342 fprintf(stderr, "no throw-in group\n");
344 /* No way to pull out, no way to connect out. This really
345 * is a bad self-atari! */
346 return true;
350 /* Is this ladder breaker friendly for the one who catches ladder. */
351 static bool
352 ladder_catcher(struct board *b, int x, int y, enum stone laddered)
354 enum stone breaker = board_atxy(b, x, y);
355 return breaker == stone_other(laddered) || breaker == S_OFFBOARD;
358 bool
359 is_border_ladder(struct board *b, coord_t coord, enum stone lcolor)
361 int x = coord_x(coord, b), y = coord_y(coord, b);
363 if (DEBUGL(5))
364 fprintf(stderr, "border ladder\n");
365 /* Direction along border; xd is horiz. border, yd vertical. */
366 int xd = 0, yd = 0;
367 if (board_atxy(b, x + 1, y) == S_OFFBOARD || board_atxy(b, x - 1, y) == S_OFFBOARD)
368 yd = 1;
369 else
370 xd = 1;
371 /* Direction from the border; -1 is above/left, 1 is below/right. */
372 int dd = (board_atxy(b, x + yd, y + xd) == S_OFFBOARD) ? 1 : -1;
373 if (DEBUGL(6))
374 fprintf(stderr, "xd %d yd %d dd %d\n", xd, yd, dd);
375 /* | ? ?
376 * | . O #
377 * | c X #
378 * | . O #
379 * | ? ? */
380 /* This is normally caught, unless we have friends both above
381 * and below... */
382 if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor
383 && board_atxy(b, x - xd * 2, y - yd * 2) == lcolor)
384 return false;
385 /* ...or can't block where we need because of shortage
386 * of liberties. */
387 int libs1 = board_group_info(b, group_atxy(b, x + xd - yd * dd, y + yd - xd * dd)).libs;
388 int libs2 = board_group_info(b, group_atxy(b, x - xd - yd * dd, y - yd - xd * dd)).libs;
389 if (DEBUGL(6))
390 fprintf(stderr, "libs1 %d libs2 %d\n", libs1, libs2);
391 if (libs1 < 2 && libs2 < 2)
392 return false;
393 if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor && libs1 < 3)
394 return false;
395 if (board_atxy(b, x - xd * 2, y - yd * 2) == lcolor && libs2 < 3)
396 return false;
397 return true;
400 /* This is very trivial and gets a lot of corner cases wrong.
401 * We need this to be just very fast. One important point is
402 * that we sometimes might not notice a ladder but if we do,
403 * it should always work; thus we can use this for strong
404 * negative hinting safely. */
405 bool
406 is_middle_ladder(struct board *b, coord_t coord, enum stone lcolor)
408 int x = coord_x(coord, b), y = coord_y(coord, b);
410 /* Figure out the ladder direction */
411 int xd, yd;
412 xd = board_atxy(b, x + 1, y) == S_NONE ? 1 : board_atxy(b, x - 1, y) == S_NONE ? -1 : 0;
413 yd = board_atxy(b, x, y + 1) == S_NONE ? 1 : board_atxy(b, x, y - 1) == S_NONE ? -1 : 0;
415 if (!xd || !yd) {
416 if (DEBUGL(5))
417 fprintf(stderr, "no ladder, too little space; self-atari?\n");
418 return false;
421 /* For given (xd,yd), we have two possibilities where to move
422 * next. Consider (-1,-1):
423 * n X . n c X
424 * c O X X O #
425 * X # # . X #
427 bool horiz_first = ladder_catcher(b, x, y - yd, lcolor); // left case
428 bool vert_first = ladder_catcher(b, x - xd, y, lcolor); // right case
430 /* We don't have to look at the other 'X' in the position - if it
431 * wouldn't be there, the group wouldn't be in atari. */
433 /* We do only tight ladders, not loose ladders. Furthermore,
434 * the ladders need to be simple:
435 * . X . . . X
436 * c O X supported . c O unsupported
437 * X # # X O #
439 assert(!(horiz_first && vert_first));
440 if (!horiz_first && !vert_first) {
441 /* TODO: In case of basic non-simple ladder, play out both variants. */
442 if (DEBUGL(5))
443 fprintf(stderr, "non-simple ladder\n");
444 return false;
447 /* We do that below for further moves, but now initially - check
448 * that at 'c', we aren't putting any of the catching stones
449 * in atari. */
450 #if 1 // this might be broken?
451 #define check_catcher_danger(b, x_, y_) do { \
452 if (board_atxy(b, (x_), (y_)) != S_OFFBOARD \
453 && board_group_info(b, group_atxy(b, (x_), (y_))).libs <= 2) { \
454 if (DEBUGL(5)) \
455 fprintf(stderr, "ladder failed - atari at the beginning\n"); \
456 return false; \
457 } } while (0)
459 if (horiz_first) {
460 check_catcher_danger(b, x, y - yd);
461 check_catcher_danger(b, x - xd, y + yd);
462 } else {
463 check_catcher_danger(b, x - xd, y);
464 check_catcher_danger(b, x + xd, y - yd);
466 #undef check_catcher_danger
467 #endif
469 #define ladder_check(xd1_, yd1_, xd2_, yd2_, xd3_, yd3_) \
470 if (board_atxy(b, x, y) != S_NONE) { \
471 /* Did we hit a stone when playing out ladder? */ \
472 if (ladder_catcher(b, x, y, lcolor)) \
473 return true; /* ladder works */ \
474 if (board_group_info(b, group_atxy(b, x, y)).lib[0] > 0) \
475 return false; /* friend that's not in atari himself */ \
476 } else { \
477 /* No. So we are at new position. \
478 * We need to check indirect ladder breakers. */ \
479 /* . 2 x 3 . \
480 * . x o O 1 <- only at O we can check for o at 2 \
481 * x o o x . otherwise x at O would be still deadly \
482 * o o x . . \
483 * We check for o and x at 1, these are vital. \
484 * We check only for o at 2; x at 2 would mean we \
485 * need to fork (one step earlier). */ \
486 coord_t c1 = coord_xy(b, x + (xd1_), y + (yd1_)); \
487 enum stone s1 = board_at(b, c1); \
488 if (s1 == lcolor) return false; \
489 if (s1 == stone_other(lcolor)) { \
490 /* One more thing - if the position at 3 is \
491 * friendly and safe, we escaped anyway! */ \
492 coord_t c3 = coord_xy(b, x + (xd3_), y + (yd3_)); \
493 return board_at(b, c3) != lcolor \
494 || board_group_info(b, group_at(b, c3)).libs < 2; \
496 enum stone s2 = board_atxy(b, x + (xd2_), y + (yd2_)); \
497 if (s2 == lcolor) return false; \
498 /* Then, can X actually "play" 1 in the ladder? */ \
499 if (neighbor_count_at(b, c1, lcolor) + neighbor_count_at(b, c1, S_OFFBOARD) >= 2) \
500 return false; /* It would be self-atari! */ \
502 #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)
503 #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)
505 if (ladder_catcher(b, x - xd, y, lcolor))
506 ladder_horiz;
507 do {
508 ladder_vert;
509 ladder_horiz;
510 } while (1);
514 bool
515 board_stone_radar(struct board *b, coord_t coord, int distance)
517 int bounds[4] = {
518 coord_x(coord, b) - distance,
519 coord_y(coord, b) - distance,
520 coord_x(coord, b) + distance,
521 coord_y(coord, b) + distance
523 for (int i = 0; i < 4; i++)
524 if (bounds[i] < 1)
525 bounds[i] = 1;
526 else if (bounds[i] > board_size(b) - 2)
527 bounds[i] = board_size(b) - 2;
528 for (int x = bounds[0]; x <= bounds[2]; x++)
529 for (int y = bounds[1]; y <= bounds[3]; y++)
530 if (board_atxy(b, x, y) != S_NONE) {
531 /* fprintf(stderr, "radar %d,%d,%d: %d,%d (%d)\n",
532 coord_x(coord, b), coord_y(coord, b),
533 distance, x, y, board_atxy(b, x, y)); */
534 return true;
536 return false;
540 void
541 cfg_distances(struct board *b, coord_t start, int *distances, int maxdist)
543 /* Queue for d+1 spots; no two spots of the same group
544 * should appear in the queue. */
545 #define qinc(x) (x = ((x + 1) >= board_size2(b) ? ((x) + 1 - board_size2(b)) : (x) + 1))
546 coord_t queue[board_size2(b)]; int qstart = 0, qstop = 0;
548 foreach_point(b) {
549 distances[c] = board_at(b, c) == S_OFFBOARD ? maxdist + 1 : -1;
550 } foreach_point_end;
552 queue[qstop++] = start;
553 for (int d = 0; d <= maxdist; d++) {
554 /* Process queued moves, while setting the queue
555 * for new wave. */
556 int qa = qstart, qb = qstop;
557 qstart = qstop;
558 for (int q = qa; q < qb; qinc(q)) {
559 #define cfg_one(coord, grp) do {\
560 distances[coord] = d; \
561 foreach_neighbor (b, coord, { \
562 if (distances[c] < 0 && (!grp || group_at(b, coord) != grp)) { \
563 queue[qstop] = c; \
564 qinc(qstop); \
566 }); \
567 } while (0)
568 coord_t cq = queue[q];
569 if (distances[cq] >= 0)
570 continue; /* We already looked here. */
571 if (board_at(b, cq) == S_NONE) {
572 cfg_one(cq, 0);
573 } else {
574 group_t g = group_at(b, cq);
575 foreach_in_group(b, g) {
576 cfg_one(c, g);
577 } foreach_in_group_end;
579 #undef cfg_one
583 foreach_point(b) {
584 if (distances[c] < 0)
585 distances[c] = maxdist + 1;
586 } foreach_point_end;
590 float
591 board_effective_handicap(struct board *b, int first_move_value)
593 assert(b->handicap != 1);
594 return (b->handicap ? b->handicap : 1) * first_move_value + 0.5 - b->komi;
598 bool
599 pass_is_safe(struct board *b, enum stone color, struct move_queue *mq)
601 float score = board_official_score(b, mq);
602 if (color == S_BLACK)
603 score = -score;
604 //fprintf(stderr, "%d score %f\n", color, score);
605 return (score > 0);
609 /* On average 25% of points remain empty at the end of a game */
610 #define EXPECTED_FINAL_EMPTY_PERCENT 25
612 /* Returns estimated number of remaining moves for one player until end of game. */
614 board_estimated_moves_left(struct board *b)
616 int total_points = (board_size(b)-2)*(board_size(b)-2);
617 int moves_left = (b->flen - total_points*EXPECTED_FINAL_EMPTY_PERCENT/100)/2;
618 return moves_left > MIN_MOVES_LEFT ? moves_left : MIN_MOVES_LEFT;