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/slave.h"
  17 #include "uct/tree.h"
  18 #include "uct/uct.h"
  19 #include "uct/walk.h"
  20
  21
  22 /* UCT infrastructure for a distributed engine slave. */
  23
  24 /* Get stats updates for the distributed engine. Return a buffer with
  25  * one line "played_own root_playouts threads keep_looking" then a list
  26  * of lines "coord playouts value amaf_playouts amaf_value".
  27  * The last line must not end with \n.
  28  * If c is pass or resign, add this move with root->playouts weight.
  29  * This function is called only by the main thread, but may be
  30  * called while the tree is updated by the worker threads.
  31  * Keep this code in sync with select_best_move(). */
  32 static char *
  33 uct_getstats(struct uct *u, struct board *b, coord_t c, bool keep_looking)
  34 {
  35         static char reply[10240];
  36         char *r = reply;
  37         char *end = reply + sizeof(reply);
  38         struct tree_node *root = u->t->root;
  39         r += snprintf(r, end - r, "%d %d %d %d", u->played_own, root->u.playouts, u->threads, keep_looking);
  40         int min_playouts = root->u.playouts / 100;
  41
  42         /* Give a large weight to pass or resign, but still allow other moves.
  43          * Only root->u.playouts will be used (majority vote) but send amaf
  44          * stats too for consistency. */
  45         if (is_pass(c) || is_resign(c))
  46                 r += snprintf(r, end - r, "\n%s %d %.1f %d %.1f", coord2sstr(c, b),
  47                               root->u.playouts, 0.0, root->amaf.playouts, 0.0);
  48
  49         /* We rely on the fact that root->children is set only
  50          * after all children are created. */
  51         for (struct tree_node *ni = root->children; ni; ni = ni->sibling) {
  52
  53                 if (is_pass(ni->coord)) continue;
  54                 struct node_stats *ns = &u->stats[ni->coord];
  55                 ns->last_sent_own.u.playouts = ns->last_sent_own.amaf.playouts = 0;
  56                 ns->node = ni;
  57                 if (ni->u.playouts <= min_playouts || ni->hints & TREE_HINT_INVALID)
  58                         continue;
  59
  60                 char *coord = coord2sstr(ni->coord, b);
  61                 /* We return the values as stored in the tree, so from black's view.
  62                  *   own = total_in_tree - added_from_others */
  63                 struct move_stats2 s = { .u = ni->u, .amaf = ni->amaf };
  64                 struct move_stats2 others = ns->added_from_others;
  65                 if (s.u.playouts - others.u.playouts <= min_playouts)
  66                         continue;
  67                 if (others.u.playouts)
  68                         stats_rm_result(&s.u, others.u.value, others.u.playouts);
  69                 if (others.amaf.playouts)
  70                         stats_rm_result(&s.amaf, others.amaf.value, others.amaf.playouts);
  71
  72                 r += snprintf(r, end - r, "\n%s %d %.7f %d %.7f", coord,
  73                               s.u.playouts, s.u.value, s.amaf.playouts, s.amaf.value);
  74                 ns->last_sent_own = s;
  75                 /* If the master discards these values because this slave
  76                  * is out of sync, u->stats will be reset anyway. */
  77         }
  78         return reply;
  79 }
  80
  81 /* Set mapping from coordinates to children of the root node. */
  82 static void
  83 find_top_nodes(struct uct *u)
  84 {
  85         if (!u->t || !u->t->root) return;
  86
  87         for (struct tree_node *ni = u->t->root->children; ni; ni = ni->sibling) {
  88                 if (!is_pass(ni->coord))
  89                     u->stats[ni->coord].node = ni;
  90         }
  91 }
  92
  93 /* genmoves gets in the args parameter
  94  * "played_games main_time byoyomi_time byoyomi_periods byoyomi_stones"
  95  * and reads a list of lines "coord playouts value amaf_playouts amaf_value"
  96  * to get stats of other slaves, except for the first call at a given move number.
  97  * See uct_getstats() for the description of the return value. */
  98 char *
  99 uct_genmoves(struct engine *e, struct board *b, struct time_info *ti, enum stone color,
 100              char *args, bool pass_all_alive)
 101 {
 102         struct uct *u = e->data;
 103         assert(u->slave);
 104
 105         /* Seed the tree if the search is not already running. */
 106         if (!thread_manager_running) {
 107                 uct_prepare_move(u, b, color);
 108                 uct_search_setup(u, b, color);
 109         }
 110
 111         /* Get playouts and time information from master.
 112          * Keep this code in sync with distributed_genmove(). */
 113         if ((ti->dim == TD_WALLTIME
 114              && sscanf(args, "%d %lf %lf %d %d", &u->played_all, &ti->len.t.main_time,
 115                        &ti->len.t.byoyomi_time, &ti->len.t.byoyomi_periods,
 116                        &ti->len.t.byoyomi_stones) != 5)
 117
 118             || (ti->dim == TD_GAMES && sscanf(args, "%d", &u->played_all) != 1)) {
 119                 return NULL;
 120         }
 121
 122         /* Get the move stats if they are present. They are
 123          * coord-sorted but the code here doesn't depend on this.
 124          * Keep this code in sync with select_best_move(). */
 125
 126         char line[128];
 127         while (fgets(line, sizeof(line), stdin) && *line != '\n') {
 128                 char move[64];
 129                 struct move_stats2 s;
 130                 if (sscanf(line, "%63s %d %f %d %f", move,
 131                            &s.u.playouts, &s.u.value,
 132                            &s.amaf.playouts, &s.amaf.value) != 5)
 133                         return NULL;
 134                 coord_t *c_ = str2coord(move, board_size(b));
 135                 coord_t c = *c_;
 136                 coord_done(c_);
 137                 assert(!is_pass(c) && !is_resign(c));
 138
 139                 struct node_stats *ns = &u->stats[c];
 140                 if (!ns->node) find_top_nodes(u);
 141                 /* The node may not exist if this slave was behind
 142                  * but this should be rare so it is not worth creating
 143                  * the node here. */
 144                 if (!ns->node) {
 145                         if (DEBUGL(2))
 146                                 fprintf(stderr, "can't find node %s %d\n", move, c);
 147                         continue;
 148                 }
 149
 150                 /* The master may not send moves below a certain threshold,
 151                  * but if it sends one it includes the contributions from
 152                  * all slaves including ours (last_sent_own):
 153                  *   received_others = received_total - last_sent_own  */
 154                 if (ns->last_sent_own.u.playouts)
 155                         stats_rm_result(&s.u, ns->last_sent_own.u.value,
 156                                         ns->last_sent_own.u.playouts);
 157                 if (ns->last_sent_own.amaf.playouts)
 158                         stats_rm_result(&s.amaf, ns->last_sent_own.amaf.value,
 159                                         ns->last_sent_own.amaf.playouts);
 160
 161                 /* others_delta = received_others - added_from_others */
 162                 struct move_stats2 delta = s;
 163                 if (ns->added_from_others.u.playouts)
 164                         stats_rm_result(&delta.u, ns->added_from_others.u.value,
 165                                         ns->added_from_others.u.playouts);
 166                 /* delta may be <= 0 if some slaves stopped sending this move
 167                  * because it became below a playouts threshold. In this case
 168                  * we just keep the old stats in our tree. */
 169                 if (delta.u.playouts <= 0) continue;
 170
 171                 if (ns->added_from_others.amaf.playouts)
 172                         stats_rm_result(&delta.amaf, ns->added_from_others.amaf.value,
 173                                         ns->added_from_others.amaf.playouts);
 174
 175                 stats_add_result(&ns->node->u, delta.u.value, delta.u.playouts);
 176                 stats_add_result(&ns->node->amaf, delta.amaf.value, delta.amaf.playouts);
 177                 ns->added_from_others = s;
 178         }
 179
 180         /* Continue the Monte Carlo Tree Search. */
 181         bool keep_looking;
 182         coord_t best_coord;
 183         int base_playouts = u->t->root->u.playouts;
 184         int played_games = uct_search(u, b, ti, color, u->t, &keep_looking);
 185         u->played_own += played_games;
 186         uct_search_best(u, b, color, pass_all_alive, played_games, base_playouts, &best_coord);
 187
 188         char *reply = uct_getstats(u, b, best_coord, keep_looking);
 189         return reply;
 190 }