tactics/goals.c

   1 #include <assert.h>
   2 #include <limits.h>
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5
   6 #include "board.h"
   7 #include "debug.h"
   8 #include "libmap.h"
   9 #include "move.h"
  10 #include "tactics/goals.h"
  11 #include "tactics/util.h"
  12
  13
  14 struct libmap_config libmap_config = {
  15         .pick_mode = LMP_THRESHOLD,
  16         .pick_threshold = 0.7,
  17         .pick_epsilon = 10,
  18
  19         .explore_p = 0.2,
  20         .prior = { .value = 0.5, .playouts = 1 },
  21         .tenuki_prior = { .value = 0.4, .playouts = 1 },
  22
  23         .mq_merge_groups = true,
  24         .counterattack = LMC_DEFENSE | LMC_ATTACK | LMC_DEFENSE_ATTACK,
  25         .eval = LME_LVALUE,
  26 };
  27
  28 void
  29 libmap_setup(char *arg)
  30 {
  31         if (!arg)
  32                 return;
  33
  34         char *optspec, *next = arg;
  35         while (*next) {
  36                 optspec = next;
  37                 next += strcspn(next, ":");
  38                 if (*next) { *next++ = 0; } else { *next = 0; }
  39
  40                 char *optname = optspec;
  41                 char *optval = strchr(optspec, '=');
  42                 if (optval) *optval++ = 0;
  43
  44                 if (!strcasecmp(optname, "pick_mode") && optval) {
  45                         if (!strcasecmp(optval, "threshold")) {
  46                                 libmap_config.pick_mode = LMP_THRESHOLD;
  47                         } else if (!strcasecmp(optval, "ucb")) {
  48                                 libmap_config.pick_mode = LMP_UCB;
  49                         } else {
  50                                 fprintf(stderr, "Invalid libmap:pick_mode value %s\n", optval);
  51                                 exit(1);
  52                         }
  53
  54                 } else if (!strcasecmp(optname, "pick_threshold") && optval) {
  55                         libmap_config.pick_threshold = atof(optval);
  56                 } else if (!strcasecmp(optname, "pick_epsilon") && optval) {
  57                         libmap_config.pick_epsilon = atoi(optval);
  58                 } else if (!strcasecmp(optname, "avoid_bad")) {
  59                         libmap_config.avoid_bad = !optval || atoi(optval);
  60
  61                 } else if (!strcasecmp(optname, "explore_p") && optval) {
  62                         libmap_config.explore_p = atof(optval);
  63                 } else if (!strcasecmp(optname, "prior") && optval && strchr(optval, 'x')) {
  64                         libmap_config.prior.value = atof(optval);
  65                         optval += strcspn(optval, "x") + 1;
  66                         libmap_config.prior.playouts = atoi(optval);
  67                 } else if (!strcasecmp(optname, "tenuki_prior") && optval && strchr(optval, 'x')) {
  68                         libmap_config.tenuki_prior.value = atof(optval);
  69                         optval += strcspn(optval, "x") + 1;
  70                         libmap_config.tenuki_prior.playouts = atoi(optval);
  71
  72                 } else if (!strcasecmp(optname, "mq_merge_groups")) {
  73                         libmap_config.mq_merge_groups = !optval || atoi(optval);
  74                 } else if (!strcasecmp(optname, "counterattack") && optval) {
  75                         /* Combination of letters d, a, x (both), these kinds
  76                          * of hashes are going to be recorded. */
  77                         /* Note that using multiple letters makes no sense
  78                          * if mq_merge_groups is set. */
  79                         libmap_config.counterattack = 0;
  80                         if (strchr(optval, 'd'))
  81                                 libmap_config.counterattack |= LMC_DEFENSE;
  82                         if (strchr(optval, 'a'))
  83                                 libmap_config.counterattack |= LMC_ATTACK;
  84                         if (strchr(optval, 'x'))
  85                                 libmap_config.counterattack |= LMC_DEFENSE_ATTACK;
  86                 } else if (!strcasecmp(optname, "eval") && optval) {
  87                         if (!strcasecmp(optval, "local")) {
  88                                 libmap_config.eval = LME_LOCAL;
  89                         } else if (!strcasecmp(optval, "lvalue")) {
  90                                 libmap_config.eval = LME_LVALUE;
  91                         } else if (!strcasecmp(optval, "global")) {
  92                                 libmap_config.eval = LME_GLOBAL;
  93                         } else {
  94                                 fprintf(stderr, "Invalid libmap:eval value %s\n", optval);
  95                                 exit(1);
  96                         }
  97                 } else if (!strcasecmp(optname, "tenuki")) {
  98                         libmap_config.tenuki = !optval || atoi(optval);
  99                 } else {
 100                         fprintf(stderr, "Invalid libmap argument %s or missing value\n", optname);
 101                         exit(1);
 102                 }
 103         }
 104 }
 105
 106
 107 struct libmap_hash *
 108 libmap_init(struct board *b)
 109 {
 110         struct libmap_hash *lm = calloc2(1, sizeof(*lm));
 111         lm->b = b;
 112         b->libmap = lm;
 113         lm->refcount = 1;
 114         return lm;
 115 }
 116
 117 void
 118 libmap_put(struct libmap_hash *lm)
 119 {
 120         if (__sync_sub_and_fetch(&lm->refcount, 1) > 0)
 121                 return;
 122         free(lm);
 123 }
 124
 125 void
 126 libmap_queue_process(struct libmap_hash *lm, struct libmap_mq *lmqueue, struct board *b, enum stone winner)
 127 {
 128         assert(lmqueue->mq.moves <= MQL);
 129         for (unsigned int i = 0; i < lmqueue->mq.moves; i++) {
 130                 struct libmap_group *g = &lmqueue->group[i];
 131                 struct move m = { .coord = lmqueue->mq.move[i], .color = lmqueue->color[i] };
 132                 floating_t val;
 133                 if (libmap_config.eval == LME_LOCAL || libmap_config.eval == LME_LVALUE) {
 134                         val = board_local_value(libmap_config.eval == LME_LVALUE, b, g->group, g->goal);
 135
 136                 } else { assert(libmap_config.eval == LME_GLOBAL);
 137                         val = winner == g->goal ? 1.0 : 0.0;
 138                 }
 139                 libmap_add_result(lm, g->hash, m, val, 1);
 140         }
 141         lmqueue->mq.moves = 0;
 142 }
 143
 144 void
 145 libmap_add_result(struct libmap_hash *lm, hash_t hash, struct move move,
 146                   floating_t result, int playouts)
 147 {
 148         /* If hash line is full, replacement strategy is naive - pick the
 149          * move with minimum move[0].stats.playouts; resolve each tie
 150          * randomly. */
 151         unsigned int min_playouts = INT_MAX; hash_t min_hash = hash;
 152         hash_t ih;
 153         for (ih = hash; lm->hash[ih & libmap_hash_mask].hash != hash; ih++) {
 154                 // fprintf(stderr, "%"PRIhash": check %"PRIhash" (%d)\n", hash & libmap_hash_mask, ih & libmap_hash_mask, lm->hash[ih & libmap_hash_mask].moves);
 155                 if (lm->hash[ih & libmap_hash_mask].moves == 0) {
 156                         lm->hash[ih & libmap_hash_mask].hash = hash;
 157                         break;
 158                 }
 159                 if (ih >= hash + libmap_hash_maxline) {
 160                         /* Snatch the least used bucket. */
 161                         ih = min_hash;
 162                         // fprintf(stderr, "clear %"PRIhash"\n", ih & libmap_hash_mask);
 163                         memset(&lm->hash[ih & libmap_hash_mask], 0, sizeof(lm->hash[0]));
 164                         lm->hash[ih & libmap_hash_mask].hash = hash;
 165                         break;
 166                 }
 167
 168                 /* Keep track of least used bucket. */
 169                 assert(lm->hash[ih & libmap_hash_mask].moves > 0);
 170                 unsigned int hp = lm->hash[ih & libmap_hash_mask].move[0].stats.playouts;
 171                 if (hp < min_playouts || (hp == min_playouts && fast_random(2))) {
 172                         min_playouts = hp;
 173                         min_hash = ih;
 174                 }
 175         }
 176
 177         // fprintf(stderr, "%"PRIhash": use %"PRIhash" (%d)\n", hash & libmap_hash_mask, ih & libmap_hash_mask, lm->hash[ih & libmap_hash_mask].moves);
 178         struct libmap_context *lc = &lm->hash[ih & libmap_hash_mask];
 179         lc->visits++;
 180
 181         for (int i = 0; i < lc->moves; i++) {
 182                 if (lc->move[i].move.coord == move.coord
 183                     && lc->move[i].move.color == move.color) {
 184                         stats_add_result(&lc->move[i].stats, result, playouts);
 185                         return;
 186                 }
 187         }
 188
 189         int moves = lc->moves; // to preserve atomicity
 190         if (moves >= GROUP_REFILL_LIBS) {
 191                 if (DEBUGL(5))
 192                         fprintf(stderr, "(%s) too many libs\n", coord2sstr(move.coord, lm->b));
 193                 return;
 194         }
 195         lc->move[moves].move = move;
 196         stats_add_result(&lc->move[moves].stats, result, playouts);
 197         lc->moves = ++moves;
 198 }
 199
 200 struct move_stats
 201 libmap_board_move_stats(struct libmap_hash *lm, struct board *b, struct move move)
 202 {
 203         struct move_stats tot = { .playouts = 0, .value = 0 };
 204         if (is_pass(move.coord))
 205                 return tot;
 206         assert(board_at(b, move.coord) != S_OFFBOARD);
 207
 208         neighboring_groups_list(b, board_at(b, c) == S_BLACK || board_at(b, c) == S_WHITE,
 209                         move.coord, groups, groups_n, groupsbycolor_xxunused);
 210         for (int i = 0; i < groups_n; i++) {
 211                 hash_t hash = group_to_libmap(b, groups[i]);
 212                 struct move_stats *lp = libmap_move_stats(b->libmap, hash, move);
 213                 if (!lp) continue;
 214                 stats_merge(&tot, lp);
 215         }
 216
 217         return tot;
 218 }