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 int
  29 examine_friendly_groups(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
  30 {
  31         for (int i = 0; i < s->groupcts[color]; i++) {
  32                 /* We can escape by connecting to this group if it's
  33                  * not in atari. */
  34                 group_t g = s->groupids[color][i];
  35
  36                 if (board_group_info(b, g).libs == 1) {
  37                         if (!s->needs_more_lib)
  38                                 s->friend_has_no_libs = true;
  39                         // or we already have a friend with 1 lib
  40                         continue;
  41                 }
  42
  43                 /* Could we self-atari the group here? */
  44                 if (board_group_info(b, g).libs > 2)
  45                         return false;
  46
  47                 /* We need to have another liberty, and
  48                  * it must not be the other liberty of
  49                  * the group. */
  50                 int lib2 = board_group_other_lib(b, g, to);
  51                 /* Maybe we already looked at another
  52                  * group providing one liberty? */
  53                 if (s->needs_more_lib && s->needs_more_lib != g
  54                     && s->needs_more_lib_except != lib2)
  55                         return false;
  56
  57                 /* Can we get the liberty locally? */
  58                 /* Yes if we are route to more liberties... */
  59                 if (s->groupcts[S_NONE] > 1)
  60                         return false;
  61                 /* ...or one liberty, but not lib2. */
  62                 if (s->groupcts[S_NONE] > 0
  63                     && !coord_is_adjecent(lib2, to, b))
  64                         return false;
  65
  66                 /* ...ok, then we can still contribute a liberty
  67                  * later by capturing something. */
  68                 s->needs_more_lib = g;
  69                 s->needs_more_lib_except = lib2;
  70                 s->friend_has_no_libs = false;
  71         }
  72
  73         return -1;
  74 }
  75
  76 static int
  77 examine_enemy_groups(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
  78 {
  79         /* We may be able to gain a liberty by capturing this group. */
  80         group_t can_capture = 0;
  81
  82         /* Examine enemy groups: */
  83         for (int i = 0; i < s->groupcts[stone_other(color)]; i++) {
  84                 /* We can escape by capturing this group if it's in atari. */
  85                 group_t g = s->groupids[stone_other(color)][i];
  86                 if (board_group_info(b, g).libs > 1)
  87                         continue;
  88
  89                 /* But we need to get to at least two liberties by this;
  90                  * we already have one outside liberty, or the group is
  91                  * more than 1 stone (in that case, capturing is always
  92                  * nice!). */
  93                 if (s->groupcts[S_NONE] > 0 || !group_is_onestone(b, g))
  94                         return false;
  95                 /* ...or, it's a ko stone, */
  96                 if (neighbor_count_at(b, g, color) + neighbor_count_at(b, g, S_OFFBOARD) == 3) {
  97                         /* and we don't have a group to save: then, just taking
  98                          * single stone means snapback! */
  99                         if (!s->friend_has_no_libs)
 100                                 return false;
 101                 }
 102                 /* ...or, we already have one indirect liberty provided
 103                  * by another group. */
 104                 if (s->needs_more_lib || (can_capture && can_capture != g))
 105                         return false;
 106                 can_capture = g;
 107
 108         }
 109
 110         if (DEBUGL(6))
 111                 fprintf(stderr, "no cap group\n");
 112
 113         if (!s->needs_more_lib && !can_capture && !s->groupcts[S_NONE]) {
 114                 /* We have no hope for more fancy tactics - this move is simply
 115                  * a suicide, not even a self-atari. */
 116                 if (DEBUGL(6))
 117                         fprintf(stderr, "suicide\n");
 118                 return true;
 119         }
 120         /* XXX: I wonder if it makes sense to continue if we actually
 121          * just !s->needs_more_lib. */
 122
 123         return -1;
 124 }
 125
 126 static int
 127 setup_nakade_or_snapback(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
 128 {
 129         /* There is another possibility - we can self-atari if it is
 130          * a nakade: we put an enemy group in atari from the inside. */
 131         /* This branch also allows eyes falsification:
 132          * O O O . .  (This is different from throw-in to false eye
 133          * X X O O .  checked below in that there is no X stone at the
 134          * X . X O .  right of the star point in this diagram.)
 135          * X X X O O
 136          * X O * . . */
 137         /* TODO: Allow to only nakade if the created shape is dead
 138          * (http://senseis.xmp.net/?Nakade). */
 139
 140         /* This branch also covers snapback, which is kind of special
 141          * nakade case. ;-) */
 142         for (int i = 0; i < s->groupcts[stone_other(color)]; i++) {
 143                 group_t g = s->groupids[stone_other(color)][i];
 144                 if (board_group_info(b, g).libs != 2)
 145                         goto next_group;
 146                 /* Simple check not to re-examine the same group. */
 147                 if (i > 0 && s->groupids[stone_other(color)][i] == s->groupids[stone_other(color)][i - 1])
 148                         continue;
 149
 150                 /* We must make sure the other liberty of that group:
 151                  * (i) is an internal liberty
 152                  * (ii) filling it to capture our group will not gain
 153                  * safety */
 154
 155                 /* Let's look at neighbors of the other liberty: */
 156                 int lib2 = board_group_other_lib(b, g, to);
 157                 foreach_neighbor(b, lib2, {
 158                         /* This neighbor of course does not contribute
 159                          * anything to the enemy. */
 160                         if (board_at(b, c) == S_OFFBOARD)
 161                                 continue;
 162
 163                         /* If the other liberty has empty neighbor,
 164                          * it must be the original liberty; otherwise,
 165                          * since the whole group has only 2 liberties,
 166                          * the other liberty may not be internal and
 167                          * we are nakade'ing eyeless group from outside,
 168                          * which is stupid. */
 169                         if (board_at(b, c) == S_NONE) {
 170                                 if (c == to)
 171                                         continue;
 172                                 else
 173                                         goto next_group;
 174                         }
 175
 176                         int g2 = group_at(b, c);
 177                         /* If the neighbor is of our color, it must
 178                          * be also a 2-lib group. If it is more,
 179                          * we CERTAINLY want that liberty to be played
 180                          * first, what if it is an alive group? If it
 181                          * is in atari, we want to extend from it to
 182                          * prevent eye-making capture. However, if it
 183                          * is 2-lib, it is selfatari connecting two
 184                          * nakade'ing groups! */
 185                         /* X X X X  We will not allow play on 'a',
 186                          * X X a X  because 'b' would capture two
 187                          * X O b X  different groups, forming two
 188                          * X X X X  eyes. */
 189                         if (board_at(b, c) == color) {
 190                                 if (board_group_info(b, group_at(b, c)).libs == 2)
 191                                         continue;
 192                                 goto next_group;
 193                         }
 194
 195                         /* The neighbor is enemy color. It's ok if
 196                          * it's still the same group or this is its
 197                          * only liberty. */
 198                         if (g == g2 || board_group_info(b, g2).libs == 1)
 199                                 continue;
 200                         /* Otherwise, it must have the exact same
 201                          * liberties as the original enemy group. */
 202                         if (board_group_info(b, g2).libs == 2
 203                             && (board_group_info(b, g2).lib[0] == to
 204                                 || board_group_info(b, g2).lib[1] == to))
 205                                 continue;
 206
 207                         goto next_group;
 208                 });
 209
 210                 /* Now, we must distinguish between nakade and eye
 211                  * falsification; we must not falsify an eye by more
 212                  * than two stones. */
 213                 if (s->groupcts[color] < 1)
 214                         return false; // simple throw-in
 215                 if (s->groupcts[color] == 1 && group_is_onestone(b, s->groupids[color][0])) {
 216                         /* More complex throw-in - we are in one of
 217                          * three situations:
 218                          * a O O O O X  b O O O X  c O O O X
 219                          *   O . X . O    O X . .    O . X .
 220                          *   # # # # #    # # # #    # # # #
 221                          * b is desirable here (since maybe O has no
 222                          * backup two eyes); a may be desirable, but
 223                          * is tested next in check_throwin(). c is
 224                          * never desirable. */
 225                         group_t g2 = s->groupids[color][0];
 226                         assert(board_group_info(b, g2).libs <= 2);
 227                         if (board_group_info(b, g2).libs == 1)
 228                                 return false; // b
 229                         goto next_group; // a or c
 230                 }
 231
 232                 /* We would create more than 2-stone group; in that
 233                  * case, the liberty of our result must be lib2,
 234                  * indicating this really is a nakade. */
 235                 for (int j = 0; j < s->groupcts[color]; j++) {
 236                         group_t g2 = s->groupids[color][j];
 237                         assert(board_group_info(b, g2).libs <= 2);
 238                         if (board_group_info(b, g2).libs == 2) {
 239                                 if (board_group_info(b, g2).lib[0] != lib2
 240                                     && board_group_info(b, g2).lib[1] != lib2)
 241                                         goto next_group;
 242                         } else {
 243                                 assert(board_group_info(b, g2).lib[0] == to);
 244                         }
 245                 }
 246
 247                 return false;
 248 next_group:
 249                 /* Unless we are dealing with snapback setup, we don't need to look
 250                  * further. */
 251                 if (s->groupcts[color])
 252                         return -1;
 253         }
 254
 255         return -1;
 256 }
 257
 258 static int
 259 check_throwin(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
 260 {
 261         /* We can be throwing-in to false eye:
 262          * X X X O X X X O X X X X X
 263          * X . * X * O . X * O O . X
 264          * # # # # # # # # # # # # # */
 265         /* We cannot sensibly throw-in into a corner. */
 266         if (neighbor_count_at(b, to, S_OFFBOARD) < 2
 267             && neighbor_count_at(b, to, stone_other(color))
 268                + neighbor_count_at(b, to, S_OFFBOARD) == 3
 269             && board_is_false_eyelike(b, to, stone_other(color))) {
 270                 assert(s->groupcts[color] <= 1);
 271                 /* Single-stone throw-in may be ok... */
 272                 if (s->groupcts[color] == 0) {
 273                         /* O X .  There is one problem - when it's
 274                          * . * X  actually not a throw-in!
 275                          * # # #  */
 276                         foreach_neighbor(b, to, {
 277                                 if (board_at(b, c) == S_NONE) {
 278                                         /* Is the empty neighbor an escape path? */
 279                                         /* (Note that one S_NONE neighbor is already @to.) */
 280                                         if (neighbor_count_at(b, c, stone_other(color))
 281                                             + neighbor_count_at(b, c, S_OFFBOARD) < 2)
 282                                                 return -1;
 283                                 }
 284                         });
 285                         return false;
 286                 }
 287
 288                 /* Multi-stone throwin...? */
 289                 assert(s->groupcts[color] == 1);
 290                 group_t g = s->groupids[color][0];
 291
 292                 assert(board_group_info(b, g).libs <= 2);
 293                 /* Suicide is definitely NOT ok, no matter what else
 294                  * we could test. */
 295                 if (board_group_info(b, g).libs == 1)
 296                         return true;
 297
 298                 /* In that case, we must be connected to at most one stone,
 299                  * or throwin will not destroy any eyes. */
 300                 if (group_is_onestone(b, g))
 301                         return false;
 302         }
 303         return -1;
 304 }
 305
 306 bool
 307 is_bad_selfatari_slow(struct board *b, enum stone color, coord_t to)
 308 {
 309         if (DEBUGL(5))
 310                 fprintf(stderr, "sar check %s %s\n", stone2str(color), coord2sstr(to, b));
 311         /* Assess if we actually gain any liberties by this escape route.
 312          * Note that this is not 100% as we cannot check whether we are
 313          * connecting out or just to ourselves. */
 314
 315         struct selfatari_state s;
 316         memset(&s, 0, sizeof(s));
 317         int d;
 318
 319         foreach_neighbor(b, to, {
 320                 enum stone color = board_at(b, c);
 321                 s.groupids[color][s.groupcts[color]++] = group_at(b, c);
 322         });
 323
 324         /* We have shortage of liberties; that's the point. */
 325         assert(s.groupcts[S_NONE] <= 1);
 326
 327         d = examine_friendly_groups(b, color, to, &s);
 328         if (d >= 0)
 329                 return d;
 330
 331         if (DEBUGL(6))
 332                 fprintf(stderr, "no friendly group\n");
 333
 334         d = examine_enemy_groups(b, color, to, &s);
 335         if (d >= 0)
 336                 return d;
 337
 338         if (DEBUGL(6))
 339                 fprintf(stderr, "no escape\n");
 340
 341         d = setup_nakade_or_snapback(b, color, to, &s);
 342         if (d >= 0)
 343                 return d;
 344
 345         if (DEBUGL(6))
 346                 fprintf(stderr, "no nakade group\n");
 347
 348         d = check_throwin(b, color, to, &s);
 349         if (d >= 0)
 350                 return d;
 351
 352         if (DEBUGL(6))
 353                 fprintf(stderr, "no throw-in group\n");
 354
 355         /* No way to pull out, no way to connect out. This really
 356          * is a bad self-atari! */
 357         return true;
 358 }
 359
 360
 361 coord_t
 362 selfatari_cousin(struct board *b, enum stone color, coord_t coord)
 363 {
 364         group_t groups[4]; int groups_n = 0;
 365         foreach_neighbor(b, coord, {
 366                 enum stone s = board_at(b, c);
 367                 if (s != color) continue;
 368                 group_t g = group_at(b, c);
 369                 if (board_group_info(b, g).libs == 2)
 370                         groups[groups_n++] = g;
 371         });
 372
 373         if (!groups_n)
 374                 return pass;
 375         group_t group = groups[fast_random(groups_n)];
 376
 377         coord_t lib2 = board_group_other_lib(b, group, coord);
 378         if (is_bad_selfatari(b, color, lib2))
 379                 return pass;
 380         return lib2;
 381 }