17 #include "uct/internal.h"
18 #include "uct/prior.h"
22 /* Allocate one node in the fast_alloc mode. The returned node
23 * is _not_ initialized. Returns NULL if not enough memory.
24 * This function may be called by multiple threads in parallel. */
25 static struct tree_node
*
26 tree_fast_alloc_node(struct tree
*t
)
28 assert(t
->nodes
!= NULL
);
29 struct tree_node
*n
= NULL
;
30 unsigned long old_size
=__sync_fetch_and_add(&t
->nodes_size
, sizeof(*n
));
32 /* The test below works even if max_tree_size is not a
33 * multiple of the node size because tree_init() allocates
34 * space for an extra node. */
35 if (old_size
< t
->max_tree_size
)
36 n
= (struct tree_node
*)(t
->nodes
+ old_size
);
40 /* Allocate and initialize a node. Returns NULL (fast_alloc mode)
41 * or exits the main program if not enough memory.
42 * This function may be called by multiple threads in parallel. */
43 static struct tree_node
*
44 tree_init_node(struct tree
*t
, coord_t coord
, int depth
, bool fast_alloc
)
48 n
= tree_fast_alloc_node(t
);
50 memset(n
, 0, sizeof(*n
));
52 n
= calloc(1, sizeof(*n
));
54 fprintf(stderr
, "tree_init_node(): OUT OF MEMORY\n");
57 __sync_fetch_and_add(&t
->nodes_size
, sizeof(*n
));
61 volatile static long c
= 1000000;
62 n
->hash
= __sync_fetch_and_add(&c
, 1);
63 if (depth
> t
->max_depth
)
68 /* Create a tree structure. Pre-allocate all nodes if max_tree_size is > 0. */
70 tree_init(struct board
*board
, enum stone color
, unsigned long max_tree_size
, float ltree_aging
)
72 struct tree
*t
= calloc(1, sizeof(*t
));
74 t
->max_tree_size
= max_tree_size
;
75 if (max_tree_size
!= 0) {
76 /* Allocate one extra node, max_tree_size may not be multiple of node size. */
77 t
->nodes
= malloc(max_tree_size
+ sizeof(struct tree_node
));
78 /* The nodes buffer doesn't need initialization. This is currently
79 * done by tree_init_node to spread the load. Doing a memset for the
80 * entire buffer here would be too slow for large trees (>10 GB). */
82 fprintf(stderr
, "tree_init(): OUT OF MEMORY\n");
86 /* The root PASS move is only virtual, we never play it. */
87 t
->root
= tree_init_node(t
, pass
, 0, t
->nodes
);
88 t
->root_symmetry
= board
->symmetry
;
89 t
->root_color
= stone_other(color
); // to research black moves, root will be white
91 t
->ltree_black
= tree_init_node(t
, pass
, 0, false);
92 t
->ltree_white
= tree_init_node(t
, pass
, 0, false);
93 t
->ltree_aging
= ltree_aging
;
98 /* This function may be called by multiple threads in parallel on the
99 * same tree, but not on node n. n may be detached from the tree but
100 * must have been created in this tree originally.
101 * It returns the remaining size of the tree after n has been freed. */
103 tree_done_node(struct tree
*t
, struct tree_node
*n
)
105 struct tree_node
*ni
= n
->children
;
107 struct tree_node
*nj
= ni
->sibling
;
108 tree_done_node(t
, ni
);
112 unsigned long old_size
= __sync_fetch_and_sub(&t
->nodes_size
, sizeof(*n
));
113 return old_size
- sizeof(*n
);
121 /* Worker thread for tree_done_node_detached(). Only for fast_alloc=false. */
123 tree_done_node_worker(void *ctx_
)
125 struct subtree_ctx
*ctx
= ctx_
;
126 char *str
= coord2str(ctx
->n
->coord
, ctx
->t
->board
);
128 unsigned long tree_size
= tree_done_node(ctx
->t
, ctx
->n
);
132 fprintf(stderr
, "done freeing node at %s, tree size %lu\n", str
, tree_size
);
138 /* Asynchronously free the subtree of nodes rooted at n. If the tree becomes
139 * empty free the tree also. Only for fast_alloc=false. */
141 tree_done_node_detached(struct tree
*t
, struct tree_node
*n
)
143 if (n
->u
.playouts
< 1000) { // no thread for small tree
144 if (!tree_done_node(t
, n
))
149 pthread_attr_init(&attr
);
150 pthread_attr_setdetachstate(&attr
, PTHREAD_CREATE_DETACHED
);
153 struct subtree_ctx
*ctx
= malloc(sizeof(struct subtree_ctx
));
155 fprintf(stderr
, "tree_done_node_detached(): OUT OF MEMORY\n");
160 pthread_create(&thread
, &attr
, tree_done_node_worker
, ctx
);
161 pthread_attr_destroy(&attr
);
165 tree_done(struct tree
*t
)
167 tree_done_node(t
, t
->ltree_black
);
168 tree_done_node(t
, t
->ltree_white
);
172 } else if (!tree_done_node(t
, t
->root
)) {
174 /* A tree_done_node_worker might still be running on this tree but
175 * it will free the tree later. It is also freeing nodes faster than
176 * we will create new ones. */
182 tree_node_dump(struct tree
*tree
, struct tree_node
*node
, int l
, int thres
)
184 for (int i
= 0; i
< l
; i
++) fputc(' ', stderr
);
186 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
188 /* We use 1 as parity, since for all nodes we want to know the
189 * win probability of _us_, not the node color. */
190 fprintf(stderr
, "[%s] %f %% %d [prior %f %% %d amaf %f %% %d]; hints %x; %d children <%"PRIhash
">\n",
191 coord2sstr(node
->coord
, tree
->board
),
192 tree_node_get_value(tree
, 1, node
->u
.value
), node
->u
.playouts
,
193 tree_node_get_value(tree
, 1, node
->prior
.value
), node
->prior
.playouts
,
194 tree_node_get_value(tree
, 1, node
->amaf
.value
), node
->amaf
.playouts
,
195 node
->hints
, children
, node
->hash
);
197 /* Print nodes sorted by #playouts. */
199 struct tree_node
*nbox
[1000]; int nboxl
= 0;
200 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
201 if (ni
->u
.playouts
> thres
)
206 for (int i
= 0; i
< nboxl
; i
++)
207 if (nbox
[i
] && (best
< 0 || nbox
[i
]->u
.playouts
> nbox
[best
]->u
.playouts
))
211 tree_node_dump(tree
, nbox
[best
], l
+ 1, /* node->u.value < 0.1 ? 0 : */ thres
);
217 tree_dump(struct tree
*tree
, int thres
)
219 if (thres
&& tree
->root
->u
.playouts
/ thres
> 100) {
220 /* Be a bit sensible about this; the opening book can create
221 * huge dumps at first. */
222 thres
= tree
->root
->u
.playouts
/ 100 * (thres
< 1000 ? 1 : thres
/ 1000);
224 fprintf(stderr
, "(UCT tree; root %s; extra komi %f)\n",
225 stone2str(tree
->root_color
), tree
->extra_komi
);
226 tree_node_dump(tree
, tree
->root
, 0, thres
);
228 if (DEBUGL(3) && tree
->ltree_black
) {
229 fprintf(stderr
, "B local tree:\n");
230 tree_node_dump(tree
, tree
->ltree_black
, 0, thres
);
231 fprintf(stderr
, "W local tree:\n");
232 tree_node_dump(tree
, tree
->ltree_white
, 0, thres
);
238 tree_book_name(struct board
*b
)
240 static char buf
[256];
241 if (b
->handicap
> 0) {
242 sprintf(buf
, "uctbook-%d-%02.01f-h%d.pachitree", b
->size
- 2, b
->komi
, b
->handicap
);
244 sprintf(buf
, "uctbook-%d-%02.01f.pachitree", b
->size
- 2, b
->komi
);
250 tree_node_save(FILE *f
, struct tree_node
*node
, int thres
)
252 bool save_children
= node
->u
.playouts
>= thres
;
255 node
->is_expanded
= 0;
258 fwrite(((void *) node
) + offsetof(struct tree_node
, depth
),
259 sizeof(struct tree_node
) - offsetof(struct tree_node
, depth
),
263 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
264 tree_node_save(f
, ni
, thres
);
267 node
->is_expanded
= 1;
274 tree_save(struct tree
*tree
, struct board
*b
, int thres
)
276 char *filename
= tree_book_name(b
);
277 FILE *f
= fopen(filename
, "wb");
282 tree_node_save(f
, tree
->root
, thres
);
289 tree_node_load(FILE *f
, struct tree_node
*node
, int *num
)
293 fread(((void *) node
) + offsetof(struct tree_node
, depth
),
294 sizeof(struct tree_node
) - offsetof(struct tree_node
, depth
),
297 /* Keep values in sane scale, otherwise we start overflowing. */
298 #define MAX_PLAYOUTS 10000000
299 if (node
->u
.playouts
> MAX_PLAYOUTS
) {
300 node
->u
.playouts
= MAX_PLAYOUTS
;
302 if (node
->amaf
.playouts
> MAX_PLAYOUTS
) {
303 node
->amaf
.playouts
= MAX_PLAYOUTS
;
305 memcpy(&node
->pamaf
, &node
->amaf
, sizeof(node
->amaf
));
306 memcpy(&node
->pu
, &node
->u
, sizeof(node
->u
));
308 struct tree_node
*ni
= NULL
, *ni_prev
= NULL
;
310 ni_prev
= ni
; ni
= calloc(1, sizeof(*ni
));
314 ni_prev
->sibling
= ni
;
316 tree_node_load(f
, ni
, num
);
321 tree_load(struct tree
*tree
, struct board
*b
)
323 char *filename
= tree_book_name(b
);
324 FILE *f
= fopen(filename
, "rb");
328 fprintf(stderr
, "Loading opening book %s...\n", filename
);
332 tree_node_load(f
, tree
->root
, &num
);
333 fprintf(stderr
, "Loaded %d nodes.\n", num
);
339 static struct tree_node
*
340 tree_node_copy(struct tree_node
*node
)
342 struct tree_node
*n2
= malloc(sizeof(*n2
));
346 struct tree_node
*ni
= node
->children
;
347 struct tree_node
*ni2
= tree_node_copy(ni
);
348 n2
->children
= ni2
; ni2
->parent
= n2
;
349 while ((ni
= ni
->sibling
)) {
350 ni2
->sibling
= tree_node_copy(ni
);
351 ni2
= ni2
->sibling
; ni2
->parent
= n2
;
357 tree_copy(struct tree
*tree
)
359 assert(!tree
->nodes
);
360 struct tree
*t2
= malloc(sizeof(*t2
));
362 t2
->root
= tree_node_copy(tree
->root
);
366 /* Copy the subtree rooted at node: all nodes at or below depth
367 * or with at least threshold playouts. Only for fast_alloc.
368 * The code is destructive on src. The relative order of children of
369 * a given node is preserved (assumed by tree_get_node in particular).
370 * Returns the copy of node in the destination tree, or NULL
371 * if we could not copy it. */
372 static struct tree_node
*
373 tree_prune(struct tree
*dest
, struct tree
*src
, struct tree_node
*node
,
374 int threshold
, int depth
)
376 assert(dest
->nodes
&& node
);
377 struct tree_node
*n2
= tree_fast_alloc_node(dest
);
381 if (n2
->depth
> dest
->max_depth
)
382 dest
->max_depth
= n2
->depth
;
384 n2
->is_expanded
= false;
386 if (node
->depth
>= depth
&& node
->u
.playouts
< threshold
)
388 /* For deep nodes with many playouts, we must copy all children,
389 * even those with zero playouts, because partially expanded
390 * nodes are not supported. Considering them as fully expanded
391 * would degrade the playing strength. The only exception is
392 * when dest becomes full, but this should never happen in practice
393 * if threshold is chosen to limit the number of nodes traversed. */
394 struct tree_node
*ni
= node
->children
;
397 struct tree_node
**prev2
= &(n2
->children
);
399 struct tree_node
*ni2
= tree_prune(dest
, src
, ni
, threshold
, depth
);
402 prev2
= &(ni2
->sibling
);
407 n2
->is_expanded
= true;
409 n2
->children
= NULL
; // avoid partially expanded nodes
414 /* The following constants are used for garbage collection of nodes.
415 * A tree is considered large if the top node has >= 40K playouts.
416 * For such trees, we copy deep nodes only if they have >= 40 playouts.
417 * These constants define how much time we're willing to spend
418 * scanning the source tree when promoting a move. The values 40K
419 * and 40 makes worst case pruning in about 3s for 20 GB ram, and this
420 * is only for long thinking time (>1M playouts). For fast games the
421 * trees don't grow large. For small ram or fast game we copy the
422 * entire tree. These values do not degrade playing strength and are
423 * necessary to avoid losing on time; increasing MIN_DEEP_PLAYOUTS
424 * or decreasing LARGE_TREE_PLAYOUTS will make the program faster but
426 #define LARGE_TREE_PLAYOUTS 40000
427 #define MIN_DEEP_PLAYOUTS 40
429 /* Garbage collect the tree early if the top node has < 5K playouts,
430 * to avoid having to do it later on a large subtree.
431 * This guarantees garbage collection in < 1s. */
432 #define SMALL_TREE_PLAYOUTS 5000
434 /* Free all the tree, keeping only the subtree rooted at node.
435 * Prune the subtree if necessary to fit in max_size bytes or
436 * to save time scanning the tree.
437 * Returns the moved node. Only for fast_alloc. */
439 tree_garbage_collect(struct tree
*tree
, unsigned long max_size
, struct tree_node
*node
)
441 assert(tree
->nodes
&& !node
->parent
&& !node
->sibling
);
442 double start_time
= time_now();
444 struct tree
*temp_tree
= tree_init(tree
->board
, tree
->root_color
, max_size
, tree
->ltree_aging
);
445 temp_tree
->nodes_size
= 0; // We do not want the dummy pass node
446 struct tree_node
*temp_node
;
448 /* Find the maximum depth at which we can copy all nodes. */
450 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
452 unsigned long nodes_size
= max_nodes
* sizeof(*node
);
453 int max_depth
= node
->depth
;
454 while (nodes_size
< max_size
&& max_nodes
> 1) {
456 nodes_size
+= max_nodes
* nodes_size
;
460 /* Copy all nodes for small trees. For large trees, copy all nodes
461 * with depth <= max_depth, and all nodes with at least MIN_DEEP_PLAYOUTS.
462 * Avoiding going too deep (except for nodes with many playouts) is mostly
463 * to save time scanning the source tree. It can take over 20s to traverse
464 * completely a large source tree (20 GB) even without copying because
465 * the traversal is not friendly at all with the memory cache. */
466 if (node
->u
.playouts
< LARGE_TREE_PLAYOUTS
) {
467 temp_node
= tree_prune(temp_tree
, tree
, node
, 0, max_depth
+ 20);
469 temp_node
= tree_prune(temp_tree
, tree
, node
, MIN_DEEP_PLAYOUTS
, max_depth
);
473 /* Now copy back to original tree. */
474 tree
->nodes_size
= 0;
476 struct tree_node
*new_node
= tree_prune(tree
, temp_tree
, temp_node
, 0, temp_tree
->max_depth
);
479 double now
= time_now();
480 static double prev_time
;
481 if (!prev_time
) prev_time
= start_time
;
483 "tree pruned in %0.6g s, prev %0.3g s ago, dest depth %d wanted %d,"
484 " max_size %lu, pruned size %lu, playouts %d\n",
485 now
- start_time
, start_time
- prev_time
, temp_tree
->max_depth
, max_depth
,
486 max_size
, temp_tree
->nodes_size
, new_node
->u
.playouts
);
487 prev_time
= start_time
;
489 if (temp_tree
->nodes_size
>= temp_tree
->max_tree_size
) {
490 fprintf(stderr
, "temp tree overflow, increase max_tree_size %lu or MIN_FREE_MEM_PERCENT %d\n",
491 tree
->max_tree_size
, MIN_FREE_MEM_PERCENT
);
493 assert(tree
->nodes_size
== temp_tree
->nodes_size
);
494 assert(tree
->max_depth
== temp_tree
->max_depth
);
496 tree_done(temp_tree
);
502 tree_node_merge(struct tree_node
*dest
, struct tree_node
*src
)
504 /* Do not merge nodes that weren't touched at all. */
505 assert(dest
->pamaf
.playouts
== src
->pamaf
.playouts
);
506 assert(dest
->pu
.playouts
== src
->pu
.playouts
);
507 if (src
->amaf
.playouts
- src
->pamaf
.playouts
== 0
508 && src
->u
.playouts
- src
->pu
.playouts
== 0) {
512 dest
->hints
|= src
->hints
;
514 /* Merge the children, both are coord-sorted lists. */
515 struct tree_node
*di
= dest
->children
, **dref
= &dest
->children
;
516 struct tree_node
*si
= src
->children
, **sref
= &src
->children
;
518 if (di
->coord
!= si
->coord
) {
519 /* src has some extra items or misses di */
520 struct tree_node
*si2
= si
->sibling
;
521 while (si2
&& di
->coord
!= si2
->coord
) {
525 goto next_di
; /* src misses di, move on */
526 /* chain the extra [si,si2) items before di */
528 while (si
->sibling
!= si2
) {
537 /* Matching nodes - recurse... */
538 tree_node_merge(di
, si
);
539 /* ...and move on. */
540 sref
= &si
->sibling
; si
= si
->sibling
;
542 dref
= &di
->sibling
; di
= di
->sibling
;
545 /* Some outstanding nodes are left on src side, rechain
555 /* Priors should be constant. */
556 assert(dest
->prior
.playouts
== src
->prior
.playouts
&& dest
->prior
.value
== src
->prior
.value
);
558 stats_merge(&dest
->amaf
, &src
->amaf
);
559 stats_merge(&dest
->u
, &src
->u
);
562 /* Merge two trees built upon the same board. Note that the operation is
563 * destructive on src. */
565 tree_merge(struct tree
*dest
, struct tree
*src
)
567 if (src
->max_depth
> dest
->max_depth
)
568 dest
->max_depth
= src
->max_depth
;
569 tree_node_merge(dest
->root
, src
->root
);
574 tree_node_normalize(struct tree_node
*node
, int factor
)
576 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
577 tree_node_normalize(ni
, factor
);
579 #define normalize(s1, s2, t) node->s2.t = node->s1.t + (node->s2.t - node->s1.t) / factor;
580 normalize(pamaf
, amaf
, playouts
);
581 memcpy(&node
->pamaf
, &node
->amaf
, sizeof(node
->amaf
));
583 normalize(pu
, u
, playouts
);
584 memcpy(&node
->pu
, &node
->u
, sizeof(node
->u
));
588 /* Normalize a tree, dividing the amaf and u values by given
589 * factor; otherwise, simulations run in independent threads
590 * two trees built upon the same board. To correctly handle
591 * results taken from previous simulation run, they are backed
594 tree_normalize(struct tree
*tree
, int factor
)
596 tree_node_normalize(tree
->root
, factor
);
600 /* Get a node of given coordinate from within parent, possibly creating it
601 * if necessary - in a very raw form (no .d, priors, ...). */
602 /* FIXME: Adjust for board symmetry. */
604 tree_get_node(struct tree
*t
, struct tree_node
*parent
, coord_t c
, bool create
)
606 if (!parent
->children
|| parent
->children
->coord
>= c
) {
607 /* Special case: Insertion at the beginning. */
608 if (parent
->children
&& parent
->children
->coord
== c
)
609 return parent
->children
;
613 struct tree_node
*nn
= tree_init_node(t
, c
, parent
->depth
+ 1, false);
614 nn
->parent
= parent
; nn
->sibling
= parent
->children
;
615 parent
->children
= nn
;
619 /* No candidate at the beginning, look through all the children. */
621 struct tree_node
*ni
;
622 for (ni
= parent
->children
; ni
->sibling
; ni
= ni
->sibling
)
623 if (ni
->sibling
->coord
>= c
)
626 if (ni
->sibling
&& ni
->sibling
->coord
== c
)
628 assert(ni
->coord
< c
);
632 struct tree_node
*nn
= tree_init_node(t
, c
, parent
->depth
+ 1, false);
633 nn
->parent
= parent
; nn
->sibling
= ni
->sibling
; ni
->sibling
= nn
;
637 /* Get local tree node corresponding to given node, given local node child
638 * iterator @lni (which points either at the corresponding node, or at the
639 * nearest local tree node after @ni). */
641 tree_lnode_for_node(struct tree
*tree
, struct tree_node
*ni
, struct tree_node
*lni
, int tenuki_d
)
643 /* Now set up lnode, which is the actual local node
644 * corresponding to ni - either lni if it is an
645 * exact match and ni is not tenuki, <pass> local
646 * node if ni is tenuki, or NULL if there is no
647 * corresponding node available. */
649 if (is_pass(ni
->coord
)) {
650 /* Also, for sanity reasons we never use local
651 * tree for passes. (Maybe we could, but it's
652 * too hard to think about.) */
656 if (lni
->coord
== ni
->coord
) {
657 /* We don't consider tenuki a sequence play
658 * that we have in local tree even though
659 * ni->d is too high; this can happen if this
660 * occured in different board topology. */
664 if (ni
->d
>= tenuki_d
) {
665 /* Tenuki, pick a pass lsibling if available. */
666 assert(lni
->parent
&& lni
->parent
->children
);
667 if (is_pass(lni
->parent
->children
->coord
)) {
668 return lni
->parent
->children
;
674 /* No corresponding local node, lnode stays NULL. */
679 /* Tree symmetry: When possible, we will localize the tree to a single part
680 * of the board in tree_expand_node() and possibly flip along symmetry axes
681 * to another part of the board in tree_promote_at(). We follow b->symmetry
682 * guidelines here. */
685 /* This function must be thread safe, given that board b is only modified by the calling thread. */
687 tree_expand_node(struct tree
*t
, struct tree_node
*node
, struct board
*b
, enum stone color
, struct uct
*u
, int parity
)
689 /* Get a Common Fate Graph distance map from parent node. */
690 int distances
[board_size2(b
)];
691 if (!is_pass(b
->last_move
.coord
) && !is_resign(b
->last_move
.coord
)) {
692 cfg_distances(b
, node
->coord
, distances
, TREE_NODE_D_MAX
);
694 // Pass or resign - everything is too far.
695 foreach_point(b
) { distances
[c
] = TREE_NODE_D_MAX
+ 1; } foreach_point_end
;
698 /* Get a map of prior values to initialize the new nodes with. */
699 struct prior_map map
= {
702 .parity
= tree_parity(t
, parity
),
703 .distances
= distances
,
705 // Include pass in the prior map.
706 struct move_stats map_prior
[board_size2(b
) + 1]; map
.prior
= &map_prior
[1];
707 bool map_consider
[board_size2(b
) + 1]; map
.consider
= &map_consider
[1];
708 memset(map_prior
, 0, sizeof(map_prior
));
709 memset(map_consider
, 0, sizeof(map_consider
));
710 map
.consider
[pass
] = true;
712 if (board_at(b
, c
) != S_NONE
)
714 if (!board_is_valid_play(b
, color
, c
))
716 map
.consider
[c
] = true;
718 uct_prior(u
, node
, &map
);
720 /* Now, create the nodes. */
721 struct tree_node
*ni
= tree_init_node(t
, pass
, node
->depth
+ 1, t
->nodes
);
722 /* In fast_alloc mode we might temporarily run out of nodes but
723 * this should be rare if MIN_FREE_MEM_PERCENT is set correctly. */
725 node
->is_expanded
= false;
728 struct tree_node
*first_child
= ni
;
730 ni
->prior
= map
.prior
[pass
]; ni
->d
= TREE_NODE_D_MAX
+ 1;
732 /* The loop considers only the symmetry playground. */
734 fprintf(stderr
, "expanding %s within [%d,%d],[%d,%d] %d-%d\n",
735 coord2sstr(node
->coord
, b
),
736 b
->symmetry
.x1
, b
->symmetry
.y1
,
737 b
->symmetry
.x2
, b
->symmetry
.y2
,
738 b
->symmetry
.type
, b
->symmetry
.d
);
740 for (int j
= b
->symmetry
.y1
; j
<= b
->symmetry
.y2
; j
++) {
741 for (int i
= b
->symmetry
.x1
; i
<= b
->symmetry
.x2
; i
++) {
743 int x
= b
->symmetry
.type
== SYM_DIAG_DOWN
? board_size(b
) - 1 - i
: i
;
746 fprintf(stderr
, "drop %d,%d\n", i
, j
);
751 coord_t c
= coord_xy_otf(i
, j
, t
->board
);
752 if (!map
.consider
[c
]) // Filter out invalid moves
754 assert(c
!= node
->coord
); // I have spotted "C3 C3" in some sequence...
756 struct tree_node
*nj
= tree_init_node(t
, c
, node
->depth
+ 1, t
->nodes
);
758 node
->is_expanded
= false;
761 nj
->parent
= node
; ni
->sibling
= nj
; ni
= nj
;
763 ni
->prior
= map
.prior
[c
];
764 ni
->d
= distances
[c
];
767 node
->children
= first_child
; // must be done at the end to avoid race
772 flip_coord(struct board
*b
, coord_t c
,
773 bool flip_horiz
, bool flip_vert
, int flip_diag
)
775 int x
= coord_x(c
, b
), y
= coord_y(c
, b
);
777 int z
= x
; x
= y
; y
= z
;
780 x
= board_size(b
) - 1 - x
;
783 y
= board_size(b
) - 1 - y
;
785 return coord_xy_otf(x
, y
, b
);
789 tree_fix_node_symmetry(struct board
*b
, struct tree_node
*node
,
790 bool flip_horiz
, bool flip_vert
, int flip_diag
)
792 if (!is_pass(node
->coord
))
793 node
->coord
= flip_coord(b
, node
->coord
, flip_horiz
, flip_vert
, flip_diag
);
795 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
796 tree_fix_node_symmetry(b
, ni
, flip_horiz
, flip_vert
, flip_diag
);
800 tree_fix_symmetry(struct tree
*tree
, struct board
*b
, coord_t c
)
805 struct board_symmetry
*s
= &tree
->root_symmetry
;
806 int cx
= coord_x(c
, b
), cy
= coord_y(c
, b
);
808 /* playground X->h->v->d normalization
814 bool flip_horiz
= cx
< s
->x1
|| cx
> s
->x2
;
815 bool flip_vert
= cy
< s
->y1
|| cy
> s
->y2
;
819 bool dir
= (s
->type
== SYM_DIAG_DOWN
);
820 int x
= dir
^ flip_horiz
^ flip_vert
? board_size(b
) - 1 - cx
: cx
;
821 if (flip_vert
? x
< cy
: x
> cy
) {
827 fprintf(stderr
, "%s [%d,%d -> %d,%d;%d,%d] will flip %d %d %d -> %s, sym %d (%d) -> %d (%d)\n",
829 cx
, cy
, s
->x1
, s
->y1
, s
->x2
, s
->y2
,
830 flip_horiz
, flip_vert
, flip_diag
,
831 coord2sstr(flip_coord(b
, c
, flip_horiz
, flip_vert
, flip_diag
), b
),
832 s
->type
, s
->d
, b
->symmetry
.type
, b
->symmetry
.d
);
834 if (flip_horiz
|| flip_vert
|| flip_diag
)
835 tree_fix_node_symmetry(b
, tree
->root
, flip_horiz
, flip_vert
, flip_diag
);
840 tree_unlink_node(struct tree_node
*node
)
842 struct tree_node
*ni
= node
->parent
;
843 if (ni
->children
== node
) {
844 ni
->children
= node
->sibling
;
847 while (ni
->sibling
!= node
)
849 ni
->sibling
= node
->sibling
;
851 node
->sibling
= NULL
;
855 /* Reduce weight of statistics on promotion. Remove nodes that
856 * get reduced to zero playouts; returns next node to consider
857 * in the children list (@node may get deleted). */
858 static struct tree_node
*
859 tree_age_node(struct tree
*tree
, struct tree_node
*node
)
861 node
->u
.playouts
/= tree
->ltree_aging
;
862 if (node
->parent
&& !node
->u
.playouts
) {
863 struct tree_node
*sibling
= node
->sibling
;
864 /* Delete node, no playouts. */
865 tree_unlink_node(node
);
866 tree_done_node(tree
, node
);
870 struct tree_node
*ni
= node
->children
;
871 while (ni
) ni
= tree_age_node(tree
, ni
);
872 return node
->sibling
;
875 /* Promotes the given node as the root of the tree. In the fast_alloc
876 * mode, the node may be moved and some of its subtree may be pruned. */
878 tree_promote_node(struct tree
*tree
, struct tree_node
**node
)
880 assert((*node
)->parent
== tree
->root
);
881 tree_unlink_node(*node
);
883 /* Freeing the rest of the tree can take several seconds on large
884 * trees, so we must do it asynchronously: */
885 tree_done_node_detached(tree
, tree
->root
);
887 /* Garbage collect if we run out of memory, or it is cheap to do so now: */
888 unsigned long min_free_size
= (MIN_FREE_MEM_PERCENT
* tree
->max_tree_size
) / 100;
889 if (tree
->nodes_size
>= tree
->max_tree_size
- min_free_size
890 || (tree
->nodes_size
>= min_free_size
&& (*node
)->u
.playouts
< SMALL_TREE_PLAYOUTS
))
891 *node
= tree_garbage_collect(tree
, min_free_size
, *node
);
894 tree
->root_color
= stone_other(tree
->root_color
);
895 board_symmetry_update(tree
->board
, &tree
->root_symmetry
, (*node
)->coord
);
897 /* If the tree deepest node was under node, or if we called tree_garbage_collect,
898 * tree->max_depth is correct. Otherwise we could traverse the tree
899 * to recompute max_depth but it's not worth it: it's just for debugging
900 * and soon the tree will grow and max_depth will become correct again. */
902 if (tree
->ltree_aging
!= 1.0f
) { // XXX: != should work here even with the float
903 tree_age_node(tree
, tree
->ltree_black
);
904 tree_age_node(tree
, tree
->ltree_white
);
909 tree_promote_at(struct tree
*tree
, struct board
*b
, coord_t c
)
911 tree_fix_symmetry(tree
, b
, c
);
913 for (struct tree_node
*ni
= tree
->root
->children
; ni
; ni
= ni
->sibling
) {
914 if (ni
->coord
== c
) {
915 tree_promote_node(tree
, &ni
);