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                 if (neighbor_count_at(b, c1, lcolor) + neighbor_count_at(b, c1, S_OFFBOARD) >= 2) \
 102                         return false; /* It would be self-atari! */ \
 103         }
 104 #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)
 105 #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)
 106
 107         if (ladder_catcher(b, x - xd, y, lcolor))
 108                 ladder_horiz;
 109         do {
 110                 ladder_vert;
 111                 ladder_horiz;
 112         } while (1);
 113 }
 114
 115 bool
 116 is_middle_ladder(struct board *b, coord_t coord, enum stone lcolor)
 117 {
 118         int x = coord_x(coord, b), y = coord_y(coord, b);
 119
 120         /* Figure out the ladder direction */
 121         int xd, yd;
 122         xd = board_atxy(b, x + 1, y) == S_NONE ? 1 : board_atxy(b, x - 1, y) == S_NONE ? -1 : 0;
 123         yd = board_atxy(b, x, y + 1) == S_NONE ? 1 : board_atxy(b, x, y - 1) == S_NONE ? -1 : 0;
 124
 125         if (!xd || !yd) {
 126                 if (DEBUGL(5))
 127                         fprintf(stderr, "no ladder, too little space; self-atari?\n");
 128                 return false;
 129         }
 130
 131         /* For given (xd,yd), we have two possibilities where to move
 132          * next. Consider (-1,-1):
 133          * n X .   n c X
 134          * c O X   X O #
 135          * X # #   . X #
 136          */
 137         bool horiz_first = ladder_catcher(b, x, y - yd, lcolor); // left case
 138         bool vert_first = ladder_catcher(b, x - xd, y, lcolor); // right case
 139
 140         /* We don't have to look at the other 'X' in the position - if it
 141          * wouldn't be there, the group wouldn't be in atari. */
 142
 143         /* We do only tight ladders, not loose ladders. Furthermore,
 144          * the ladders need to be simple:
 145          * . X .             . . X
 146          * c O X supported   . c O unsupported
 147          * X # #             X O #
 148          */
 149         assert(!(horiz_first && vert_first));
 150         if (!horiz_first && !vert_first) {
 151                 /* TODO: In case of basic non-simple ladder, play out both variants. */
 152                 if (DEBUGL(5))
 153                         fprintf(stderr, "non-simple ladder\n");
 154                 return false;
 155         }
 156
 157         /* We do that below for further moves, but now initially - check
 158          * that at 'c', we aren't putting any of the catching stones
 159          * in atari. */
 160 #if 1 // this might be broken?
 161 #define check_catcher_danger(b, x_, y_) do { \
 162         if (board_atxy(b, (x_), (y_)) != S_OFFBOARD \
 163             && board_group_info(b, group_atxy(b, (x_), (y_))).libs <= 2) { \
 164                 if (DEBUGL(5)) \
 165                         fprintf(stderr, "ladder failed - atari at the beginning\n"); \
 166                 return false; \
 167         } } while (0)
 168
 169         if (horiz_first) {
 170                 check_catcher_danger(b, x, y - yd);
 171                 check_catcher_danger(b, x - xd, y + yd);
 172         } else {
 173                 check_catcher_danger(b, x - xd, y);
 174                 check_catcher_danger(b, x + xd, y - yd);
 175         }
 176 #undef check_catcher_danger
 177 #endif
 178
 179         return middle_ladder_walk(b, lcolor, x, y, xd, yd);
 180 }