17 #include "tactics/util.h"
18 #include "uct/dynkomi.h"
19 #include "uct/internal.h"
20 #include "uct/search.h"
25 #define DESCENT_DLEN 512
29 uct_progress_text(struct uct
*u
, struct tree
*t
, enum stone color
, int playouts
, bool final
)
35 struct tree_node
*best
= u
->policy
->choose(u
->policy
, t
->root
, t
->board
, color
, resign
);
37 fprintf(stderr
, "... No moves left\n");
40 fprintf(stderr
, "[%d] ", playouts
);
41 fprintf(stderr
, "best %f ", tree_node_get_value(t
, 1, best
->u
.value
));
44 if (t
->use_extra_komi
)
45 fprintf(stderr
, "komi %.1f ", t
->extra_komi
);
48 fprintf(stderr
, "| seq ");
49 for (int depth
= 0; depth
< 4; depth
++) {
50 if (best
&& best
->u
.playouts
>= 25) {
51 fprintf(stderr
, "%3s ", coord2sstr(node_coord(best
), t
->board
));
52 best
= u
->policy
->choose(u
->policy
, best
, t
->board
, color
, resign
);
59 fprintf(stderr
, "| can ");
61 struct tree_node
*can
[cans
];
62 memset(can
, 0, sizeof(can
));
63 best
= t
->root
->children
;
66 while ((!can
[c
] || best
->u
.playouts
> can
[c
]->u
.playouts
) && ++c
< cans
);
67 for (int d
= 0; d
< c
; d
++) can
[d
] = can
[d
+ 1];
68 if (c
> 0) can
[c
- 1] = best
;
73 fprintf(stderr
, "%3s(%.3f) ",
74 coord2sstr(node_coord(can
[cans
]), t
->board
),
75 tree_node_get_value(t
, 1, can
[cans
]->u
.value
));
81 fprintf(stderr
, "\n");
85 uct_progress_json(struct uct
*u
, struct tree
*t
, enum stone color
, int playouts
, bool final
, bool big
)
87 /* Prefix indicating JSON line. */
88 fprintf(stderr
, "{\"%s\": {", final
? "move" : "frame");
91 fprintf(stderr
, "\"playouts\": %d", playouts
);
94 if (t
->use_extra_komi
)
95 fprintf(stderr
, ", \"extrakomi\": %.1f", t
->extra_komi
);
97 struct tree_node
*best
= u
->policy
->choose(u
->policy
, t
->root
, t
->board
, color
, resign
);
100 fprintf(stderr
, ", \"best\": {\"%s\": %f}",
101 coord2sstr(best
->coord
, t
->board
),
102 tree_node_get_value(t
, 1, best
->u
.value
));
105 /* Best candidates */
107 struct tree_node
*can
[cans
];
108 memset(can
, 0, sizeof(can
));
109 best
= t
->root
->children
;
112 while ((!can
[c
] || best
->u
.playouts
> can
[c
]->u
.playouts
) && ++c
< cans
);
113 for (int d
= 0; d
< c
; d
++) can
[d
] = can
[d
+ 1];
114 if (c
> 0) can
[c
- 1] = best
;
115 best
= best
->sibling
;
117 fprintf(stderr
, ", \"can\": [");
118 while (--cans
>= 0) {
119 if (!can
[cans
]) break;
121 fprintf(stderr
, "%s[", cans
< 3 ? ", " : "");
123 for (int depth
= 0; depth
< 4; depth
++) {
124 if (!best
|| best
->u
.playouts
< 25) break;
125 fprintf(stderr
, "%s{\"%s\":%.3f}", depth
> 0 ? "," : "",
126 coord2sstr(best
->coord
, t
->board
),
127 tree_node_get_value(t
, 1, best
->u
.value
));
128 best
= u
->policy
->choose(u
->policy
, best
, t
->board
, color
, resign
);
130 fprintf(stderr
, "]");
132 fprintf(stderr
, "]");
136 if (t
->avg_score
.playouts
> 0)
137 fprintf(stderr
, ", \"avg\": {\"score\": %.3f}", t
->avg_score
.value
);
138 /* Per-intersection information. */
139 fprintf(stderr
, ", \"boards\": {");
140 /* Position coloring information. */
141 fprintf(stderr
, "\"colors\": [");
143 foreach_point(t
->board
) {
144 if (board_at(t
->board
, c
) == S_OFFBOARD
) continue;
145 fprintf(stderr
, "%s%d", f
++ > 0 ? "," : "", board_at(t
->board
, c
));
147 fprintf(stderr
, "]");
148 /* Ownership statistics. Value (0..1000) for each possible
149 * point describes likelihood of this point becoming black.
150 * Normally, white rate is 1000-value; exception are possible
151 * seki points, but these should be rare. */
152 fprintf(stderr
, ", \"territory\": [");
154 foreach_point(t
->board
) {
155 if (board_at(t
->board
, c
) == S_OFFBOARD
) continue;
156 int rate
= u
->ownermap
.map
[c
][S_BLACK
] * 1000 / u
->ownermap
.playouts
;
157 fprintf(stderr
, "%s%d", f
++ > 0 ? "," : "", rate
);
159 fprintf(stderr
, "]");
160 fprintf(stderr
, "}");
163 fprintf(stderr
, "}}\n");
167 uct_progress_status(struct uct
*u
, struct tree
*t
, enum stone color
, int playouts
, bool final
)
169 switch (u
->reporting
) {
171 uct_progress_text(u
, t
, color
, playouts
, final
);
175 uct_progress_json(u
, t
, color
, playouts
, final
,
176 u
->reporting
== UR_JSON_BIG
);
184 record_amaf_move(struct playout_amafmap
*amaf
, coord_t coord
, bool is_ko_capture
)
186 assert(amaf
->gamelen
< MAX_GAMELEN
);
187 amaf
->is_ko_capture
[amaf
->gamelen
] = is_ko_capture
;
188 amaf
->game
[amaf
->gamelen
++] = coord
;
192 struct uct_playout_callback
{
195 struct tree_node
*lnode
;
200 uct_playout_hook(struct playout_policy
*playout
, struct playout_setup
*setup
, struct board
*b
, enum stone color
, int mode
)
202 /* XXX: This is used in some non-master branches. */
207 uct_playout_prepolicy(struct playout_policy
*playout
, struct playout_setup
*setup
, struct board
*b
, enum stone color
)
209 return uct_playout_hook(playout
, setup
, b
, color
, 0);
213 uct_playout_postpolicy(struct playout_policy
*playout
, struct playout_setup
*setup
, struct board
*b
, enum stone color
)
215 return uct_playout_hook(playout
, setup
, b
, color
, 1);
220 uct_leaf_node(struct uct
*u
, struct board
*b
, enum stone player_color
,
221 struct playout_amafmap
*amaf
,
222 struct uct_descent
*descent
, int *dlen
,
223 struct tree_node
*significant
[2],
224 struct tree
*t
, struct tree_node
*n
, enum stone node_color
,
227 enum stone next_color
= stone_other(node_color
);
228 int parity
= (next_color
== player_color
? 1 : -1);
231 fprintf(stderr
, "%s*-- UCT playout #%d start [%s] %f\n",
232 spaces
, n
->u
.playouts
, coord2sstr(node_coord(n
), t
->board
),
233 tree_node_get_value(t
, parity
, n
->u
.value
));
235 struct uct_playout_callback upc
= {
238 /* TODO: Don't necessarily restart the sequence walk when
239 * entering playout. */
243 struct playout_setup ps
= {
244 .gamelen
= u
->gamelen
,
245 .mercymin
= u
->mercymin
,
246 .prepolicy_hook
= uct_playout_prepolicy
,
247 .postpolicy_hook
= uct_playout_postpolicy
,
250 int result
= play_random_game(&ps
, b
, next_color
,
251 u
->playout_amaf
? amaf
: NULL
,
252 &u
->ownermap
, u
->playout
);
253 if (next_color
== S_WHITE
) {
254 /* We need the result from black's perspective. */
258 fprintf(stderr
, "%s -- [%d..%d] %s random playout result %d\n",
259 spaces
, player_color
, next_color
, coord2sstr(node_coord(n
), t
->board
), result
);
265 scale_value(struct uct
*u
, struct board
*b
, int result
)
267 floating_t rval
= result
> 0 ? 1.0 : result
< 0 ? 0.0 : 0.5;
268 if (u
->val_scale
&& result
!= 0) {
269 int vp
= u
->val_points
;
271 vp
= board_size(b
) - 1; vp
*= vp
; vp
*= 2;
274 floating_t sval
= (floating_t
) abs(result
) / vp
;
275 sval
= sval
> 1 ? 1 : sval
;
276 if (result
< 0) sval
= 1 - sval
;
278 rval
+= u
->val_scale
* sval
;
280 rval
= (1 - u
->val_scale
) * rval
+ u
->val_scale
* sval
;
281 // fprintf(stderr, "score %d => sval %f, rval %f\n", result, sval, rval);
287 local_value(struct uct
*u
, struct board
*b
, coord_t coord
, enum stone color
)
289 /* Tactical evaluation of move @coord by color @color, given
290 * simulation end position @b. I.e., a move is tactically good
291 * if the resulting group stays on board until the game end. */
292 /* We can also take into account surrounding stones, e.g. to
293 * encourage taking off external liberties during a semeai. */
294 double val
= board_local_value(u
->local_tree_neival
, b
, coord
, color
);
295 return (color
== S_WHITE
) ? 1.f
- val
: val
;
299 record_local_sequence(struct uct
*u
, struct tree
*t
, struct board
*endb
,
300 struct uct_descent
*descent
, int dlen
, int di
,
301 enum stone seq_color
)
303 #define LTREE_DEBUG if (UDEBUGL(6))
305 /* Ignore pass sequences. */
306 if (is_pass(node_coord(descent
[di
].node
)))
309 LTREE_DEBUG
board_print(endb
, stderr
);
310 LTREE_DEBUG
fprintf(stderr
, "recording local %s sequence: ",
311 stone2str(seq_color
));
313 /* Sequences starting deeper are less relevant in general. */
314 int pval
= LTREE_PLAYOUTS_MULTIPLIER
;
315 if (u
->local_tree
&& u
->local_tree_depth_decay
> 0)
316 pval
= ((floating_t
) pval
) / pow(u
->local_tree_depth_decay
, di
- 1);
318 LTREE_DEBUG
fprintf(stderr
, "too deep @%d\n", di
);
322 /* Pick the right local tree root... */
323 struct tree_node
*lnode
= seq_color
== S_BLACK
? t
->ltree_black
: t
->ltree_white
;
326 /* ...determine the sequence value... */
328 if (u
->local_tree_eval
!= LTE_EACH
) {
329 sval
= local_value(u
, endb
, node_coord(descent
[di
].node
), seq_color
);
330 LTREE_DEBUG
fprintf(stderr
, "(goal %s[%s %1.3f][%d]) ",
331 coord2sstr(node_coord(descent
[di
].node
), t
->board
),
332 stone2str(seq_color
), sval
, descent
[di
].node
->d
);
334 if (u
->local_tree_eval
== LTE_TOTAL
) {
336 while (di
< dlen
&& (di
== di0
|| descent
[di
].node
->d
< u
->tenuki_d
)) {
337 enum stone color
= (di
- di0
) % 2 ? stone_other(seq_color
) : seq_color
;
338 double rval
= local_value(u
, endb
, node_coord(descent
[di
].node
), color
);
344 sval
/= (di
- di0
+ 1);
349 /* ...and record the sequence. */
351 while (di
< dlen
&& !is_pass(node_coord(descent
[di
].node
))
352 && (di
== di0
|| descent
[di
].node
->d
< u
->tenuki_d
)) {
353 enum stone color
= (di
- di0
) % 2 ? stone_other(seq_color
) : seq_color
;
355 if (u
->local_tree_eval
!= LTE_EACH
)
358 rval
= local_value(u
, endb
, node_coord(descent
[di
].node
), color
);
359 LTREE_DEBUG
fprintf(stderr
, "%s[%s %1.3f][%d] ",
360 coord2sstr(node_coord(descent
[di
].node
), t
->board
),
361 stone2str(color
), rval
, descent
[di
].node
->d
);
362 lnode
= tree_get_node(t
, lnode
, node_coord(descent
[di
++].node
), true);
364 stats_add_result(&lnode
->u
, rval
, pval
);
367 /* Add lnode for tenuki (pass) if we descended further. */
369 double rval
= u
->local_tree_eval
!= LTE_EACH
? sval
: 0.5;
370 LTREE_DEBUG
fprintf(stderr
, "pass ");
371 lnode
= tree_get_node(t
, lnode
, pass
, true);
373 stats_add_result(&lnode
->u
, rval
, pval
);
376 LTREE_DEBUG
fprintf(stderr
, "\n");
381 uct_playout(struct uct
*u
, struct board
*b
, enum stone player_color
, struct tree
*t
)
386 struct playout_amafmap amaf
;
387 amaf
.gamelen
= amaf
.game_baselen
= 0;
389 /* Walk the tree until we find a leaf, then expand it and do
390 * a random playout. */
391 struct tree_node
*n
= t
->root
;
392 enum stone node_color
= stone_other(player_color
);
393 assert(node_color
== t
->root_color
);
395 /* Make sure the root node is expanded. */
396 if (tree_leaf_node(n
) && !__sync_lock_test_and_set(&n
->is_expanded
, 1))
397 tree_expand_node(t
, n
, &b2
, player_color
, u
, 1);
399 /* Tree descent history. */
400 /* XXX: This is somewhat messy since @n and descent[dlen-1].node are
402 struct uct_descent descent
[DESCENT_DLEN
];
403 descent
[0].node
= n
; descent
[0].lnode
= NULL
;
405 /* Total value of the sequence. */
406 struct move_stats seq_value
= { .playouts
= 0 };
407 /* The last "significant" node along the descent (i.e. node
408 * with higher than configured number of playouts). For black
410 struct tree_node
*significant
[2] = { NULL
, NULL
};
411 if (n
->u
.playouts
>= u
->significant_threshold
)
412 significant
[node_color
- 1] = n
;
415 int pass_limit
= (board_size(&b2
) - 2) * (board_size(&b2
) - 2) / 2;
416 int passes
= is_pass(b
->last_move
.coord
) && b
->moves
> 0;
419 static char spaces
[] = "\0 ";
422 fprintf(stderr
, "--- UCT walk with color %d\n", player_color
);
424 while (!tree_leaf_node(n
) && passes
< 2) {
425 spaces
[dlen
- 1] = ' '; spaces
[dlen
] = 0;
428 /*** Choose a node to descend to: */
430 /* Parity is chosen already according to the child color, since
431 * it is applied to children. */
432 node_color
= stone_other(node_color
);
433 int parity
= (node_color
== player_color
? 1 : -1);
435 assert(dlen
< DESCENT_DLEN
);
436 descent
[dlen
] = descent
[dlen
- 1];
437 if (u
->local_tree
&& (!descent
[dlen
].lnode
|| descent
[dlen
].node
->d
>= u
->tenuki_d
)) {
438 /* Start new local sequence. */
439 /* Remember that node_color already holds color of the
440 * to-be-found child. */
441 descent
[dlen
].lnode
= node_color
== S_BLACK
? t
->ltree_black
: t
->ltree_white
;
444 if (!u
->random_policy_chance
|| fast_random(u
->random_policy_chance
))
445 u
->policy
->descend(u
->policy
, t
, &descent
[dlen
], parity
, b2
.moves
> pass_limit
);
447 u
->random_policy
->descend(u
->random_policy
, t
, &descent
[dlen
], parity
, b2
.moves
> pass_limit
);
450 /*** Perform the descent: */
452 if (descent
[dlen
].node
->u
.playouts
>= u
->significant_threshold
) {
453 significant
[node_color
- 1] = descent
[dlen
].node
;
456 seq_value
.playouts
+= descent
[dlen
].value
.playouts
;
457 seq_value
.value
+= descent
[dlen
].value
.value
* descent
[dlen
].value
.playouts
;
458 n
= descent
[dlen
++].node
;
459 assert(n
== t
->root
|| n
->parent
);
461 fprintf(stderr
, "%s+-- UCT sent us to [%s:%d] %d,%f\n",
462 spaces
, coord2sstr(node_coord(n
), t
->board
),
463 node_coord(n
), n
->u
.playouts
,
464 tree_node_get_value(t
, parity
, n
->u
.value
));
466 /* Add virtual loss if we need to; this is used to discourage
467 * other threads from visiting this node in case of multiple
468 * threads doing the tree search. */
470 stats_add_result(&n
->u
, node_color
== S_BLACK
? 0.0 : 1.0, u
->virtual_loss
);
472 struct move m
= { node_coord(n
), node_color
};
473 int res
= board_play(&b2
, &m
);
475 if (res
< 0 || (!is_pass(m
.coord
) && !group_at(&b2
, m
.coord
)) /* suicide */
476 || b2
.superko_violation
) {
478 for (struct tree_node
*ni
= n
; ni
; ni
= ni
->parent
)
479 fprintf(stderr
, "%s<%"PRIhash
"> ", coord2sstr(node_coord(ni
), t
->board
), ni
->hash
);
480 fprintf(stderr
, "marking invalid %s node %d,%d res %d group %d spk %d\n",
481 stone2str(node_color
), coord_x(node_coord(n
),b
), coord_y(node_coord(n
),b
),
482 res
, group_at(&b2
, m
.coord
), b2
.superko_violation
);
484 n
->hints
|= TREE_HINT_INVALID
;
489 assert(node_coord(n
) >= -1);
490 record_amaf_move(&amaf
, node_coord(n
), board_playing_ko_threat(&b2
));
492 if (is_pass(node_coord(n
)))
497 enum stone next_color
= stone_other(node_color
);
498 /* We need to make sure only one thread expands the node. If
499 * we are unlucky enough for two threads to meet in the same
500 * node, the latter one will simply do another simulation from
501 * the node itself, no big deal. t->nodes_size may exceed
502 * the maximum in multi-threaded case but not by much so it's ok.
503 * The size test must be before the test&set not after, to allow
504 * expansion of the node later if enough nodes have been freed. */
505 if (tree_leaf_node(n
)
506 && n
->u
.playouts
- u
->virtual_loss
>= u
->expand_p
&& t
->nodes_size
< u
->max_tree_size
507 && !__sync_lock_test_and_set(&n
->is_expanded
, 1))
508 tree_expand_node(t
, n
, &b2
, next_color
, u
, -parity
);
511 amaf
.game_baselen
= amaf
.gamelen
;
513 if (t
->use_extra_komi
&& u
->dynkomi
->persim
) {
514 b2
.komi
+= round(u
->dynkomi
->persim(u
->dynkomi
, &b2
, t
, n
));
518 /* XXX: No dead groups support. */
519 floating_t score
= board_official_score(&b2
, NULL
);
520 /* Result from black's perspective (no matter who
521 * the player; black's perspective is always
522 * what the tree stores. */
523 result
= - (score
* 2);
526 fprintf(stderr
, "[%d..%d] %s p-p scoring playout result %d (W %f)\n",
527 player_color
, node_color
, coord2sstr(node_coord(n
), t
->board
), result
, score
);
529 board_print(&b2
, stderr
);
531 board_ownermap_fill(&u
->ownermap
, &b2
);
533 } else { // assert(tree_leaf_node(n));
534 /* In case of parallel tree search, the assertion might
535 * not hold if two threads chew on the same node. */
536 result
= uct_leaf_node(u
, &b2
, player_color
, &amaf
, descent
, &dlen
, significant
, t
, n
, node_color
, spaces
);
539 if (u
->policy
->wants_amaf
&& u
->playout_amaf_cutoff
) {
540 unsigned int cutoff
= amaf
.game_baselen
;
541 cutoff
+= (amaf
.gamelen
- amaf
.game_baselen
) * u
->playout_amaf_cutoff
/ 100;
542 amaf
.gamelen
= cutoff
;
545 /* Record the result. */
547 assert(n
== t
->root
|| n
->parent
);
548 floating_t rval
= scale_value(u
, b
, result
);
549 u
->policy
->update(u
->policy
, t
, n
, node_color
, player_color
, &amaf
, &b2
, rval
);
551 stats_add_result(&t
->avg_score
, result
/ 2, 1);
552 if (t
->use_extra_komi
) {
553 stats_add_result(&u
->dynkomi
->score
, result
/ 2, 1);
554 stats_add_result(&u
->dynkomi
->value
, rval
, 1);
557 if (u
->local_tree
&& n
->parent
&& !is_pass(node_coord(n
)) && dlen
> 0) {
558 /* Get the local sequences and record them in ltree. */
559 /* We will look for sequence starts in our descent
560 * history, then run record_local_sequence() for each
561 * found sequence start; record_local_sequence() may
562 * pick longer sequences from descent history then,
563 * which is expected as it will create new lnodes. */
564 enum stone seq_color
= player_color
;
565 /* First move always starts a sequence. */
566 record_local_sequence(u
, t
, &b2
, descent
, dlen
, 1, seq_color
);
567 seq_color
= stone_other(seq_color
);
568 for (int dseqi
= 2; dseqi
< dlen
; dseqi
++, seq_color
= stone_other(seq_color
)) {
569 if (u
->local_tree_allseq
) {
570 /* We are configured to record all subsequences. */
571 record_local_sequence(u
, t
, &b2
, descent
, dlen
, dseqi
, seq_color
);
574 if (descent
[dseqi
].node
->d
>= u
->tenuki_d
) {
575 /* Tenuki! Record the fresh sequence. */
576 record_local_sequence(u
, t
, &b2
, descent
, dlen
, dseqi
, seq_color
);
579 if (descent
[dseqi
].lnode
&& !descent
[dseqi
].lnode
) {
580 /* Record result for in-descent picked sequence. */
581 record_local_sequence(u
, t
, &b2
, descent
, dlen
, dseqi
, seq_color
);
588 /* We need to undo the virtual loss we added during descend. */
589 if (u
->virtual_loss
) {
590 floating_t loss
= node_color
== S_BLACK
? 0.0 : 1.0;
591 for (; n
->parent
; n
= n
->parent
) {
592 stats_rm_result(&n
->u
, loss
, u
->virtual_loss
);
597 board_done_noalloc(&b2
);
602 uct_playouts(struct uct
*u
, struct board
*b
, enum stone color
, struct tree
*t
, struct time_info
*ti
)
605 if (ti
&& ti
->dim
== TD_GAMES
) {
606 for (i
= 0; t
->root
->u
.playouts
<= ti
->len
.games
&& !uct_halt
; i
++)
607 uct_playout(u
, b
, color
, t
);
609 for (i
= 0; !uct_halt
; i
++)
610 uct_playout(u
, b
, color
, t
);