16 #include "uct/internal.h"
17 #include "uct/prior.h"
20 /* This function may be called by multiple threads in parallel */
21 static struct tree_node
*
22 tree_init_node(struct tree
*t
, coord_t coord
, int depth
)
24 struct tree_node
*n
= calloc(1, sizeof(*n
));
26 fprintf(stderr
, "tree_init_node(): OUT OF MEMORY\n");
29 __sync_fetch_and_add(&t
->node_sizes
, sizeof(*n
));
32 volatile static long c
= 1000000;
33 n
->hash
= __sync_fetch_and_add(&c
, 1) - 1;
34 if (depth
> t
->max_depth
)
40 tree_init(struct board
*board
, enum stone color
)
42 struct tree
*t
= calloc(1, sizeof(*t
));
44 /* The root PASS move is only virtual, we never play it. */
45 t
->root
= tree_init_node(t
, pass
, 0);
46 t
->root_symmetry
= board
->symmetry
;
47 t
->root_color
= stone_other(color
); // to research black moves, root will be white
53 tree_done_node(struct tree
*t
, struct tree_node
*n
)
55 struct tree_node
*ni
= n
->children
;
57 struct tree_node
*nj
= ni
->sibling
;
58 tree_done_node(t
, ni
);
62 t
->node_sizes
-= sizeof(*n
); // atomic operation not needed here
66 tree_done(struct tree
*t
)
68 tree_done_node(t
, t
->root
);
69 if (t
->chchvals
) free(t
->chchvals
);
70 if (t
->chvals
) free(t
->chvals
);
76 tree_node_dump(struct tree
*tree
, struct tree_node
*node
, int l
, int thres
)
78 for (int i
= 0; i
< l
; i
++) fputc(' ', stderr
);
80 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
82 /* We use 1 as parity, since for all nodes we want to know the
83 * win probability of _us_, not the node color. */
84 fprintf(stderr
, "[%s] %f %% %d [prior %f %% %d amaf %f %% %d]; hints %x; %d children <%"PRIhash
">\n",
85 coord2sstr(node
->coord
, tree
->board
),
86 tree_node_get_value(tree
, 1, node
->u
.value
), node
->u
.playouts
,
87 tree_node_get_value(tree
, 1, node
->prior
.value
), node
->prior
.playouts
,
88 tree_node_get_value(tree
, 1, node
->amaf
.value
), node
->amaf
.playouts
,
89 node
->hints
, children
, node
->hash
);
91 /* Print nodes sorted by #playouts. */
93 struct tree_node
*nbox
[1000]; int nboxl
= 0;
94 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
95 if (ni
->u
.playouts
> thres
)
100 for (int i
= 0; i
< nboxl
; i
++)
101 if (nbox
[i
] && (best
< 0 || nbox
[i
]->u
.playouts
> nbox
[best
]->u
.playouts
))
105 tree_node_dump(tree
, nbox
[best
], l
+ 1, /* node->u.value < 0.1 ? 0 : */ thres
);
111 tree_dump_chval(struct tree
*tree
, struct move_stats
*v
)
113 for (int y
= board_size(tree
->board
) - 2; y
> 1; y
--) {
114 for (int x
= 1; x
< board_size(tree
->board
) - 1; x
++) {
115 coord_t c
= coord_xy(tree
->board
, x
, y
);
116 fprintf(stderr
, "%.2f%%%05d ", v
[c
].value
, v
[c
].playouts
);
118 fprintf(stderr
, "\n");
123 tree_dump(struct tree
*tree
, int thres
)
125 if (thres
&& tree
->root
->u
.playouts
/ thres
> 100) {
126 /* Be a bit sensible about this; the opening book can create
127 * huge dumps at first. */
128 thres
= tree
->root
->u
.playouts
/ 100 * (thres
< 1000 ? 1 : thres
/ 1000);
130 fprintf(stderr
, "(UCT tree; root %s; extra komi %f)\n",
131 stone2str(tree
->root_color
), tree
->extra_komi
);
132 tree_node_dump(tree
, tree
->root
, 0, thres
);
134 if (DEBUGL(3) && tree
->chvals
) {
135 fprintf(stderr
, "children stats:\n");
136 tree_dump_chval(tree
, tree
->chvals
);
137 fprintf(stderr
, "grandchildren stats:\n");
138 tree_dump_chval(tree
, tree
->chchvals
);
144 tree_book_name(struct board
*b
)
146 static char buf
[256];
147 if (b
->handicap
> 0) {
148 sprintf(buf
, "uctbook-%d-%02.01f-h%d.pachitree", b
->size
- 2, b
->komi
, b
->handicap
);
150 sprintf(buf
, "uctbook-%d-%02.01f.pachitree", b
->size
- 2, b
->komi
);
156 tree_node_save(FILE *f
, struct tree_node
*node
, int thres
)
159 fwrite(((void *) node
) + offsetof(struct tree_node
, depth
),
160 sizeof(struct tree_node
) - offsetof(struct tree_node
, depth
),
163 if (node
->u
.playouts
>= thres
)
164 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
165 tree_node_save(f
, ni
, thres
);
171 tree_save(struct tree
*tree
, struct board
*b
, int thres
)
173 char *filename
= tree_book_name(b
);
174 FILE *f
= fopen(filename
, "wb");
179 tree_node_save(f
, tree
->root
, thres
);
186 tree_node_load(FILE *f
, struct tree_node
*node
, int *num
)
190 fread(((void *) node
) + offsetof(struct tree_node
, depth
),
191 sizeof(struct tree_node
) - offsetof(struct tree_node
, depth
),
194 /* Keep values in sane scale, otherwise we start overflowing. */
195 #define MAX_PLAYOUTS 10000000
196 if (node
->u
.playouts
> MAX_PLAYOUTS
) {
197 node
->u
.playouts
= MAX_PLAYOUTS
;
199 if (node
->amaf
.playouts
> MAX_PLAYOUTS
) {
200 node
->amaf
.playouts
= MAX_PLAYOUTS
;
203 // Code needed only for thread_model=root which is much worse
204 // than treevl. I suggest removing this model entirely.
205 memcpy(&node
->pamaf
, &node
->amaf
, sizeof(node
->amaf
));
206 memcpy(&node
->pu
, &node
->u
, sizeof(node
->u
));
208 struct tree_node
*ni
= NULL
, *ni_prev
= NULL
;
210 ni_prev
= ni
; ni
= calloc(1, sizeof(*ni
));
214 ni_prev
->sibling
= ni
;
216 tree_node_load(f
, ni
, num
);
221 tree_load(struct tree
*tree
, struct board
*b
)
223 char *filename
= tree_book_name(b
);
224 FILE *f
= fopen(filename
, "rb");
228 fprintf(stderr
, "Loading opening book %s...\n", filename
);
232 tree_node_load(f
, tree
->root
, &num
);
233 fprintf(stderr
, "Loaded %d nodes.\n", num
);
239 static struct tree_node
*
240 tree_node_copy(struct tree_node
*node
)
242 struct tree_node
*n2
= malloc(sizeof(*n2
));
246 struct tree_node
*ni
= node
->children
;
247 struct tree_node
*ni2
= tree_node_copy(ni
);
248 n2
->children
= ni2
; ni2
->parent
= n2
;
249 while ((ni
= ni
->sibling
)) {
250 ni2
->sibling
= tree_node_copy(ni
);
251 ni2
= ni2
->sibling
; ni2
->parent
= n2
;
257 tree_copy(struct tree
*tree
)
259 struct tree
*t2
= malloc(sizeof(*t2
));
261 t2
->root
= tree_node_copy(tree
->root
);
267 tree_node_merge(struct tree_node
*dest
, struct tree_node
*src
)
269 /* Do not merge nodes that weren't touched at all. */
270 assert(dest
->pamaf
.playouts
== src
->pamaf
.playouts
);
271 assert(dest
->pu
.playouts
== src
->pu
.playouts
);
272 if (src
->amaf
.playouts
- src
->pamaf
.playouts
== 0
273 && src
->u
.playouts
- src
->pu
.playouts
== 0) {
277 dest
->hints
|= src
->hints
;
279 /* Merge the children, both are coord-sorted lists. */
280 struct tree_node
*di
= dest
->children
, **dref
= &dest
->children
;
281 struct tree_node
*si
= src
->children
, **sref
= &src
->children
;
283 if (di
->coord
!= si
->coord
) {
284 /* src has some extra items or misses di */
285 struct tree_node
*si2
= si
->sibling
;
286 while (si2
&& di
->coord
!= si2
->coord
) {
290 goto next_di
; /* src misses di, move on */
291 /* chain the extra [si,si2) items before di */
293 while (si
->sibling
!= si2
) {
302 /* Matching nodes - recurse... */
303 tree_node_merge(di
, si
);
304 /* ...and move on. */
305 sref
= &si
->sibling
; si
= si
->sibling
;
307 dref
= &di
->sibling
; di
= di
->sibling
;
310 /* Some outstanding nodes are left on src side, rechain
320 /* Priors should be constant. */
321 assert(dest
->prior
.playouts
== src
->prior
.playouts
&& dest
->prior
.value
== src
->prior
.value
);
323 stats_merge(&dest
->amaf
, &src
->amaf
);
324 stats_merge(&dest
->u
, &src
->u
);
327 /* Merge two trees built upon the same board. Note that the operation is
328 * destructive on src. */
330 tree_merge(struct tree
*dest
, struct tree
*src
)
332 if (src
->max_depth
> dest
->max_depth
)
333 dest
->max_depth
= src
->max_depth
;
334 tree_node_merge(dest
->root
, src
->root
);
339 tree_node_normalize(struct tree_node
*node
, int factor
)
341 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
342 tree_node_normalize(ni
, factor
);
344 #define normalize(s1, s2, t) node->s2.t = node->s1.t + (node->s2.t - node->s1.t) / factor;
345 normalize(pamaf
, amaf
, playouts
);
346 memcpy(&node
->pamaf
, &node
->amaf
, sizeof(node
->amaf
));
348 normalize(pu
, u
, playouts
);
349 memcpy(&node
->pu
, &node
->u
, sizeof(node
->u
));
353 /* Normalize a tree, dividing the amaf and u values by given
354 * factor; otherwise, simulations run in independent threads
355 * two trees built upon the same board. To correctly handle
356 * results taken from previous simulation run, they are backed
359 tree_normalize(struct tree
*tree
, int factor
)
361 tree_node_normalize(tree
->root
, factor
);
363 #endif // ROOT_PARALLEL
366 /* Get a node of given coordinate from within parent, possibly creating it
367 * if necessary - in a very raw form (no .d, priors, ...). */
368 /* FIXME: Adjust for board symmetry. */
370 tree_get_node(struct tree
*t
, struct tree_node
*parent
, coord_t c
, bool create
)
372 if (!parent
->children
|| parent
->children
->coord
>= c
) {
373 /* Special case: Insertion at the beginning. */
374 if (parent
->children
&& parent
->children
->coord
== c
)
375 return parent
->children
;
379 struct tree_node
*nn
= tree_init_node(t
, c
, parent
->depth
+ 1);
380 nn
->parent
= parent
; nn
->sibling
= parent
->children
;
381 parent
->children
= nn
;
385 /* No candidate at the beginning, look through all the children. */
387 struct tree_node
*ni
;
388 for (ni
= parent
->children
; ni
->sibling
; ni
= ni
->sibling
)
389 if (ni
->sibling
->coord
>= c
)
392 if (ni
->sibling
&& ni
->sibling
->coord
== c
)
394 assert(ni
->coord
< c
);
398 struct tree_node
*nn
= tree_init_node(t
, c
, parent
->depth
+ 1);
399 nn
->parent
= parent
; nn
->sibling
= ni
->sibling
; ni
->sibling
= nn
;
404 /* Tree symmetry: When possible, we will localize the tree to a single part
405 * of the board in tree_expand_node() and possibly flip along symmetry axes
406 * to another part of the board in tree_promote_at(). We follow b->symmetry
407 * guidelines here. */
411 tree_expand_node(struct tree
*t
, struct tree_node
*node
, struct board
*b
, enum stone color
, struct uct
*u
, int parity
)
413 /* Get a Common Fate Graph distance map from parent node. */
414 int distances
[board_size2(b
)];
415 if (!is_pass(b
->last_move
.coord
) && !is_resign(b
->last_move
.coord
)) {
416 cfg_distances(b
, node
->coord
, distances
, TREE_NODE_D_MAX
);
418 // Pass or resign - everything is too far.
419 foreach_point(b
) { distances
[c
] = TREE_NODE_D_MAX
+ 1; } foreach_point_end
;
422 /* Get a map of prior values to initialize the new nodes with. */
423 struct prior_map map
= {
426 .parity
= tree_parity(t
, parity
),
427 .distances
= distances
,
429 // Include pass in the prior map.
430 struct move_stats map_prior
[board_size2(b
) + 1]; map
.prior
= &map_prior
[1];
431 bool map_consider
[board_size2(b
) + 1]; map
.consider
= &map_consider
[1];
432 memset(map_prior
, 0, sizeof(map_prior
));
433 memset(map_consider
, 0, sizeof(map_consider
));
434 struct move pm
= { .color
= color
};
435 map
.consider
[pass
] = true;
437 if (board_at(b
, c
) != S_NONE
)
440 if (!board_is_valid_move(b
, &pm
))
442 map
.consider
[c
] = true;
444 uct_prior(u
, node
, &map
);
446 /* Now, create the nodes. */
447 struct tree_node
*ni
= tree_init_node(t
, pass
, node
->depth
+ 1);
448 struct tree_node
*first_child
= ni
;
450 ni
->prior
= map
.prior
[pass
]; ni
->d
= TREE_NODE_D_MAX
+ 1;
452 /* The loop considers only the symmetry playground. */
454 fprintf(stderr
, "expanding %s within [%d,%d],[%d,%d] %d-%d\n",
455 coord2sstr(node
->coord
, b
),
456 b
->symmetry
.x1
, b
->symmetry
.y1
,
457 b
->symmetry
.x2
, b
->symmetry
.y2
,
458 b
->symmetry
.type
, b
->symmetry
.d
);
460 for (int i
= b
->symmetry
.x1
; i
<= b
->symmetry
.x2
; i
++) {
461 for (int j
= b
->symmetry
.y1
; j
<= b
->symmetry
.y2
; j
++) {
463 int x
= b
->symmetry
.type
== SYM_DIAG_DOWN
? board_size(b
) - 1 - i
: i
;
466 fprintf(stderr
, "drop %d,%d\n", i
, j
);
471 coord_t c
= coord_xy_otf(i
, j
, t
->board
);
472 if (!map
.consider
[c
]) // Filter out invalid moves
474 assert(c
!= node
->coord
); // I have spotted "C3 C3" in some sequence...
476 struct tree_node
*nj
= tree_init_node(t
, c
, node
->depth
+ 1);
477 nj
->parent
= node
; ni
->sibling
= nj
; ni
= nj
;
479 ni
->prior
= map
.prior
[c
];
480 ni
->d
= distances
[c
];
483 // Must set children only after everything else is properly initialized
484 node
->children
= first_child
;
489 flip_coord(struct board
*b
, coord_t c
,
490 bool flip_horiz
, bool flip_vert
, int flip_diag
)
492 int x
= coord_x(c
, b
), y
= coord_y(c
, b
);
494 int z
= x
; x
= y
; y
= z
;
497 x
= board_size(b
) - 1 - x
;
500 y
= board_size(b
) - 1 - y
;
502 return coord_xy_otf(x
, y
, b
);
506 tree_fix_node_symmetry(struct board
*b
, struct tree_node
*node
,
507 bool flip_horiz
, bool flip_vert
, int flip_diag
)
509 if (!is_pass(node
->coord
))
510 node
->coord
= flip_coord(b
, node
->coord
, flip_horiz
, flip_vert
, flip_diag
);
512 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
513 tree_fix_node_symmetry(b
, ni
, flip_horiz
, flip_vert
, flip_diag
);
517 tree_fix_symmetry(struct tree
*tree
, struct board
*b
, coord_t c
)
522 struct board_symmetry
*s
= &tree
->root_symmetry
;
523 int cx
= coord_x(c
, b
), cy
= coord_y(c
, b
);
525 /* playground X->h->v->d normalization
531 bool flip_horiz
= cx
< s
->x1
|| cx
> s
->x2
;
532 bool flip_vert
= cy
< s
->y1
|| cy
> s
->y2
;
536 bool dir
= (s
->type
== SYM_DIAG_DOWN
);
537 int x
= dir
^ flip_horiz
^ flip_vert
? board_size(b
) - 1 - cx
: cx
;
538 if (flip_vert
? x
< cy
: x
> cy
) {
544 fprintf(stderr
, "%s [%d,%d -> %d,%d;%d,%d] will flip %d %d %d -> %s, sym %d (%d) -> %d (%d)\n",
546 cx
, cy
, s
->x1
, s
->y1
, s
->x2
, s
->y2
,
547 flip_horiz
, flip_vert
, flip_diag
,
548 coord2sstr(flip_coord(b
, c
, flip_horiz
, flip_vert
, flip_diag
), b
),
549 s
->type
, s
->d
, b
->symmetry
.type
, b
->symmetry
.d
);
551 if (flip_horiz
|| flip_vert
|| flip_diag
)
552 tree_fix_node_symmetry(b
, tree
->root
, flip_horiz
, flip_vert
, flip_diag
);
557 tree_unlink_node(struct tree_node
*node
)
559 struct tree_node
*ni
= node
->parent
;
560 if (ni
->children
== node
) {
561 ni
->children
= node
->sibling
;
564 while (ni
->sibling
!= node
)
566 ni
->sibling
= node
->sibling
;
568 node
->sibling
= NULL
;
573 tree_delete_node(struct tree
*tree
, struct tree_node
*node
)
575 tree_unlink_node(node
);
576 tree_done_node(tree
, node
);
580 tree_promote_node(struct tree
*tree
, struct tree_node
*node
)
582 assert(node
->parent
== tree
->root
);
583 tree_unlink_node(node
);
584 tree_done_node(tree
, tree
->root
);
586 tree
->root_color
= stone_other(tree
->root_color
);
587 board_symmetry_update(tree
->board
, &tree
->root_symmetry
, node
->coord
);
589 if (tree
->chchvals
) { free(tree
->chchvals
); tree
->chchvals
= NULL
; }
590 if (tree
->chvals
) { free(tree
->chvals
); tree
->chvals
= NULL
; }
594 tree_promote_at(struct tree
*tree
, struct board
*b
, coord_t c
)
596 tree_fix_symmetry(tree
, b
, c
);
598 for (struct tree_node
*ni
= tree
->root
->children
; ni
; ni
= ni
->sibling
) {
599 if (ni
->coord
== c
) {
600 tree_promote_node(tree
, ni
);