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 /* This is very trivial and gets a lot of corner cases wrong.
  62  * We need this to be just very fast. One important point is
  63  * that we sometimes might not notice a ladder but if we do,
  64  * it should always work; thus we can use this for strong
  65  * negative hinting safely. */
  66 bool
  67 is_middle_ladder(struct board *b, coord_t coord, enum stone lcolor)
  68 {
  69         int x = coord_x(coord, b), y = coord_y(coord, b);
  70
  71         /* Figure out the ladder direction */
  72         int xd, yd;
  73         xd = board_atxy(b, x + 1, y) == S_NONE ? 1 : board_atxy(b, x - 1, y) == S_NONE ? -1 : 0;
  74         yd = board_atxy(b, x, y + 1) == S_NONE ? 1 : board_atxy(b, x, y - 1) == S_NONE ? -1 : 0;
  75
  76         if (!xd || !yd) {
  77                 if (DEBUGL(5))
  78                         fprintf(stderr, "no ladder, too little space; self-atari?\n");
  79                 return false;
  80         }
  81
  82         /* For given (xd,yd), we have two possibilities where to move
  83          * next. Consider (-1,-1):
  84          * n X .   n c X
  85          * c O X   X O #
  86          * X # #   . X #
  87          */
  88         bool horiz_first = ladder_catcher(b, x, y - yd, lcolor); // left case
  89         bool vert_first = ladder_catcher(b, x - xd, y, lcolor); // right case
  90
  91         /* We don't have to look at the other 'X' in the position - if it
  92          * wouldn't be there, the group wouldn't be in atari. */
  93
  94         /* We do only tight ladders, not loose ladders. Furthermore,
  95          * the ladders need to be simple:
  96          * . X .             . . X
  97          * c O X supported   . c O unsupported
  98          * X # #             X O #
  99          */
 100         assert(!(horiz_first && vert_first));
 101         if (!horiz_first && !vert_first) {
 102                 /* TODO: In case of basic non-simple ladder, play out both variants. */
 103                 if (DEBUGL(5))
 104                         fprintf(stderr, "non-simple ladder\n");
 105                 return false;
 106         }
 107
 108         /* We do that below for further moves, but now initially - check
 109          * that at 'c', we aren't putting any of the catching stones
 110          * in atari. */
 111 #if 1 // this might be broken?
 112 #define check_catcher_danger(b, x_, y_) do { \
 113         if (board_atxy(b, (x_), (y_)) != S_OFFBOARD \
 114             && board_group_info(b, group_atxy(b, (x_), (y_))).libs <= 2) { \
 115                 if (DEBUGL(5)) \
 116                         fprintf(stderr, "ladder failed - atari at the beginning\n"); \
 117                 return false; \
 118         } } while (0)
 119
 120         if (horiz_first) {
 121                 check_catcher_danger(b, x, y - yd);
 122                 check_catcher_danger(b, x - xd, y + yd);
 123         } else {
 124                 check_catcher_danger(b, x - xd, y);
 125                 check_catcher_danger(b, x + xd, y - yd);
 126         }
 127 #undef check_catcher_danger
 128 #endif
 129
 130 #define ladder_check(xd1_, yd1_, xd2_, yd2_, xd3_, yd3_)        \
 131         if (board_atxy(b, x, y) != S_NONE) { \
 132                 /* Did we hit a stone when playing out ladder? */ \
 133                 if (ladder_catcher(b, x, y, lcolor)) \
 134                         return true; /* ladder works */ \
 135                 if (board_group_info(b, group_atxy(b, x, y)).lib[0] > 0) \
 136                         return false; /* friend that's not in atari himself */ \
 137         } else { \
 138                 /* No. So we are at new position. \
 139                  * We need to check indirect ladder breakers. */ \
 140                 /* . 2 x 3 . \
 141                  * . x o O 1 <- only at O we can check for o at 2 \
 142                  * x o o x .    otherwise x at O would be still deadly \
 143                  * o o x . . \
 144                  * We check for o and x at 1, these are vital. \
 145                  * We check only for o at 2; x at 2 would mean we \
 146                  * need to fork (one step earlier). */ \
 147                 coord_t c1 = coord_xy(b, x + (xd1_), y + (yd1_)); \
 148                 enum stone s1 = board_at(b, c1); \
 149                 if (s1 == lcolor) return false; \
 150                 if (s1 == stone_other(lcolor)) { \
 151                         /* One more thing - if the position at 3 is \
 152                          * friendly and safe, we escaped anyway! */ \
 153                         coord_t c3 = coord_xy(b, x + (xd3_), y + (yd3_)); \
 154                         return board_at(b, c3) != lcolor \
 155                                || board_group_info(b, group_at(b, c3)).libs < 2; \
 156                 } \
 157                 enum stone s2 = board_atxy(b, x + (xd2_), y + (yd2_)); \
 158                 if (s2 == lcolor) return false; \
 159                 /* Then, can X actually "play" 1 in the ladder? */ \
 160                 if (neighbor_count_at(b, c1, lcolor) + neighbor_count_at(b, c1, S_OFFBOARD) >= 2) \
 161                         return false; /* It would be self-atari! */ \
 162         }
 163 #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)
 164 #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)
 165
 166         if (ladder_catcher(b, x - xd, y, lcolor))
 167                 ladder_horiz;
 168         do {
 169                 ladder_vert;
 170                 ladder_horiz;
 171         } while (1);
 172 }