joseki*.dict: Skip lines starting with #
[pachi/derm.git] / uct / walk.c
blob93cf127a53164218c544910c8484d35c06afbf42
1 #include <assert.h>
2 #include <math.h>
3 #include <pthread.h>
4 #include <signal.h>
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
9 #define DEBUG
11 #include "debug.h"
12 #include "board.h"
13 #include "move.h"
14 #include "playout.h"
15 #include "playout/elo.h"
16 #include "probdist.h"
17 #include "random.h"
18 #include "uct/dynkomi.h"
19 #include "uct/internal.h"
20 #include "uct/search.h"
21 #include "uct/tree.h"
22 #include "uct/uct.h"
23 #include "uct/walk.h"
25 void
26 uct_progress_status(struct uct *u, struct tree *t, enum stone color, int playouts)
28 if (!UDEBUGL(0))
29 return;
31 /* Best move */
32 struct tree_node *best = u->policy->choose(u->policy, t->root, t->board, color, resign);
33 if (!best) {
34 fprintf(stderr, "... No moves left\n");
35 return;
37 fprintf(stderr, "[%d] ", playouts);
38 fprintf(stderr, "best %f ", tree_node_get_value(t, 1, best->u.value));
40 /* Dynamic komi */
41 if (t->use_extra_komi)
42 fprintf(stderr, "komi %.1f ", t->extra_komi);
44 /* Best sequence */
45 fprintf(stderr, "| seq ");
46 for (int depth = 0; depth < 4; depth++) {
47 if (best && best->u.playouts >= 25) {
48 fprintf(stderr, "%3s ", coord2sstr(best->coord, t->board));
49 best = u->policy->choose(u->policy, best, t->board, color, resign);
50 } else {
51 fprintf(stderr, " ");
55 /* Best candidates */
56 fprintf(stderr, "| can ");
57 int cans = 4;
58 struct tree_node *can[cans];
59 memset(can, 0, sizeof(can));
60 best = t->root->children;
61 while (best) {
62 int c = 0;
63 while ((!can[c] || best->u.playouts > can[c]->u.playouts) && ++c < cans);
64 for (int d = 0; d < c; d++) can[d] = can[d + 1];
65 if (c > 0) can[c - 1] = best;
66 best = best->sibling;
68 while (--cans >= 0) {
69 if (can[cans]) {
70 fprintf(stderr, "%3s(%.3f) ",
71 coord2sstr(can[cans]->coord, t->board),
72 tree_node_get_value(t, 1, can[cans]->u.value));
73 } else {
74 fprintf(stderr, " ");
78 fprintf(stderr, "\n");
82 static void
83 record_amaf_move(struct playout_amafmap *amaf, coord_t coord, enum stone color)
85 if (amaf->map[coord] == S_NONE || amaf->map[coord] == color) {
86 amaf->map[coord] = color;
87 } else { // XXX: Respect amaf->record_nakade
88 amaf_op(amaf->map[coord], +);
90 amaf->game[amaf->gamelen].coord = coord;
91 amaf->game[amaf->gamelen].color = color;
92 amaf->gamelen++;
93 assert(amaf->gamelen < sizeof(amaf->game) / sizeof(amaf->game[0]));
96 static double
97 ltree_node_gamma(struct tree_node *li, enum stone color)
99 /* TODO: How to do this? */
100 #define li_value(color, li) (li->u.playouts * (color == S_BLACK ? li->u.value : (1 - li->u.value)))
101 return 0.5 + li_value(color, li);
105 struct uct_playout_callback {
106 struct uct *uct;
107 struct tree *tree;
108 struct tree_node *lnode;
111 static void
112 uct_playout_probdist(void *data, struct board *b, enum stone to_play, struct probdist *pd)
114 /* Create probability distribution according to found local tree
115 * sequence. */
116 struct uct_playout_callback *upc = data;
117 assert(upc && upc->tree && pd && b);
118 coord_t c = b->last_move.coord;
119 enum stone color = b->last_move.color;
121 if (is_pass(c)) {
122 /* Break local sequence. */
123 upc->lnode = NULL;
124 } else if (upc->lnode) {
125 /* Try to follow local sequence. */
126 upc->lnode = tree_get_node(upc->tree, upc->lnode, c, false);
129 if (!upc->lnode || !upc->lnode->children) {
130 /* There's no local sequence, start new one! */
131 upc->lnode = color == S_BLACK ? upc->tree->ltree_black : upc->tree->ltree_white;
132 upc->lnode = tree_get_node(upc->tree, upc->lnode, c, false);
135 if (!upc->lnode || !upc->lnode->children) {
136 /* We have no local sequence and we cannot find any starting
137 * by node corresponding to last move. */
138 if (!upc->uct->local_tree_pseqroot) {
139 /* Give up then, we have nothing to contribute. */
140 return;
142 /* Construct probability distribution from possible first
143 * sequence move. Remember that @color is color of the
144 * *last* move. */
145 upc->lnode = color == S_BLACK ? upc->tree->ltree_white : upc->tree->ltree_black;
146 if (!upc->lnode->children) {
147 /* We don't even have anything in our tree yet. */
148 return;
152 /* The probdist has the right structure only if BOARD_GAMMA is defined. */
153 #ifndef BOARD_GAMMA
154 assert(0);
155 #endif
157 /* Construct probability distribution from lnode children. */
158 struct tree_node *li = upc->lnode->children;
159 assert(li);
160 if (is_pass(li->coord)) {
161 /* Tenuki. */
162 /* TODO: Spread tenuki gamma over all moves we don't touch. */
163 li = li->sibling;
165 for (; li; li = li->sibling) {
166 if (board_at(b, li->coord) != S_NONE)
167 continue;
168 double gamma = fixp_to_double(pd->items[li->coord]) * ltree_node_gamma(li, to_play);
169 probdist_set(pd, li->coord, double_to_fixp(gamma));
174 static int
175 uct_leaf_node(struct uct *u, struct board *b, enum stone player_color,
176 struct playout_amafmap *amaf,
177 struct tree *t, struct tree_node *n, enum stone node_color,
178 char *spaces)
180 enum stone next_color = stone_other(node_color);
181 int parity = (next_color == player_color ? 1 : -1);
183 /* We need to make sure only one thread expands the node. If
184 * we are unlucky enough for two threads to meet in the same
185 * node, the latter one will simply do another simulation from
186 * the node itself, no big deal. t->nodes_size may exceed
187 * the maximum in multi-threaded case but not by much so it's ok.
188 * The size test must be before the test&set not after, to allow
189 * expansion of the node later if enough nodes have been freed. */
190 if (n->u.playouts >= u->expand_p && t->nodes_size < u->max_tree_size
191 && !__sync_lock_test_and_set(&n->is_expanded, 1)) {
192 tree_expand_node(t, n, b, next_color, u, parity);
194 if (UDEBUGL(7))
195 fprintf(stderr, "%s*-- UCT playout #%d start [%s] %f\n",
196 spaces, n->u.playouts, coord2sstr(n->coord, t->board),
197 tree_node_get_value(t, parity, n->u.value));
199 /* TODO: Don't necessarily restart the sequence walk when entering
200 * playout. */
201 struct uct_playout_callback upc = { .uct = u, .tree = t, .lnode = NULL };
202 if (u->local_tree_playout) {
203 /* N.B.: We know this is ELO playout. */
204 playout_elo_callback(u->playout, uct_playout_probdist, &upc);
207 struct playout_setup ps = { .gamelen = u->gamelen, .mercymin = u->mercymin };
208 int result = play_random_game(&ps, b, next_color,
209 u->playout_amaf ? amaf : NULL,
210 &u->ownermap, u->playout);
211 if (next_color == S_WHITE) {
212 /* We need the result from black's perspective. */
213 result = - result;
215 if (UDEBUGL(7))
216 fprintf(stderr, "%s -- [%d..%d] %s random playout result %d\n",
217 spaces, player_color, next_color, coord2sstr(n->coord, t->board), result);
219 return result;
222 static float
223 scale_value(struct uct *u, struct board *b, int result)
225 float rval = result > 0;
226 if (u->val_scale) {
227 int vp = u->val_points;
228 if (!vp) {
229 vp = board_size(b) - 1; vp *= vp; vp *= 2;
232 float sval = (float) abs(result) / vp;
233 sval = sval > 1 ? 1 : sval;
234 if (result < 0) sval = 1 - sval;
235 if (u->val_extra)
236 rval += u->val_scale * sval;
237 else
238 rval = (1 - u->val_scale) * rval + u->val_scale * sval;
239 // fprintf(stderr, "score %d => sval %f, rval %f\n", result, sval, rval);
241 return rval;
244 static void
245 record_local_sequence(struct uct *u, struct tree *t,
246 struct uct_descent *descent, int dlen, int di,
247 enum stone seq_color, float rval)
249 /* Ignore pass sequences. */
250 if (is_pass(descent[di].node->coord))
251 return;
253 #define LTREE_DEBUG if (UDEBUGL(6))
254 LTREE_DEBUG fprintf(stderr, "recording result %f in local %s sequence: ",
255 rval, stone2str(seq_color));
256 int di0 = di;
258 /* Pick the right local tree root... */
259 struct tree_node *lnode = seq_color == S_BLACK ? t->ltree_black : t->ltree_white;
260 lnode->u.playouts++;
262 /* ...and record the sequence. */
263 while (di < dlen && (di == di0 || descent[di].node->d < u->tenuki_d)) {
264 LTREE_DEBUG fprintf(stderr, "%s[%d] ",
265 coord2sstr(descent[di].node->coord, t->board),
266 descent[di].node->d);
267 lnode = tree_get_node(t, lnode, descent[di++].node->coord, true);
268 assert(lnode);
269 stats_add_result(&lnode->u, rval, 1);
272 /* Add lnode for tenuki (pass) if we descended further. */
273 if (di < dlen) {
274 LTREE_DEBUG fprintf(stderr, "pass ");
275 lnode = tree_get_node(t, lnode, pass, true);
276 assert(lnode);
277 stats_add_result(&lnode->u, rval, 1);
280 LTREE_DEBUG fprintf(stderr, "\n");
285 uct_playout(struct uct *u, struct board *b, enum stone player_color, struct tree *t)
287 struct board b2;
288 board_copy(&b2, b);
290 struct playout_amafmap *amaf = NULL;
291 if (u->policy->wants_amaf) {
292 amaf = calloc2(1, sizeof(*amaf));
293 amaf->map = calloc2(board_size2(&b2) + 1, sizeof(*amaf->map));
294 amaf->map++; // -1 is pass
297 /* Walk the tree until we find a leaf, then expand it and do
298 * a random playout. */
299 struct tree_node *n = t->root;
300 enum stone node_color = stone_other(player_color);
301 assert(node_color == t->root_color);
303 /* Tree descent history. */
304 /* XXX: This is somewhat messy since @n and descent[dlen-1].node are
305 * redundant. */
306 #define DLEN 512
307 struct uct_descent descent[DLEN];
308 descent[0].node = n; descent[0].lnode = NULL;
309 int dlen = 1;
310 /* Total value of the sequence. */
311 struct move_stats seq_value = { .playouts = 0 };
313 int result;
314 int pass_limit = (board_size(&b2) - 2) * (board_size(&b2) - 2) / 2;
315 int passes = is_pass(b->last_move.coord) && b->moves > 0;
317 /* debug */
318 int depth = 0;
319 static char spaces[] = "\0 ";
320 /* /debug */
321 if (UDEBUGL(8))
322 fprintf(stderr, "--- UCT walk with color %d\n", player_color);
324 while (!tree_leaf_node(n) && passes < 2) {
325 spaces[depth++] = ' '; spaces[depth] = 0;
328 /*** Choose a node to descend to: */
330 /* Parity is chosen already according to the child color, since
331 * it is applied to children. */
332 node_color = stone_other(node_color);
333 int parity = (node_color == player_color ? 1 : -1);
335 assert(dlen < DLEN);
336 descent[dlen] = descent[dlen - 1];
337 if (u->local_tree && (!descent[dlen].lnode || descent[dlen].node->d >= u->tenuki_d)) {
338 /* Start new local sequence. */
339 /* Remember that node_color already holds color of the
340 * to-be-found child. */
341 descent[dlen].lnode = node_color == S_BLACK ? t->ltree_black : t->ltree_white;
344 if (!u->random_policy_chance || fast_random(u->random_policy_chance))
345 u->policy->descend(u->policy, t, &descent[dlen], parity, b2.moves > pass_limit);
346 else
347 u->random_policy->descend(u->random_policy, t, &descent[dlen], parity, b2.moves > pass_limit);
350 /*** Perform the descent: */
352 seq_value.playouts += descent[dlen].value.playouts;
353 seq_value.value += descent[dlen].value.value * descent[dlen].value.playouts;
354 n = descent[dlen++].node;
355 assert(n == t->root || n->parent);
356 if (UDEBUGL(7))
357 fprintf(stderr, "%s+-- UCT sent us to [%s:%d] %f\n",
358 spaces, coord2sstr(n->coord, t->board), n->coord,
359 tree_node_get_value(t, parity, n->u.value));
361 /* Add virtual loss if we need to; this is used to discourage
362 * other threads from visiting this node in case of multiple
363 * threads doing the tree search. */
364 if (u->virtual_loss)
365 stats_add_result(&n->u, tree_parity(t, parity) > 0 ? 0 : 1, 1);
367 assert(n->coord >= -1);
368 if (amaf && !is_pass(n->coord))
369 record_amaf_move(amaf, n->coord, node_color);
371 struct move m = { n->coord, node_color };
372 int res = board_play(&b2, &m);
374 if (res < 0 || (!is_pass(m.coord) && !group_at(&b2, m.coord)) /* suicide */
375 || b2.superko_violation) {
376 if (UDEBUGL(4)) {
377 for (struct tree_node *ni = n; ni; ni = ni->parent)
378 fprintf(stderr, "%s<%"PRIhash"> ", coord2sstr(ni->coord, t->board), ni->hash);
379 fprintf(stderr, "marking invalid %s node %d,%d res %d group %d spk %d\n",
380 stone2str(node_color), coord_x(n->coord,b), coord_y(n->coord,b),
381 res, group_at(&b2, m.coord), b2.superko_violation);
383 n->hints |= TREE_HINT_INVALID;
384 result = 0;
385 goto end;
388 if (is_pass(n->coord))
389 passes++;
390 else
391 passes = 0;
394 if (amaf) {
395 amaf->game_baselen = amaf->gamelen;
396 amaf->record_nakade = u->playout_amaf_nakade;
399 if (t->use_extra_komi && u->dynkomi->persim) {
400 b2.komi += round(u->dynkomi->persim(u->dynkomi, &b2, t, n));
403 if (passes >= 2) {
404 /* XXX: No dead groups support. */
405 float score = board_official_score(&b2, NULL);
406 /* Result from black's perspective (no matter who
407 * the player; black's perspective is always
408 * what the tree stores. */
409 result = - (score * 2);
411 if (UDEBUGL(5))
412 fprintf(stderr, "[%d..%d] %s p-p scoring playout result %d (W %f)\n",
413 player_color, node_color, coord2sstr(n->coord, t->board), result, score);
414 if (UDEBUGL(6))
415 board_print(&b2, stderr);
417 board_ownermap_fill(&u->ownermap, &b2);
419 } else { // assert(tree_leaf_node(n));
420 /* In case of parallel tree search, the assertion might
421 * not hold if two threads chew on the same node. */
422 result = uct_leaf_node(u, &b2, player_color, amaf, t, n, node_color, spaces);
425 if (amaf && u->playout_amaf_cutoff) {
426 unsigned int cutoff = amaf->game_baselen;
427 cutoff += (amaf->gamelen - amaf->game_baselen) * u->playout_amaf_cutoff / 100;
428 /* Now, reconstruct the amaf map. */
429 memset(amaf->map, 0, board_size2(&b2) * sizeof(*amaf->map));
430 for (unsigned int i = 0; i < cutoff; i++) {
431 coord_t coord = amaf->game[i].coord;
432 enum stone color = amaf->game[i].color;
433 if (amaf->map[coord] == S_NONE || amaf->map[coord] == color) {
434 amaf->map[coord] = color;
435 /* Nakade always recorded for in-tree part */
436 } else if (amaf->record_nakade || i <= amaf->game_baselen) {
437 amaf_op(amaf->map[n->coord], +);
442 assert(n == t->root || n->parent);
443 if (result != 0) {
444 float rval = scale_value(u, b, result);
445 u->policy->update(u->policy, t, n, node_color, player_color, amaf, rval);
447 if (t->use_extra_komi) {
448 stats_add_result(&u->dynkomi->score, result / 2, 1);
449 stats_add_result(&u->dynkomi->value, rval, 1);
452 if (u->local_tree && n->parent && !is_pass(n->coord) && dlen > 0) {
453 /* Possibly transform the rval appropriately. */
454 float expval = seq_value.value / seq_value.playouts;
455 rval = stats_temper_value(rval, expval, u->local_tree);
457 /* Get the local sequences and record them in ltree. */
458 /* We will look for sequence starts in our descent
459 * history, then run record_local_sequence() for each
460 * found sequence start; record_local_sequence() may
461 * pick longer sequences from descent history then,
462 * which is expected as it will create new lnodes. */
463 enum stone seq_color = player_color;
464 /* First move always starts a sequence. */
465 record_local_sequence(u, t, descent, dlen, 1, seq_color, rval);
466 seq_color = stone_other(seq_color);
467 for (int dseqi = 2; dseqi < dlen; dseqi++, seq_color = stone_other(seq_color)) {
468 if (u->local_tree_allseq) {
469 /* We are configured to record all subsequences. */
470 record_local_sequence(u, t, descent, dlen, dseqi, seq_color, rval);
471 continue;
473 if (descent[dseqi].node->d >= u->tenuki_d) {
474 /* Tenuki! Record the fresh sequence. */
475 record_local_sequence(u, t, descent, dlen, dseqi, seq_color, rval);
476 continue;
478 if (descent[dseqi].lnode && !descent[dseqi].lnode) {
479 /* Record result for in-descent picked sequence. */
480 record_local_sequence(u, t, descent, dlen, dseqi, seq_color, rval);
481 continue;
487 end:
488 /* We need to undo the virtual loss we added during descend. */
489 if (u->virtual_loss) {
490 int parity = (node_color == player_color ? 1 : -1);
491 for (; n->parent; n = n->parent) {
492 stats_rm_result(&n->u, tree_parity(t, parity) > 0 ? 0 : 1, 1);
493 parity = -parity;
497 if (amaf) {
498 free(amaf->map - 1);
499 free(amaf);
501 board_done_noalloc(&b2);
502 return result;
506 uct_playouts(struct uct *u, struct board *b, enum stone color, struct tree *t)
508 int i;
509 for (i = 0; !uct_halt; i++)
510 uct_playout(u, b, color, t);
511 return i;