mq.h

   1 #ifndef PACHI_MQ_H
   2 #define PACHI_MQ_H
   3
   4 /* Move queues; in fact, they are more like move lists, usually used
   5  * to accumulate equally good move candidates, then choosing from them
   6  * randomly. But they are also used to juggle group lists (using the
   7  * fact that coord_t == group_t). */
   8
   9 #include "move.h"
  10 #include "random.h"
  11
  12 #define MQL 512 /* XXX: On larger board this might not be enough. */
  13 struct move_queue {
  14         unsigned int moves;
  15         coord_t move[MQL];
  16         /* Each move can have an optional tag or set of tags.
  17          * The usage of these is user-dependent. */
  18         unsigned char tag[MQL];
  19 };
  20
  21 /* Pick a random move from the queue. */
  22 static coord_t mq_pick(struct move_queue *q);
  23
  24 /* Add a move to the queue. */
  25 static void mq_add(struct move_queue *q, coord_t c, unsigned char tag);
  26
  27 /* Is move in the queue ? */
  28 static bool mq_has(struct move_queue *q, coord_t c);
  29
  30 /* Cat two queues together. */
  31 static void mq_append(struct move_queue *qd, struct move_queue *qs);
  32
  33 /* Check if the last move in queue is not a dupe, and remove it
  34  * in that case. */
  35 static void mq_nodup(struct move_queue *q);
  36
  37 /* Print queue contents on stderr. */
  38 static void mq_print(struct move_queue *q, struct board *b, char *label);
  39
  40
  41 /* Variations of the above that allow move weighting. */
  42 /* XXX: The "kinds of move queue" issue (it's even worse in some other
  43  * branches) is one of the few good arguments for C++ in Pachi...
  44  * At least rewrite it to be less hacky and maybe make a move_gamma_queue
  45  * that encapsulates move_queue. */
  46
  47 static coord_t mq_gamma_pick(struct move_queue *q, fixp_t *gammas);
  48 static void mq_gamma_add(struct move_queue *q, fixp_t *gammas, coord_t c, double gamma, unsigned char tag);
  49 static void mq_gamma_print(struct move_queue *q, fixp_t *gammas, struct board *b, char *label);
  50
  51
  52 static inline coord_t
  53 mq_pick(struct move_queue *q)
  54 {
  55         return q->moves ? q->move[fast_random(q->moves)] : pass;
  56 }
  57
  58 static inline void
  59 mq_add(struct move_queue *q, coord_t c, unsigned char tag)
  60 {
  61         assert(q->moves < MQL);
  62         q->tag[q->moves] = tag;
  63         q->move[q->moves++] = c;
  64 }
  65
  66 static inline bool
  67 mq_has(struct move_queue *q, coord_t c)
  68 {
  69         for (unsigned int i = 0; i < q->moves; i++)
  70                 if (q->move[i] == c)
  71                         return true;
  72         return false;
  73 }
  74
  75 static inline void
  76 mq_append(struct move_queue *qd, struct move_queue *qs)
  77 {
  78         assert(qd->moves + qs->moves < MQL);
  79         memcpy(&qd->tag[qd->moves], qs->tag, qs->moves * sizeof(*qs->tag));
  80         memcpy(&qd->move[qd->moves], qs->move, qs->moves * sizeof(*qs->move));
  81         qd->moves += qs->moves;
  82 }
  83
  84 static inline void
  85 mq_nodup(struct move_queue *q)
  86 {
  87         for (unsigned int i = 1; i < 4; i++) {
  88                 if (q->moves <= i)
  89                         return;
  90                 if (q->move[q->moves - 1 - i] == q->move[q->moves - 1]) {
  91                         q->tag[q->moves - 1 - i] |= q->tag[q->moves - 1];
  92                         q->moves--;
  93                         return;
  94                 }
  95         }
  96 }
  97
  98 static inline void
  99 mq_print(struct move_queue *q, struct board *b, char *label)
 100 {
 101         fprintf(stderr, "%s candidate moves: ", label);
 102         for (unsigned int i = 0; i < q->moves; i++) {
 103                 fprintf(stderr, "%s ", coord2sstr(q->move[i], b));
 104         }
 105         fprintf(stderr, "\n");
 106 }
 107
 108 static inline coord_t
 109 mq_gamma_pick(struct move_queue *q, fixp_t *gammas)
 110 {
 111         if (!q->moves)
 112                 return pass;
 113         fixp_t total = 0;
 114         for (unsigned int i = 0; i < q->moves; i++) {
 115                 total += gammas[i];
 116         }
 117         if (!total)
 118                 return pass;
 119         fixp_t stab = fast_irandom(total);
 120         for (unsigned int i = 0; i < q->moves; i++) {
 121                 if (stab < gammas[i])
 122                         return q->move[i];
 123                 stab -= gammas[i];
 124         }
 125         assert(0);
 126         return pass;
 127 }
 128
 129 static inline void
 130 mq_gamma_add(struct move_queue *q, fixp_t *gammas, coord_t c, double gamma, unsigned char tag)
 131 {
 132         mq_add(q, c, tag);
 133         gammas[q->moves - 1] = double_to_fixp(gamma);
 134 }
 135
 136 static inline void
 137 mq_gamma_print(struct move_queue *q, fixp_t *gammas, struct board *b, char *label)
 138 {
 139         fprintf(stderr, "%s candidate moves: ", label);
 140         for (unsigned int i = 0; i < q->moves; i++) {
 141                 fprintf(stderr, "%s(%.3f) ", coord2sstr(q->move[i], b), fixp_to_double(gammas[i]));
 142         }
 143         fprintf(stderr, "\n");
 144 }
 145
 146 #endif