tactics/util.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/util.h"
   9
  10
  11 bool
  12 board_stone_radar(struct board *b, coord_t coord, int distance)
  13 {
  14         int bounds[4] = {
  15                 coord_x(coord, b) - distance,
  16                 coord_y(coord, b) - distance,
  17                 coord_x(coord, b) + distance,
  18                 coord_y(coord, b) + distance
  19         };
  20         for (int i = 0; i < 4; i++)
  21                 if (bounds[i] < 1)
  22                         bounds[i] = 1;
  23                 else if (bounds[i] > board_size(b) - 2)
  24                         bounds[i] = board_size(b) - 2;
  25         for (int x = bounds[0]; x <= bounds[2]; x++)
  26                 for (int y = bounds[1]; y <= bounds[3]; y++)
  27                         if (board_atxy(b, x, y) != S_NONE) {
  28                                 /* fprintf(stderr, "radar %d,%d,%d: %d,%d (%d)\n",
  29                                         coord_x(coord, b), coord_y(coord, b),
  30                                         distance, x, y, board_atxy(b, x, y)); */
  31                                 return true;
  32                         }
  33         return false;
  34 }
  35
  36
  37 void
  38 cfg_distances(struct board *b, coord_t start, int *distances, int maxdist)
  39 {
  40         /* Queue for d+1 spots; no two spots of the same group
  41          * should appear in the queue. */
  42 #define qinc(x) (x = ((x + 1) >= board_size2(b) ? ((x) + 1 - board_size2(b)) : (x) + 1))
  43         coord_t queue[board_size2(b)]; int qstart = 0, qstop = 0;
  44
  45         foreach_point(b) {
  46                 distances[c] = board_at(b, c) == S_OFFBOARD ? maxdist + 1 : -1;
  47         } foreach_point_end;
  48
  49         queue[qstop++] = start;
  50         for (int d = 0; d <= maxdist; d++) {
  51                 /* Process queued moves, while setting the queue
  52                  * for new wave. */
  53                 int qa = qstart, qb = qstop;
  54                 qstart = qstop;
  55                 for (int q = qa; q < qb; qinc(q)) {
  56 #define cfg_one(coord, grp) do {\
  57         distances[coord] = d; \
  58         foreach_neighbor (b, coord, { \
  59                 if (distances[c] < 0 && (!grp || group_at(b, coord) != grp)) { \
  60                         queue[qstop] = c; \
  61                         qinc(qstop); \
  62                 } \
  63         }); \
  64 } while (0)
  65                         coord_t cq = queue[q];
  66                         if (distances[cq] >= 0)
  67                                 continue; /* We already looked here. */
  68                         if (board_at(b, cq) == S_NONE) {
  69                                 cfg_one(cq, 0);
  70                         } else {
  71                                 group_t g = group_at(b, cq);
  72                                 foreach_in_group(b, g) {
  73                                         cfg_one(c, g);
  74                                 } foreach_in_group_end;
  75                         }
  76 #undef cfg_one
  77                 }
  78         }
  79
  80         foreach_point(b) {
  81                 if (distances[c] < 0)
  82                         distances[c] = maxdist + 1;
  83         } foreach_point_end;
  84 }
  85
  86
  87 floating_t
  88 board_effective_handicap(struct board *b, int first_move_value)
  89 {
  90         /* This can happen if the opponent passes during handicap
  91          * placing phase. */
  92         // assert(b->handicap != 1);
  93
  94         /* Always return 0 for even games, in particular if
  95          * first_move_value is set on purpose to a value different
  96          * from the correct theoretical value (2*komi). */
  97         if (!b->handicap)
  98                 return 7.5 - b->komi;
  99         return b->handicap * first_move_value + 0.5 - b->komi;
 100 }
 101
 102
 103 bool
 104 pass_is_safe(struct board *b, enum stone color, struct move_queue *mq)
 105 {
 106         floating_t score = board_official_score(b, mq);
 107         if (color == S_BLACK)
 108                 score = -score;
 109         //fprintf(stderr, "%d score %f\n", color, score);
 110         return (score >= 0);
 111 }
 112
 113
 114 /* On average 25% of points remain empty at the end of a game */
 115 #define EXPECTED_FINAL_EMPTY_PERCENT 25
 116
 117 /* Returns estimated number of remaining moves for one player until end of game. */
 118 int
 119 board_estimated_moves_left(struct board *b)
 120 {
 121         int total_points = (board_size(b)-2)*(board_size(b)-2);
 122         int moves_left = (b->flen - total_points*EXPECTED_FINAL_EMPTY_PERCENT/100)/2;
 123         return moves_left > MIN_MOVES_LEFT ? moves_left : MIN_MOVES_LEFT;
 124 }