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