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
  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
  24          * interesting. */
  25         coord_t needs_more_lib_except;
  26 };
  27
  28 static bool
  29 three_liberty_suicide(struct board *b, group_t g, enum stone color, coord_t to, struct selfatari_state *s)
  30 {
  31         /* If a group has three liberties, by playing on one of
  32          * them it is possible to kill the group clumsily. Check
  33          * against that condition: "After our move, the opponent
  34          * can unconditionally capture the group."
  35          *
  36          * Examples:
  37          *
  38          * O O O O O O O   X X O O O O O O     v-v- ladder
  39          * O X X X X X O   . O X X X X X O   . . . O O
  40          * O X ! . ! X O   . O X ! . ! O .   O X X . O
  41          * O X X X X X O   # # # # # # # #   O O O O O */
  42
  43         /* Extract the other two liberties. */
  44         coord_t other_libs[2];
  45         bool other_libs_adj[2];
  46         for (int i = 0, j = 0; i < 3; i++) {
  47                 coord_t lib = board_group_info(b, g).lib[i];
  48                 if (lib != to) {
  49                         other_libs_adj[j] = coord_is_adjecent(lib, to, b);
  50                         other_libs[j++] = lib;
  51                 }
  52         }
  53
  54         /* Make sure this move is not useful by gaining liberties,
  55          * splitting the other two liberties (quite possibly splitting
  56          * 3-eyespace!) or connecting to a different group. */
  57         if (immediate_liberty_count(b, to) - (other_libs_adj[0] || other_libs_adj[1]) > 0)
  58                 return false;
  59         assert(!(other_libs_adj[0] && other_libs_adj[1]));
  60         if (s->groupcts[color] > 1)
  61                 return false;
  62
  63         /* Playing on the third liberty might be useful if it enables
  64          * capturing some group. */
  65         for (int i = 0; i < s->groupcts[stone_other(color)]; i++)
  66                 if (board_group_info(b, s->groupids[stone_other(color)][i]).libs <= 2)
  67                         return false;
  68
  69
  70         /* Okay. This looks like a pretty dangerous situation. The
  71          * move looks useless, it definitely converts us to a 2-lib
  72          * group. But we still want to play it e.g. if it takes off
  73          * liberties of some unconspicous enemy group, and of course
  74          * also at the game end to leave just single-point eyes. */
  75
  76         if (DEBUGL(6))
  77                 fprintf(stderr, "3-lib danger\n");
  78
  79         /* Therefore, the final suicidal test is: (After filling this
  80          * liberty,) when opponent fills liberty [0], playing liberty
  81          * [1] will not help the group, or vice versa. */
  82         bool other_libs_neighbors = coord_is_adjecent(other_libs[0], other_libs[1], b);
  83         for (int i = 0; i < 2; i++) {
  84                 int null_libs = other_libs_neighbors + other_libs_adj[i];
  85                 if (board_is_one_point_eye(b, other_libs[1 - i], color)) {
  86                         /* The other liberty is an eye, happily go ahead.
  87                          * There are of course situations where this will
  88                          * take off semeai liberties, but without this check,
  89                          * many terminal endgame plays will be messed up. */
  90                         return false;
  91                 }
  92                 if (immediate_liberty_count(b, other_libs[i]) - null_libs > 1) {
  93                         /* Gains liberties. */
  94                         /* TODO: Check for ladder! */
  95 next_lib:
  96                         continue;
  97                 }
  98                 foreach_neighbor(b, other_libs[i], {
  99                         if (board_at(b, c) == color
 100                             && group_at(b, c) != g
 101                             && board_group_info(b, group_at(b, c)).libs > 1) {
 102                                 /* Can connect to a friend. */
 103                                 /* TODO: > 2? But maybe the group can capture
 104                                  * a neighbor! But then better let it do that
 105                                  * first? */
 106                                 goto next_lib;
 107                         }
 108                 });
 109                 /* If we can capture a neighbor, better do it now
 110                  * before wasting a liberty. So no need to check. */
 111                 /* Ok, the last liberty has no way to get out. */
 112                 if (DEBUGL(6))
 113                         fprintf(stderr, "3-lib dangerous: %s\n", coord2sstr(other_libs[i], b));
 114                 return true;
 115         }
 116
 117         return false;
 118 }
 119
 120 static int
 121 examine_friendly_groups(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
 122 {
 123         for (int i = 0; i < s->groupcts[color]; i++) {
 124                 /* We can escape by connecting to this group if it's
 125                  * not in atari. */
 126                 group_t g = s->groupids[color][i];
 127
 128                 if (board_group_info(b, g).libs == 1) {
 129                         if (!s->needs_more_lib)
 130                                 s->friend_has_no_libs = true;
 131                         // or we already have a friend with 1 lib
 132                         continue;
 133                 }
 134
 135                 /* Could we self-atari the group here? */
 136                 if (board_group_info(b, g).libs > 2) {
 137                         if (board_group_info(b, g).libs == 3
 138                             && three_liberty_suicide(b, g, color, to, s))
 139                                 return true;
 140                         return false;
 141                 }
 142
 143                 /* We need to have another liberty, and
 144                  * it must not be the other liberty of
 145                  * the group. */
 146                 int lib2 = board_group_other_lib(b, g, to);
 147                 /* Maybe we already looked at another
 148                  * group providing one liberty? */
 149                 if (s->needs_more_lib && s->needs_more_lib != g
 150                     && s->needs_more_lib_except != lib2)
 151                         return false;
 152
 153                 /* Can we get the liberty locally? */
 154                 /* Yes if we are route to more liberties... */
 155                 if (s->groupcts[S_NONE] > 1)
 156                         return false;
 157                 /* ...or one liberty, but not lib2. */
 158                 if (s->groupcts[S_NONE] > 0
 159                     && !coord_is_adjecent(lib2, to, b))
 160                         return false;
 161
 162                 /* ...ok, then we can still contribute a liberty
 163                  * later by capturing something. */
 164                 s->needs_more_lib = g;
 165                 s->needs_more_lib_except = lib2;
 166                 s->friend_has_no_libs = false;
 167         }
 168
 169         return -1;
 170 }
 171
 172 static int
 173 examine_enemy_groups(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
 174 {
 175         /* We may be able to gain a liberty by capturing this group. */
 176         group_t can_capture = 0;
 177
 178         /* Examine enemy groups: */
 179         for (int i = 0; i < s->groupcts[stone_other(color)]; i++) {
 180                 /* We can escape by capturing this group if it's in atari. */
 181                 group_t g = s->groupids[stone_other(color)][i];
 182                 if (board_group_info(b, g).libs > 1)
 183                         continue;
 184
 185                 /* But we need to get to at least two liberties by this;
 186                  * we already have one outside liberty, or the group is
 187                  * more than 1 stone (in that case, capturing is always
 188                  * nice!). */
 189                 if (s->groupcts[S_NONE] > 0 || !group_is_onestone(b, g))
 190                         return false;
 191                 /* ...or, it's a ko stone, */
 192                 if (neighbor_count_at(b, g, color) + neighbor_count_at(b, g, S_OFFBOARD) == 3) {
 193                         /* and we don't have a group to save: then, just taking
 194                          * single stone means snapback! */
 195                         if (!s->friend_has_no_libs)
 196                                 return false;
 197                 }
 198                 /* ...or, we already have one indirect liberty provided
 199                  * by another group. */
 200                 if (s->needs_more_lib || (can_capture && can_capture != g))
 201                         return false;
 202                 can_capture = g;
 203
 204         }
 205
 206         if (DEBUGL(6))
 207                 fprintf(stderr, "no cap group\n");
 208
 209         if (!s->needs_more_lib && !can_capture && !s->groupcts[S_NONE]) {
 210                 /* We have no hope for more fancy tactics - this move is simply
 211                  * a suicide, not even a self-atari. */
 212                 if (DEBUGL(6))
 213                         fprintf(stderr, "suicide\n");
 214                 return true;
 215         }
 216         /* XXX: I wonder if it makes sense to continue if we actually
 217          * just !s->needs_more_lib. */
 218
 219         return -1;
 220 }
 221
 222 static int
 223 setup_nakade_or_snapback(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
 224 {
 225         /* There is another possibility - we can self-atari if it is
 226          * a nakade: we put an enemy group in atari from the inside. */
 227         /* This branch also allows eyes falsification:
 228          * O O O . .  (This is different from throw-in to false eye
 229          * X X O O .  checked below in that there is no X stone at the
 230          * X . X O .  right of the star point in this diagram.)
 231          * X X X O O
 232          * X O * . . */
 233         /* TODO: Allow to only nakade if the created shape is dead
 234          * (http://senseis.xmp.net/?Nakade). */
 235
 236         /* This branch also covers snapback, which is kind of special
 237          * nakade case. ;-) */
 238         for (int i = 0; i < s->groupcts[stone_other(color)]; i++) {
 239                 group_t g = s->groupids[stone_other(color)][i];
 240                 if (board_group_info(b, g).libs != 2)
 241                         goto next_group;
 242                 /* Simple check not to re-examine the same group. */
 243                 if (i > 0 && s->groupids[stone_other(color)][i] == s->groupids[stone_other(color)][i - 1])
 244                         continue;
 245
 246                 /* We must make sure the other liberty of that group:
 247                  * (i) is an internal liberty
 248                  * (ii) filling it to capture our group will not gain
 249                  * safety */
 250
 251                 /* Let's look at neighbors of the other liberty: */
 252                 int lib2 = board_group_other_lib(b, g, to);
 253                 foreach_neighbor(b, lib2, {
 254                         /* This neighbor of course does not contribute
 255                          * anything to the enemy. */
 256                         if (board_at(b, c) == S_OFFBOARD)
 257                                 continue;
 258
 259                         /* If the other liberty has empty neighbor,
 260                          * it must be the original liberty; otherwise,
 261                          * since the whole group has only 2 liberties,
 262                          * the other liberty may not be internal and
 263                          * we are nakade'ing eyeless group from outside,
 264                          * which is stupid. */
 265                         if (board_at(b, c) == S_NONE) {
 266                                 if (c == to)
 267                                         continue;
 268                                 else
 269                                         goto next_group;
 270                         }
 271
 272                         int g2 = group_at(b, c);
 273                         /* If the neighbor is of our color, it must
 274                          * be also a 2-lib group. If it is more,
 275                          * we CERTAINLY want that liberty to be played
 276                          * first, what if it is an alive group? If it
 277                          * is in atari, we want to extend from it to
 278                          * prevent eye-making capture. However, if it
 279                          * is 2-lib, it is selfatari connecting two
 280                          * nakade'ing groups! */
 281                         /* X X X X  We will not allow play on 'a',
 282                          * X X a X  because 'b' would capture two
 283                          * X O b X  different groups, forming two
 284                          * X X X X  eyes. */
 285                         if (board_at(b, c) == color) {
 286                                 if (board_group_info(b, group_at(b, c)).libs == 2)
 287                                         continue;
 288                                 goto next_group;
 289                         }
 290
 291                         /* The neighbor is enemy color. It's ok if
 292                          * it's still the same group or this is its
 293                          * only liberty. */
 294                         if (g == g2 || board_group_info(b, g2).libs == 1)
 295                                 continue;
 296                         /* Otherwise, it must have the exact same
 297                          * liberties as the original enemy group. */
 298                         if (board_group_info(b, g2).libs == 2
 299                             && (board_group_info(b, g2).lib[0] == to
 300                                 || board_group_info(b, g2).lib[1] == to))
 301                                 continue;
 302
 303                         goto next_group;
 304                 });
 305
 306                 /* Now, we must distinguish between nakade and eye
 307                  * falsification; we must not falsify an eye by more
 308                  * than two stones. */
 309                 if (s->groupcts[color] < 1)
 310                         return false; // simple throw-in
 311                 if (s->groupcts[color] == 1 && group_is_onestone(b, s->groupids[color][0])) {
 312                         /* More complex throw-in - we are in one of
 313                          * three situations:
 314                          * a O O O O X  b O O O X  c O O O X
 315                          *   O . X . O    O X . .    O . X .
 316                          *   # # # # #    # # # #    # # # #
 317                          * b is desirable here (since maybe O has no
 318                          * backup two eyes); a may be desirable, but
 319                          * is tested next in check_throwin(). c is
 320                          * never desirable. */
 321                         group_t g2 = s->groupids[color][0];
 322                         assert(board_group_info(b, g2).libs <= 2);
 323                         if (board_group_info(b, g2).libs == 1)
 324                                 return false; // b
 325                         goto next_group; // a or c
 326                 }
 327
 328                 /* We would create more than 2-stone group; in that
 329                  * case, the liberty of our result must be lib2,
 330                  * indicating this really is a nakade. */
 331                 for (int j = 0; j < s->groupcts[color]; j++) {
 332                         group_t g2 = s->groupids[color][j];
 333                         assert(board_group_info(b, g2).libs <= 2);
 334                         if (board_group_info(b, g2).libs == 2) {
 335                                 if (board_group_info(b, g2).lib[0] != lib2
 336                                     && board_group_info(b, g2).lib[1] != lib2)
 337                                         goto next_group;
 338                         } else {
 339                                 assert(board_group_info(b, g2).lib[0] == to);
 340                         }
 341                 }
 342
 343                 return false;
 344 next_group:
 345                 /* Unless we are dealing with snapback setup, we don't need to look
 346                  * further. */
 347                 if (s->groupcts[color])
 348                         return -1;
 349         }
 350
 351         return -1;
 352 }
 353
 354 static int
 355 check_throwin(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
 356 {
 357         /* We can be throwing-in to false eye:
 358          * X X X O X X X O X X X X X
 359          * X . * X * O . X * O O . X
 360          * # # # # # # # # # # # # # */
 361         /* We cannot sensibly throw-in into a corner. */
 362         if (neighbor_count_at(b, to, S_OFFBOARD) < 2
 363             && neighbor_count_at(b, to, stone_other(color))
 364                + neighbor_count_at(b, to, S_OFFBOARD) == 3
 365             && board_is_false_eyelike(b, to, stone_other(color))) {
 366                 assert(s->groupcts[color] <= 1);
 367                 /* Single-stone throw-in may be ok... */
 368                 if (s->groupcts[color] == 0) {
 369                         /* O X .  There is one problem - when it's
 370                          * . * X  actually not a throw-in!
 371                          * # # #  */
 372                         foreach_neighbor(b, to, {
 373                                 if (board_at(b, c) == S_NONE) {
 374                                         /* Is the empty neighbor an escape path? */
 375                                         /* (Note that one S_NONE neighbor is already @to.) */
 376                                         if (neighbor_count_at(b, c, stone_other(color))
 377                                             + neighbor_count_at(b, c, S_OFFBOARD) < 2)
 378                                                 return -1;
 379                                 }
 380                         });
 381                         return false;
 382                 }
 383
 384                 /* Multi-stone throwin...? */
 385                 assert(s->groupcts[color] == 1);
 386                 group_t g = s->groupids[color][0];
 387
 388                 assert(board_group_info(b, g).libs <= 2);
 389                 /* Suicide is definitely NOT ok, no matter what else
 390                  * we could test. */
 391                 if (board_group_info(b, g).libs == 1)
 392                         return true;
 393
 394                 /* In that case, we must be connected to at most one stone,
 395                  * or throwin will not destroy any eyes. */
 396                 if (group_is_onestone(b, g))
 397                         return false;
 398         }
 399         return -1;
 400 }
 401
 402 bool
 403 is_bad_selfatari_slow(struct board *b, enum stone color, coord_t to)
 404 {
 405         if (DEBUGL(5))
 406                 fprintf(stderr, "sar check %s %s\n", stone2str(color), coord2sstr(to, b));
 407         /* Assess if we actually gain any liberties by this escape route.
 408          * Note that this is not 100% as we cannot check whether we are
 409          * connecting out or just to ourselves. */
 410
 411         struct selfatari_state s;
 412         memset(&s, 0, sizeof(s));
 413         int d;
 414
 415         foreach_neighbor(b, to, {
 416                 enum stone color = board_at(b, c);
 417                 s.groupids[color][s.groupcts[color]++] = group_at(b, c);
 418         });
 419
 420         /* We have shortage of liberties; that's the point. */
 421         assert(s.groupcts[S_NONE] <= 1);
 422
 423         d = examine_friendly_groups(b, color, to, &s);
 424         if (d >= 0)
 425                 return d;
 426
 427         if (DEBUGL(6))
 428                 fprintf(stderr, "no friendly group\n");
 429
 430         d = examine_enemy_groups(b, color, to, &s);
 431         if (d >= 0)
 432                 return d;
 433
 434         if (DEBUGL(6))
 435                 fprintf(stderr, "no escape\n");
 436
 437         d = setup_nakade_or_snapback(b, color, to, &s);
 438         if (d >= 0)
 439                 return d;
 440
 441         if (DEBUGL(6))
 442                 fprintf(stderr, "no nakade group\n");
 443
 444         d = check_throwin(b, color, to, &s);
 445         if (d >= 0)
 446                 return d;
 447
 448         if (DEBUGL(6))
 449                 fprintf(stderr, "no throw-in group\n");
 450
 451         /* No way to pull out, no way to connect out. This really
 452          * is a bad self-atari! */
 453         return true;
 454 }
 455
 456
 457 coord_t
 458 selfatari_cousin(struct board *b, enum stone color, coord_t coord)
 459 {
 460         group_t groups[4]; int groups_n = 0;
 461         foreach_neighbor(b, coord, {
 462                 enum stone s = board_at(b, c);
 463                 if (s != color) continue;
 464                 group_t g = group_at(b, c);
 465                 if (board_group_info(b, g).libs == 2)
 466                         groups[groups_n++] = g;
 467         });
 468
 469         if (!groups_n)
 470                 return pass;
 471         group_t group = groups[fast_random(groups_n)];
 472
 473         coord_t lib2 = board_group_other_lib(b, group, coord);
 474         if (is_bad_selfatari(b, color, lib2))
 475                 return pass;
 476         return lib2;
 477 }