stats.h

   1 #ifndef PACHI_STATS_H
   2 #define PACHI_STATS_H
   3
   4 #include <math.h>
   5
   6 /* Move statistics; we track how good value each move has. */
   7 /* These operations are supposed to be atomic - reasonably
   8  * safe to perform by multiple threads at once on the same stats.
   9  * What this means in practice is that perhaps the value will get
  10  * slightly wrong, but not drastically corrupted. */
  11
  12 struct move_stats {
  13         int playouts; // # of playouts
  14         floating_t value; // BLACK wins/playouts
  15 };
  16
  17 /* Add a result to the stats. */
  18 static void stats_add_result(struct move_stats *s, floating_t result, int playouts);
  19 static void stats_add_result_decay(struct move_stats *s, floating_t result, floating_t decay);
  20
  21 /* Remove a result from the stats. */
  22 static void stats_rm_result(struct move_stats *s, floating_t result, int playouts);
  23
  24 /* Merge two stats together. THIS IS NOT ATOMIC! */
  25 static void stats_merge(struct move_stats *dest, struct move_stats *src);
  26
  27 /* Reverse stats parity. */
  28 static void stats_reverse_parity(struct move_stats *s);
  29
  30
  31 /* We actually do the atomicity in a pretty hackish way - we simply
  32  * rely on the fact that int,floating_t operations should be atomic with
  33  * reasonable compilers (gcc) on reasonable architectures (i386,
  34  * x86_64). */
  35 /* There is a write order dependency - when we bump the playouts,
  36  * our value must be already correct, otherwise the node will receive
  37  * invalid evaluation if that's made in parallel, esp. when
  38  * current s->playouts is zero. */
  39
  40 static inline void
  41 stats_add_result(struct move_stats *s, floating_t result, int playouts)
  42 {
  43         int s_playouts = s->playouts;
  44         floating_t s_value = s->value;
  45         /* Force the load, another thread can work on the
  46          * values in parallel. */
  47         __sync_synchronize(); /* full memory barrier */
  48
  49         s_playouts += playouts;
  50         s_value += (result - s_value) * playouts / s_playouts;
  51
  52         /* We rely on the fact that these two assignments are atomic. */
  53         s->value = s_value;
  54         __sync_synchronize(); /* full memory barrier */
  55         s->playouts = s_playouts;
  56 }
  57
  58 static inline void
  59 stats_add_result_decay(struct move_stats *s, floating_t result, floating_t decay)
  60 {
  61         int s_playouts = s->playouts;
  62         floating_t s_value = s->value;
  63         /* Force the load, another thread can work on the
  64          * values in parallel. */
  65         __sync_synchronize(); /* full memory barrier */
  66
  67         /* We assume iterative decay, yielding a geometric series. */
  68         s_playouts++;
  69         floating_t d_playouts = fabs(decay - 1) < 0.00001 ? s_playouts : (1 - pow(decay, s_playouts)) / (1 - decay);
  70         s_value += (result - s_value) / d_playouts;
  71
  72         /* We rely on the fact that these two assignments are atomic. */
  73         s->value = s_value;
  74         __sync_synchronize(); /* full memory barrier */
  75         s->playouts = s_playouts;
  76 }
  77
  78 static inline void
  79 stats_rm_result(struct move_stats *s, floating_t result, int playouts)
  80 {
  81         if (s->playouts > playouts) {
  82                 int s_playouts = s->playouts;
  83                 floating_t s_value = s->value;
  84                 /* Force the load, another thread can work on the
  85                  * values in parallel. */
  86                 __sync_synchronize(); /* full memory barrier */
  87
  88                 s_playouts -= playouts;
  89                 s_value += (s_value - result) * playouts / s_playouts;
  90
  91                 /* We rely on the fact that these two assignments are atomic. */
  92                 s->value = s_value;
  93                 __sync_synchronize(); /* full memory barrier */
  94                 s->playouts = s_playouts;
  95
  96         } else {
  97                 /* We don't touch the value, since in parallel, another
  98                  * thread can be adding a result, thus raising the
  99                  * playouts count after we zero the value. Instead,
 100                  * leaving the value as is with zero playouts should
 101                  * not break anything. */
 102                 s->playouts = 0;
 103         }
 104 }
 105
 106 static inline void
 107 stats_merge(struct move_stats *dest, struct move_stats *src)
 108 {
 109         /* In a sense, this is non-atomic version of stats_add_result(). */
 110         if (src->playouts) {
 111                 dest->playouts += src->playouts;
 112                 dest->value += (src->value - dest->value) * src->playouts / dest->playouts;
 113         }
 114 }
 115
 116 static inline void
 117 stats_reverse_parity(struct move_stats *s)
 118 {
 119         s->value = 1 - s->value;
 120 }
 121
 122 #endif