tactics/2lib.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/2lib.h"
  10 #include "tactics/selfatari.h"
  11
  12
  13 /* Whether to avoid capturing/atariing doomed groups (this is big
  14  * performance hit and may reduce playouts balance; it does increase
  15  * the strength, but not quite proportionally to the performance). */
  16 //#define NO_DOOMED_GROUPS
  17
  18
  19 static bool
  20 miai_2lib(struct board *b, group_t group, enum stone color)
  21 {
  22         bool can_connect = false, can_pull_out = false;
  23         /* We have miai if we can either connect on both libs,
  24          * or connect on one lib and escape on another. (Just
  25          * having two escape routes can be risky.) We must make
  26          * sure that we don't consider following as miai:
  27          * X X X O
  28          * X . . O
  29          * O O X O - left dot would be pull-out, right dot connect */
  30         foreach_neighbor(b, board_group_info(b, group).lib[0], {
  31                 enum stone cc = board_at(b, c);
  32                 if (cc == S_NONE && cc != board_at(b, board_group_info(b, group).lib[1])) {
  33                         can_pull_out = true;
  34                 } else if (cc != color) {
  35                         continue;
  36                 }
  37
  38                 group_t cg = group_at(b, c);
  39                 if (cg && cg != group && board_group_info(b, cg).libs > 1)
  40                         can_connect = true;
  41         });
  42         foreach_neighbor(b, board_group_info(b, group).lib[1], {
  43                 enum stone cc = board_at(b, c);
  44                 if (c == board_group_info(b, group).lib[0])
  45                         continue;
  46                 if (cc == S_NONE && can_connect) {
  47                         return true;
  48                 } else if (cc != color) {
  49                         continue;
  50                 }
  51
  52                 group_t cg = group_at(b, c);
  53                 if (cg && cg != group && board_group_info(b, cg).libs > 1)
  54                         return (can_connect || can_pull_out);
  55         });
  56         return false;
  57 }
  58
  59 static bool
  60 defense_is_hopeless(struct board *b, group_t group, enum stone owner,
  61                         enum stone to_play, coord_t lib, coord_t otherlib,
  62                         bool use)
  63 {
  64         /* If we are the defender not connecting out, do not
  65          * escape with moves that do not gain liberties anyway
  66          * - either the new extension has just single extra
  67          * liberty, or the "gained" liberties are shared. */
  68         /* XXX: We do not check connecting to a short-on-liberty
  69          * group (e.g. ourselves). */
  70         if (DEBUGL(7))
  71                 fprintf(stderr, "\tif_check %d and defending %d and uscount %d ilcount %d\n",
  72                         use, to_play == owner,
  73                         neighbor_count_at(b, lib, owner),
  74                         immediate_liberty_count(b, lib));
  75         if (!use)
  76                 return false;
  77         if (to_play == owner && neighbor_count_at(b, lib, owner) == 1) {
  78                 if (immediate_liberty_count(b, lib) == 1)
  79                         return true;
  80                 if (immediate_liberty_count(b, lib) == 2
  81                     && coord_is_adjecent(lib, otherlib, b))
  82                         return true;
  83         }
  84         return false;
  85 }
  86
  87 void
  88 can_atari_group(struct board *b, group_t group, enum stone owner,
  89                   enum stone to_play, struct move_queue *q,
  90                   int tag, bool use_def_no_hopeless)
  91 {
  92         bool have[2] = { false, false };
  93         bool preference[2] = { true, true };
  94         for (int i = 0; i < 2; i++) {
  95                 coord_t lib = board_group_info(b, group).lib[i];
  96                 assert(board_at(b, lib) == S_NONE);
  97                 if (!board_is_valid_play(b, to_play, lib))
  98                         continue;
  99
 100                 if (DEBUGL(6))
 101                         fprintf(stderr, "- checking liberty %s of %s %s, filled by %s\n",
 102                                 coord2sstr(lib, b),
 103                                 stone2str(owner), coord2sstr(group, b),
 104                                 stone2str(to_play));
 105
 106                 /* Don't play at the spot if it is extremely short
 107                  * of liberties... */
 108                 /* XXX: This looks harmful, could significantly
 109                  * prefer atari to throwin:
 110                  *
 111                  * XXXOOOOOXX
 112                  * .OO.....OX
 113                  * XXXOOOOOOX */
 114 #if 0
 115                 if (neighbor_count_at(b, lib, stone_other(owner)) + immediate_liberty_count(b, lib) < 2)
 116                         continue;
 117 #endif
 118
 119                 /* Prevent hopeless escape attempts. */
 120                 if (defense_is_hopeless(b, group, owner, to_play, lib,
 121                                         board_group_info(b, group).lib[1 - i],
 122                                         use_def_no_hopeless))
 123                         continue;
 124
 125 #ifdef NO_DOOMED_GROUPS
 126                 /* If the owner can't play at the spot, we don't want
 127                  * to bother either. */
 128                 if (is_bad_selfatari(b, owner, lib))
 129                         continue;
 130 #endif
 131
 132                 /* Of course we don't want to play bad selfatari
 133                  * ourselves, if we are the attacker... */
 134                 if (
 135 #ifdef NO_DOOMED_GROUPS
 136                     to_play != owner &&
 137 #endif
 138                     is_bad_selfatari(b, to_play, lib)) {
 139                         if (DEBUGL(7))
 140                                 fprintf(stderr, "\tliberty is selfatari\n");
 141                         coord_t coord = pass;
 142                         group_t bygroup = 0;
 143                         if (to_play != owner) {
 144                                 /* Okay! We are attacker; maybe we just need
 145                                  * to connect a false eye before atari - this
 146                                  * is very common in the corner. */
 147                                 coord = selfatari_cousin(b, to_play, lib, &bygroup);
 148                         }
 149                         if (is_pass(coord))
 150                                 continue;
 151                         /* Ok, connect, but prefer not to. */
 152                         enum stone byowner = board_at(b, bygroup);
 153                         if (DEBUGL(7))
 154                                 fprintf(stderr, "\treluctantly switching to cousin %s (group %s %s)\n",
 155                                         coord2sstr(coord, b), coord2sstr(bygroup, b), stone2str(byowner));
 156                         /* One more thing - is the cousin sensible defense
 157                          * for the other group? */
 158                         if (defense_is_hopeless(b, bygroup, byowner, to_play,
 159                                                 coord, lib,
 160                                                 use_def_no_hopeless))
 161                                 continue;
 162                         lib = coord;
 163                         preference[i] = false;
 164
 165                 /* By now, we must be decided we add the move to the
 166                  * queue!  [comment intentionally misindented] */
 167
 168                 }
 169
 170                 have[i] = true;
 171
 172                 /* If the move is too "lumpy", prefer the alternative:
 173                  *
 174                  * #######
 175                  * ..O.X.X <- always play the left one!
 176                  * OXXXXXX */
 177                 if (neighbor_count_at(b, lib, to_play) + neighbor_count_at(b, lib, S_OFFBOARD) >= 3) {
 178                         if (DEBUGL(7))
 179                                 fprintf(stderr, "\tlumpy: mine %d + edge %d\n",
 180                                         neighbor_count_at(b, lib, to_play),
 181                                         neighbor_count_at(b, lib, S_OFFBOARD));
 182                         preference[i] = false;
 183                 }
 184
 185                 if (DEBUGL(6))
 186                         fprintf(stderr, "+ liberty %s ready with preference %d\n", coord2sstr(lib, b), preference[i]);
 187
 188                 /* If we prefer only one of the moves, pick that one. */
 189                 if (i == 1 && have[0] && preference[0] != preference[1]) {
 190                         if (!preference[0]) {
 191                                 if (q->move[q->moves - 1] == board_group_info(b, group).lib[0])
 192                                         q->moves--;
 193                                 /* ...else{ may happen, since we call
 194                                  * mq_nodup() and the move might have
 195                                  * been there earlier. */
 196                         } else {
 197                                 assert(!preference[1]);
 198                                 continue;
 199                         }
 200                 }
 201
 202                 /* Tasty! Crispy! Good! */
 203                 mq_add(q, lib, tag);
 204                 mq_nodup(q);
 205         }
 206
 207         if (DEBUGL(7)) {
 208                 char label[256];
 209                 snprintf(label, 256, "= final %s %s liberties to play by %s",
 210                         stone2str(owner), coord2sstr(group, b),
 211                         stone2str(to_play));
 212                 mq_print(q, b, label);
 213         }
 214 }
 215
 216 void
 217 group_2lib_check(struct board *b, group_t group, enum stone to_play, struct move_queue *q, int tag, bool use_miaisafe, bool use_def_no_hopeless)
 218 {
 219         enum stone color = board_at(b, group_base(group));
 220         assert(color != S_OFFBOARD && color != S_NONE);
 221
 222         if (DEBUGL(5))
 223                 fprintf(stderr, "[%s] 2lib check of color %d\n",
 224                         coord2sstr(group, b), color);
 225
 226         /* Do not try to atari groups that cannot be harmed. */
 227         if (use_miaisafe && miai_2lib(b, group, color))
 228                 return;
 229
 230         can_atari_group(b, group, color, to_play, q, tag, use_def_no_hopeless);
 231
 232         /* Can we counter-atari another group, if we are the defender? */
 233         if (to_play != color)
 234                 return;
 235         foreach_in_group(b, group) {
 236                 foreach_neighbor(b, c, {
 237                         if (board_at(b, c) != stone_other(color))
 238                                 continue;
 239                         group_t g2 = group_at(b, c);
 240                         if (board_group_info(b, g2).libs == 1) {
 241                                 /* We can capture a neighbor. */
 242                                 mq_add(q, board_group_info(b, g2).lib[0], tag);
 243                                 mq_nodup(q);
 244                                 continue;
 245                         }
 246                         if (board_group_info(b, g2).libs != 2)
 247                                 continue;
 248                         can_atari_group(b, g2, stone_other(color), to_play, q, tag, use_def_no_hopeless);
 249                 });
 250         } foreach_in_group_end;
 251 }