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. */
10 /* Similarly the master only sends stats increments.
11 * They include only contributions from other slaves. */
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. */
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. */
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
35 #define MAX_VERBOSE_LOGS 1000
43 #include "uct/internal.h"
44 #include "uct/search.h"
45 #include "uct/slave.h"
49 /* UCT infrastructure for a distributed engine slave. */
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;
57 /* Hash table entry mapping path to node. */
60 struct tree_node
*node
;
64 uct_htable_alloc(int hbits
)
66 return calloc2(1 << hbits
, sizeof(struct tree_hash
));
69 /* Clear the hash table. Used only when running as slave for the distributed engine. */
70 void uct_htable_reset(struct tree
*t
)
72 if (!t
->htable
) return;
73 double start
= time_now();
74 memset(t
->htable
, 0, (1 << t
->hbits
) * sizeof(t
->htable
[0]));
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;
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
)
98 assert(t
&& t
->htable
);
99 path_t path
= is
->coord_path
;
100 /* pass and resign must never be inserted in the hash table. */
103 int hash
, parent_hash
;
105 find_hash(hash
, t
->htable
, t
->hbits
, path
, found
, h_counts
);
106 struct tree_hash
*hnode
= &t
->htable
[hash
];
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
);
113 if (found
) return hnode
->node
;
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
;
120 find_hash(parent_hash
, t
->htable
, t
->hbits
,
121 parent_p
, found
, h_counts
);
122 parent
= t
->htable
[parent_hash
].node
;
126 struct tree_node
*node
= NULL
;
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
;
133 if (DEBUG_MODE
) parent_leaf
+= !parent
->is_expanded
;
135 if (DEBUG_MODE
) parent_not_found
++;
137 fprintf(stderr
, "parent of %"PRIpath
" %s not found\n",
138 path
, path2sstr(path
, t
->board
));
141 /* Insert the node in the hash table. */
143 if (DEBUG_MODE
) h_counts
.inserts
++, h_counts
.occupied
++;
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
);
148 if (DEBUG_MODE
&& !node
) node_not_found
++;
150 hnode
->coord_path
= path
;
155 /* Read and discard any binary arguments. The number of
156 * bytes to be skipped is given by @size in the command. */
158 discard_bin_args(char *args
)
160 char *s
= strchr(args
, '@');
162 if (s
) size
= atoi(s
+1);
165 int len
= sizeof(buf
);
166 if (len
> size
) len
= size
;
167 len
= fread(buf
, 1, len
, stdin
);
174 uct_notify(struct engine
*e
, struct board
*b
, int id
, char *cmd
, char *args
, char **reply
)
176 struct uct
*u
= e
->data
;
178 static bool board_resized
= false;
179 if (is_gamestart(cmd
)) {
180 board_resized
= true;
181 uct_pondering_stop(u
);
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
)) {
189 fprintf(stderr
, "Out of sync, id %d, move %d\n", id
, b
->moves
);
190 discard_bin_args(args
);
192 static char buf
[128];
193 snprintf(buf
, sizeof(buf
), "out of sync, move %d expected", b
->moves
);
197 return reply_disabled(id
) ? P_NOREPLY
: P_OK
;
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. */
208 receive_stats(struct uct
*u
, int size
)
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;
214 struct tree
*t
= u
->t
;
215 assert(nodes
&& t
->htable
);
216 struct tree_node
*prev
= NULL
;
217 double start_time
= time_now();
219 for (int n
= 0; n
< nodes
; n
++) {
220 struct incr_stats is
;
221 if (fread(&is
, sizeof(struct incr_stats
), 1, stdin
) != 1)
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
));
229 struct tree_node
*node
= tree_find_node(t
, &is
, prev
);
232 /* node_total += others_incr */
233 stats_add_result(&node
->u
, is
.incr
.value
, is
.incr
.playouts
);
235 /* last_total += others_incr */
236 stats_add_result(&node
->pu
, is
.incr
.value
, is
.incr
.playouts
);
241 fprintf(stderr
, "read args for %d nodes in %.4fms\n", nodes
,
242 (time_now() - start_time
)*1000);
246 /* A tree traversal fills this array, then the nodes with most increments are sent. */
247 struct stats_candidate
{
250 struct tree_node
*node
;
253 /* We maintain counts per bucket to avoid sorting stats_queue.
254 * All nodes with n updates since last send go to bucket n.
255 * If we put all nodes above 1023 updates in the top bucket,
256 * we get at most 27 nodes in this bucket. So we can select
257 * exactly the best shared_nodes nodes if shared_nodes >= 27. */
258 #define MAX_BUCKETS 1024
259 static int bucket_count
[MAX_BUCKETS
];
261 /* Traverse the tree rooted at node, and append incremental stats
262 * for children to stats_queue. start_path is the coordinate path
263 * for the top node. Stats for a node are only appended if enough playouts
264 * have been made since the last send, and the level is not too deep.
265 * Return the updated stats count. */
267 append_stats(struct stats_candidate
*stats_queue
, struct tree_node
*node
, int stats_count
,
268 int max_count
, path_t start_path
, path_t max_path
, int min_increment
, struct board
*b
)
270 /* The children field is set only after all children are created
271 * so we can traverse the the tree while it is updated. */
272 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
) {
274 if (is_pass(ni
->coord
)) continue;
275 if (ni
->hints
& TREE_HINT_INVALID
) continue;
277 int incr
= ni
->u
.playouts
- ni
->pu
.playouts
;
278 if (incr
< min_increment
) continue;
280 /* min_increment should be tuned to avoid overflow. */
281 if (stats_count
>= max_count
) {
283 fprintf(stderr
, "*** stats overflow %d nodes\n", stats_count
);
286 path_t child_path
= append_child(start_path
, ni
->coord
, b
);
287 stats_queue
[stats_count
].playout_incr
= incr
;
288 stats_queue
[stats_count
].coord_path
= child_path
;
289 stats_queue
[stats_count
++].node
= ni
;
291 if (incr
>= MAX_BUCKETS
) incr
= MAX_BUCKETS
- 1;
292 bucket_count
[incr
]++;
294 /* Do not recurse if level deep enough. */
295 if (child_path
>= max_path
) continue;
297 stats_count
= append_stats(stats_queue
, ni
, stats_count
, max_count
,
298 child_path
, max_path
, min_increment
, b
);
303 /* Used to sort by coord path the incremental stats to be sent. */
305 coord_cmp(const void *p1
, const void *p2
)
307 path_t diff
= ((struct incr_stats
*)p1
)->coord_path
308 - ((struct incr_stats
*)p2
)->coord_path
;
309 return (int)(diff
>> 32) | !!(int)diff
;
312 /* Select from stats_queue at most shared_nodes candidates with
313 * biggest increments. Return a binary array sorted by coord path. */
314 static struct incr_stats
*
315 select_best_stats(struct stats_candidate
*stats_queue
, int stats_count
,
316 int shared_nodes
, int *byte_size
)
318 static struct incr_stats
*out_stats
= NULL
;
320 out_stats
= malloc2(shared_nodes
* sizeof(*out_stats
));
322 /* Find the minimum increment to send. The bucket with minimum
323 * increment may be sent only partially. */
325 int min_incr
= MAX_BUCKETS
;
327 out_count
+= bucket_count
[--min_incr
];
328 } while (min_incr
> 1 && out_count
< shared_nodes
);
330 /* Send all all increments > min_incr plus whatever we can at min_incr. */
331 int min_count
= bucket_count
[min_incr
] - (out_count
- shared_nodes
);
332 struct incr_stats
*os
= out_stats
;
334 for (int count
= 0; count
< stats_count
; count
++) {
335 int delta
= stats_queue
[count
].playout_incr
- min_incr
;
336 if (delta
< 0 || (delta
== 0 && --min_count
< 0)) continue;
338 struct tree_node
*node
= stats_queue
[count
].node
;
340 stats_rm_result(&os
->incr
, node
->pu
.value
, node
->pu
.playouts
);
342 /* With virtual loss os->incr.playouts might be <= 0; we only
343 * send positive increments to other slaves so a virtual loss
344 * can be propagated to other machines (good). The undo of the
345 * virtual loss will be propagated later when node->u gets
347 if (os
->incr
.playouts
> 0) {
349 os
->coord_path
= stats_queue
[count
].coord_path
;
350 assert(os
->coord_path
> 0);
354 assert (out_count
<= shared_nodes
);
356 *byte_size
= (char *)os
- (char *)out_stats
;
358 /* Sort the increments by increasing coord path (required by master).
359 * Can be done in linear time with radix sort if qsort is too slow. */
360 qsort(out_stats
, out_count
, sizeof(*os
), coord_cmp
);
364 /* Get incremental stats updates for the distributed engine.
365 * Return a binary array of incr_stats structs in coordinate order
366 * (increasing levels and increasing coordinates within a level).
367 * This function is called only by the main thread, but may be
368 * called while the tree is updated by the worker threads. Keep this
369 * code in sync with distributed/distributed.c:select_best_move(). */
371 report_incr_stats(struct uct
*u
, int *stats_size
)
373 double start_time
= time_now();
375 struct tree_node
*root
= u
->t
->root
;
376 struct board
*b
= u
->t
->board
;
378 /* The factor 3 below has experimentally been found to be
379 * sufficient. At worst if we fill stats_queue we will
380 * discard some stats updates but this is rare. */
381 int max_nodes
= 3 * u
->shared_nodes
;
382 static struct stats_candidate
*stats_queue
= NULL
;
383 if (!stats_queue
) stats_queue
= malloc2(max_nodes
* sizeof(*stats_queue
));
385 memset(bucket_count
, 0, sizeof(bucket_count
));
387 /* Try to fill the output buffer with the most important
388 * nodes (highest increments), while still traversing
389 * as little of the tree as possible. If we set min_increment
390 * too low we waste time. If we set it too high we can't
391 * fill the output buffer with the desired number of nodes.
392 * The best min_increment results in stats_count just above
393 * shared_nodes. However perfect tuning is not necessary:
394 * if we send too few nodes we just send shorter buffers
395 * more frequently. */
396 static int min_increment
= 1;
397 static int stats_count
= 0;
398 if (stats_count
> 2 * u
->shared_nodes
) {
400 } else if (stats_count
< u
->shared_nodes
/ 2 && min_increment
> 1) {
404 stats_count
= append_stats(stats_queue
, root
, 0, max_nodes
, 0,
405 max_parent_path(u
, b
), min_increment
, b
);
407 void *buf
= select_best_stats(stats_queue
, stats_count
, u
->shared_nodes
, stats_size
);
411 "min_incr %d games %d stats_queue %d/%d sending %d/%d in %.3fms\n",
412 min_increment
, root
->u
.playouts
- root
->pu
.playouts
, stats_count
,
413 max_nodes
, *stats_size
/ (int)sizeof(struct incr_stats
), u
->shared_nodes
,
414 (time_now() - start_time
)*1000);
419 /* Get stats for the distributed engine. Return a buffer with one
420 * line "played_own root_playouts threads keep_looking @size", then
421 * a list of lines "coord playouts value" with absolute counts for
422 * children of the root node (including contributions from other
423 * slaves). The last line must not end with \n.
424 * If c is pass or resign, add this move with root->playouts weight.
425 * This function is called only by the main thread, but may be
426 * called while the tree is updated by the worker threads. Keep this
427 * code in sync with distributed/distributed.c:select_best_move(). */
429 report_stats(struct uct
*u
, struct board
*b
, coord_t c
,
430 bool keep_looking
, int bin_size
)
432 static char reply
[10240];
434 char *end
= reply
+ sizeof(reply
);
435 struct tree_node
*root
= u
->t
->root
;
436 r
+= snprintf(r
, end
- r
, "%d %d %d %d @%d", u
->played_own
, root
->u
.playouts
,
437 u
->threads
, keep_looking
, bin_size
);
438 int min_playouts
= root
->u
.playouts
/ 100;
440 /* Give a large weight to pass or resign, but still allow other moves. */
441 if (is_pass(c
) || is_resign(c
))
442 r
+= snprintf(r
, end
- r
, "\n%s %d %.1f", coord2sstr(c
, b
),
443 root
->u
.playouts
, 0.0);
445 /* We rely on the fact that root->children is set only
446 * after all children are created. */
447 for (struct tree_node
*ni
= root
->children
; ni
; ni
= ni
->sibling
) {
449 if (is_pass(ni
->coord
)) continue;
450 if (ni
->u
.playouts
<= min_playouts
|| ni
->hints
& TREE_HINT_INVALID
)
453 assert(ni
->coord
> 0 && ni
->coord
< board_size2(b
));
455 /* We return the values as stored in the tree, so from black's view. */
456 r
+= snprintf(r
, end
- r
, "\n%s %d %.7f", coord2bstr(buf
, ni
->coord
, b
),
457 ni
->u
.playouts
, ni
->u
.value
);
462 /* How long to wait in slave for initial stats to build up before
463 * replying to the genmoves command (in seconds) */
464 #define MIN_STATS_INTERVAL 0.05 /* 50ms */
466 /* genmoves is issued by the distributed engine master to all slaves, to:
467 * 1. Start a MCTS search if not running yet
468 * 2. Report current move statistics of the on-going search.
469 * The MCTS search is left running on the background when uct_genmoves()
470 * returns. It is stopped by receiving a play GTP command, triggering
471 * uct_pondering_stop(). */
472 /* genmoves gets in the args parameter
473 * "played_games nodes main_time byoyomi_time byoyomi_periods byoyomi_stones @size"
474 * and reads a binary array of coord, playouts, value to get stats of other slaves,
475 * except possibly for the first call at a given move number.
476 * See report_stats() for the description of the return value. */
478 uct_genmoves(struct engine
*e
, struct board
*b
, struct time_info
*ti
, enum stone color
,
479 char *args
, bool pass_all_alive
, void **stats_buf
, int *stats_size
)
481 struct uct
*u
= e
->data
;
484 /* Prepare the state if the search is not already running.
485 * We must do this first since we tweak the state below
486 * based on instructions from the master. */
487 if (!thread_manager_running
)
488 uct_genmove_setup(u
, b
, color
);
490 /* Get playouts and time information from master. Keep this code
491 * in sync with distibuted/distributed.c:distributed_genmove(). */
492 if ((ti
->dim
== TD_WALLTIME
493 && sscanf(args
, "%d %lf %lf %d %d", &u
->played_all
,
494 &ti
->len
.t
.main_time
, &ti
->len
.t
.byoyomi_time
,
495 &ti
->len
.t
.byoyomi_periods
, &ti
->len
.t
.byoyomi_stones
) != 5)
497 || (ti
->dim
== TD_GAMES
&& sscanf(args
, "%d", &u
->played_all
) != 1)) {
501 static struct uct_search_state s
;
502 if (!thread_manager_running
) {
503 /* This is the first genmoves issue, start the MCTS
504 * now and let it run while we receive stats. */
505 memset(&s
, 0, sizeof(s
));
506 uct_search_start(u
, b
, color
, u
->t
, ti
, &s
);
509 /* Read binary incremental stats if present, otherwise
510 * wait a bit to populate the statistics. */
512 char *sizep
= strchr(args
, '@');
513 if (sizep
) size
= atoi(sizep
+1);
515 time_sleep(MIN_STATS_INTERVAL
);
516 } else if (!receive_stats(u
, size
)) {
520 /* Check the state of the Monte Carlo Tree Search. */
522 int played_games
= uct_search_games(&s
);
523 uct_search_progress(u
, b
, color
, u
->t
, ti
, &s
, played_games
);
524 u
->played_own
= played_games
- s
.base_playouts
;
526 bool keep_looking
= !uct_search_check_stop(u
, b
, color
, u
->t
, ti
, &s
, played_games
);
528 uct_search_result(u
, b
, color
, pass_all_alive
, played_games
, s
.base_playouts
, &best_coord
);
530 *stats_buf
= report_incr_stats(u
, stats_size
);
532 char *reply
= report_stats(u
, b
, best_coord
, keep_looking
, *stats_size
);