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. */
  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 <= 2)
  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         for (int i = 0; i < s->groupcts[stone_other(color)]; i++) {
 240                 group_t g = s->groupids[stone_other(color)][i];
 241                 if (board_group_info(b, g).libs != 2)
 242                         goto next_group;
 243
 244                 /* We must make sure the other liberty of that group:
 245                  * (i) is an internal liberty
 246                  * (ii) filling it to capture our group will not gain
 247                  * safety */
 248
 249                 /* Let's look at neighbors of the other liberty: */
 250                 int lib2 = board_group_other_lib(b, g, to);
 251                 foreach_neighbor(b, lib2, {
 252                         /* This neighbor of course does not contribute
 253                          * anything to the enemy. */
 254                         if (board_at(b, c) == S_OFFBOARD)
 255                                 continue;
 256
 257                         /* If the other liberty has empty neighbor,
 258                          * it must be the original liberty; otherwise,
 259                          * since the whole group has only 2 liberties,
 260                          * the other liberty may not be internal and
 261                          * we are nakade'ing eyeless group from outside,
 262                          * which is stupid. */
 263                         if (board_at(b, c) == S_NONE) {
 264                                 if (c == to)
 265                                         continue;
 266                                 else
 267                                         goto next_group;
 268                         }
 269
 270                         int g2 = group_at(b, c);
 271                         /* If the neighbor is of our color, it must
 272                          * be also a 2-lib group. If it is more,
 273                          * we CERTAINLY want that liberty to be played
 274                          * first, what if it is an alive group? If it
 275                          * is in atari, we want to extend from it to
 276                          * prevent eye-making capture. However, if it
 277                          * is 2-lib, it is selfatari connecting two
 278                          * nakade'ing groups! */
 279                         /* X X X X  We will not allow play on 'a',
 280                          * X X a X  because 'b' would capture two
 281                          * X O b X  different groups, forming two
 282                          * X X X X  eyes. */
 283                         if (board_at(b, c) == color) {
 284                                 if (board_group_info(b, group_at(b, c)).libs == 2)
 285                                         continue;
 286                                 goto next_group;
 287                         }
 288
 289                         /* The neighbor is enemy color. It's ok if
 290                          * it's still the same group or this is its
 291                          * only liberty. */
 292                         if (g == g2 || board_group_info(b, g2).libs == 1)
 293                                 continue;
 294                         /* Otherwise, it must have the exact same
 295                          * liberties as the original enemy group. */
 296                         if (board_group_info(b, g2).libs == 2
 297                             && (board_group_info(b, g2).lib[0] == to
 298                                 || board_group_info(b, g2).lib[1] == to))
 299                                 continue;
 300
 301                         goto next_group;
 302                 });
 303
 304                 /* Now, we must distinguish between nakade and eye
 305                  * falsification; we must not falsify an eye by more
 306                  * than two stones. */
 307                 if (s->groupcts[color] < 1)
 308                         return false; // simple throw-in
 309                 if (s->groupcts[color] == 1 && group_is_onestone(b, s->groupids[color][0])) {
 310                         /* More complex throw-in - we are in one of
 311                          * three situations:
 312                          * a O O O O X  b O O O X  c O O O X
 313                          *   O . X . O    O X . .    O . X .
 314                          *   # # # # #    # # # #    # # # #
 315                          * b is desirable here (since maybe O has no
 316                          * backup two eyes); a may be desirable, but
 317                          * is tested next in check_throwin(). c is
 318                          * never desirable. */
 319                         group_t g2 = s->groupids[color][0];
 320                         assert(board_group_info(b, g2).libs <= 2);
 321                         if (board_group_info(b, g2).libs == 1)
 322                                 return false; // b
 323                         goto next_group; // a or c
 324                 }
 325
 326                 /* We would create more than 2-stone group; in that
 327                  * case, the liberty of our result must be lib2,
 328                  * indicating this really is a nakade. */
 329                 int stones = 0;
 330                 for (int j = 0; j < s->groupcts[color]; j++) {
 331                         group_t g2 = s->groupids[color][j];
 332                         assert(board_group_info(b, g2).libs <= 2);
 333                         if (board_group_info(b, g2).libs == 2) {
 334                                 if (board_group_info(b, g2).lib[0] != lib2
 335                                     && board_group_info(b, g2).lib[1] != lib2)
 336                                         goto next_group;
 337                         } else {
 338                                 assert(board_group_info(b, g2).lib[0] == to);
 339                         }
 340                         /* See below: */
 341                         stones += group_stone_count(b, g2, 6);
 342                         // fprintf(stderr, "%d (%d,%d) %d,%d\n", __LINE__, j, g2, stones);
 343                         if (stones > 5)
 344                                 return true;
 345                 }
 346
 347                 /* It also remains to be seen whether it is nakade
 348                  * and not seki destruction. To do this properly, we
 349                  * would have to look at the group shape. But we can
 350                  * cheat too! Brett Combs helps to introduce a static
 351                  * rule that should in fact cover *all* cases:
 352                  * 1. Total number of pre-selfatari nakade stones must
 353                  *    be 5 or smaller. (See above for that.)
 354                  * 2. If the selfatari is 8-touching all nakade stones,
 355                  *    it is proper nakade.
 356                  * 3. Otherwise, there must be only a single nakade
 357                  *    group, it must be at least 4-stone and its other
 358                  *    liberty must be 8-touching the same number of
 359                  *    stones as us. */
 360                 int touch8 = neighbor_count_at(b, to, color);
 361                 foreach_diag_neighbor(b, to) {
 362                         if (board_at(b, c) != color) continue;
 363                         /* Consider only internal stones. Otherwise, e.g.
 364                          * X O . X
 365                          * X . O X  can make trouble, bottom O is
 366                          * O X X X  irrelevant. */
 367                         if (board_group_info(b, group_at(b, c)).lib[0] == to
 368                             || board_group_info(b, group_at(b, c)).lib[1] == to)
 369                                 touch8++;
 370                 } foreach_diag_neighbor_end;
 371                 if (touch8 == stones)
 372                         return false;
 373
 374                 if (s->groupcts[color] > 1 || stones < 4)
 375                         return true;
 376                 int ltouch8 = neighbor_count_at(b, lib2, color);
 377                 foreach_diag_neighbor(b, lib2) {
 378                         if (board_at(b, c) != color) continue;
 379                         if (board_group_info(b, group_at(b, c)).lib[0] == to
 380                             || board_group_info(b, group_at(b, c)).lib[1] == to)
 381                                 ltouch8++;
 382                 } foreach_diag_neighbor_end;
 383                 return ltouch8 != touch8;
 384
 385 next_group:
 386                 /* Unless we are dealing with snapback setup, we don't need to look
 387                  * further. */
 388                 if (s->groupcts[color])
 389                         return -1;
 390         }
 391
 392         return -1;
 393 }
 394
 395 static int
 396 check_throwin(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
 397 {
 398         /* We can be throwing-in to false eye:
 399          * X X X O X X X O X X X X X
 400          * X . * X * O . X * O O . X
 401          * # # # # # # # # # # # # # */
 402         /* We cannot sensibly throw-in into a corner. */
 403         if (neighbor_count_at(b, to, S_OFFBOARD) < 2
 404             && neighbor_count_at(b, to, stone_other(color))
 405                + neighbor_count_at(b, to, S_OFFBOARD) == 3
 406             && board_is_false_eyelike(b, to, stone_other(color))) {
 407                 assert(s->groupcts[color] <= 1);
 408                 /* Single-stone throw-in may be ok... */
 409                 if (s->groupcts[color] == 0) {
 410                         /* O X .  There is one problem - when it's
 411                          * . * X  actually not a throw-in!
 412                          * # # #  */
 413                         foreach_neighbor(b, to, {
 414                                 if (board_at(b, c) == S_NONE) {
 415                                         /* Is the empty neighbor an escape path? */
 416                                         /* (Note that one S_NONE neighbor is already @to.) */
 417                                         if (neighbor_count_at(b, c, stone_other(color))
 418                                             + neighbor_count_at(b, c, S_OFFBOARD) < 2)
 419                                                 return -1;
 420                                 }
 421                         });
 422                         return false;
 423                 }
 424
 425                 /* Multi-stone throwin...? */
 426                 assert(s->groupcts[color] == 1);
 427                 group_t g = s->groupids[color][0];
 428
 429                 assert(board_group_info(b, g).libs <= 2);
 430                 /* Suicide is definitely NOT ok, no matter what else
 431                  * we could test. */
 432                 if (board_group_info(b, g).libs == 1)
 433                         return true;
 434
 435                 /* In that case, we must be connected to at most one stone,
 436                  * or throwin will not destroy any eyes. */
 437                 if (group_is_onestone(b, g))
 438                         return false;
 439         }
 440         return -1;
 441 }
 442
 443 bool
 444 is_bad_selfatari_slow(struct board *b, enum stone color, coord_t to)
 445 {
 446         if (DEBUGL(5))
 447                 fprintf(stderr, "sar check %s %s\n", stone2str(color), coord2sstr(to, b));
 448         /* Assess if we actually gain any liberties by this escape route.
 449          * Note that this is not 100% as we cannot check whether we are
 450          * connecting out or just to ourselves. */
 451
 452         struct selfatari_state s;
 453         memset(&s, 0, sizeof(s));
 454         int d;
 455
 456         foreach_neighbor(b, to, {
 457                 enum stone color = board_at(b, c);
 458                 group_t group = group_at(b, c);
 459                 bool dup = false;
 460                 for (int i = 0; i < s.groupcts[color]; i++)
 461                         if (s.groupids[color][i] == group) {
 462                                 dup = true;
 463                                 break;
 464                         }
 465                 if (!dup) {
 466                         s.groupneis[color][s.groupcts[color]] = c;
 467                         s.groupids[color][s.groupcts[color]++] = group_at(b, c);
 468                 }
 469         });
 470
 471         /* We have shortage of liberties; that's the point. */
 472         assert(s.groupcts[S_NONE] <= 1);
 473
 474         d = examine_friendly_groups(b, color, to, &s);
 475         if (d >= 0)
 476                 return d;
 477
 478         if (DEBUGL(6))
 479                 fprintf(stderr, "no friendly group\n");
 480
 481         d = examine_enemy_groups(b, color, to, &s);
 482         if (d >= 0)
 483                 return d;
 484
 485         if (DEBUGL(6))
 486                 fprintf(stderr, "no escape\n");
 487
 488         d = setup_nakade_or_snapback(b, color, to, &s);
 489         if (d >= 0)
 490                 return d;
 491
 492         if (DEBUGL(6))
 493                 fprintf(stderr, "no nakade group\n");
 494
 495         d = check_throwin(b, color, to, &s);
 496         if (d >= 0)
 497                 return d;
 498
 499         if (DEBUGL(6))
 500                 fprintf(stderr, "no throw-in group\n");
 501
 502         /* No way to pull out, no way to connect out. This really
 503          * is a bad self-atari! */
 504         return true;
 505 }
 506
 507
 508 coord_t
 509 selfatari_cousin(struct board *b, enum stone color, coord_t coord)
 510 {
 511         group_t groups[4]; int groups_n = 0;
 512         foreach_neighbor(b, coord, {
 513                 enum stone s = board_at(b, c);
 514                 if (s != color) continue;
 515                 group_t g = group_at(b, c);
 516                 if (board_group_info(b, g).libs == 2)
 517                         groups[groups_n++] = g;
 518         });
 519
 520         if (!groups_n)
 521                 return pass;
 522         group_t group = groups[fast_random(groups_n)];
 523
 524         coord_t lib2 = board_group_other_lib(b, group, coord);
 525         if (is_bad_selfatari(b, color, lib2))
 526                 return pass;
 527         return lib2;
 528 }