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 enum parse_code
 155 uct_notify(struct engine *e, struct board *b, int id, char *cmd, char *args, char **reply)
 156 {
 157         struct uct *u = e->data;
 158
 159         static bool board_resized = false;
 160         if (is_gamestart(cmd)) {
 161                 board_resized = true;
 162                 uct_pondering_stop(u);
 163         }
 164
 165         /* Force resending the whole command history if we are out of sync
 166          * but do it only once, not if already getting the history. */
 167         if ((move_number(id) != b->moves || !board_resized)
 168             && !reply_disabled(id) && !is_reset(cmd)) {
 169                 if (UDEBUGL(0))
 170                         fprintf(stderr, "Out of sync, id %d, move %d\n", id, b->moves);
 171
 172                 /* Skip rest of multi-line command (genmoves only) */
 173                 if (!strcasecmp(cmd, "pachi-genmoves")
 174                     || !strcasecmp(cmd, "pachi-genmoves_cleanup")) {
 175                         char line[128];
 176                         while (fgets(line, sizeof(line), stdin) && *line != '\n') ;
 177                 }
 178
 179                 static char buf[128];
 180                 snprintf(buf, sizeof(buf), "out of sync, move %d expected", b->moves);
 181                 *reply = buf;
 182                 return P_DONE_ERROR;
 183         }
 184         return reply_disabled(id) ? P_NOREPLY : P_OK;
 185 }
 186
 187
 188 /* Read the move stats sent by the master, as a binary array of
 189  * incr_stats structs. The stats come sorted by increasing coord path.
 190  * To simplify the code, we assume that master and slave have the same
 191  * architecture (store values identically).
 192  * Keep this code in sync with distributed/distributed.c:select_best_move().
 193  * Return true if ok, false if error. */
 194 static bool
 195 receive_stats(struct uct *u, int size)
 196 {
 197         if (size % sizeof(struct incr_stats)) return false;
 198         int nodes = size / sizeof(struct incr_stats);
 199         if (nodes > (1 << u->stats_hbits)) return false;
 200
 201         struct tree *t = u->t;
 202         assert(nodes && t->htable);
 203         struct tree_node *prev = NULL;
 204         double start_time = time_now();
 205
 206         for (int n = 0; n < nodes; n++) {
 207                 struct incr_stats is;
 208                 if (fread(&is, sizeof(struct incr_stats), 1, stdin) != 1)
 209                         return false;
 210
 211                 if (UDEBUGL(7))
 212                         fprintf(stderr, "read %5d/%d %6d %.3f %"PRIpath" %s\n", n, nodes,
 213                                 is.incr.playouts, is.incr.value, is.coord_path,
 214                                 path2sstr(is.coord_path, t->board));
 215
 216                 struct tree_node *node = tree_find_node(t, &is, prev);
 217                 if (!node) continue;
 218
 219                 /* node_total += others_incr */
 220                 stats_add_result(&node->u, is.incr.value, is.incr.playouts);
 221
 222                 /* last_total += others_incr */
 223                 stats_add_result(&node->pu, is.incr.value, is.incr.playouts);
 224
 225                 prev = node;
 226         }
 227         if (DEBUGVV(2))
 228                 fprintf(stderr, "read args for %d nodes in %.4fms\n", nodes,
 229                         (time_now() - start_time)*1000);
 230         return true;
 231 }
 232
 233 /* Get stats for the distributed engine. Return a buffer with one
 234  * line "played_own root_playouts threads keep_looking", then
 235  * a list of lines "coord playouts value" with absolute counts for
 236  * children of the root node (including contributions from other
 237  * slaves). The last line must not end with \n.
 238  * If c is pass or resign, add this move with root->playouts weight.
 239  * This function is called only by the main thread, but may be
 240  * called while the tree is updated by the worker threads. Keep this
 241  * code in sync with distributed/distributed.c:select_best_move(). */
 242 static char *
 243 report_stats(struct uct *u, struct board *b, coord_t c, bool keep_looking)
 244 {
 245         static char reply[10240];
 246         char *r = reply;
 247         char *end = reply + sizeof(reply);
 248         struct tree_node *root = u->t->root;
 249         r += snprintf(r, end - r, "%d %d %d %d", u->played_own, root->u.playouts, u->threads, keep_looking);
 250         int min_playouts = root->u.playouts / 100;
 251
 252         /* Give a large weight to pass or resign, but still allow other moves. */
 253         if (is_pass(c) || is_resign(c))
 254                 r += snprintf(r, end - r, "\n%s %d %.1f", coord2sstr(c, b),
 255                               root->u.playouts, 0.0);
 256
 257         /* We rely on the fact that root->children is set only
 258          * after all children are created. */
 259         for (struct tree_node *ni = root->children; ni; ni = ni->sibling) {
 260
 261                 if (is_pass(ni->coord)) continue;
 262                 if (ni->u.playouts <= min_playouts || ni->hints & TREE_HINT_INVALID)
 263                         continue;
 264
 265                 assert(ni->coord > 0 && ni->coord < board_size2(b));
 266                 char buf[4];
 267                 /* We return the values as stored in the tree, so from black's view. */
 268                 r += snprintf(r, end - r, "\n%s %d %.7f", coord2bstr(buf, ni->coord, b),
 269                               ni->u.playouts, ni->u.value);
 270         }
 271         return reply;
 272 }
 273
 274 /* How long to wait in slave for initial stats to build up before
 275  * replying to the genmoves command (in seconds) */
 276 #define MIN_STATS_INTERVAL 0.05 /* 50ms */
 277
 278 /* genmoves is issued by the distributed engine master to all slaves, to:
 279  * 1. Start a MCTS search if not running yet
 280  * 2. Report current move statistics of the on-going search.
 281  * The MCTS search is left running on the background when uct_genmoves()
 282  * returns. It is stopped by receiving a play GTP command, triggering
 283  * uct_pondering_stop(). */
 284 /* genmoves gets in the args parameter
 285  * "played_games nodes main_time byoyomi_time byoyomi_periods byoyomi_stones @size"
 286  * and reads a binary array of coord, playouts, value to get stats of other slaves,
 287  * except possibly for the first call at a given move number.
 288  * See report_stats() for the description of the return value. */
 289 char *
 290 uct_genmoves(struct engine *e, struct board *b, struct time_info *ti, enum stone color,
 291              char *args, bool pass_all_alive)
 292 {
 293         struct uct *u = e->data;
 294         assert(u->slave);
 295
 296         /* Prepare the state if the search is not already running.
 297          * We must do this first since we tweak the state below
 298          * based on instructions from the master. */
 299         if (!thread_manager_running)
 300                 uct_genmove_setup(u, b, color);
 301
 302         /* Get playouts and time information from master. Keep this code
 303          * in sync with distibuted/distributed.c:distributed_genmove(). */
 304         if ((ti->dim == TD_WALLTIME
 305              && sscanf(args, "%d %lf %lf %d %d", &u->played_all,
 306                        &ti->len.t.main_time, &ti->len.t.byoyomi_time,
 307                        &ti->len.t.byoyomi_periods, &ti->len.t.byoyomi_stones) != 5)
 308
 309             || (ti->dim == TD_GAMES && sscanf(args, "%d", &u->played_all) != 1)) {
 310                 return NULL;
 311         }
 312
 313         static struct uct_search_state s;
 314         if (!thread_manager_running) {
 315                 /* This is the first genmoves issue, start the MCTS
 316                  * now and let it run while we receive stats. */
 317                 memset(&s, 0, sizeof(s));
 318                 uct_search_start(u, b, color, u->t, ti, &s);
 319         }
 320
 321         /* Read binary incremental stats if present, otherwise
 322          * wait a bit to populate the statistics. */
 323         int size = 0;
 324         char *sizep = strchr(args, '@');
 325         if (sizep) size = atoi(sizep+1);
 326         if (!size) {
 327                 time_sleep(MIN_STATS_INTERVAL);
 328         } else if (!receive_stats(u, size)) {
 329                 return NULL;
 330         }
 331
 332         /* Check the state of the Monte Carlo Tree Search. */
 333
 334         int played_games = uct_search_games(&s);
 335         uct_search_progress(u, b, color, u->t, ti, &s, played_games);
 336         u->played_own = played_games - s.base_playouts;
 337
 338         bool keep_looking = !uct_search_check_stop(u, b, color, u->t, ti, &s, played_games);
 339         coord_t best_coord;
 340         uct_search_result(u, b, color, pass_all_alive, played_games, s.base_playouts, &best_coord);
 341
 342         char *reply = report_stats(u, b, best_coord, keep_looking);
 343         return reply;
 344 }