uct/slave.c

   1 #include <assert.h>
   2 #include <math.h>
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6
   7 #define DEBUG
   8
   9 #include "debug.h"
  10 #include "board.h"
  11 #include "gtp.h"
  12 #include "move.h"
  13 #include "timeinfo.h"
  14 #include "distributed/distributed.h"
  15 #include "uct/internal.h"
  16 #include "uct/search.h"
  17 #include "uct/slave.h"
  18 #include "uct/tree.h"
  19
  20
  21 /* UCT infrastructure for a distributed engine slave. */
  22
  23 enum parse_code
  24 uct_notify(struct engine *e, struct board *b, int id, char *cmd, char *args, char **reply)
  25 {
  26         struct uct *u = e->data;
  27
  28         static bool board_resized = false;
  29         board_resized |= is_gamestart(cmd);
  30
  31         /* Force resending the whole command history if we are out of sync
  32          * but do it only once, not if already getting the history. */
  33         if ((move_number(id) != b->moves || !board_resized)
  34             && !reply_disabled(id) && !is_reset(cmd)) {
  35                 if (UDEBUGL(0))
  36                         fprintf(stderr, "Out of sync, id %d, move %d\n", id, b->moves);
  37
  38                 /* Skip rest of multi-line command (genmoves only) */
  39                 if (!strcasecmp(cmd, "pachi-genmoves")
  40                     || !strcasecmp(cmd, "pachi-genmoves_cleanup")) {
  41                         char line[128];
  42                         while (fgets(line, sizeof(line), stdin) && *line != '\n') ;
  43                 }
  44
  45                 static char buf[128];
  46                 snprintf(buf, sizeof(buf), "out of sync, move %d expected", b->moves);
  47                 *reply = buf;
  48                 return P_DONE_ERROR;
  49         }
  50         return reply_disabled(id) ? P_NOREPLY : P_OK;
  51 }
  52
  53
  54 /* Set mapping from coordinates to children of the root node. */
  55 static void
  56 find_top_nodes(struct uct *u)
  57 {
  58         if (!u->t || !u->t->root) return;
  59
  60         for (struct tree_node *ni = u->t->root->children; ni; ni = ni->sibling) {
  61                 if (!is_pass(ni->coord))
  62                     u->stats[ni->coord].node = ni;
  63         }
  64 }
  65
  66 /* Get the move stats if they are present. They are
  67  * coord-sorted but the code here doesn't depend on this.
  68  * Keep this code in sync with select_best_move(). */
  69 static bool
  70 receive_stats(struct uct *u, struct board *b)
  71 {
  72         char line[128];
  73         while (fgets(line, sizeof(line), stdin) && *line != '\n') {
  74                 char move[64];
  75                 struct move_stats2 s;
  76                 if (sscanf(line, "%63s %d %f %d %f", move,
  77                            &s.u.playouts, &s.u.value,
  78                            &s.amaf.playouts, &s.amaf.value) != 5)
  79                         return false;
  80                 coord_t *c_ = str2coord(move, board_size(b));
  81                 coord_t c = *c_;
  82                 coord_done(c_);
  83                 assert(!is_pass(c) && !is_resign(c));
  84
  85                 struct node_stats *ns = &u->stats[c];
  86                 if (!ns->node) find_top_nodes(u);
  87                 /* The node may not exist if this slave was behind
  88                  * but this should be rare so it is not worth creating
  89                  * the node here. */
  90                 if (!ns->node) {
  91                         if (DEBUGL(2))
  92                                 fprintf(stderr, "can't find node %s %d\n", move, c);
  93                         continue;
  94                 }
  95
  96                 /* The master may not send moves below a certain threshold,
  97                  * but if it sends one it includes the contributions from
  98                  * all slaves including ours (last_sent_own):
  99                  *   received_others = received_total - last_sent_own  */
 100                 if (ns->last_sent_own.u.playouts)
 101                         stats_rm_result(&s.u, ns->last_sent_own.u.value,
 102                                         ns->last_sent_own.u.playouts);
 103                 if (ns->last_sent_own.amaf.playouts)
 104                         stats_rm_result(&s.amaf, ns->last_sent_own.amaf.value,
 105                                         ns->last_sent_own.amaf.playouts);
 106
 107                 /* others_delta = received_others - added_from_others */
 108                 struct move_stats2 delta = s;
 109                 if (ns->added_from_others.u.playouts)
 110                         stats_rm_result(&delta.u, ns->added_from_others.u.value,
 111                                         ns->added_from_others.u.playouts);
 112                 /* delta may be <= 0 if some slaves stopped sending this move
 113                  * because it became below a playouts threshold. In this case
 114                  * we just keep the old stats in our tree. */
 115                 if (delta.u.playouts <= 0) continue;
 116
 117                 if (ns->added_from_others.amaf.playouts)
 118                         stats_rm_result(&delta.amaf, ns->added_from_others.amaf.value,
 119                                         ns->added_from_others.amaf.playouts);
 120
 121                 stats_add_result(&ns->node->u, delta.u.value, delta.u.playouts);
 122                 stats_add_result(&ns->node->amaf, delta.amaf.value, delta.amaf.playouts);
 123                 ns->added_from_others = s;
 124         }
 125         return true;
 126 }
 127
 128 /* Get stats updates for the distributed engine. Return a buffer with
 129  * one line "played_own root_playouts threads keep_looking" then a list
 130  * of lines "coord playouts value amaf_playouts amaf_value".
 131  * The last line must not end with \n.
 132  * If c is pass or resign, add this move with root->playouts weight.
 133  * This function is called only by the main thread, but may be
 134  * called while the tree is updated by the worker threads.
 135  * Keep this code in sync with select_best_move(). */
 136 static char *
 137 report_stats(struct uct *u, struct board *b, coord_t c, bool keep_looking)
 138 {
 139         static char reply[10240];
 140         char *r = reply;
 141         char *end = reply + sizeof(reply);
 142         struct tree_node *root = u->t->root;
 143         r += snprintf(r, end - r, "%d %d %d %d", u->played_own, root->u.playouts, u->threads, keep_looking);
 144         int min_playouts = root->u.playouts / 100;
 145
 146         /* Give a large weight to pass or resign, but still allow other moves.
 147          * Only root->u.playouts will be used (majority vote) but send amaf
 148          * stats too for consistency. */
 149         if (is_pass(c) || is_resign(c))
 150                 r += snprintf(r, end - r, "\n%s %d %.1f %d %.1f", coord2sstr(c, b),
 151                               root->u.playouts, 0.0, root->amaf.playouts, 0.0);
 152
 153         /* We rely on the fact that root->children is set only
 154          * after all children are created. */
 155         for (struct tree_node *ni = root->children; ni; ni = ni->sibling) {
 156
 157                 if (is_pass(ni->coord)) continue;
 158                 struct node_stats *ns = &u->stats[ni->coord];
 159                 ns->last_sent_own.u.playouts = ns->last_sent_own.amaf.playouts = 0;
 160                 ns->node = ni;
 161                 if (ni->u.playouts <= min_playouts || ni->hints & TREE_HINT_INVALID)
 162                         continue;
 163
 164                 char *coord = coord2sstr(ni->coord, b);
 165                 /* We return the values as stored in the tree, so from black's view.
 166                  *   own = total_in_tree - added_from_others */
 167                 struct move_stats2 s = { .u = ni->u, .amaf = ni->amaf };
 168                 struct move_stats2 others = ns->added_from_others;
 169                 if (s.u.playouts - others.u.playouts <= min_playouts)
 170                         continue;
 171                 if (others.u.playouts)
 172                         stats_rm_result(&s.u, others.u.value, others.u.playouts);
 173                 if (others.amaf.playouts)
 174                         stats_rm_result(&s.amaf, others.amaf.value, others.amaf.playouts);
 175
 176                 r += snprintf(r, end - r, "\n%s %d %.7f %d %.7f", coord,
 177                               s.u.playouts, s.u.value, s.amaf.playouts, s.amaf.value);
 178                 ns->last_sent_own = s;
 179                 /* If the master discards these values because this slave
 180                  * is out of sync, u->stats will be reset anyway. */
 181         }
 182         return reply;
 183 }
 184
 185 /* genmoves is issued by the distributed engine master to all slaves, to:
 186  * 1. Start a MCTS search if not running yet
 187  * 2. Report current move statistics of the on-going search.
 188  * The MCTS search is left running on the background when uct_genmoves()
 189  * returns. It is stopped by receiving a play GTP command, triggering
 190  * uct_pondering_stop(). */
 191 /* genmoves gets in the args parameter
 192  * "played_games main_time byoyomi_time byoyomi_periods byoyomi_stones"
 193  * and reads a list of lines "coord playouts value amaf_playouts amaf_value"
 194  * to get stats of other slaves, except for the first call at a given move number.
 195  * See uct_getstats() for the description of the return value. */
 196 char *
 197 uct_genmoves(struct engine *e, struct board *b, struct time_info *ti, enum stone color,
 198              char *args, bool pass_all_alive)
 199 {
 200         struct uct *u = e->data;
 201         assert(u->slave);
 202
 203         /* Prepare the state if the search is not already running.
 204          * We must do this first since we tweak the state below
 205          * based on instructions from the master. */
 206         if (!thread_manager_running)
 207                 uct_genmove_setup(u, b, color);
 208
 209         /* Get playouts and time information from master.
 210          * Keep this code in sync with distributed_genmove(). */
 211         if ((ti->dim == TD_WALLTIME
 212              && sscanf(args, "%d %lf %lf %d %d", &u->played_all, &ti->len.t.main_time,
 213                        &ti->len.t.byoyomi_time, &ti->len.t.byoyomi_periods,
 214                        &ti->len.t.byoyomi_stones) != 5)
 215
 216             || (ti->dim == TD_GAMES && sscanf(args, "%d", &u->played_all) != 1)) {
 217                 return NULL;
 218         }
 219
 220         if (!receive_stats(u, b))
 221                 return NULL;
 222
 223         static struct uct_search_state s;
 224         if (!thread_manager_running) {
 225                 /* This is the first genmoves issue, start the MCTS. */
 226                 memset(&s, 0, sizeof(s));
 227                 uct_search_start(u, b, color, u->t, ti, &s);
 228         }
 229         /* Wait a bit to populate the statistics
 230          * and avoid a busy loop with the master. */
 231         time_sleep(TREE_BUSYWAIT_INTERVAL);
 232
 233         /* Check the state of the Monte Carlo Tree Search. */
 234
 235         int played_games = uct_search_games(&s);
 236         uct_search_progress(u, b, color, u->t, ti, &s, played_games);
 237         u->played_own = played_games;
 238
 239         bool keep_looking = !uct_search_check_stop(u, b, color, u->t, ti, &s, played_games);
 240         coord_t best_coord;
 241         uct_search_result(u, b, color, pass_all_alive, played_games, s.base_playouts, &best_coord);
 242
 243         char *reply = report_stats(u, b, best_coord, keep_looking);
 244         return reply;
 245 }