probdist.h

   1 #ifndef ZZGO_PROBDIST_H
   2 #define ZZGO_PROBDIST_H
   3
   4 /* Tools for picking an item according to a probability distribution. */
   5
   6 /* The probability distribution structure is designed to be once
   7  * initialized, then random items assigned a value repeatedly and
   8  * random items picked repeatedly as well. */
   9
  10 #include "move.h"
  11 #include "util.h"
  12
  13 struct board;
  14
  15 /* The interface looks a bit funny-wrapped since we used to switch
  16  * between different probdist representations. */
  17
  18 struct probdist {
  19         struct board *b;
  20         double *items; // [bsize2], [i] = P(pick==i)
  21         double *rowtotals; // [bsize], [i] = sum of items in row i
  22         double total; // sum of all items
  23 };
  24 /* Probability so small that it's same as zero; used to compensate
  25  * for probdist.total inaccuracies. */
  26 #define PROBDIST_EPSILON 0.05
  27
  28
  29 /* Declare pd_ corresponding to board b_ in the local scope. */
  30 #define probdist_alloca(pd_, b_) \
  31         double pd_ ## __pdi[board_size2(b_)]; memset(pd_ ## __pdi, 0, sizeof(pd_ ## __pdi)); \
  32         double pd_ ## __pdr[board_size(b_)]; memset(pd_ ## __pdr, 0, sizeof(pd_ ## __pdr)); \
  33         struct probdist pd_ = { .b = b_, .items = pd_ ## __pdi, .rowtotals = pd_ ## __pdr, .total = 0 };
  34
  35 /* Get the value of given item. */
  36 #define probdist_one(pd, c) ((pd)->items[c])
  37
  38 /* Get the cummulative probability value (normalizing constant). */
  39 #define probdist_total(pd) ((pd)->total)
  40
  41 /* Set the value of given item. */
  42 static void probdist_set(struct probdist *pd, coord_t c, double val);
  43
  44 /* Remove the item from the totals; this is used when you then
  45  * pass it in the ignore list to probdist_pick(). Of course you
  46  * must restore the totals afterwards. */
  47 static void probdist_mute(struct probdist *pd, coord_t c);
  48
  49 /* Pick a random item. ignore is a pass-terminated sorted array of items
  50  * that are not to be considered (and whose values are not in @total). */
  51 coord_t probdist_pick(struct probdist *pd, coord_t *ignore);
  52
  53
  54 /* Now, we do something horrible - include board.h for the inline helpers.
  55  * Yay for us. */
  56 #include "board.h"
  57
  58
  59 static inline void
  60 probdist_set(struct probdist *pd, coord_t c, double val)
  61 {
  62         /* We disable the assertions here since this is quite time-critical
  63          * part of code, and also the compiler is reluctant to inline the
  64          * functions otherwise. */
  65 #if 0
  66         assert(c >= 0 && c < board_size2(pd->b));
  67         assert(val >= 0);
  68 #endif
  69         pd->total += val - pd->items[c];
  70         pd->rowtotals[coord_y(c, pd->b)] += val - pd->items[c];
  71         pd->items[c] = val;
  72 }
  73
  74 static inline void
  75 probdist_mute(struct probdist *pd, coord_t c)
  76 {
  77         pd->total -= pd->items[c];
  78         pd->rowtotals[coord_y(c, pd->b)] -= pd->items[c];
  79 }
  80
  81 #endif