tactics/selfatari.c

   1 #include <assert.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4
   5 #define DEBUG
   6 #include "board.h"
   7 #include "debug.h"
   8 #include "random.h"
   9 #include "tactics/selfatari.h"
  10
  11
  12 struct selfatari_state {
  13         int groupcts[S_MAX];
  14         group_t groupids[S_MAX][4];
  15         coord_t groupneis[S_MAX][4];
  16
  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
  25          * interesting. */
  26         coord_t needs_more_lib_except;
  27 };
  28
  29 static bool
  30 three_liberty_suicide(struct board *b, group_t g, enum stone color, coord_t to, struct selfatari_state *s)
  31 {
  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."
  36          *
  37          * Examples:
  38          *
  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 */
  43
  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];
  49                 if (lib != to) {
  50                         other_libs_adj[j] = coord_is_adjecent(lib, to, b);
  51                         other_libs[j++] = lib;
  52                 }
  53         }
  54
  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)
  59                 return false;
  60         assert(!(other_libs_adj[0] && other_libs_adj[1]));
  61         if (s->groupcts[color] > 1)
  62                 return false;
  63
  64         /* Playing on the third liberty might be useful if it enables
  65          * capturing some group (are we doing nakade or semeai?). */
  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 <= 3)
  68                         return false;
  69
  70
  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. */
  76
  77         if (DEBUGL(6))
  78                 fprintf(stderr, "3-lib danger\n");
  79
  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. */
  91                         return false;
  92                 }
  93                 if (immediate_liberty_count(b, other_libs[i]) - null_libs > 1) {
  94                         /* Gains liberties. */
  95                         /* TODO: Check for ladder! */
  96 next_lib:
  97                         continue;
  98                 }
  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
 106                                  * first? */
 107                                 goto next_lib;
 108                         }
 109                 });
 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. */
 113                 if (DEBUGL(6))
 114                         fprintf(stderr, "3-lib dangerous: %s\n", coord2sstr(other_libs[i], b));
 115                 return true;
 116         }
 117
 118         return false;
 119 }
 120
 121 static int
 122 examine_friendly_groups(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
 123 {
 124         for (int i = 0; i < s->groupcts[color]; i++) {
 125                 /* We can escape by connecting to this group if it's
 126                  * not in atari. */
 127                 group_t g = s->groupids[color][i];
 128
 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
 133                         continue;
 134                 }
 135
 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))
 140                                 return true;
 141                         return false;
 142                 }
 143
 144                 /* We need to have another liberty, and
 145                  * it must not be the other liberty of
 146                  * the group. */
 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)
 152                         return false;
 153
 154                 /* Can we get the liberty locally? */
 155                 /* Yes if we are route to more liberties... */
 156                 if (s->groupcts[S_NONE] > 1)
 157                         return false;
 158                 /* ...or one liberty, but not lib2. */
 159                 if (s->groupcts[S_NONE] > 0
 160                     && !coord_is_adjecent(lib2, to, b))
 161                         return false;
 162
 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;
 168         }
 169
 170         return -1;
 171 }
 172
 173 static int
 174 examine_enemy_groups(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
 175 {
 176         /* We may be able to gain a liberty by capturing this group. */
 177         group_t can_capture = 0;
 178
 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)
 184                         continue;
 185
 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
 189                  * nice!). */
 190                 if (s->groupcts[S_NONE] > 0 || !group_is_onestone(b, g))
 191                         return false;
 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)
 197                                 return false;
 198                 }
 199                 /* ...or, we already have one indirect liberty provided
 200                  * by another group. */
 201                 if (s->needs_more_lib || (can_capture && can_capture != g))
 202                         return false;
 203                 can_capture = g;
 204
 205         }
 206
 207         if (DEBUGL(6))
 208                 fprintf(stderr, "no cap group\n");
 209
 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. */
 213                 if (DEBUGL(6))
 214                         fprintf(stderr, "suicide\n");
 215                 return true;
 216         }
 217         /* XXX: I wonder if it makes sense to continue if we actually
 218          * just !s->needs_more_lib. */
 219
 220         return -1;
 221 }
 222
 223 static int
 224 setup_nakade_or_snapback(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
 225 {
 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.)
 232          * X X X O O
 233          * X O * . . */
 234         /* TODO: Allow to only nakade if the created shape is dead
 235          * (http://senseis.xmp.net/?Nakade). */
 236
 237         /* This branch also covers snapback, which is kind of special
 238          * nakade case. ;-) */
 239
 240         /* Look at the enemy groups and determine the other contended
 241          * liberty. We must make sure the liberty:
 242          * (i) is an internal liberty
 243          * (ii) filling it to capture our group will not gain safety */
 244         coord_t lib2 = pass;
 245         for (int i = 0; i < s->groupcts[stone_other(color)]; i++) {
 246                 group_t g = s->groupids[stone_other(color)][i];
 247                 if (board_group_info(b, g).libs != 2)
 248                         continue;
 249
 250                 coord_t this_lib2 = board_group_other_lib(b, g, to);
 251                 if (is_pass(lib2))
 252                         lib2 = this_lib2;
 253                 else if (this_lib2 != lib2) {
 254                         /* If we have two neighboring groups that do
 255                          * not share the other liberty, this for sure
 256                          * is not a good nakade. */
 257                         return -1;
 258                 }
 259         }
 260         if (is_pass(lib2)) {
 261                 /* Not putting any group in atari. Therefore, this
 262                  * self-atari is not nakade or snapback. */
 263                 return -1;
 264         }
 265
 266         /* Let's look at neighbors of the other liberty: */
 267         foreach_neighbor(b, lib2, {
 268                 /* This neighbor of course does not contribute
 269                  * anything to the enemy. */
 270                 if (board_at(b, c) == S_OFFBOARD)
 271                         continue;
 272
 273                 /* If the other liberty has empty neighbor,
 274                  * it must be the original liberty; otherwise,
 275                  * since the whole group has only 2 liberties,
 276                  * the other liberty may not be internal and
 277                  * we are nakade'ing eyeless group from outside,
 278                  * which is stupid. */
 279                 if (board_at(b, c) == S_NONE) {
 280                         if (c == to)
 281                                 continue;
 282                         else
 283                                 return -1;
 284                 }
 285
 286                 int g2 = group_at(b, c);
 287                 /* If the neighbor is of our color, it must
 288                  * be also a 2-lib group. If it is more,
 289                  * we CERTAINLY want that liberty to be played
 290                  * first, what if it is an alive group? If it
 291                  * is in atari, we want to extend from it to
 292                  * prevent eye-making capture. However, if it
 293                  * is 2-lib, it is selfatari connecting two
 294                  * nakade'ing groups! */
 295                 /* X X X X  We will not allow play on 'a',
 296                  * X X a X  because 'b' would capture two
 297                  * X O b X  different groups, forming two
 298                  * X X X X  eyes. */
 299                 if (board_at(b, c) == color) {
 300                         if (board_group_info(b, group_at(b, c)).libs == 2)
 301                                 continue;
 302                         return -1;
 303                 }
 304
 305                 /* The neighbor is enemy color. It's ok if this is its
 306                  * only liberty or it's one of our neighbor groups. */
 307                 if (board_group_info(b, g2).libs == 1)
 308                         continue;
 309                 if (board_group_info(b, g2).libs == 2
 310                     && (board_group_info(b, g2).lib[0] == to
 311                         || board_group_info(b, g2).lib[1] == to))
 312                         continue;
 313
 314                 /* Stronger enemy group. No nakade. */
 315                 return -1;
 316         });
 317
 318         /* Now, we must distinguish between nakade and eye
 319          * falsification; we must not falsify an eye by more
 320          * than two stones. */
 321         if (s->groupcts[color] < 1)
 322                 return false; // simple throw-in
 323         if (s->groupcts[color] == 1 && group_is_onestone(b, s->groupids[color][0])) {
 324                 /* More complex throw-in - we are in one of
 325                  * three situations:
 326                  * a O O O O X  b O O O X  c O O O X
 327                  *   O . X . O    O X . .    O . X .
 328                  *   # # # # #    # # # #    # # # #
 329                  * b is desirable here (since maybe O has no
 330                  * backup two eyes); a may be desirable, but
 331                  * is tested next in check_throwin(). c is
 332                  * never desirable. */
 333                 group_t g2 = s->groupids[color][0];
 334                 assert(board_group_info(b, g2).libs <= 2);
 335                 if (board_group_info(b, g2).libs == 1)
 336                         return false; // b
 337                 return -1; // a or c
 338         }
 339
 340         /* We would create more than 2-stone group; in that
 341          * case, the liberty of our result must be lib2,
 342          * indicating this really is a nakade. */
 343         int stones = 0;
 344         for (int j = 0; j < s->groupcts[color]; j++) {
 345                 group_t g2 = s->groupids[color][j];
 346                 assert(board_group_info(b, g2).libs <= 2);
 347                 if (board_group_info(b, g2).libs == 2) {
 348                         if (board_group_info(b, g2).lib[0] != lib2
 349                             && board_group_info(b, g2).lib[1] != lib2)
 350                                 return -1;
 351                 } else {
 352                         assert(board_group_info(b, g2).lib[0] == to);
 353                 }
 354                 /* See below: */
 355                 stones += group_stone_count(b, g2, 6);
 356                 // fprintf(stderr, "%d (%d,%d) %d,%d\n", __LINE__, j, g2, stones);
 357                 if (stones > 5)
 358                         return true;
 359         }
 360
 361         /* It also remains to be seen whether it is nakade
 362          * and not seki destruction. To do this properly, we
 363          * would have to look at the group shape. But we can
 364          * cheat too! Brett Combs helps to introduce a static
 365          * rule that should in fact cover *all* cases:
 366          * 1. Total number of pre-selfatari nakade stones must
 367          *    be 5 or smaller. (See above for that.)
 368          * 2. If the selfatari is 8-touching all nakade stones,
 369          *    it is proper nakade.
 370          * 3. Otherwise, there must be only a single nakade
 371          *    group, it must be at least 4-stone and its other
 372          *    liberty must be 8-touching the same number of
 373          *    stones as us. */
 374         int touch8 = neighbor_count_at(b, to, color);
 375         foreach_diag_neighbor(b, to) {
 376                 if (board_at(b, c) != color) continue;
 377                 /* Consider only internal stones. Otherwise, e.g.
 378                  * X O . X
 379                  * X . O X  can make trouble, bottom O is
 380                  * O X X X  irrelevant. */
 381                 if (board_group_info(b, group_at(b, c)).lib[0] == to
 382                     || board_group_info(b, group_at(b, c)).lib[1] == to)
 383                         touch8++;
 384         } foreach_diag_neighbor_end;
 385         if (touch8 == stones)
 386                 return false;
 387
 388         if (s->groupcts[color] > 1 || stones < 4)
 389                 return true;
 390         int ltouch8 = neighbor_count_at(b, lib2, color);
 391         foreach_diag_neighbor(b, lib2) {
 392                 if (board_at(b, c) != color) continue;
 393                 if (board_group_info(b, group_at(b, c)).lib[0] == to
 394                     || board_group_info(b, group_at(b, c)).lib[1] == to)
 395                         ltouch8++;
 396         } foreach_diag_neighbor_end;
 397         return ltouch8 != touch8;
 398 }
 399
 400 static int
 401 check_throwin(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
 402 {
 403         /* We can be throwing-in to false eye:
 404          * X X X O X X X O X X X X X
 405          * X . * X * O . X * O O . X
 406          * # # # # # # # # # # # # # */
 407         /* We cannot sensibly throw-in into a corner. */
 408         if (neighbor_count_at(b, to, S_OFFBOARD) < 2
 409             && neighbor_count_at(b, to, stone_other(color))
 410                + neighbor_count_at(b, to, S_OFFBOARD) == 3
 411             && board_is_false_eyelike(b, to, stone_other(color))) {
 412                 assert(s->groupcts[color] <= 1);
 413                 /* Single-stone throw-in may be ok... */
 414                 if (s->groupcts[color] == 0) {
 415                         /* O X .  There is one problem - when it's
 416                          * . * X  actually not a throw-in!
 417                          * # # #  */
 418                         foreach_neighbor(b, to, {
 419                                 if (board_at(b, c) == S_NONE) {
 420                                         /* Is the empty neighbor an escape path? */
 421                                         /* (Note that one S_NONE neighbor is already @to.) */
 422                                         if (neighbor_count_at(b, c, stone_other(color))
 423                                             + neighbor_count_at(b, c, S_OFFBOARD) < 2)
 424                                                 return -1;
 425                                 }
 426                         });
 427                         return false;
 428                 }
 429
 430                 /* Multi-stone throwin...? */
 431                 assert(s->groupcts[color] == 1);
 432                 group_t g = s->groupids[color][0];
 433
 434                 assert(board_group_info(b, g).libs <= 2);
 435                 /* Suicide is definitely NOT ok, no matter what else
 436                  * we could test. */
 437                 if (board_group_info(b, g).libs == 1)
 438                         return true;
 439
 440                 /* In that case, we must be connected to at most one stone,
 441                  * or throwin will not destroy any eyes. */
 442                 if (group_is_onestone(b, g))
 443                         return false;
 444         }
 445         return -1;
 446 }
 447
 448 bool
 449 is_bad_selfatari_slow(struct board *b, enum stone color, coord_t to)
 450 {
 451         if (DEBUGL(5))
 452                 fprintf(stderr, "sar check %s %s\n", stone2str(color), coord2sstr(to, b));
 453         /* Assess if we actually gain any liberties by this escape route.
 454          * Note that this is not 100% as we cannot check whether we are
 455          * connecting out or just to ourselves. */
 456
 457         struct selfatari_state s;
 458         memset(&s, 0, sizeof(s));
 459         int d;
 460
 461         foreach_neighbor(b, to, {
 462                 enum stone color = board_at(b, c);
 463                 group_t group = group_at(b, c);
 464                 bool dup = false;
 465                 for (int i = 0; i < s.groupcts[color]; i++)
 466                         if (s.groupids[color][i] == group) {
 467                                 dup = true;
 468                                 break;
 469                         }
 470                 if (!dup) {
 471                         s.groupneis[color][s.groupcts[color]] = c;
 472                         s.groupids[color][s.groupcts[color]++] = group_at(b, c);
 473                 }
 474         });
 475
 476         /* We have shortage of liberties; that's the point. */
 477         assert(s.groupcts[S_NONE] <= 1);
 478
 479         d = examine_friendly_groups(b, color, to, &s);
 480         if (d >= 0)
 481                 return d;
 482
 483         if (DEBUGL(6))
 484                 fprintf(stderr, "no friendly group\n");
 485
 486         d = examine_enemy_groups(b, color, to, &s);
 487         if (d >= 0)
 488                 return d;
 489
 490         if (DEBUGL(6))
 491                 fprintf(stderr, "no escape\n");
 492
 493         d = setup_nakade_or_snapback(b, color, to, &s);
 494         if (d >= 0)
 495                 return d;
 496
 497         if (DEBUGL(6))
 498                 fprintf(stderr, "no nakade group\n");
 499
 500         d = check_throwin(b, color, to, &s);
 501         if (d >= 0)
 502                 return d;
 503
 504         if (DEBUGL(6))
 505                 fprintf(stderr, "no throw-in group\n");
 506
 507         /* No way to pull out, no way to connect out. This really
 508          * is a bad self-atari! */
 509         return true;
 510 }
 511
 512
 513 coord_t
 514 selfatari_cousin(struct board *b, enum stone color, coord_t coord, group_t *bygroup)
 515 {
 516         group_t groups[4]; int groups_n = 0;
 517         int groupsbycolor[4] = {0, 0, 0, 0};
 518         if (DEBUGL(6))
 519                 fprintf(stderr, "cousin group search: ");
 520         foreach_neighbor(b, coord, {
 521                 enum stone s = board_at(b, c);
 522                 group_t g = group_at(b, c);
 523                 if (board_group_info(b, g).libs == 2) {
 524                         groups[groups_n++] = g;
 525                         groupsbycolor[s]++;
 526                         if (DEBUGL(6))
 527                                 fprintf(stderr, "%s(%s) ", coord2sstr(c, b), stone2str(s));
 528                 }
 529         });
 530         if (DEBUGL(6))
 531                 fprintf(stderr, "\n");
 532
 533         if (!groups_n)
 534                 return pass;
 535
 536         int gn;
 537         if (groupsbycolor[stone_other(color)]) {
 538                 /* Prefer to fill the other liberty of an opponent
 539                  * group to filling own approach liberties. */
 540                 int gl = fast_random(groups_n);
 541                 for (gn = gl; gn < groups_n; gn++)
 542                         if (board_at(b, groups[gn]) == stone_other(color))
 543                                 goto found;
 544                 for (gn = 0; gn < gl; gn++)
 545                         if (board_at(b, groups[gn]) == stone_other(color))
 546                                 goto found;
 547 found:;
 548         } else {
 549                 gn = fast_random(groups_n);
 550         }
 551         int gl = gn;
 552         for (; gn - gl < groups_n; gn++) {
 553                 int gnm = gn % groups_n;
 554                 group_t group = groups[gnm];
 555
 556                 coord_t lib2 = board_group_other_lib(b, group, coord);
 557                 if (board_is_one_point_eye(b, lib2, board_at(b, group)))
 558                         continue;
 559                 if (is_bad_selfatari(b, color, lib2))
 560                         continue;
 561                 if (bygroup)
 562                         *bygroup = group;
 563                 return lib2;
 564         }
 565         return pass;
 566 }