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                 /* Terminate early if we got near the board edge
 114                  * and can force sagari:
 115                  * | . O . .
 116                  * | . 1 x .  2 would be expected by our ladder reader but we
 117                  * | 2 o o x  essentially opt for 1 by explicit edge check
 118                  * | . x o x  */
 119                 if (board_atxy(b, x + 2 * xd, y) == S_OFFBOARD
 120                     && board_atxy(b, x + xd, y - 1) == S_NONE && board_atxy(b, x + xd, y + 1) == S_NONE)
 121                         return true;
 122                 ladder_vert;
 123                 if (board_atxy(b, x, y + 2 * yd) == S_OFFBOARD
 124                     && board_atxy(b, x + 1, y + yd) == S_NONE && board_atxy(b, x - 1, y + yd) == S_NONE)
 125                         return true;
 126                 ladder_horiz;
 127         } while (1);
 128 }
 129
 130 bool
 131 is_middle_ladder(struct board *b, coord_t coord, enum stone lcolor)
 132 {
 133         int x = coord_x(coord, b), y = coord_y(coord, b);
 134
 135         /* Figure out the ladder direction */
 136         int xd, yd;
 137         xd = board_atxy(b, x + 1, y) == S_NONE ? 1 : board_atxy(b, x - 1, y) == S_NONE ? -1 : 0;
 138         yd = board_atxy(b, x, y + 1) == S_NONE ? 1 : board_atxy(b, x, y - 1) == S_NONE ? -1 : 0;
 139
 140         if (!xd || !yd) {
 141                 if (DEBUGL(5))
 142                         fprintf(stderr, "no ladder, too little space; self-atari?\n");
 143                 return false;
 144         }
 145
 146         /* For given (xd,yd), we have two possibilities where to move
 147          * next. Consider (-1,-1):
 148          * n X .   n c X
 149          * c O X   X O #
 150          * X # #   . X #
 151          */
 152         bool horiz_first = ladder_catcher(b, x, y - yd, lcolor); // left case
 153         bool vert_first = ladder_catcher(b, x - xd, y, lcolor); // right case
 154
 155         /* We don't have to look at the other 'X' in the position - if it
 156          * wouldn't be there, the group wouldn't be in atari. */
 157
 158         /* We do only tight ladders, not loose ladders. Furthermore,
 159          * the ladders need to be simple:
 160          * . X .             . . X
 161          * c O X supported   . c O unsupported
 162          * X # #             X O #
 163          */
 164         assert(!(horiz_first && vert_first));
 165         if (!horiz_first && !vert_first) {
 166                 /* TODO: In case of basic non-simple ladder, play out both variants. */
 167                 if (DEBUGL(5))
 168                         fprintf(stderr, "non-simple ladder\n");
 169                 return false;
 170         }
 171
 172         /* We do that below for further moves, but now initially - check
 173          * that at 'c', we aren't putting any of the catching stones
 174          * in atari. */
 175 #if 1 // this might be broken?
 176 #define check_catcher_danger(b, x_, y_) do { \
 177         if (board_atxy(b, (x_), (y_)) != S_OFFBOARD \
 178             && board_group_info(b, group_atxy(b, (x_), (y_))).libs <= 2) { \
 179                 if (DEBUGL(5)) \
 180                         fprintf(stderr, "ladder failed - atari at the beginning\n"); \
 181                 return false; \
 182         } } while (0)
 183
 184         if (horiz_first) {
 185                 check_catcher_danger(b, x, y - yd);
 186                 check_catcher_danger(b, x - xd, y + yd);
 187         } else {
 188                 check_catcher_danger(b, x - xd, y);
 189                 check_catcher_danger(b, x + xd, y - yd);
 190         }
 191 #undef check_catcher_danger
 192 #endif
 193
 194         return middle_ladder_walk(b, lcolor, x, y, xd, yd);
 195 }
 196
 197 bool
 198 wouldbe_ladder(struct board *b, coord_t escapelib, coord_t chaselib, enum stone lcolor)
 199 {
 200         if (DEBUGL(6))
 201                 fprintf(stderr, "would-be ladder check - does %s %s play out chasing move %s?\n",
 202                         stone2str(lcolor), coord2sstr(escapelib, b), coord2sstr(chaselib, b));
 203
 204         if (!coord_is_8adjecent(escapelib, chaselib, b)) {
 205                 if (DEBUGL(5))
 206                         fprintf(stderr, "cannot determine ladder for remote simulated stone\n");
 207                 return false;
 208         }
 209
 210         if (neighbor_count_at(b, chaselib, lcolor) != 1 || immediate_liberty_count(b, chaselib) != 2) {
 211                 if (DEBUGL(5))
 212                         fprintf(stderr, "overly trivial for a ladder\n");
 213                 return false;
 214         }
 215
 216         int x = coord_x(escapelib, b), y = coord_y(escapelib, b);
 217         int cx = coord_x(chaselib, b), cy = coord_y(chaselib, b);
 218
 219         /* Figure out the ladder direction */
 220         int xd, yd;
 221         xd = board_atxy(b, x + 1, y) == S_NONE ? 1 : board_atxy(b, x - 1, y) == S_NONE ? -1 : 0;
 222         yd = board_atxy(b, x, y + 1) == S_NONE ? 1 : board_atxy(b, x, y - 1) == S_NONE ? -1 : 0;
 223
 224         if (board_atxy(b, x + 1, y) == board_atxy(b, x - 1, y)
 225             || board_atxy(b, x, y + 1) == board_atxy(b, x, y - 1)) {
 226                 if (DEBUGL(5))
 227                         fprintf(stderr, "no ladder, distorted space\n");
 228                 return false;
 229         }
 230
 231         /* The ladder may be
 232          * . c .        . e X
 233          * e O X   or   c O X
 234          * X X X        . X X */
 235         bool horiz_first = cx + xd == x;
 236         bool vert_first = cy + yd == y;
 237         //fprintf(stderr, "esc %d,%d chase %d,%d xd %d yd %d\n", x,y, cx,cy, xd, yd);
 238         if (horiz_first == vert_first) {
 239                 /* TODO: In case of basic non-simple ladder, play out both variants. */
 240                 if (DEBUGL(5))
 241                         fprintf(stderr, "non-simple ladder\n");
 242                 return false;
 243         }
 244
 245         /* We skip the atari check, obviously. */
 246         return middle_ladder_walk(b, lcolor, x, y, xd, yd);
 247 }