tactics.c

   1 #include <assert.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4
   5 #include "board.h"
   6 #include "debug.h"
   7
   8
   9 bool
  10 is_bad_selfatari_slow(struct board *b, enum stone color, coord_t to)
  11 {
  12         //fprintf(stderr, "sar check %s %s\n", stone2str(color), coord2sstr(to, b));
  13         /* Assess if we actually gain any liberties by this escape route.
  14          * Note that this is not 100% as we cannot check whether we are
  15          * connecting out or just to ourselves. */
  16         int groupcts[S_MAX] = {};
  17         group_t groupids[S_MAX][4] = {};
  18         foreach_neighbor(b, to, {
  19                 enum stone s = board_at(b, c);
  20                 groupids[s][groupcts[s]++] = group_at(b, c);
  21         });
  22
  23         /* We have shortage of liberties; that's the point. */
  24         assert(groupcts[S_NONE] <= 1);
  25
  26         /* This is set if this move puts a group out of _all_
  27          * liberties; we need to watch out for snapback then. */
  28         bool friend_has_no_libs = false;
  29         /* We may have one liberty, but be looking for one more.
  30          * In that case, @needs_more_lib is id of group
  31          * already providing one, don't consider it again. */
  32         group_t needs_more_lib = 0;
  33         /* ID of the first liberty, providing it again is not
  34          * interesting. */
  35         coord_t needs_more_lib_except = 0;
  36
  37         /* Examine friendly groups: */
  38         for (int i = 0; i < 4; i++) {
  39                 /* We can escape by connecting to this group if it's
  40                  * not in atari. */
  41                 group_t g = groupids[color][i];
  42                 if (!g) continue;
  43
  44                 if (board_group_info(b, g).libs == 1) {
  45                         if (!needs_more_lib)
  46                                 friend_has_no_libs = true;
  47                         // or we already have a friend with 1 lib
  48                         continue;
  49                 }
  50
  51                 /* Could we self-atari the group here? */
  52                 if (board_group_info(b, g).libs > 2)
  53                         return false;
  54
  55                 /* We need to have another liberty, and
  56                  * it must not be the other liberty of
  57                  * the group. */
  58                 int lib2 = board_group_info(b, g).lib[0];
  59                 if (lib2 == to) lib2 = board_group_info(b, g).lib[1];
  60                 /* Maybe we already looked at another
  61                  * group providing one liberty? */
  62                 if (needs_more_lib && needs_more_lib != g
  63                     && needs_more_lib_except != lib2)
  64                         return false;
  65
  66                 /* Can we get the liberty locally? */
  67                 /* Yes if we are route to more liberties... */
  68                 if (groupcts[S_NONE] > 1)
  69                         return false;
  70                 /* ...or one liberty, but not lib2. */
  71                 if (groupcts[S_NONE] > 0
  72                     && !coord_is_adjecent(lib2, to, b))
  73                         return false;
  74
  75                 /* ...ok, then we can still contribute a liberty
  76                  * later by capturing something. */
  77                 needs_more_lib = g;
  78                 needs_more_lib_except = lib2;
  79                 friend_has_no_libs = false;
  80         }
  81
  82         //fprintf(stderr, "no friendly group\n");
  83
  84         /* We may be able to gain a liberty by capturing this group. */
  85         group_t can_capture = 0;
  86
  87         /* Examine enemy groups: */
  88         for (int i = 0; i < 4; i++) {
  89                 /* We can escape by capturing this group if it's in atari. */
  90                 group_t g = groupids[stone_other(color)][i];
  91                 if (!g || board_group_info(b, g).libs > 1)
  92                         continue;
  93
  94                 /* But we need to get to at least two liberties by this;
  95                  * we already have one outside liberty, or the group is
  96                  * more than 1 stone (in that case, capturing is always
  97                  * nice!). */
  98                 if (groupcts[S_NONE] > 0 || !group_is_onestone(b, g))
  99                         return false;
 100                 /* ...or, it's a ko stone, */
 101                 if (neighbor_count_at(b, g, color) + neighbor_count_at(b, g, S_OFFBOARD) == 3) {
 102                         /* and we don't have a group to save: then, just taking
 103                          * single stone means snapback! */
 104                         if (!friend_has_no_libs)
 105                                 return false;
 106                 }
 107                 /* ...or, we already have one indirect liberty provided
 108                  * by another group. */
 109                 if (needs_more_lib || (can_capture && can_capture != g))
 110                         return false;
 111                 can_capture = g;
 112
 113         }
 114
 115         //fprintf(stderr, "no cap group\n");
 116
 117         if (!needs_more_lib && !can_capture && !groupcts[S_NONE]) {
 118                 /* We have no hope for more fancy tactics - this move is simply
 119                  * a suicide, not even a self-atari. */
 120                 //fprintf(stderr, "suicide\n");
 121                 return true;
 122         }
 123         /* XXX: I wonder if it makes sense to continue if we actually
 124          * just !needs_more_lib. */
 125
 126         /* There is another possibility - we can self-atari if it is
 127          * a nakade: we put an enemy group in atari from the inside. */
 128         /* This branch also allows eyes falsification:
 129          * O O O . .  (This is different from throw-in to false eye
 130          * X X O O .  checked below in that there is no X stone at the
 131          * X . X O .  right of the star point in this diagram.)
 132          * X X X O O
 133          * X O * . . */
 134         /* TODO: Allow to only nakade if the created shape is dead
 135          * (http://senseis.xmp.net/?Nakade). */
 136
 137         /* This branch also covers snapback, which is kind of special
 138          * nakade case. ;-) */
 139         for (int i = 0; i < 4; i++) {
 140                 group_t g = groupids[stone_other(color)][i];
 141                 if (!g || board_group_info(b, g).libs != 2)
 142                         continue;
 143                 /* Simple check not to re-examine the same group. */
 144                 if (i > 0 && groupids[stone_other(color)][i] == groupids[stone_other(color)][i - 1])
 145                         continue;
 146
 147                 /* We must make sure the other liberty of that group:
 148                  * (i) is an internal liberty
 149                  * (ii) filling it to capture our group will not gain
 150                  * safety */
 151
 152                 /* Let's look at the other liberty neighbors: */
 153                 int lib2 = board_group_info(b, g).lib[0];
 154                 if (lib2 == to) lib2 = board_group_info(b, g).lib[1];
 155                 foreach_neighbor(b, lib2, {
 156                         /* This neighbor of course does not contribute
 157                          * anything to the enemy. */
 158                         if (board_at(b, c) == S_OFFBOARD)
 159                                 continue;
 160
 161                         /* If the other liberty has empty neighbor,
 162                          * it must be the original liberty; otherwise,
 163                          * since the whole group has only 2 liberties,
 164                          * the other liberty may not be internal and
 165                          * we are nakade'ing eyeless group from outside,
 166                          * which is stupid. */
 167                         if (board_at(b, c) == S_NONE) {
 168                                 if (c == to)
 169                                         continue;
 170                                 else
 171                                         goto invalid_nakade;
 172                         }
 173
 174                         int g2 = group_at(b, c);
 175                         /* If the neighbor is of our color, it must
 176                          * be our group; if it is a different group,
 177                          * it must not be in atari. */
 178                         /* X X X X  We will not allow play on 'a',
 179                          * X X a X  because 'b' would capture two
 180                          * X O b X  different groups, forming two
 181                          * X X X X  eyes. */
 182                         if (board_at(b, c) == color) {
 183                                 if (board_group_info(b, group_at(b, c)).libs > 1)
 184                                         continue;
 185                                 /* Our group == one of the groups
 186                                  * we (@to) are connected to. */
 187                                 int j;
 188                                 for (j = 0; j < 4; j++)
 189                                         if (groupids[color][j] == g2)
 190                                                 break;
 191                                 if (j == 4)
 192                                         goto invalid_nakade;
 193                                 continue;
 194                         }
 195
 196                         /* The neighbor is enemy color. It's ok if
 197                          * it's still the same group or this is its
 198                          * only liberty. */
 199                         if (g == g2 || board_group_info(b, g2).libs == 1)
 200                                 continue;
 201                         /* Otherwise, it must have the exact same
 202                          * liberties as the original enemy group. */
 203                         if (board_group_info(b, g2).libs == 2
 204                             && (board_group_info(b, g2).lib[0] == to
 205                                 || board_group_info(b, g2).lib[1] == to))
 206                                 continue;
 207
 208                         goto invalid_nakade;
 209                 });
 210
 211                 /* Now, we must distinguish between nakade and eye
 212                  * falsification; we must not falsify an eye by more
 213                  * than two stones. */
 214                 if (groupcts[color] < 1 ||
 215                     (groupcts[color] == 1 && group_is_onestone(b, groupids[color][0])))
 216                         return false;
 217
 218                 /* We would create more than 2-stone group; in that
 219                  * case, the liberty of our result must be lib2,
 220                  * indicating this really is a nakade. */
 221                 for (int j = 0; j < 4; j++) {
 222                         group_t g2 = groupids[color][j];
 223                         if (!g2) continue;
 224                         assert(board_group_info(b, g2).libs <= 2);
 225                         if (board_group_info(b, g2).libs == 2) {
 226                                 if (board_group_info(b, g2).lib[0] != lib2
 227                                     && board_group_info(b, g2).lib[1] != lib2)
 228                                         goto invalid_nakade;
 229                         } else {
 230                                 assert(board_group_info(b, g2).lib[0] == to);
 231                         }
 232                 }
 233
 234                 return false;
 235
 236 invalid_nakade:;
 237         }
 238
 239         //fprintf(stderr, "no nakade group\n");
 240
 241         /* We can be throwing-in to false eye:
 242          * X X X O X X X O X X X X X
 243          * X . * X * O . X * O O . X
 244          * # # # # # # # # # # # # # */
 245         /* We cannot sensibly throw-in into a corner. */
 246         if (neighbor_count_at(b, to, S_OFFBOARD) < 2
 247             && neighbor_count_at(b, to, stone_other(color))
 248                + neighbor_count_at(b, to, S_OFFBOARD) == 3
 249             && board_is_false_eyelike(b, &to, stone_other(color))) {
 250                 assert(groupcts[color] <= 1);
 251                 /* Single-stone throw-in may be ok... */
 252                 if (groupcts[color] == 0) {
 253                         /* O X .  There is one problem - when it's
 254                          * . * X  actually not a throw-in!
 255                          * # # #  */
 256                         foreach_neighbor(b, to, {
 257                                 if (board_at(b, c) == S_NONE) {
 258                                         /* Is the empty neighbor an escape path? */
 259                                         /* (Note that one S_NONE neighbor is already @to.) */
 260                                         if (neighbor_count_at(b, c, stone_other(color))
 261                                             + neighbor_count_at(b, c, S_OFFBOARD) < 2)
 262                                                 goto invalid_throwin;
 263                                 }
 264                         });
 265                         return false;
 266                 }
 267
 268                 /* Multi-stone throwin...? */
 269                 assert(groupcts[color] == 1);
 270                 group_t g = groupids[color][0];
 271
 272                 assert(board_group_info(b, g).libs <= 2);
 273                 /* Suicide is definitely NOT ok, no matter what else
 274                  * we could test. */
 275                 if (board_group_info(b, g).libs == 1)
 276                         return true;
 277
 278                 /* In that case, we must be connected to at most one stone,
 279                  * or throwin will not destroy any eyes. */
 280                 if (group_is_onestone(b, g))
 281                         return false;
 282 invalid_throwin:;
 283         }
 284
 285         //fprintf(stderr, "no throw-in group\n");
 286
 287         /* No way to pull out, no way to connect out. This really
 288          * is a bad self-atari! */
 289         return true;
 290 }
 291
 292
 293 /* Is this ladder breaker friendly for the one who catches ladder. */
 294 static bool
 295 ladder_catcher(struct board *b, int x, int y, enum stone laddered)
 296 {
 297         enum stone breaker = board_atxy(b, x, y);
 298         return breaker == stone_other(laddered) || breaker == S_OFFBOARD;
 299 }
 300
 301 bool
 302 is_border_ladder(struct board *b, coord_t coord, enum stone lcolor)
 303 {
 304         int x = coord_x(coord, b), y = coord_y(coord, b);
 305
 306         if (DEBUGL(5))
 307                 fprintf(stderr, "border ladder\n");
 308         /* Direction along border; xd is horiz. border, yd vertical. */
 309         int xd = 0, yd = 0;
 310         if (board_atxy(b, x + 1, y) == S_OFFBOARD || board_atxy(b, x - 1, y) == S_OFFBOARD)
 311                 yd = 1;
 312         else
 313                 xd = 1;
 314         /* Direction from the border; -1 is above/left, 1 is below/right. */
 315         int dd = (board_atxy(b, x + yd, y + xd) == S_OFFBOARD) ? 1 : -1;
 316         if (DEBUGL(6))
 317                 fprintf(stderr, "xd %d yd %d dd %d\n", xd, yd, dd);
 318         /* | ? ?
 319          * | . O #
 320          * | c X #
 321          * | . O #
 322          * | ? ?   */
 323         /* This is normally caught, unless we have friends both above
 324          * and below... */
 325         if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor
 326             && board_atxy(b, x - xd * 2, y - yd * 2) == lcolor)
 327                 return false;
 328         /* ...or can't block where we need because of shortage
 329          * of liberties. */
 330         int libs1 = board_group_info(b, group_atxy(b, x + xd - yd * dd, y + yd - xd * dd)).libs;
 331         int libs2 = board_group_info(b, group_atxy(b, x - xd - yd * dd, y - yd - xd * dd)).libs;
 332         if (DEBUGL(6))
 333                 fprintf(stderr, "libs1 %d libs2 %d\n", libs1, libs2);
 334         if (libs1 < 2 && libs2 < 2)
 335                 return false;
 336         if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor && libs1 < 3)
 337                 return false;
 338         if (board_atxy(b, x - xd * 2, y - yd * 2) == lcolor && libs2 < 3)
 339                 return false;
 340         return true;
 341 }
 342
 343 /* This is very trivial and gets a lot of corner cases wrong.
 344  * We need this to be just very fast. One important point is
 345  * that we sometimes might not notice a ladder but if we do,
 346  * it should always work; thus we can use this for strong
 347  * negative hinting safely. */
 348 bool
 349 is_middle_ladder(struct board *b, coord_t coord, enum stone lcolor)
 350 {
 351         int x = coord_x(coord, b), y = coord_y(coord, b);
 352
 353         /* Figure out the ladder direction */
 354         int xd, yd;
 355         xd = board_atxy(b, x + 1, y) == S_NONE ? 1 : board_atxy(b, x - 1, y) == S_NONE ? -1 : 0;
 356         yd = board_atxy(b, x, y + 1) == S_NONE ? 1 : board_atxy(b, x, y - 1) == S_NONE ? -1 : 0;
 357
 358         if (!xd || !yd) {
 359                 if (DEBUGL(5))
 360                         fprintf(stderr, "no ladder, too little space; self-atari?\n");
 361                 return false;
 362         }
 363
 364         /* For given (xd,yd), we have two possibilities where to move
 365          * next. Consider (-1,-1):
 366          * n X .   n c X
 367          * c O X   X O #
 368          * X # #   . X #
 369          */
 370         bool horiz_first = ladder_catcher(b, x, y - yd, lcolor); // left case
 371         bool vert_first = ladder_catcher(b, x - xd, y, lcolor); // right case
 372
 373         /* We don't have to look at the other 'X' in the position - if it
 374          * wouldn't be there, the group wouldn't be in atari. */
 375
 376         /* We do only tight ladders, not loose ladders. Furthermore,
 377          * the ladders need to be simple:
 378          * . X .             . . X
 379          * c O X supported   . c O unsupported
 380          * X # #             X O #
 381          */
 382         assert(!(horiz_first && vert_first));
 383         if (!horiz_first && !vert_first) {
 384                 /* TODO: In case of basic non-simple ladder, play out both variants. */
 385                 if (DEBUGL(5))
 386                         fprintf(stderr, "non-simple ladder\n");
 387                 return false;
 388         }
 389
 390         /* We do that below for further moves, but now initially - check
 391          * that at 'c', we aren't putting any of the catching stones
 392          * in atari. */
 393 #if 1 // this might be broken?
 394 #define check_catcher_danger(b, x_, y_) do { \
 395         if (board_atxy(b, (x_), (y_)) != S_OFFBOARD \
 396             && board_group_info(b, group_atxy(b, (x_), (y_))).libs <= 2) { \
 397                 if (DEBUGL(5)) \
 398                         fprintf(stderr, "ladder failed - atari at the beginning\n"); \
 399                 return false; \
 400         } } while (0)
 401
 402         if (horiz_first) {
 403                 check_catcher_danger(b, x, y - yd);
 404                 check_catcher_danger(b, x - xd, y + yd);
 405         } else {
 406                 check_catcher_danger(b, x - xd, y);
 407                 check_catcher_danger(b, x + xd, y - yd);
 408         }
 409 #undef check_catcher_danger
 410 #endif
 411
 412 #define ladder_check(xd1_, yd1_, xd2_, yd2_, xd3_, yd3_)        \
 413         if (board_atxy(b, x, y) != S_NONE) { \
 414                 /* Did we hit a stone when playing out ladder? */ \
 415                 if (ladder_catcher(b, x, y, lcolor)) \
 416                         return true; /* ladder works */ \
 417                 if (board_group_info(b, group_atxy(b, x, y)).lib[0] > 0) \
 418                         return false; /* friend that's not in atari himself */ \
 419         } else { \
 420                 /* No. So we are at new position. \
 421                  * We need to check indirect ladder breakers. */ \
 422                 /* . 2 x 3 . \
 423                  * . x o O 1 <- only at O we can check for o at 2 \
 424                  * x o o x .    otherwise x at O would be still deadly \
 425                  * o o x . . \
 426                  * We check for o and x at 1, these are vital. \
 427                  * We check only for o at 2; x at 2 would mean we \
 428                  * need to fork (one step earlier). */ \
 429                 coord_t c1 = coord_xy(b, x + (xd1_), y + (yd1_)); \
 430                 enum stone s1 = board_at(b, c1); \
 431                 if (s1 == lcolor) return false; \
 432                 if (s1 == stone_other(lcolor)) { \
 433                         /* One more thing - if the position at 3 is \
 434                          * friendly and safe, we escaped anyway! */ \
 435                         coord_t c3 = coord_xy(b, x + (xd3_), y + (yd3_)); \
 436                         return board_at(b, c3) != lcolor \
 437                                || board_group_info(b, group_at(b, c3)).libs < 2; \
 438                 } \
 439                 enum stone s2 = board_atxy(b, x + (xd2_), y + (yd2_)); \
 440                 if (s2 == lcolor) return false; \
 441                 /* Then, can X actually "play" 1 in the ladder? */ \
 442                 if (neighbor_count_at(b, c1, lcolor) + neighbor_count_at(b, c1, S_OFFBOARD) >= 2) \
 443                         return false; /* It would be self-atari! */ \
 444         }
 445 #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)
 446 #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)
 447
 448         if (ladder_catcher(b, x - xd, y, lcolor))
 449                 ladder_horiz;
 450         do {
 451                 ladder_vert;
 452                 ladder_horiz;
 453         } while (1);
 454 }
 455
 456
 457 bool
 458 board_stone_radar(struct board *b, coord_t coord, int distance)
 459 {
 460         int bounds[4] = {
 461                 coord_x(coord, b) - distance,
 462                 coord_y(coord, b) - distance,
 463                 coord_x(coord, b) + distance,
 464                 coord_y(coord, b) + distance
 465         };
 466         for (int i = 0; i < 4; i++)
 467                 if (bounds[i] < 1)
 468                         bounds[i] = 1;
 469                 else if (bounds[i] > board_size(b) - 2)
 470                         bounds[i] = board_size(b) - 2;
 471         for (int x = bounds[0]; x <= bounds[2]; x++)
 472                 for (int y = bounds[1]; y <= bounds[3]; y++)
 473                         if (board_atxy(b, x, y) != S_NONE) {
 474                                 /* fprintf(stderr, "radar %d,%d,%d: %d,%d (%d)\n",
 475                                         coord_x(coord, b), coord_y(coord, b),
 476                                         distance, x, y, board_atxy(b, x, y)); */
 477                                 return true;
 478                         }
 479         return false;
 480 }
 481
 482 void
 483 cfg_distances(struct board *b, coord_t start, int *distances, int maxdist)
 484 {
 485         /* Queue for d+1 spots; no two spots of the same group
 486          * should appear in the queue. */
 487 #define qinc(x) (x = ((x + 1) >= board_size2(b) ? ((x) + 1 - board_size2(b)) : (x) + 1))
 488         coord_t queue[board_size2(b)]; int qstart = 0, qstop = 0;
 489
 490         foreach_point(b) {
 491                 distances[c] = board_at(b, c) == S_OFFBOARD ? maxdist + 1 : -1;
 492         } foreach_point_end;
 493
 494         queue[qstop++] = start;
 495         for (int d = 0; d <= maxdist; d++) {
 496                 /* Process queued moves, while setting the queue
 497                  * for new wave. */
 498                 int qa = qstart, qb = qstop;
 499                 qstart = qstop;
 500                 for (int q = qa; q < qb; qinc(q)) {
 501 #define cfg_one(coord, grp) do {\
 502         distances[coord] = d; \
 503         foreach_neighbor (b, coord, { \
 504                 if (distances[c] < 0 && (!grp || group_at(b, coord) != grp)) { \
 505                         queue[qstop] = c; \
 506                         qinc(qstop); \
 507                 } \
 508         }); \
 509 } while (0)
 510                         coord_t cq = queue[q];
 511                         if (distances[cq] >= 0)
 512                                 continue; /* We already looked here. */
 513                         if (board_at(b, cq) == S_NONE) {
 514                                 cfg_one(cq, 0);
 515                         } else {
 516                                 group_t g = group_at(b, cq);
 517                                 foreach_in_group(b, g) {
 518                                         cfg_one(c, g);
 519                                 } foreach_in_group_end;
 520                         }
 521 #undef cfg_one
 522                 }
 523         }
 524
 525         foreach_point(b) {
 526                 if (distances[c] < 0)
 527                         distances[c] = maxdist + 1;
 528         } foreach_point_end;
 529 }