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                 /* We have hit a stone when playing out ladder? */ \
  74                 if (DEBUGL(6)) fprintf(stderr, "hit %s @ %s\n", stone2str(board_atxy(b, x, y)), coord2sstr(coord_xy(b, x, y), b)); \
  75                 if (ladder_catcher(b, x, y, lcolor)) \
  76                         return true; /* ladder works */ \
  77                 if (board_group_info(b, group_atxy(b, x, y)).lib[0] > 0) \
  78                         return false; /* friend that's not in atari himself */ \
  79         } else { \
  80                 /* No. So we are at new position. \
  81                  * We need to check indirect ladder breakers. */ \
  82                 /* . 2 x 3 . \
  83                  * . x o O 1 <- only at O we can check for o at 2 \
  84                  * x o o x .    otherwise x at O would be still deadly \
  85                  * o o x . . \
  86                  * We check for o and x at 1, these are vital. \
  87                  * We check only for o at 2; x at 2 would mean we \
  88                  * need to fork (one step earlier). */ \
  89                 coord_t c = coord_xy(b, x, y); \
  90                 coord_t c1 = coord_xy(b, x + (xd1_), y + (yd1_)); \
  91                 enum stone s1 = board_at(b, c1); \
  92                 if (s1 == lcolor) { \
  93                         if (DEBUGL(6)) fprintf(stderr, "hit c1 %s @ %s\n", stone2str(s1), coord2sstr(c1, b)); \
  94                         return false; \
  95                 } \
  96                 if (s1 == stone_other(lcolor)) { \
  97                         /* One more thing - if the position at 3 is \
  98                          * friendly and safe, we escaped anyway! */ \
  99                         coord_t c3 = coord_xy(b, x + (xd3_), y + (yd3_)); \
 100                         if (DEBUGL(6)) fprintf(stderr, "hit c1 %s @ %s, c3 %s @ %s\n", stone2str(s1), coord2sstr(c1, b), stone2str(board_at(b, c3)), coord2sstr(c3, b)); \
 101                         return board_at(b, c3) != lcolor \
 102                                || board_group_info(b, group_at(b, c3)).libs < 2; \
 103                 } \
 104                 coord_t c2 = coord_xy(b, x + (xd2_), y + (yd2_));\
 105                 enum stone s2 = board_at(b, c2); \
 106                 if (s2 == lcolor) { \
 107                         if (DEBUGL(6)) fprintf(stderr, "hit c2 %s @ %s\n", stone2str(s2), coord2sstr(c2, b)); \
 108                         return false; \
 109                 } \
 110                 /* Then, can X actually "play" 1 in the ladder? Of course,
 111                  * if we had already hit the edge, no need. */ \
 112                 if (neighbor_count_at(b, c, S_OFFBOARD) == 0 \
 113                     && neighbor_count_at(b, c1, lcolor) + neighbor_count_at(b, c1, S_OFFBOARD) >= 2) { \
 114                         if (DEBUGL(6)) fprintf(stderr, "hit selfatari at c1 %s\n", coord2sstr(c1, b)); \
 115                         return false; /* It would be self-atari! */ \
 116                 } \
 117         }
 118 #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)
 119 #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)
 120
 121         if (ladder_catcher(b, x - xd, y, lcolor))
 122                 ladder_horiz;
 123         do {
 124                 /* Terminate early if we got near the board edge
 125                  * and can force sagari:
 126                  * | . O . .
 127                  * | . 1 x .  2 would be expected by our ladder reader but we
 128                  * | 2 o o x  essentially opt for 1 by explicit edge check
 129                  * | . x o x  */
 130                 if (board_atxy(b, x + 2 * xd, y) == S_OFFBOARD
 131                     && board_atxy(b, x + xd, y - 1) == S_NONE && board_atxy(b, x + xd, y + 1) == S_NONE)
 132                         return true;
 133                 ladder_vert;
 134                 if (board_atxy(b, x, y + 2 * yd) == S_OFFBOARD
 135                     && board_atxy(b, x + 1, y + yd) == S_NONE && board_atxy(b, x - 1, y + yd) == S_NONE)
 136                         return true;
 137                 ladder_horiz;
 138         } while (1);
 139 }
 140
 141 bool
 142 is_middle_ladder(struct board *b, coord_t coord, group_t laddered, enum stone lcolor)
 143 {
 144         int x = coord_x(coord, b), y = coord_y(coord, b);
 145
 146         /* Figure out the ladder direction */
 147         int xd, yd;
 148         xd = board_atxy(b, x + 1, y) == S_NONE ? 1 : board_atxy(b, x - 1, y) == S_NONE ? -1 : 0;
 149         yd = board_atxy(b, x, y + 1) == S_NONE ? 1 : board_atxy(b, x, y - 1) == S_NONE ? -1 : 0;
 150
 151         if (!xd || !yd) {
 152                 if (DEBUGL(5))
 153                         fprintf(stderr, "no ladder, too little space; self-atari?\n");
 154                 return false;
 155         }
 156
 157         /* For given (xd,yd), we have two possibilities where to move
 158          * next. Consider (-1,-1):
 159          * n X .   n c X
 160          * c O X   X O #
 161          * X # #   . X #
 162          */
 163         bool horiz_first = ladder_catcher(b, x, y - yd, lcolor); // left case
 164         bool vert_first = ladder_catcher(b, x - xd, y, lcolor); // right case
 165
 166         /* We don't have to look at the other 'X' in the position - if it
 167          * wouldn't be there, the group wouldn't be in atari. */
 168
 169         /* We do only tight ladders, not loose ladders. Furthermore,
 170          * the ladders need to be simple:
 171          * . X .             . . X
 172          * c O X supported   . c O unsupported
 173          * X # #             X O #
 174          */
 175         assert(!(horiz_first && vert_first));
 176         if (!horiz_first && !vert_first) {
 177                 /* TODO: In case of basic non-simple ladder, play out both variants. */
 178                 if (DEBUGL(5))
 179                         fprintf(stderr, "non-simple ladder\n");
 180                 return false;
 181         }
 182
 183         /* We do that below for further moves, but now initially - check
 184          * that at 'c', we aren't putting any of the catching stones
 185          * in atari. */
 186 #if 1 // this might be broken?
 187 #define check_catcher_danger(b, x_, y_) do { \
 188         if (board_atxy(b, (x_), (y_)) != S_OFFBOARD \
 189             && board_group_info(b, group_atxy(b, (x_), (y_))).libs <= 2) { \
 190                 if (DEBUGL(5)) \
 191                         fprintf(stderr, "ladder failed - atari at the beginning\n"); \
 192                 return false; \
 193         } } while (0)
 194
 195         if (horiz_first) {
 196                 check_catcher_danger(b, x, y - yd);
 197                 check_catcher_danger(b, x - xd, y + yd);
 198         } else {
 199                 check_catcher_danger(b, x - xd, y);
 200                 check_catcher_danger(b, x + xd, y - yd);
 201         }
 202 #undef check_catcher_danger
 203 #endif
 204
 205         return middle_ladder_walk(b, lcolor, x, y, xd, yd);
 206 }
 207
 208 bool
 209 wouldbe_ladder(struct board *b, group_t group, coord_t escapelib, coord_t chaselib, enum stone lcolor)
 210 {
 211         if (DEBUGL(6))
 212                 fprintf(stderr, "would-be ladder check - does %s %s play out chasing move %s?\n",
 213                         stone2str(lcolor), coord2sstr(escapelib, b), coord2sstr(chaselib, b));
 214
 215         if (!coord_is_8adjecent(escapelib, chaselib, b)) {
 216                 if (DEBUGL(5))
 217                         fprintf(stderr, "cannot determine ladder for remote simulated stone\n");
 218                 return false;
 219         }
 220
 221         if (neighbor_count_at(b, chaselib, lcolor) != 1 || immediate_liberty_count(b, chaselib) != 2) {
 222                 if (DEBUGL(5))
 223                         fprintf(stderr, "overly trivial for a ladder\n");
 224                 return false;
 225         }
 226
 227         int x = coord_x(escapelib, b), y = coord_y(escapelib, b);
 228         int cx = coord_x(chaselib, b), cy = coord_y(chaselib, b);
 229
 230         /* Figure out the ladder direction */
 231         int xd, yd;
 232         xd = board_atxy(b, x + 1, y) == S_NONE ? 1 : board_atxy(b, x - 1, y) == S_NONE ? -1 : 0;
 233         yd = board_atxy(b, x, y + 1) == S_NONE ? 1 : board_atxy(b, x, y - 1) == S_NONE ? -1 : 0;
 234
 235         if (board_atxy(b, x + 1, y) == board_atxy(b, x - 1, y)
 236             || board_atxy(b, x, y + 1) == board_atxy(b, x, y - 1)) {
 237                 if (DEBUGL(5))
 238                         fprintf(stderr, "no ladder, distorted space\n");
 239                 return false;
 240         }
 241
 242         /* The ladder may be
 243          * . c .        . e X
 244          * e O X   or   c O X
 245          * X X X        . X X */
 246         bool horiz_first = cx + xd == x;
 247         bool vert_first = cy + yd == y;
 248         //fprintf(stderr, "esc %d,%d chase %d,%d xd %d yd %d\n", x,y, cx,cy, xd, yd);
 249         if (horiz_first == vert_first) {
 250                 /* TODO: In case of basic non-simple ladder, play out both variants. */
 251                 if (DEBUGL(5))
 252                         fprintf(stderr, "non-simple ladder\n");
 253                 return false;
 254         }
 255
 256         /* We skip the atari check, obviously. */
 257         return middle_ladder_walk(b, lcolor, x, y, xd, yd);
 258 }