tactics/goals.h

   1 #ifndef PACHI_TACTICS_GOALS_H
   2 #define PACHI_TACTICS_GOALS_H
   3
   4 /* Infrastructure for libmap-based goal evaluation of moves. */
   5
   6 #include "libmap.h"
   7
   8 extern struct libmap_config {
   9         enum {
  10                 LMP_THRESHOLD,
  11                 LMP_UCB,
  12         } pick_mode;
  13
  14         /* LMP_THRESHOLD: */
  15         /* Preference for moves of tactical rating over this threshold
  16          * (...or unrated moves). */
  17         floating_t pick_threshold;
  18         /* In given percentage of cases, pick move regardless of its
  19          * tactical rating.*/
  20         int pick_epsilon;
  21         /* Whether to rather skip this heuristic altogether than play
  22          * badly performing move. */
  23         bool avoid_bad;
  24
  25         /* LMP_UCB: */
  26         /* Exploration coefficient for the bandit. */
  27         floating_t explore_p;
  28         /* Default prior for considered moves. */
  29         struct move_stats prior, tenuki_prior;
  30
  31         /* Whether to merge records for the same move taking care
  32          * of different groups within the move queue. */
  33         bool mq_merge_groups;
  34         /* When checking move X, defending group A by counter-attacking
  35          * group B, whether to use A, B or A^B as liberty map. */
  36         enum {
  37                 LMC_DEFENSE = 1,
  38                 LMC_ATTACK = 2,
  39                 LMC_DEFENSE_ATTACK = 4,
  40         } counterattack;
  41         /* Whether to evaluate based on local or global result. */
  42         enum {
  43                 LME_LOCAL,
  44                 LME_LVALUE,
  45                 LME_GLOBAL,
  46         } eval;
  47         /* Whether to also try and track tenuki moves. */
  48         bool tenuki;
  49 } libmap_config;
  50
  51 void libmap_setup(char *arg);
  52
  53
  54 /** Infrastructure for tracking moves to be confronted with the libmap hash. */
  55
  56 /* Our own version of move_queue, but including liberty maps of moves. */
  57 /* The user will usually first create a queue of tactical goals and pick
  58  * (using libmap_mq functions below), then add that one to libmap_hash's
  59  * global move queue, processed at the end of the whole playout. */
  60
  61 struct libmap_group {
  62         /* Group-relative tactical description of a move. */
  63         group_t group;
  64         hash_t hash;
  65         enum stone goal;
  66 };
  67
  68 struct libmap_mq {
  69         struct move_queue mq;
  70         enum stone color[MQL]; // complements mq.move
  71         struct libmap_group group[MQL];
  72 };
  73
  74 /* libmap_mq_pick() would be simple fast_random(mq.moves), but c.f.
  75  * libmap_queue_mqpick() below. */
  76 static void libmap_mq_add(struct libmap_mq *q, struct move m, unsigned char tag, struct libmap_group group);
  77 static void libmap_mq_nodup(struct libmap_mq *q);
  78 static void libmap_mq_print(struct libmap_mq *q, struct board *b, char *label);
  79
  80
  81 /** Global storage of all the libmap contexts encountered. */
  82
  83 struct libmap_hash {
  84         struct board *b;
  85         /* Multiple board instances may share the same libmap hash;
  86          * on board_copy(), libmap is shared by default, so that all
  87          * playouts reuse libmap of the master board. refcount keeps
  88          * track of all the libmap uses in multi-thread environment. */
  89         int refcount;
  90
  91         /* Stored statistics. */
  92         /* We store statistics in a hash table without separated chains;
  93          * if bucket is occupied, we look into the following ones,
  94          * allowing up to libmap_hash_maxline subsequent checks. */
  95         /* XXX: We mishandle hashes >= UINT64_MAX - libmap_hash_maxline. */
  96 #define libmap_hash_bits 19
  97 #define libmap_hash_size (1 << libmap_hash_bits)
  98 #define libmap_hash_mask (libmap_hash_size - 1)
  99 #define libmap_hash_maxline 32
 100         struct libmap_context hash[libmap_hash_size];
 101 };
 102
 103 /* Get a new libmap. */
 104 struct libmap_hash *libmap_init(struct board *b);
 105 /* Release libmap. Based on refcount, this will free it. */
 106 void libmap_put(struct libmap_hash *lm);
 107
 108 /* Pick a move from @q, enqueue it in lmqueue and return its coordinate. */
 109 static coord_t libmap_queue_mqpick(struct libmap_hash *lm, struct libmap_mq *lmqueue, struct libmap_mq *q);
 110 /* Record queued moves in the hashtable based on final position of b and winner's color. */
 111 void libmap_queue_process(struct libmap_hash *lm, struct libmap_mq *lmqueue, struct board *b, enum stone winner);
 112 /* Add a result to the hashed statistics. */
 113 void libmap_add_result(struct libmap_hash *lm, hash_t hash, struct move move, floating_t result, int playouts);
 114 /* Get libmap context of a given group. */
 115 static struct libmap_context *libmap_group_context(struct libmap_hash *lm, hash_t hash);
 116 /* Get statistics of particular move in given libmap structure. */
 117 static struct move_stats *libmap_move_stats(struct libmap_hash *lm, hash_t hash, struct move move);
 118 /* Get statistics of particular move on given board. */
 119 /* (Note that this is inherently imperfect as it does not take into account
 120  * counter-atari moves.) */
 121 struct move_stats libmap_board_move_stats(struct libmap_hash *lm, struct board *b, struct move move);
 122
 123
 124
 125 static inline void
 126 libmap_mq_add(struct libmap_mq *q, struct move m, unsigned char tag, struct libmap_group group)
 127 {
 128         assert(q->mq.moves < MQL);
 129         q->mq.tag[q->mq.moves] = tag;
 130         q->mq.move[q->mq.moves] = m.coord;
 131         q->color[q->mq.moves] = m.color;
 132         q->group[q->mq.moves] = group;
 133         q->mq.moves++;
 134 }
 135
 136 static inline void
 137 libmap_mq_nodup(struct libmap_mq *q)
 138 {
 139         for (unsigned int i = 1; i < 4; i++) {
 140                 if (q->mq.moves <= i)
 141                         return;
 142                 if (q->mq.move[q->mq.moves - 1 - i] == q->mq.move[q->mq.moves - 1]
 143                     && (libmap_config.mq_merge_groups
 144                         || (q->group[q->mq.moves - 1 - i].group == q->group[q->mq.moves - 1].group
 145                             && q->group[q->mq.moves - 1 - i].hash == q->group[q->mq.moves - 1].hash
 146                             && q->group[q->mq.moves - 1 - i].goal == q->group[q->mq.moves - 1].goal))) {
 147                         q->mq.tag[q->mq.moves - 1 - i] |= q->mq.tag[q->mq.moves - 1];
 148                         assert(q->color[q->mq.moves - 1 - i] == q->color[q->mq.moves - 1]);
 149                         q->mq.moves--;
 150                         return;
 151                 }
 152         }
 153 }
 154
 155 static inline void
 156 libmap_mq_print(struct libmap_mq *q, struct board *b, char *label)
 157 {
 158         fprintf(stderr, "%s candidate moves: ", label);
 159         for (unsigned int i = 0; i < q->mq.moves; i++) {
 160                 fprintf(stderr, "%s[%c:%s %"PRIhash"]", coord2sstr(q->mq.move[i], b),
 161                         /* attacker / defender */
 162                         board_at(b, q->group[i].group) == q->group[i].goal ? 'd' : 'a',
 163                         coord2sstr(q->group[i].group, b),
 164                         q->group[i].hash & libmap_hash_mask);
 165                 struct move m = { .coord = q->mq.move[i], .color = q->color[i] };
 166                 struct move_stats *ms = libmap_move_stats(b->libmap, q->group[i].hash, m);
 167                 if (ms) {
 168                         fprintf(stderr, "(%.3f/%d)", ms->value, ms->playouts);
 169                 }
 170                 fputc(' ', stderr);
 171         }
 172         fputc('\n', stderr);
 173 }
 174
 175
 176 static inline int
 177 libmap_queue_mqpick_threshold(struct libmap_hash *lm, struct libmap_mq *q)
 178 {
 179         /* Pick random move, up to a simple check - if a move has tactical
 180          * rating lower than threshold, prefer another. */
 181         int p = fast_random(q->mq.moves);
 182         if (fast_random(100) < libmap_config.pick_epsilon)
 183                 return p;
 184
 185         bool found = false;
 186         unsigned int pp = p;
 187         do {
 188                 int pm = p % q->mq.moves;
 189                 struct move m = { .coord = q->mq.move[pm], .color = q->color[pm] };
 190                 struct move_stats *ms = libmap_move_stats(lm, q->group[pm].hash, m);
 191                 if (!ms || ms->value >= libmap_config.pick_threshold) {
 192                         found = true;
 193                         break;
 194                 }
 195         } while (++p % q->mq.moves < pp);
 196         p %= q->mq.moves;
 197         if (!found && libmap_config.avoid_bad)
 198                 return -1;
 199         return p;
 200 }
 201
 202 static inline int
 203 libmap_queue_mqpick_ucb(struct libmap_hash *lm, struct libmap_mq *q)
 204 {
 205         int best_pa[BOARD_MAX_MOVES + 1], best_pn = 1;
 206         floating_t best_urgency = -9999;
 207         LM_DEBUG fprintf(stderr, "\tBandit: ");
 208
 209         for (unsigned int p = 0; p < q->mq.moves; p++) {
 210                 struct libmap_context *lc = libmap_group_context(lm, q->group[p].hash);
 211
 212                 /* TODO: Consider all moves of this group,
 213                  * not just mq contents. */
 214                 struct move m = { .coord = q->mq.move[p], .color = q->color[p] };
 215                 struct move_stats s = !is_pass(m.coord) ? libmap_config.prior : libmap_config.tenuki_prior;
 216                 int group_visits = (lc ? lc->visits : 0) + s.playouts;
 217                 struct move_stats *ms = libmap_move_stats(lm, q->group[p].hash, m);
 218                 if (ms) stats_merge(&s, ms);
 219
 220                 floating_t urgency = s.value + libmap_config.explore_p * sqrt(log(group_visits) / s.playouts);
 221                 LM_DEBUG fprintf(stderr, "%s[%.3f=%.3fx(%d/%d)] ", coord2sstr(m.coord, lm->b), urgency, s.value, group_visits, s.playouts);
 222                 if (urgency > best_urgency) {
 223                         best_pn = 1;
 224                         best_pa[0] = (int) p;
 225                         best_urgency = urgency;
 226
 227                 } else if (urgency == best_urgency) {
 228                         best_pa[best_pn++] = (int) p;
 229                 }
 230         }
 231
 232         int best_p = best_pa[fast_random(best_pn)];
 233         assert(best_p >= 0);
 234         LM_DEBUG fprintf(stderr, "\t=[%d]> %s\n", best_pn, coord2sstr(q->mq.move[best_p], lm->b));
 235         return best_p;
 236 }
 237
 238 static inline coord_t
 239 libmap_queue_mqpick(struct libmap_hash *lm, struct libmap_mq *lmqueue, struct libmap_mq *q)
 240 {
 241         if (!q->mq.moves)
 242                 return pass; // nothing to do
 243
 244         /* Create a list of groups involved in the MQ. */
 245         struct libmap_group *groups[MQL];
 246         unsigned int groups_n = 0;
 247         if (libmap_config.tenuki) {
 248                 for (unsigned int i = 0; i < q->mq.moves; i++) {
 249                         for (unsigned int j = 0; j < groups_n; j++)
 250                                 if (q->group[i].hash == groups[j]->hash)
 251                                         goto g_next_move;
 252                         groups[groups_n++] = &q->group[i];
 253 g_next_move:;
 254                 }
 255         }
 256
 257         /* Add tenuki move for each libmap group to the list of candidates. */
 258         /* XXX: Can the color vary within the queue? */
 259         if (libmap_config.tenuki) {
 260                 struct move tenuki = { .coord = pass, .color = q->color[0] };
 261                 for (unsigned int i = 0; i < groups_n; i++)
 262                         libmap_mq_add(q, tenuki, 0 /* XXX */, *groups[i]);
 263         }
 264
 265         unsigned int p = 0;
 266         if (q->mq.moves > 1) {
 267                 if (lm) {
 268                         switch (libmap_config.pick_mode) {
 269                         case LMP_THRESHOLD:
 270                                 p = libmap_queue_mqpick_threshold(lm, q);
 271                                 break;
 272                         case LMP_UCB:
 273                                 p = libmap_queue_mqpick_ucb(lm, q);
 274                                 break;
 275                         }
 276                 } else {
 277                         p = fast_random(q->mq.moves);
 278                 }
 279         }
 280         if (p < 0)
 281                 return pass;
 282
 283         if (lm) {
 284                 struct move m = { .coord = q->mq.move[p], .color = q->color[p] };
 285                 libmap_mq_add(lmqueue, m, q->mq.tag[p], q->group[p]);
 286         }
 287
 288         return q->mq.move[p];
 289 }
 290
 291 static inline struct libmap_context *
 292 libmap_group_context(struct libmap_hash *lm, hash_t hash)
 293 {
 294         hash_t ih;
 295         for (ih = hash; lm->hash[ih & libmap_hash_mask].hash != hash; ih++) {
 296                 if (lm->hash[ih & libmap_hash_mask].moves == 0)
 297                         return NULL;
 298                 if (ih >= hash + libmap_hash_maxline)
 299                         return NULL;
 300         }
 301         return &lm->hash[ih & libmap_hash_mask];
 302 }
 303
 304 static inline struct move_stats *
 305 libmap_move_stats(struct libmap_hash *lm, hash_t hash, struct move move)
 306 {
 307         struct libmap_context *lc = libmap_group_context(lm, hash);
 308         if (!lc) return NULL;
 309         for (int i = 0; i < lc->moves; i++) {
 310                 if (lc->move[i].move.coord == move.coord
 311                     && lc->move[i].move.color == move.color)
 312                         return &lc->move[i].stats;
 313         }
 314         return NULL;
 315 }
 316
 317 #endif