tactics.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.h"
   9
  10
  11 struct selfatari_state {
  12         int groupcts[S_MAX];
  13         group_t groupids[S_MAX][4];
  14
  15         /* This is set if this move puts a group out of _all_
  16          * liberties; we need to watch out for snapback then. */
  17         bool friend_has_no_libs;
  18         /* We may have one liberty, but be looking for one more.
  19          * In that case, @needs_more_lib is id of group
  20          * already providing one, don't consider it again. */
  21         group_t needs_more_lib;
  22         /* ID of the first liberty, providing it again is not
  23          * interesting. */
  24         coord_t needs_more_lib_except;
  25 };
  26
  27 static int
  28 examine_friendly_groups(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
  29 {
  30         for (int i = 0; i < s->groupcts[color]; i++) {
  31                 /* We can escape by connecting to this group if it's
  32                  * not in atari. */
  33                 group_t g = s->groupids[color][i];
  34
  35                 if (board_group_info(b, g).libs == 1) {
  36                         if (!s->needs_more_lib)
  37                                 s->friend_has_no_libs = true;
  38                         // or we already have a friend with 1 lib
  39                         continue;
  40                 }
  41
  42                 /* Could we self-atari the group here? */
  43                 if (board_group_info(b, g).libs > 2)
  44                         return false;
  45
  46                 /* We need to have another liberty, and
  47                  * it must not be the other liberty of
  48                  * the group. */
  49                 int lib2 = board_group_info(b, g).lib[0];
  50                 if (lib2 == to) lib2 = board_group_info(b, g).lib[1];
  51                 /* Maybe we already looked at another
  52                  * group providing one liberty? */
  53                 if (s->needs_more_lib && s->needs_more_lib != g
  54                     && s->needs_more_lib_except != lib2)
  55                         return false;
  56
  57                 /* Can we get the liberty locally? */
  58                 /* Yes if we are route to more liberties... */
  59                 if (s->groupcts[S_NONE] > 1)
  60                         return false;
  61                 /* ...or one liberty, but not lib2. */
  62                 if (s->groupcts[S_NONE] > 0
  63                     && !coord_is_adjecent(lib2, to, b))
  64                         return false;
  65
  66                 /* ...ok, then we can still contribute a liberty
  67                  * later by capturing something. */
  68                 s->needs_more_lib = g;
  69                 s->needs_more_lib_except = lib2;
  70                 s->friend_has_no_libs = false;
  71         }
  72
  73         return -1;
  74 }
  75
  76 static int
  77 examine_enemy_groups(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
  78 {
  79         /* We may be able to gain a liberty by capturing this group. */
  80         group_t can_capture = 0;
  81
  82         /* Examine enemy groups: */
  83         for (int i = 0; i < s->groupcts[stone_other(color)]; i++) {
  84                 /* We can escape by capturing this group if it's in atari. */
  85                 group_t g = s->groupids[stone_other(color)][i];
  86                 if (board_group_info(b, g).libs > 1)
  87                         continue;
  88
  89                 /* But we need to get to at least two liberties by this;
  90                  * we already have one outside liberty, or the group is
  91                  * more than 1 stone (in that case, capturing is always
  92                  * nice!). */
  93                 if (s->groupcts[S_NONE] > 0 || !group_is_onestone(b, g))
  94                         return false;
  95                 /* ...or, it's a ko stone, */
  96                 if (neighbor_count_at(b, g, color) + neighbor_count_at(b, g, S_OFFBOARD) == 3) {
  97                         /* and we don't have a group to save: then, just taking
  98                          * single stone means snapback! */
  99                         if (!s->friend_has_no_libs)
 100                                 return false;
 101                 }
 102                 /* ...or, we already have one indirect liberty provided
 103                  * by another group. */
 104                 if (s->needs_more_lib || (can_capture && can_capture != g))
 105                         return false;
 106                 can_capture = g;
 107
 108         }
 109
 110         if (DEBUGL(6))
 111                 fprintf(stderr, "no cap group\n");
 112
 113         if (!s->needs_more_lib && !can_capture && !s->groupcts[S_NONE]) {
 114                 /* We have no hope for more fancy tactics - this move is simply
 115                  * a suicide, not even a self-atari. */
 116                 if (DEBUGL(6))
 117                         fprintf(stderr, "suicide\n");
 118                 return true;
 119         }
 120         /* XXX: I wonder if it makes sense to continue if we actually
 121          * just !s->needs_more_lib. */
 122
 123         return -1;
 124 }
 125
 126 static int
 127 setup_nakade_or_snapback(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
 128 {
 129         /* There is another possibility - we can self-atari if it is
 130          * a nakade: we put an enemy group in atari from the inside. */
 131         /* This branch also allows eyes falsification:
 132          * O O O . .  (This is different from throw-in to false eye
 133          * X X O O .  checked below in that there is no X stone at the
 134          * X . X O .  right of the star point in this diagram.)
 135          * X X X O O
 136          * X O * . . */
 137         /* TODO: Allow to only nakade if the created shape is dead
 138          * (http://senseis.xmp.net/?Nakade). */
 139
 140         /* This branch also covers snapback, which is kind of special
 141          * nakade case. ;-) */
 142         for (int i = 0; i < s->groupcts[stone_other(color)]; i++) {
 143                 group_t g = s->groupids[stone_other(color)][i];
 144                 if (board_group_info(b, g).libs != 2)
 145                         goto next_group;
 146                 /* Simple check not to re-examine the same group. */
 147                 if (i > 0 && s->groupids[stone_other(color)][i] == s->groupids[stone_other(color)][i - 1])
 148                         continue;
 149
 150                 /* We must make sure the other liberty of that group:
 151                  * (i) is an internal liberty
 152                  * (ii) filling it to capture our group will not gain
 153                  * safety */
 154
 155                 /* Let's look at the other liberty neighbors: */
 156                 int lib2 = board_group_info(b, g).lib[0];
 157                 if (lib2 == to) lib2 = board_group_info(b, g).lib[1];
 158                 foreach_neighbor(b, lib2, {
 159                         /* This neighbor of course does not contribute
 160                          * anything to the enemy. */
 161                         if (board_at(b, c) == S_OFFBOARD)
 162                                 continue;
 163
 164                         /* If the other liberty has empty neighbor,
 165                          * it must be the original liberty; otherwise,
 166                          * since the whole group has only 2 liberties,
 167                          * the other liberty may not be internal and
 168                          * we are nakade'ing eyeless group from outside,
 169                          * which is stupid. */
 170                         if (board_at(b, c) == S_NONE) {
 171                                 if (c == to)
 172                                         continue;
 173                                 else
 174                                         goto next_group;
 175                         }
 176
 177                         int g2 = group_at(b, c);
 178                         /* If the neighbor is of our color, it must
 179                          * be our group; if it is a different group,
 180                          * it must not be in atari. */
 181                         /* X X X X  We will not allow play on 'a',
 182                          * X X a X  because 'b' would capture two
 183                          * X O b X  different groups, forming two
 184                          * X X X X  eyes. */
 185                         if (board_at(b, c) == color) {
 186                                 if (board_group_info(b, group_at(b, c)).libs > 1)
 187                                         continue;
 188                                 /* Our group == one of the groups
 189                                  * we (@to) are connected to. */
 190                                 int j;
 191                                 for (j = 0; j < 4; j++)
 192                                         if (s->groupids[color][j] == g2)
 193                                                 break;
 194                                 if (j == 4)
 195                                         goto next_group;
 196                                 continue;
 197                         }
 198
 199                         /* The neighbor is enemy color. It's ok if
 200                          * it's still the same group or this is its
 201                          * only liberty. */
 202                         if (g == g2 || board_group_info(b, g2).libs == 1)
 203                                 continue;
 204                         /* Otherwise, it must have the exact same
 205                          * liberties as the original enemy group. */
 206                         if (board_group_info(b, g2).libs == 2
 207                             && (board_group_info(b, g2).lib[0] == to
 208                                 || board_group_info(b, g2).lib[1] == to))
 209                                 continue;
 210
 211                         goto next_group;
 212                 });
 213
 214                 /* Now, we must distinguish between nakade and eye
 215                  * falsification; we must not falsify an eye by more
 216                  * than two stones. */
 217                 if (s->groupcts[color] < 1 ||
 218                     (s->groupcts[color] == 1 && group_is_onestone(b, s->groupids[color][0])))
 219                         return false;
 220
 221                 /* We would create more than 2-stone group; in that
 222                  * case, the liberty of our result must be lib2,
 223                  * indicating this really is a nakade. */
 224                 for (int j = 0; j < s->groupcts[color]; j++) {
 225                         group_t g2 = s->groupids[color][j];
 226                         assert(board_group_info(b, g2).libs <= 2);
 227                         if (board_group_info(b, g2).libs == 2) {
 228                                 if (board_group_info(b, g2).lib[0] != lib2
 229                                     && board_group_info(b, g2).lib[1] != lib2)
 230                                         goto next_group;
 231                         } else {
 232                                 assert(board_group_info(b, g2).lib[0] == to);
 233                         }
 234                 }
 235
 236                 return false;
 237 next_group:
 238                 /* Unless we are dealing with snapback setup, we don't need to look
 239                  * further. */
 240                 if (!s->groupcts[color])
 241                         return -1;
 242         }
 243
 244         return -1;
 245 }
 246
 247 static int
 248 check_throwin(struct board *b, enum stone color, coord_t to, struct selfatari_state *s)
 249 {
 250         /* We can be throwing-in to false eye:
 251          * X X X O X X X O X X X X X
 252          * X . * X * O . X * O O . X
 253          * # # # # # # # # # # # # # */
 254         /* We cannot sensibly throw-in into a corner. */
 255         if (neighbor_count_at(b, to, S_OFFBOARD) < 2
 256             && neighbor_count_at(b, to, stone_other(color))
 257                + neighbor_count_at(b, to, S_OFFBOARD) == 3
 258             && board_is_false_eyelike(b, &to, stone_other(color))) {
 259                 assert(s->groupcts[color] <= 1);
 260                 /* Single-stone throw-in may be ok... */
 261                 if (s->groupcts[color] == 0) {
 262                         /* O X .  There is one problem - when it's
 263                          * . * X  actually not a throw-in!
 264                          * # # #  */
 265                         foreach_neighbor(b, to, {
 266                                 if (board_at(b, c) == S_NONE) {
 267                                         /* Is the empty neighbor an escape path? */
 268                                         /* (Note that one S_NONE neighbor is already @to.) */
 269                                         if (neighbor_count_at(b, c, stone_other(color))
 270                                             + neighbor_count_at(b, c, S_OFFBOARD) < 2)
 271                                                 return -1;
 272                                 }
 273                         });
 274                         return false;
 275                 }
 276
 277                 /* Multi-stone throwin...? */
 278                 assert(s->groupcts[color] == 1);
 279                 group_t g = s->groupids[color][0];
 280
 281                 assert(board_group_info(b, g).libs <= 2);
 282                 /* Suicide is definitely NOT ok, no matter what else
 283                  * we could test. */
 284                 if (board_group_info(b, g).libs == 1)
 285                         return true;
 286
 287                 /* In that case, we must be connected to at most one stone,
 288                  * or throwin will not destroy any eyes. */
 289                 if (group_is_onestone(b, g))
 290                         return false;
 291         }
 292         return -1;
 293 }
 294
 295 bool
 296 is_bad_selfatari_slow(struct board *b, enum stone color, coord_t to)
 297 {
 298         if (DEBUGL(5))
 299                 fprintf(stderr, "sar check %s %s\n", stone2str(color), coord2sstr(to, b));
 300         /* Assess if we actually gain any liberties by this escape route.
 301          * Note that this is not 100% as we cannot check whether we are
 302          * connecting out or just to ourselves. */
 303
 304         struct selfatari_state s;
 305         memset(&s, 0, sizeof(s));
 306         int d;
 307
 308         foreach_neighbor(b, to, {
 309                 enum stone color = board_at(b, c);
 310                 s.groupids[color][s.groupcts[color]++] = group_at(b, c);
 311         });
 312
 313         /* We have shortage of liberties; that's the point. */
 314         assert(s.groupcts[S_NONE] <= 1);
 315
 316         d = examine_friendly_groups(b, color, to, &s);
 317         if (d >= 0)
 318                 return d;
 319
 320         if (DEBUGL(6))
 321                 fprintf(stderr, "no friendly group\n");
 322
 323         d = examine_enemy_groups(b, color, to, &s);
 324         if (d >= 0)
 325                 return d;
 326
 327         if (DEBUGL(6))
 328                 fprintf(stderr, "no escape\n");
 329
 330         d = setup_nakade_or_snapback(b, color, to, &s);
 331         if (d >= 0)
 332                 return d;
 333
 334         if (DEBUGL(6))
 335                 fprintf(stderr, "no nakade group\n");
 336
 337         d = check_throwin(b, color, to, &s);
 338         if (d >= 0)
 339                 return d;
 340
 341         if (DEBUGL(6))
 342                 fprintf(stderr, "no throw-in group\n");
 343
 344         /* No way to pull out, no way to connect out. This really
 345          * is a bad self-atari! */
 346         return true;
 347 }
 348
 349
 350 /* Is this ladder breaker friendly for the one who catches ladder. */
 351 static bool
 352 ladder_catcher(struct board *b, int x, int y, enum stone laddered)
 353 {
 354         enum stone breaker = board_atxy(b, x, y);
 355         return breaker == stone_other(laddered) || breaker == S_OFFBOARD;
 356 }
 357
 358 bool
 359 is_border_ladder(struct board *b, coord_t coord, enum stone lcolor)
 360 {
 361         int x = coord_x(coord, b), y = coord_y(coord, b);
 362
 363         if (DEBUGL(5))
 364                 fprintf(stderr, "border ladder\n");
 365         /* Direction along border; xd is horiz. border, yd vertical. */
 366         int xd = 0, yd = 0;
 367         if (board_atxy(b, x + 1, y) == S_OFFBOARD || board_atxy(b, x - 1, y) == S_OFFBOARD)
 368                 yd = 1;
 369         else
 370                 xd = 1;
 371         /* Direction from the border; -1 is above/left, 1 is below/right. */
 372         int dd = (board_atxy(b, x + yd, y + xd) == S_OFFBOARD) ? 1 : -1;
 373         if (DEBUGL(6))
 374                 fprintf(stderr, "xd %d yd %d dd %d\n", xd, yd, dd);
 375         /* | ? ?
 376          * | . O #
 377          * | c X #
 378          * | . O #
 379          * | ? ?   */
 380         /* This is normally caught, unless we have friends both above
 381          * and below... */
 382         if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor
 383             && board_atxy(b, x - xd * 2, y - yd * 2) == lcolor)
 384                 return false;
 385         /* ...or can't block where we need because of shortage
 386          * of liberties. */
 387         int libs1 = board_group_info(b, group_atxy(b, x + xd - yd * dd, y + yd - xd * dd)).libs;
 388         int libs2 = board_group_info(b, group_atxy(b, x - xd - yd * dd, y - yd - xd * dd)).libs;
 389         if (DEBUGL(6))
 390                 fprintf(stderr, "libs1 %d libs2 %d\n", libs1, libs2);
 391         if (libs1 < 2 && libs2 < 2)
 392                 return false;
 393         if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor && libs1 < 3)
 394                 return false;
 395         if (board_atxy(b, x - xd * 2, y - yd * 2) == lcolor && libs2 < 3)
 396                 return false;
 397         return true;
 398 }
 399
 400 /* This is very trivial and gets a lot of corner cases wrong.
 401  * We need this to be just very fast. One important point is
 402  * that we sometimes might not notice a ladder but if we do,
 403  * it should always work; thus we can use this for strong
 404  * negative hinting safely. */
 405 bool
 406 is_middle_ladder(struct board *b, coord_t coord, enum stone lcolor)
 407 {
 408         int x = coord_x(coord, b), y = coord_y(coord, b);
 409
 410         /* Figure out the ladder direction */
 411         int xd, yd;
 412         xd = board_atxy(b, x + 1, y) == S_NONE ? 1 : board_atxy(b, x - 1, y) == S_NONE ? -1 : 0;
 413         yd = board_atxy(b, x, y + 1) == S_NONE ? 1 : board_atxy(b, x, y - 1) == S_NONE ? -1 : 0;
 414
 415         if (!xd || !yd) {
 416                 if (DEBUGL(5))
 417                         fprintf(stderr, "no ladder, too little space; self-atari?\n");
 418                 return false;
 419         }
 420
 421         /* For given (xd,yd), we have two possibilities where to move
 422          * next. Consider (-1,-1):
 423          * n X .   n c X
 424          * c O X   X O #
 425          * X # #   . X #
 426          */
 427         bool horiz_first = ladder_catcher(b, x, y - yd, lcolor); // left case
 428         bool vert_first = ladder_catcher(b, x - xd, y, lcolor); // right case
 429
 430         /* We don't have to look at the other 'X' in the position - if it
 431          * wouldn't be there, the group wouldn't be in atari. */
 432
 433         /* We do only tight ladders, not loose ladders. Furthermore,
 434          * the ladders need to be simple:
 435          * . X .             . . X
 436          * c O X supported   . c O unsupported
 437          * X # #             X O #
 438          */
 439         assert(!(horiz_first && vert_first));
 440         if (!horiz_first && !vert_first) {
 441                 /* TODO: In case of basic non-simple ladder, play out both variants. */
 442                 if (DEBUGL(5))
 443                         fprintf(stderr, "non-simple ladder\n");
 444                 return false;
 445         }
 446
 447         /* We do that below for further moves, but now initially - check
 448          * that at 'c', we aren't putting any of the catching stones
 449          * in atari. */
 450 #if 1 // this might be broken?
 451 #define check_catcher_danger(b, x_, y_) do { \
 452         if (board_atxy(b, (x_), (y_)) != S_OFFBOARD \
 453             && board_group_info(b, group_atxy(b, (x_), (y_))).libs <= 2) { \
 454                 if (DEBUGL(5)) \
 455                         fprintf(stderr, "ladder failed - atari at the beginning\n"); \
 456                 return false; \
 457         } } while (0)
 458
 459         if (horiz_first) {
 460                 check_catcher_danger(b, x, y - yd);
 461                 check_catcher_danger(b, x - xd, y + yd);
 462         } else {
 463                 check_catcher_danger(b, x - xd, y);
 464                 check_catcher_danger(b, x + xd, y - yd);
 465         }
 466 #undef check_catcher_danger
 467 #endif
 468
 469 #define ladder_check(xd1_, yd1_, xd2_, yd2_, xd3_, yd3_)        \
 470         if (board_atxy(b, x, y) != S_NONE) { \
 471                 /* Did we hit a stone when playing out ladder? */ \
 472                 if (ladder_catcher(b, x, y, lcolor)) \
 473                         return true; /* ladder works */ \
 474                 if (board_group_info(b, group_atxy(b, x, y)).lib[0] > 0) \
 475                         return false; /* friend that's not in atari himself */ \
 476         } else { \
 477                 /* No. So we are at new position. \
 478                  * We need to check indirect ladder breakers. */ \
 479                 /* . 2 x 3 . \
 480                  * . x o O 1 <- only at O we can check for o at 2 \
 481                  * x o o x .    otherwise x at O would be still deadly \
 482                  * o o x . . \
 483                  * We check for o and x at 1, these are vital. \
 484                  * We check only for o at 2; x at 2 would mean we \
 485                  * need to fork (one step earlier). */ \
 486                 coord_t c1 = coord_xy(b, x + (xd1_), y + (yd1_)); \
 487                 enum stone s1 = board_at(b, c1); \
 488                 if (s1 == lcolor) return false; \
 489                 if (s1 == stone_other(lcolor)) { \
 490                         /* One more thing - if the position at 3 is \
 491                          * friendly and safe, we escaped anyway! */ \
 492                         coord_t c3 = coord_xy(b, x + (xd3_), y + (yd3_)); \
 493                         return board_at(b, c3) != lcolor \
 494                                || board_group_info(b, group_at(b, c3)).libs < 2; \
 495                 } \
 496                 enum stone s2 = board_atxy(b, x + (xd2_), y + (yd2_)); \
 497                 if (s2 == lcolor) return false; \
 498                 /* Then, can X actually "play" 1 in the ladder? */ \
 499                 if (neighbor_count_at(b, c1, lcolor) + neighbor_count_at(b, c1, S_OFFBOARD) >= 2) \
 500                         return false; /* It would be self-atari! */ \
 501         }
 502 #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)
 503 #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)
 504
 505         if (ladder_catcher(b, x - xd, y, lcolor))
 506                 ladder_horiz;
 507         do {
 508                 ladder_vert;
 509                 ladder_horiz;
 510         } while (1);
 511 }
 512
 513
 514 bool
 515 board_stone_radar(struct board *b, coord_t coord, int distance)
 516 {
 517         int bounds[4] = {
 518                 coord_x(coord, b) - distance,
 519                 coord_y(coord, b) - distance,
 520                 coord_x(coord, b) + distance,
 521                 coord_y(coord, b) + distance
 522         };
 523         for (int i = 0; i < 4; i++)
 524                 if (bounds[i] < 1)
 525                         bounds[i] = 1;
 526                 else if (bounds[i] > board_size(b) - 2)
 527                         bounds[i] = board_size(b) - 2;
 528         for (int x = bounds[0]; x <= bounds[2]; x++)
 529                 for (int y = bounds[1]; y <= bounds[3]; y++)
 530                         if (board_atxy(b, x, y) != S_NONE) {
 531                                 /* fprintf(stderr, "radar %d,%d,%d: %d,%d (%d)\n",
 532                                         coord_x(coord, b), coord_y(coord, b),
 533                                         distance, x, y, board_atxy(b, x, y)); */
 534                                 return true;
 535                         }
 536         return false;
 537 }
 538
 539
 540 void
 541 cfg_distances(struct board *b, coord_t start, int *distances, int maxdist)
 542 {
 543         /* Queue for d+1 spots; no two spots of the same group
 544          * should appear in the queue. */
 545 #define qinc(x) (x = ((x + 1) >= board_size2(b) ? ((x) + 1 - board_size2(b)) : (x) + 1))
 546         coord_t queue[board_size2(b)]; int qstart = 0, qstop = 0;
 547
 548         foreach_point(b) {
 549                 distances[c] = board_at(b, c) == S_OFFBOARD ? maxdist + 1 : -1;
 550         } foreach_point_end;
 551
 552         queue[qstop++] = start;
 553         for (int d = 0; d <= maxdist; d++) {
 554                 /* Process queued moves, while setting the queue
 555                  * for new wave. */
 556                 int qa = qstart, qb = qstop;
 557                 qstart = qstop;
 558                 for (int q = qa; q < qb; qinc(q)) {
 559 #define cfg_one(coord, grp) do {\
 560         distances[coord] = d; \
 561         foreach_neighbor (b, coord, { \
 562                 if (distances[c] < 0 && (!grp || group_at(b, coord) != grp)) { \
 563                         queue[qstop] = c; \
 564                         qinc(qstop); \
 565                 } \
 566         }); \
 567 } while (0)
 568                         coord_t cq = queue[q];
 569                         if (distances[cq] >= 0)
 570                                 continue; /* We already looked here. */
 571                         if (board_at(b, cq) == S_NONE) {
 572                                 cfg_one(cq, 0);
 573                         } else {
 574                                 group_t g = group_at(b, cq);
 575                                 foreach_in_group(b, g) {
 576                                         cfg_one(c, g);
 577                                 } foreach_in_group_end;
 578                         }
 579 #undef cfg_one
 580                 }
 581         }
 582
 583         foreach_point(b) {
 584                 if (distances[c] < 0)
 585                         distances[c] = maxdist + 1;
 586         } foreach_point_end;
 587 }
 588
 589
 590 float
 591 board_effective_handicap(struct board *b, int first_move_value)
 592 {
 593         assert(b->handicap != 1);
 594         return (b->handicap ? b->handicap : 1) * first_move_value + 0.5 - b->komi;
 595 }
 596
 597
 598 bool
 599 pass_is_safe(struct board *b, enum stone color, struct move_queue *mq)
 600 {
 601         float score = board_official_score(b, mq);
 602         if (color == S_BLACK)
 603                 score = -score;
 604         //fprintf(stderr, "%d score %f\n", color, score);
 605         return (score > 0);
 606 }
 607
 608
 609 /* On average 25% of points remain empty at the end of a game */
 610 #define EXPECTED_FINAL_EMPTY_PERCENT 25
 611
 612 /* Returns estimated number of remaining moves for one player until end of game. */
 613 int
 614 board_estimated_moves_left(struct board *b)
 615 {
 616         int total_points = (board_size(b)-2)*(board_size(b)-2);
 617         int moves_left = (b->flen - total_points*EXPECTED_FINAL_EMPTY_PERCENT/100)/2;
 618         return moves_left > MIN_MOVES_LEFT ? moves_left : MIN_MOVES_LEFT;
 619 }