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 "mq.h"
   9 #include "tactics/1lib.h"
  10 #include "tactics/ladder.h"
  11
  12
  13 bool
  14 is_border_ladder(struct board *b, coord_t coord, group_t laddered, enum stone lcolor)
  15 {
  16         if (can_countercapture(b, lcolor, laddered, lcolor, NULL, 0))
  17                 return false;
  18
  19         int x = coord_x(coord, b), y = coord_y(coord, b);
  20
  21         if (DEBUGL(5))
  22                 fprintf(stderr, "border ladder\n");
  23         /* Direction along border; xd is horiz. border, yd vertical. */
  24         int xd = 0, yd = 0;
  25         if (board_atxy(b, x + 1, y) == S_OFFBOARD || board_atxy(b, x - 1, y) == S_OFFBOARD)
  26                 yd = 1;
  27         else
  28                 xd = 1;
  29         /* Direction from the border; -1 is above/left, 1 is below/right. */
  30         int dd = (board_atxy(b, x + yd, y + xd) == S_OFFBOARD) ? 1 : -1;
  31         if (DEBUGL(6))
  32                 fprintf(stderr, "xd %d yd %d dd %d\n", xd, yd, dd);
  33         /* | ? ?
  34          * | . O #
  35          * | c X #
  36          * | . O #
  37          * | ? ?   */
  38         /* This is normally caught, unless we have friends both above
  39          * and below... */
  40         if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor
  41             && board_atxy(b, x - xd * 2, y - yd * 2) == lcolor)
  42                 return false;
  43
  44         /* ...or can't block where we need because of shortage
  45          * of liberties. */
  46         group_t g1 = group_atxy(b, x + xd - yd * dd, y + yd - xd * dd);
  47         int libs1 = board_group_info(b, g1).libs;
  48         group_t g2 = group_atxy(b, x - xd - yd * dd, y - yd - xd * dd);
  49         int libs2 = board_group_info(b, g2).libs;
  50         if (DEBUGL(6))
  51                 fprintf(stderr, "libs1 %d libs2 %d\n", libs1, libs2);
  52         /* Already in atari? */
  53         if (libs1 < 2 || libs2 < 2)
  54                 return false;
  55         /* Would be self-atari? */
  56         if (libs1 < 3 && (board_atxy(b, x + xd * 2, y + yd * 2) != S_NONE
  57                           || coord_is_adjecent(board_group_info(b, g1).lib[0], board_group_info(b, g1).lib[1], b)))
  58                 return false;
  59         if (libs2 < 3 && (board_atxy(b, x - xd * 2, y - yd * 2) != S_NONE
  60                           || coord_is_adjecent(board_group_info(b, g2).lib[0], board_group_info(b, g2).lib[1], b)))
  61                 return false;
  62         return true;
  63 }
  64
  65
  66 /* This is a rather expensive ladder reader. It can read out any sequences
  67  * where laddered group should be kept at two liberties. The recursion
  68  * always makes a "to-be-laddered" move and then considers the chaser's
  69  * two alternatives (usually, one of them is trivially refutable). The
  70  * function returns true if there is a branch that ends up with laddered
  71  * group captured, false if not (i.e. for each branch, laddered group can
  72  * gain three liberties). */
  73
  74 static bool
  75 middle_ladder_walk(struct board *b, struct board *bset, group_t laddered, coord_t nextmove, enum stone lcolor)
  76 {
  77         assert(board_group_info(b, laddered).libs == 1);
  78
  79         /* First, escape. */
  80         if (DEBUGL(6))
  81                 fprintf(stderr, "  ladder escape %s\n", coord2sstr(nextmove, b));
  82         struct move m = { nextmove, lcolor };
  83         int res = board_play(b, &m);
  84         laddered = group_at(b, laddered);
  85         assert(res >= 0);
  86         if (DEBUGL(8)) {
  87                 board_print(b, stderr);
  88                 fprintf(stderr, "%s c %d\n", coord2sstr(laddered, b), board_group_info(b, laddered).libs);
  89         }
  90
  91         if (board_group_info(b, laddered).libs == 1) {
  92                 if (DEBUGL(6))
  93                         fprintf(stderr, "* we can capture now\n");
  94                 return true;
  95         }
  96         if (board_group_info(b, laddered).libs > 2) {
  97                 if (DEBUGL(6))
  98                         fprintf(stderr, "* we are free now\n");
  99                 return false;
 100         }
 101
 102         foreach_neighbor(b, m.coord, {
 103                 if (board_at(b, c) == stone_other(lcolor) && board_group_info(b, group_at(b, c)).libs == 1) {
 104                         /* We can capture one of the ladder stones
 105                          * anytime later. */
 106                         /* XXX: If we were very lucky, capturing
 107                          * this stone will not help us escape.
 108                          * That should be pretty rate. */
 109                         if (DEBUGL(6))
 110                                 fprintf(stderr, "* can capture chaser\n");
 111                         return false;
 112                 }
 113         });
 114
 115         /* Now, consider alternatives. */
 116         int liblist[2], libs = 0;
 117         for (int i = 0; i < 2; i++) {
 118                 coord_t ataristone = board_group_info(b, laddered).lib[i];
 119                 coord_t escape = board_group_info(b, laddered).lib[1 - i];
 120                 if (immediate_liberty_count(b, escape) > 2 + coord_is_adjecent(ataristone, escape, b)) {
 121                         /* Too much free space, ignore. */
 122                         continue;
 123                 }
 124                 liblist[libs++] = i;
 125         }
 126
 127         /* Try out the alternatives. */
 128         bool is_ladder = false;
 129         for (int i = 0; !is_ladder && i < libs; i++) {
 130                 struct board *b2 = b;
 131                 if (i != libs - 1) {
 132                         b2 = bset++;
 133                         board_copy(b2, b);
 134                 }
 135
 136                 coord_t ataristone = board_group_info(b2, laddered).lib[liblist[i]];
 137                 // coord_t escape = board_group_info(b2, laddered).lib[1 - liblist[i]];
 138                 struct move m = { ataristone, stone_other(lcolor) };
 139                 int res = board_play(b2, &m);
 140                 /* If we just played self-atari, abandon ship. */
 141                 /* XXX: If we were very lucky, capturing this stone will
 142                  * not help us escape. That should be pretty rate. */
 143                 if (DEBUGL(6))
 144                         fprintf(stderr, "(%d=%d) ladder atari %s (%d libs)\n", i, res, coord2sstr(ataristone, b2), board_group_info(b2, group_at(b2, ataristone)).libs);
 145                 if (res >= 0 && board_group_info(b2, group_at(b2, ataristone)).libs > 1)
 146                         is_ladder = middle_ladder_walk(b2, bset, laddered, board_group_info(b2, laddered).lib[0], lcolor);
 147
 148                 if (i != libs - 1) {
 149                         board_done_noalloc(b2);
 150                 }
 151         }
 152         if (DEBUGL(6))
 153                 fprintf(stderr, "propagating %d\n", is_ladder);
 154         return is_ladder;
 155 }
 156
 157 bool
 158 is_middle_ladder(struct board *b, coord_t coord, group_t laddered, enum stone lcolor)
 159 {
 160         /* TODO: Remove the redundant parameters. */
 161         assert(board_group_info(b, laddered).libs == 1);
 162         assert(board_group_info(b, laddered).lib[0] == coord);
 163         assert(board_at(b, laddered) == lcolor);
 164
 165         /* If we can move into empty space or do not have enough space
 166          * to escape, this is obviously not a ladder. */
 167         if (immediate_liberty_count(b, coord) != 2) {
 168                 if (DEBUGL(5))
 169                         fprintf(stderr, "no ladder, wrong free space\n");
 170                 return false;
 171         }
 172
 173         /* A fair chance for a ladder. Group in atari, with some but limited
 174          * space to escape. Time for the expensive stuff - set up a temporary
 175          * board and start selective 2-liberty search. */
 176
 177         struct board *bset = malloc2(BOARD_MAX_SIZE * 2 * sizeof(struct board));
 178
 179         struct move_queue ccq = { .moves = 0 };
 180         if (can_countercapture(b, lcolor, laddered, lcolor, &ccq, 0)) {
 181                 /* We could escape by countercapturing a group.
 182                  * Investigate. */
 183                 assert(ccq.moves > 0);
 184                 for (unsigned int i = 0; i < ccq.moves; i++) {
 185                         struct board b2;
 186                         board_copy(&b2, b);
 187                         bool is_ladder = middle_ladder_walk(&b2, bset, laddered, ccq.move[i], lcolor);
 188                         board_done_noalloc(&b2);
 189                         if (!is_ladder) {
 190                                 free(bset);
 191                                 return false;
 192                         }
 193                 }
 194         }
 195
 196         struct board b2;
 197         board_copy(&b2, b);
 198         bool is_ladder = middle_ladder_walk(&b2, bset, laddered, board_group_info(&b2, laddered).lib[0], lcolor);
 199         board_done_noalloc(&b2);
 200         free(bset);
 201         return is_ladder;
 202 }
 203
 204 bool
 205 wouldbe_ladder(struct board *b, group_t group, coord_t escapelib, coord_t chaselib, enum stone lcolor)
 206 {
 207         assert(board_group_info(b, group).libs == 2);
 208         assert(board_at(b, group) == lcolor);
 209
 210         if (DEBUGL(6))
 211                 fprintf(stderr, "would-be ladder check - does %s %s play out chasing move %s?\n",
 212                         stone2str(lcolor), coord2sstr(escapelib, b), coord2sstr(chaselib, b));
 213
 214         if (!coord_is_8adjecent(escapelib, chaselib, b)) {
 215                 if (DEBUGL(5))
 216                         fprintf(stderr, "cannot determine ladder for remote simulated stone\n");
 217                 return false;
 218         }
 219
 220         if (neighbor_count_at(b, chaselib, lcolor) != 1 || immediate_liberty_count(b, chaselib) != 2) {
 221                 if (DEBUGL(5))
 222                         fprintf(stderr, "overly trivial for a ladder\n");
 223                 return false;
 224         }
 225
 226         bool is_ladder = false;
 227         struct board *bset = malloc2(BOARD_MAX_SIZE * 2 * sizeof(struct board));
 228         struct board b2;
 229         board_copy(&b2, b);
 230
 231         struct move m = { chaselib, stone_other(lcolor) };
 232         int res = board_play(&b2, &m);
 233         if (res >= 0)
 234                 is_ladder = middle_ladder_walk(&b2, bset, group, board_group_info(&b2, group).lib[0], lcolor);
 235
 236         board_done_noalloc(&b2);
 237         free(bset);
 238         return is_ladder;
 239 }