uct/slave.c

   1 /* This is the slave specific part of the distributed engine.
   2  * See introduction at top of distributed/distributed.c.
   3  * The slave maintains a hash table of nodes received from the
   4  * master. When receiving stats the hash table gives a pointer to the
   5  * tree node to update. When sending stats we remember in the tree
   6  * what was previously sent so that only the incremental part has to
   7  * be sent.  The incremental part is smaller and can be compressed.
   8  * The compression is not yet done in this version. */
   9
  10 /* Similarly the master only sends stats increments.
  11  * They include only contributions from other slaves. */
  12
  13 /* The keys for the hash table are coordinate paths from
  14  * a root child to a given node. See distributed/distributed.h
  15  * for the encoding of a path to a 64 bit integer. */
  16
  17 /* To allow the master to select the best move, slaves also send
  18  * absolute playout counts for the best top level nodes (children
  19  * of the root node), including contributions from other slaves. */
  20
  21 /* Pass me arguments like a=b,c=d,...
  22  * Slave specific arguments (see uct.c for the other uct arguments
  23  * and distributed.c for the port arguments) :
  24  *  slave                   required to indicate slave mode
  25  *  max_nodes=MAX_NODES     default 80K
  26  *  stats_hbits=STATS_HBITS default 24. 2^stats_bits = hash table size
  27  */
  28
  29 #include <assert.h>
  30 #include <math.h>
  31 #include <stdio.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34
  35 #define MAX_VERBOSE_LOGS 1000
  36 #define DEBUG
  37
  38 #include "debug.h"
  39 #include "board.h"
  40 #include "gtp.h"
  41 #include "move.h"
  42 #include "timeinfo.h"
  43 #include "uct/internal.h"
  44 #include "uct/search.h"
  45 #include "uct/slave.h"
  46 #include "uct/tree.h"
  47
  48
  49 /* UCT infrastructure for a distributed engine slave. */
  50
  51 /* For debugging only. */
  52 static struct hash_counts h_counts;
  53 static long parent_not_found = 0;
  54 static long parent_leaf = 0;
  55 static long node_not_found = 0;
  56
  57 /* Hash table entry mapping path to node. */
  58 struct tree_hash {
  59         path_t coord_path;
  60         struct tree_node *node;
  61 };
  62
  63 void *
  64 uct_htable_alloc(int hbits)
  65 {
  66         return calloc2(1 << hbits, sizeof(struct tree_hash));
  67 }
  68
  69 /* Clear the hash table. Used only when running as slave for the distributed engine. */
  70 void uct_htable_reset(struct tree *t)
  71 {
  72         if (!t->htable) return;
  73         double start = time_now();
  74         memset(t->htable, 0, (1 << t->hbits) * sizeof(t->htable[0]));
  75         if (DEBUGL(3))
  76                 fprintf(stderr, "tree occupied %ld %.1f%% inserts %ld collisions %ld/%ld %.1f%% clear %.3fms\n"
  77                         "parent_not_found %.1f%% parent_leaf %.1f%% node_not_found %.1f%%\n",
  78                         h_counts.occupied, h_counts.occupied * 100.0 / (1 << t->hbits),
  79                         h_counts.inserts, h_counts.collisions, h_counts.lookups,
  80                         h_counts.collisions * 100.0 / (h_counts.lookups + 1),
  81                         (time_now() - start)*1000,
  82                         parent_not_found * 100.0 / (h_counts.lookups + 1),
  83                         parent_leaf * 100.0 / (h_counts.lookups + 1),
  84                         node_not_found * 100.0 / (h_counts.lookups + 1));
  85         if (DEBUG_MODE) h_counts.occupied = 0;
  86 }
  87
  88 /* Find a node given its coord path from root. Insert it in the
  89  * hash table if it is not already there.
  90  * Return the tree node, or NULL if the node cannot be found.
  91  * The tree is modified in background while this function is running.
  92  * prev is only used to optimize the tree search, given that calls to
  93  * tree_find_node are made with sorted coordinates (increasing levels
  94  * and increasing coord within a level). */
  95 static struct tree_node *
  96 tree_find_node(struct tree *t, struct incr_stats *is, struct tree_node *prev)
  97 {
  98         assert(t && t->htable);
  99         path_t path = is->coord_path;
 100         /* pass and resign must never be inserted in the hash table. */
 101         assert(path > 0);
 102
 103         int hash, parent_hash;
 104         bool found;
 105         find_hash(hash, t->htable, t->hbits, path, found, h_counts);
 106         struct tree_hash *hnode = &t->htable[hash];
 107
 108         if (DEBUGVV(7))
 109                 fprintf(stderr,
 110                         "find_node %"PRIpath" %s found %d hash %d playouts %d node %p\n", path,
 111                         path2sstr(path, t->board), found, hash, is->incr.playouts, hnode->node);
 112
 113         if (found) return hnode->node;
 114
 115         /* The master sends parents before children so the parent should
 116          * already be in the hash table. */
 117         path_t parent_p = parent_path(path, t->board);
 118         struct tree_node *parent;
 119         if (parent_p) {
 120                 find_hash(parent_hash, t->htable, t->hbits,
 121                           parent_p, found, h_counts);
 122                 parent = t->htable[parent_hash].node;
 123         } else {
 124                 parent = t->root;
 125         }
 126         struct tree_node *node = NULL;
 127         if (parent) {
 128                 /* Search for the node in parent's children. */
 129                 coord_t leaf = leaf_coord(path, t->board);
 130                 node = (prev && prev->parent == parent ? prev->sibling : parent->children);
 131                 while (node && node->coord != leaf) node = node->sibling;
 132
 133                 if (DEBUG_MODE) parent_leaf += !parent->is_expanded;
 134         } else {
 135                 if (DEBUG_MODE) parent_not_found++;
 136                 if (DEBUGVV(7))
 137                         fprintf(stderr, "parent of %"PRIpath" %s not found\n",
 138                                 path, path2sstr(path, t->board));
 139         }
 140
 141         /* Insert the node in the hash table. */
 142         hnode->node = node;
 143         if (DEBUG_MODE) h_counts.inserts++, h_counts.occupied++;
 144         if (DEBUGVV(7))
 145                 fprintf(stderr, "insert path %"PRIpath" %s hash %d playouts %d node %p\n",
 146                         path, path2sstr(path, t->board), hash, is->incr.playouts, node);
 147
 148         if (DEBUG_MODE && !node) node_not_found++;
 149
 150         hnode->coord_path = path;
 151         return node;
 152 }
 153
 154
 155 /* Read and discard any binary arguments. The number of
 156  * bytes to be skipped is given by @size in the command. */
 157 static void
 158 discard_bin_args(char *args)
 159 {
 160         char *s = strchr(args, '@');
 161         int size = 0;
 162         if (s) size = atoi(s+1);
 163         while (size) {
 164                 char buf[64*1024];
 165                 int len = sizeof(buf);
 166                 if (len > size) len = size;
 167                 len = fread(buf, 1, len, stdin);
 168                 if (len <= 0) break;
 169                 size -= len;
 170         }
 171 }
 172
 173 enum parse_code
 174 uct_notify(struct engine *e, struct board *b, int id, char *cmd, char *args, char **reply)
 175 {
 176         struct uct *u = e->data;
 177
 178         static bool board_resized = false;
 179         if (is_gamestart(cmd)) {
 180                 board_resized = true;
 181                 uct_pondering_stop(u);
 182         }
 183
 184         /* Force resending the whole command history if we are out of sync
 185          * but do it only once, not if already getting the history. */
 186         if ((move_number(id) != b->moves || !board_resized)
 187             && !reply_disabled(id) && !is_reset(cmd)) {
 188                 if (UDEBUGL(0))
 189                         fprintf(stderr, "Out of sync, id %d, move %d\n", id, b->moves);
 190                 discard_bin_args(args);
 191
 192                 static char buf[128];
 193                 snprintf(buf, sizeof(buf), "out of sync, move %d expected", b->moves);
 194                 *reply = buf;
 195                 return P_DONE_ERROR;
 196         }
 197         return reply_disabled(id) ? P_NOREPLY : P_OK;
 198 }
 199
 200
 201 /* Read the move stats sent by the master, as a binary array of
 202  * incr_stats structs. The stats come sorted by increasing coord path.
 203  * To simplify the code, we assume that master and slave have the same
 204  * architecture (store values identically).
 205  * Keep this code in sync with distributed/distributed.c:select_best_move().
 206  * Return true if ok, false if error. */
 207 static bool
 208 receive_stats(struct uct *u, int size)
 209 {
 210         if (size % sizeof(struct incr_stats)) return false;
 211         int nodes = size / sizeof(struct incr_stats);
 212         if (nodes > (1 << u->stats_hbits)) return false;
 213
 214         struct tree *t = u->t;
 215         assert(nodes && t->htable);
 216         struct tree_node *prev = NULL;
 217         double start_time = time_now();
 218
 219         for (int n = 0; n < nodes; n++) {
 220                 struct incr_stats is;
 221                 if (fread(&is, sizeof(struct incr_stats), 1, stdin) != 1)
 222                         return false;
 223
 224                 if (UDEBUGL(7))
 225                         fprintf(stderr, "read %5d/%d %6d %.3f %"PRIpath" %s\n", n, nodes,
 226                                 is.incr.playouts, is.incr.value, is.coord_path,
 227                                 path2sstr(is.coord_path, t->board));
 228
 229                 struct tree_node *node = tree_find_node(t, &is, prev);
 230                 if (!node) continue;
 231
 232                 /* node_total += others_incr */
 233                 stats_add_result(&node->u, is.incr.value, is.incr.playouts);
 234
 235                 /* last_total += others_incr */
 236                 stats_add_result(&node->pu, is.incr.value, is.incr.playouts);
 237
 238                 prev = node;
 239         }
 240         if (DEBUGVV(2))
 241                 fprintf(stderr, "read args for %d nodes in %.4fms\n", nodes,
 242                         (time_now() - start_time)*1000);
 243         return true;
 244 }
 245
 246 /* Get stats for the distributed engine. Return a buffer with one
 247  * line "played_own root_playouts threads keep_looking", then
 248  * a list of lines "coord playouts value" with absolute counts for
 249  * children of the root node (including contributions from other
 250  * slaves). The last line must not end with \n.
 251  * If c is pass or resign, add this move with root->playouts weight.
 252  * This function is called only by the main thread, but may be
 253  * called while the tree is updated by the worker threads. Keep this
 254  * code in sync with distributed/distributed.c:select_best_move(). */
 255 static char *
 256 report_stats(struct uct *u, struct board *b, coord_t c, bool keep_looking)
 257 {
 258         static char reply[10240];
 259         char *r = reply;
 260         char *end = reply + sizeof(reply);
 261         struct tree_node *root = u->t->root;
 262         r += snprintf(r, end - r, "%d %d %d %d", u->played_own, root->u.playouts, u->threads, keep_looking);
 263         int min_playouts = root->u.playouts / 100;
 264
 265         /* Give a large weight to pass or resign, but still allow other moves. */
 266         if (is_pass(c) || is_resign(c))
 267                 r += snprintf(r, end - r, "\n%s %d %.1f", coord2sstr(c, b),
 268                               root->u.playouts, 0.0);
 269
 270         /* We rely on the fact that root->children is set only
 271          * after all children are created. */
 272         for (struct tree_node *ni = root->children; ni; ni = ni->sibling) {
 273
 274                 if (is_pass(ni->coord)) continue;
 275                 if (ni->u.playouts <= min_playouts || ni->hints & TREE_HINT_INVALID)
 276                         continue;
 277
 278                 assert(ni->coord > 0 && ni->coord < board_size2(b));
 279                 char buf[4];
 280                 /* We return the values as stored in the tree, so from black's view. */
 281                 r += snprintf(r, end - r, "\n%s %d %.7f", coord2bstr(buf, ni->coord, b),
 282                               ni->u.playouts, ni->u.value);
 283         }
 284         return reply;
 285 }
 286
 287 /* How long to wait in slave for initial stats to build up before
 288  * replying to the genmoves command (in seconds) */
 289 #define MIN_STATS_INTERVAL 0.05 /* 50ms */
 290
 291 /* genmoves is issued by the distributed engine master to all slaves, to:
 292  * 1. Start a MCTS search if not running yet
 293  * 2. Report current move statistics of the on-going search.
 294  * The MCTS search is left running on the background when uct_genmoves()
 295  * returns. It is stopped by receiving a play GTP command, triggering
 296  * uct_pondering_stop(). */
 297 /* genmoves gets in the args parameter
 298  * "played_games nodes main_time byoyomi_time byoyomi_periods byoyomi_stones @size"
 299  * and reads a binary array of coord, playouts, value to get stats of other slaves,
 300  * except possibly for the first call at a given move number.
 301  * See report_stats() for the description of the return value. */
 302 char *
 303 uct_genmoves(struct engine *e, struct board *b, struct time_info *ti, enum stone color,
 304              char *args, bool pass_all_alive)
 305 {
 306         struct uct *u = e->data;
 307         assert(u->slave);
 308
 309         /* Prepare the state if the search is not already running.
 310          * We must do this first since we tweak the state below
 311          * based on instructions from the master. */
 312         if (!thread_manager_running)
 313                 uct_genmove_setup(u, b, color);
 314
 315         /* Get playouts and time information from master. Keep this code
 316          * in sync with distibuted/distributed.c:distributed_genmove(). */
 317         if ((ti->dim == TD_WALLTIME
 318              && sscanf(args, "%d %lf %lf %d %d", &u->played_all,
 319                        &ti->len.t.main_time, &ti->len.t.byoyomi_time,
 320                        &ti->len.t.byoyomi_periods, &ti->len.t.byoyomi_stones) != 5)
 321
 322             || (ti->dim == TD_GAMES && sscanf(args, "%d", &u->played_all) != 1)) {
 323                 return NULL;
 324         }
 325
 326         static struct uct_search_state s;
 327         if (!thread_manager_running) {
 328                 /* This is the first genmoves issue, start the MCTS
 329                  * now and let it run while we receive stats. */
 330                 memset(&s, 0, sizeof(s));
 331                 uct_search_start(u, b, color, u->t, ti, &s);
 332         }
 333
 334         /* Read binary incremental stats if present, otherwise
 335          * wait a bit to populate the statistics. */
 336         int size = 0;
 337         char *sizep = strchr(args, '@');
 338         if (sizep) size = atoi(sizep+1);
 339         if (!size) {
 340                 time_sleep(MIN_STATS_INTERVAL);
 341         } else if (!receive_stats(u, size)) {
 342                 return NULL;
 343         }
 344
 345         /* Check the state of the Monte Carlo Tree Search. */
 346
 347         int played_games = uct_search_games(&s);
 348         uct_search_progress(u, b, color, u->t, ti, &s, played_games);
 349         u->played_own = played_games - s.base_playouts;
 350
 351         bool keep_looking = !uct_search_check_stop(u, b, color, u->t, ti, &s, played_games);
 352         coord_t best_coord;
 353         uct_search_result(u, b, color, pass_all_alive, played_games, s.base_playouts, &best_coord);
 354
 355         char *reply = report_stats(u, b, best_coord, keep_looking);
 356         return reply;
 357 }