tactics/ladder.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 "tactics/ladder.h"
   9
  10
  11 /* Is this ladder breaker friendly for the one who catches ladder. */
  12 static bool
  13 ladder_catcher(struct board *b, int x, int y, enum stone laddered)
  14 {
  15         enum stone breaker = board_atxy(b, x, y);
  16         return breaker == stone_other(laddered) || breaker == S_OFFBOARD;
  17 }
  18
  19 bool
  20 is_border_ladder(struct board *b, coord_t coord, enum stone lcolor)
  21 {
  22         int x = coord_x(coord, b), y = coord_y(coord, b);
  23
  24         if (DEBUGL(5))
  25                 fprintf(stderr, "border ladder\n");
  26         /* Direction along border; xd is horiz. border, yd vertical. */
  27         int xd = 0, yd = 0;
  28         if (board_atxy(b, x + 1, y) == S_OFFBOARD || board_atxy(b, x - 1, y) == S_OFFBOARD)
  29                 yd = 1;
  30         else
  31                 xd = 1;
  32         /* Direction from the border; -1 is above/left, 1 is below/right. */
  33         int dd = (board_atxy(b, x + yd, y + xd) == S_OFFBOARD) ? 1 : -1;
  34         if (DEBUGL(6))
  35                 fprintf(stderr, "xd %d yd %d dd %d\n", xd, yd, dd);
  36         /* | ? ?
  37          * | . O #
  38          * | c X #
  39          * | . O #
  40          * | ? ?   */
  41         /* This is normally caught, unless we have friends both above
  42          * and below... */
  43         if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor
  44             && board_atxy(b, x - xd * 2, y - yd * 2) == lcolor)
  45                 return false;
  46         /* ...or can't block where we need because of shortage
  47          * of liberties. */
  48         int libs1 = board_group_info(b, group_atxy(b, x + xd - yd * dd, y + yd - xd * dd)).libs;
  49         int libs2 = board_group_info(b, group_atxy(b, x - xd - yd * dd, y - yd - xd * dd)).libs;
  50         if (DEBUGL(6))
  51                 fprintf(stderr, "libs1 %d libs2 %d\n", libs1, libs2);
  52         if (libs1 < 2 && libs2 < 2)
  53                 return false;
  54         if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor && libs1 < 3)
  55                 return false;
  56         if (board_atxy(b, x - xd * 2, y - yd * 2) == lcolor && libs2 < 3)
  57                 return false;
  58         return true;
  59 }
  60
  61
  62 /* This is very trivial and gets a lot of corner cases wrong.
  63  * We need this to be just very fast. One important point is
  64  * that we sometimes might not notice a ladder but if we do,
  65  * it should always work; thus we can use this for strong
  66  * negative hinting safely. */
  67
  68 static bool
  69 middle_ladder_walk(struct board *b, enum stone lcolor, int x, int y, int xd, int yd)
  70 {
  71 #define ladder_check(xd1_, yd1_, xd2_, yd2_, xd3_, yd3_)        \
  72         if (board_atxy(b, x, y) != S_NONE) { \
  73                 /* Did we hit a stone when playing out ladder? */ \
  74                 if (ladder_catcher(b, x, y, lcolor)) \
  75                         return true; /* ladder works */ \
  76                 if (board_group_info(b, group_atxy(b, x, y)).lib[0] > 0) \
  77                         return false; /* friend that's not in atari himself */ \
  78         } else { \
  79                 /* No. So we are at new position. \
  80                  * We need to check indirect ladder breakers. */ \
  81                 /* . 2 x 3 . \
  82                  * . x o O 1 <- only at O we can check for o at 2 \
  83                  * x o o x .    otherwise x at O would be still deadly \
  84                  * o o x . . \
  85                  * We check for o and x at 1, these are vital. \
  86                  * We check only for o at 2; x at 2 would mean we \
  87                  * need to fork (one step earlier). */ \
  88                 coord_t c = coord_xy(b, x, y); \
  89                 coord_t c1 = coord_xy(b, x + (xd1_), y + (yd1_)); \
  90                 enum stone s1 = board_at(b, c1); \
  91                 if (s1 == lcolor) return false; \
  92                 if (s1 == stone_other(lcolor)) { \
  93                         /* One more thing - if the position at 3 is \
  94                          * friendly and safe, we escaped anyway! */ \
  95                         coord_t c3 = coord_xy(b, x + (xd3_), y + (yd3_)); \
  96                         return board_at(b, c3) != lcolor \
  97                                || board_group_info(b, group_at(b, c3)).libs < 2; \
  98                 } \
  99                 enum stone s2 = board_atxy(b, x + (xd2_), y + (yd2_)); \
 100                 if (s2 == lcolor) return false; \
 101                 /* Then, can X actually "play" 1 in the ladder? Of course,
 102                  * if we had already hit the edge, no need. */ \
 103                 if (neighbor_count_at(b, c, S_OFFBOARD) == 0 \
 104                     && neighbor_count_at(b, c1, lcolor) + neighbor_count_at(b, c1, S_OFFBOARD) >= 2) \
 105                         return false; /* It would be self-atari! */ \
 106         }
 107 #define ladder_horiz    do { if (DEBUGL(6)) fprintf(stderr, "%d,%d horiz step (%d,%d)\n", x, y, xd, yd); x += xd; ladder_check(xd, 0, -2 * xd, yd, 0, yd); } while (0)
 108 #define ladder_vert     do { if (DEBUGL(6)) fprintf(stderr, "%d,%d vert step of (%d,%d)\n", x, y, xd, yd); y += yd; ladder_check(0, yd, xd, -2 * yd, xd, 0); } while (0)
 109
 110         if (ladder_catcher(b, x - xd, y, lcolor))
 111                 ladder_horiz;
 112         do {
 113                 ladder_vert;
 114                 ladder_horiz;
 115         } while (1);
 116 }
 117
 118 bool
 119 is_middle_ladder(struct board *b, coord_t coord, enum stone lcolor)
 120 {
 121         int x = coord_x(coord, b), y = coord_y(coord, b);
 122
 123         /* Figure out the ladder direction */
 124         int xd, yd;
 125         xd = board_atxy(b, x + 1, y) == S_NONE ? 1 : board_atxy(b, x - 1, y) == S_NONE ? -1 : 0;
 126         yd = board_atxy(b, x, y + 1) == S_NONE ? 1 : board_atxy(b, x, y - 1) == S_NONE ? -1 : 0;
 127
 128         if (!xd || !yd) {
 129                 if (DEBUGL(5))
 130                         fprintf(stderr, "no ladder, too little space; self-atari?\n");
 131                 return false;
 132         }
 133
 134         /* For given (xd,yd), we have two possibilities where to move
 135          * next. Consider (-1,-1):
 136          * n X .   n c X
 137          * c O X   X O #
 138          * X # #   . X #
 139          */
 140         bool horiz_first = ladder_catcher(b, x, y - yd, lcolor); // left case
 141         bool vert_first = ladder_catcher(b, x - xd, y, lcolor); // right case
 142
 143         /* We don't have to look at the other 'X' in the position - if it
 144          * wouldn't be there, the group wouldn't be in atari. */
 145
 146         /* We do only tight ladders, not loose ladders. Furthermore,
 147          * the ladders need to be simple:
 148          * . X .             . . X
 149          * c O X supported   . c O unsupported
 150          * X # #             X O #
 151          */
 152         assert(!(horiz_first && vert_first));
 153         if (!horiz_first && !vert_first) {
 154                 /* TODO: In case of basic non-simple ladder, play out both variants. */
 155                 if (DEBUGL(5))
 156                         fprintf(stderr, "non-simple ladder\n");
 157                 return false;
 158         }
 159
 160         /* We do that below for further moves, but now initially - check
 161          * that at 'c', we aren't putting any of the catching stones
 162          * in atari. */
 163 #if 1 // this might be broken?
 164 #define check_catcher_danger(b, x_, y_) do { \
 165         if (board_atxy(b, (x_), (y_)) != S_OFFBOARD \
 166             && board_group_info(b, group_atxy(b, (x_), (y_))).libs <= 2) { \
 167                 if (DEBUGL(5)) \
 168                         fprintf(stderr, "ladder failed - atari at the beginning\n"); \
 169                 return false; \
 170         } } while (0)
 171
 172         if (horiz_first) {
 173                 check_catcher_danger(b, x, y - yd);
 174                 check_catcher_danger(b, x - xd, y + yd);
 175         } else {
 176                 check_catcher_danger(b, x - xd, y);
 177                 check_catcher_danger(b, x + xd, y - yd);
 178         }
 179 #undef check_catcher_danger
 180 #endif
 181
 182         return middle_ladder_walk(b, lcolor, x, y, xd, yd);
 183 }
 184
 185 bool
 186 wouldbe_ladder(struct board *b, coord_t escapelib, coord_t chaselib, enum stone lcolor)
 187 {
 188         if (DEBUGL(6))
 189                 fprintf(stderr, "would-be ladder check - does %s %s play out chasing move %s?\n",
 190                         stone2str(lcolor), coord2sstr(escapelib, b), coord2sstr(chaselib, b));
 191
 192         if (!coord_is_8adjecent(escapelib, chaselib, b)) {
 193                 if (DEBUGL(5))
 194                         fprintf(stderr, "cannot determine ladder for remote simulated stone\n");
 195                 return false;
 196         }
 197
 198         if (neighbor_count_at(b, chaselib, lcolor) != 1 || immediate_liberty_count(b, chaselib) != 2) {
 199                 if (DEBUGL(5))
 200                         fprintf(stderr, "overly trivial for a ladder\n");
 201                 return false;
 202         }
 203
 204         int x = coord_x(escapelib, b), y = coord_y(escapelib, b);
 205         int cx = coord_x(chaselib, b), cy = coord_y(chaselib, b);
 206
 207         /* Figure out the ladder direction */
 208         int xd, yd;
 209         xd = board_atxy(b, x + 1, y) == S_NONE ? 1 : board_atxy(b, x - 1, y) == S_NONE ? -1 : 0;
 210         yd = board_atxy(b, x, y + 1) == S_NONE ? 1 : board_atxy(b, x, y - 1) == S_NONE ? -1 : 0;
 211
 212         if (board_atxy(b, x + 1, y) == board_atxy(b, x - 1, y)
 213             || board_atxy(b, x, y + 1) == board_atxy(b, x, y - 1)) {
 214                 if (DEBUGL(5))
 215                         fprintf(stderr, "no ladder, distorted space\n");
 216                 return false;
 217         }
 218
 219         /* The ladder may be
 220          * . c .        . e X
 221          * e O X   or   c O X
 222          * X X X        . X X */
 223         bool horiz_first = cx + xd == x;
 224         bool vert_first = cy + yd == y;
 225         //fprintf(stderr, "esc %d,%d chase %d,%d xd %d yd %d\n", x,y, cx,cy, xd, yd);
 226         if (horiz_first == vert_first) {
 227                 /* TODO: In case of basic non-simple ladder, play out both variants. */
 228                 if (DEBUGL(5))
 229                         fprintf(stderr, "non-simple ladder\n");
 230                 return false;
 231         }
 232
 233         /* We skip the atari check, obviously. */
 234         return middle_ladder_walk(b, lcolor, x, y, xd, yd);
 235 }