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