tactics/ladder.c

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