14 #include "uct/internal.h"
18 static struct tree_node
*
19 tree_init_node(struct tree
*t
, coord_t coord
, int depth
)
21 struct tree_node
*n
= calloc(1, sizeof(*n
));
24 static long c
= 1000000;
26 if (depth
> t
->max_depth
)
32 tree_init(struct board
*board
, enum stone color
)
34 struct tree
*t
= calloc(1, sizeof(*t
));
36 /* The root PASS move is only virtual, we never play it. */
37 t
->root
= tree_init_node(t
, pass
, 0);
38 t
->root_symmetry
= board
->symmetry
;
44 tree_done_node(struct tree
*t
, struct tree_node
*n
)
46 struct tree_node
*ni
= n
->children
;
48 struct tree_node
*nj
= ni
->sibling
;
49 tree_done_node(t
, ni
);
56 tree_done(struct tree
*t
)
58 tree_done_node(t
, t
->root
);
64 tree_node_dump(struct tree
*tree
, struct tree_node
*node
, int l
, int thres
)
66 for (int i
= 0; i
< l
; i
++) fputc(' ', stderr
);
68 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
70 fprintf(stderr
, "[%s] %f (%d/%d playouts [prior %d/%d amaf %d/%d]; hints %x; %d children) <%lld>\n", coord2sstr(node
->coord
, tree
->board
), node
->u
.value
, node
->u
.wins
, node
->u
.playouts
, node
->prior
.wins
, node
->prior
.playouts
, node
->amaf
.wins
, node
->amaf
.playouts
, node
->hints
, children
, node
->hash
);
72 /* Print nodes sorted by #playouts. */
74 struct tree_node
*nbox
[1000]; int nboxl
= 0;
75 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
76 if (ni
->u
.playouts
> thres
)
81 for (int i
= 0; i
< nboxl
; i
++)
82 if (nbox
[i
] && (best
< 0 || nbox
[i
]->u
.playouts
> nbox
[best
]->u
.playouts
))
86 tree_node_dump(tree
, nbox
[best
], l
+ 1, /* node->u.value < 0.1 ? 0 : */ thres
);
92 tree_dump(struct tree
*tree
, int thres
)
94 if (thres
&& tree
->root
->u
.playouts
/ thres
> 100) {
95 /* Be a bit sensible about this; the opening book can create
96 * huge dumps at first. */
97 thres
= tree
->root
->u
.playouts
/ 100 * (thres
< 1000 ? 1 : thres
/ 1000);
99 tree_node_dump(tree
, tree
->root
, 0, thres
);
104 tree_book_name(struct board
*b
)
106 static char buf
[256];
107 if (b
->handicap
> 0) {
108 sprintf(buf
, "uctbook-%d-%02.01f-h%d.pachitree", b
->size
- 2, b
->komi
, b
->handicap
);
110 sprintf(buf
, "uctbook-%d-%02.01f.pachitree", b
->size
- 2, b
->komi
);
116 tree_node_save(FILE *f
, struct tree_node
*node
, int thres
)
119 fwrite(((void *) node
) + offsetof(struct tree_node
, depth
),
120 sizeof(struct tree_node
) - offsetof(struct tree_node
, depth
),
123 if (node
->u
.playouts
>= thres
)
124 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
125 tree_node_save(f
, ni
, thres
);
131 tree_save(struct tree
*tree
, struct board
*b
, int thres
)
133 char *filename
= tree_book_name(b
);
134 FILE *f
= fopen(filename
, "wb");
139 tree_node_save(f
, tree
->root
, thres
);
146 tree_node_load(FILE *f
, struct tree_node
*node
, int *num
, bool invert
)
150 fread(((void *) node
) + offsetof(struct tree_node
, depth
),
151 sizeof(struct tree_node
) - offsetof(struct tree_node
, depth
),
154 /* Keep values in sane scale, otherwise we start overflowing.
155 * We may go slow here but we must be careful about not getting
156 * too huge integers.*/
157 #define MAX_PLAYOUTS 10000000
158 if (node
->u
.playouts
> MAX_PLAYOUTS
) {
159 int over
= node
->u
.playouts
- MAX_PLAYOUTS
;
160 node
->u
.wins
-= ((double) node
->u
.wins
/ node
->u
.playouts
) * over
;
161 node
->u
.playouts
= MAX_PLAYOUTS
;
163 if (node
->amaf
.playouts
> MAX_PLAYOUTS
) {
164 int over
= node
->amaf
.playouts
- MAX_PLAYOUTS
;
165 node
->amaf
.wins
-= ((double) node
->amaf
.wins
/ node
->amaf
.playouts
) * over
;
166 node
->amaf
.playouts
= MAX_PLAYOUTS
;
170 node
->u
.wins
= node
->u
.playouts
- node
->u
.wins
;
171 node
->u
.value
= 1 - node
->u
.value
;
172 node
->amaf
.wins
= node
->amaf
.playouts
- node
->amaf
.wins
;
173 node
->amaf
.value
= 1 - node
->amaf
.value
;
174 node
->prior
.wins
= node
->prior
.playouts
- node
->prior
.wins
;
175 node
->prior
.value
= 1 - node
->prior
.value
;
178 struct tree_node
*ni
= NULL
, *ni_prev
= NULL
;
180 ni_prev
= ni
; ni
= calloc(1, sizeof(*ni
));
184 ni_prev
->sibling
= ni
;
186 tree_node_load(f
, ni
, num
, invert
);
191 tree_load(struct tree
*tree
, struct board
*b
, enum stone color
)
193 char *filename
= tree_book_name(b
);
194 FILE *f
= fopen(filename
, "rb");
198 fprintf(stderr
, "Loading opening book %s...\n", filename
);
202 tree_node_load(f
, tree
->root
, &num
, color
!= S_BLACK
);
203 fprintf(stderr
, "Loaded %d nodes.\n", num
);
209 static struct tree_node
*
210 tree_node_copy(struct tree_node
*node
)
212 struct tree_node
*n2
= malloc(sizeof(*n2
));
216 struct tree_node
*ni
= node
->children
;
217 struct tree_node
*ni2
= tree_node_copy(ni
);
218 n2
->children
= ni2
; ni2
->parent
= n2
;
219 while ((ni
= ni
->sibling
)) {
220 ni2
->sibling
= tree_node_copy(ni
);
221 ni2
= ni2
->sibling
; ni2
->parent
= n2
;
227 tree_copy(struct tree
*tree
)
229 struct tree
*t2
= malloc(sizeof(*t2
));
231 t2
->root
= tree_node_copy(tree
->root
);
237 tree_node_merge(struct tree_node
*dest
, struct tree_node
*src
)
239 dest
->hints
|= src
->hints
;
241 /* Merge the children, both are coord-sorted lists. */
242 struct tree_node
*di
= dest
->children
, *dip
= NULL
;
243 struct tree_node
*si
= src
->children
, *sip
= NULL
;
245 if (di
->coord
!= si
->coord
) {
246 /* src has some extra items or misses di */
247 struct tree_node
*si2
= si
->sibling
;
248 while (si2
&& di
->coord
!= si2
->coord
) {
252 goto next_di
; /* src misses di, move on */
253 /* chain the extra [si,si2) items before di */
258 while (si
->sibling
!= si2
) {
269 /* Matching nodes - recurse... */
270 tree_node_merge(di
, si
);
271 /* ...and move on. */
272 sip
= si
; si
= si
->sibling
;
274 dip
= di
; di
= di
->sibling
;
288 src
->children
= NULL
;
291 /* In case of prior playouts, we do not want to accumulate them
292 * over merges - they remain static after setup. However, different
293 * trees may have different priors non-deterministically. We just
294 * take the average. */
295 if (dest
->prior
.playouts
!= src
->prior
.playouts
296 || dest
->prior
.wins
!= src
->prior
.wins
) {
297 dest
->prior
.playouts
= (dest
->prior
.playouts
+ src
->prior
.playouts
) / 2;
298 dest
->prior
.wins
= (dest
->prior
.wins
+ src
->prior
.wins
) / 2;
299 if (dest
->prior
.playouts
)
300 dest
->prior
.value
= dest
->prior
.wins
/ dest
->prior
.playouts
;
303 dest
->amaf
.playouts
+= src
->amaf
.playouts
;
304 dest
->amaf
.wins
+= src
->amaf
.wins
;
305 if (dest
->amaf
.playouts
)
306 dest
->amaf
.value
= dest
->amaf
.wins
/ dest
->amaf
.playouts
;
308 dest
->u
.playouts
+= src
->u
.playouts
;
309 dest
->u
.wins
+= src
->u
.wins
;
310 if (dest
->prior
.playouts
+ dest
->amaf
.playouts
+ dest
->u
.playouts
)
311 tree_update_node_value(dest
);
314 /* Merge two trees built upon the same board. Note that the operation is
315 * destructive on src. */
317 tree_merge(struct tree
*dest
, struct tree
*src
)
319 if (src
->max_depth
> dest
->max_depth
)
320 dest
->max_depth
= src
->max_depth
;
321 tree_node_merge(dest
->root
, src
->root
);
325 /* Tree symmetry: When possible, we will localize the tree to a single part
326 * of the board in tree_expand_node() and possibly flip along symmetry axes
327 * to another part of the board in tree_promote_at(). We follow b->symmetry
328 * guidelines here. */
332 tree_expand_node(struct tree
*t
, struct tree_node
*node
, struct board
*b
, enum stone color
, int radar
, struct uct_policy
*policy
, int parity
)
334 struct tree_node
*ni
= tree_init_node(t
, pass
, node
->depth
+ 1);
335 ni
->parent
= node
; node
->children
= ni
;
337 policy
->prior(policy
, t
, ni
, b
, color
, parity
);
339 /* The loop considers only the symmetry playground. */
341 fprintf(stderr
, "expanding %s within [%d,%d],[%d,%d] %d-%d\n",
342 coord2sstr(node
->coord
, b
),
343 b
->symmetry
.x1
, b
->symmetry
.y1
,
344 b
->symmetry
.x2
, b
->symmetry
.y2
,
345 b
->symmetry
.type
, b
->symmetry
.d
);
347 for (int i
= b
->symmetry
.x1
; i
<= b
->symmetry
.x2
; i
++) {
348 for (int j
= b
->symmetry
.y1
; j
<= b
->symmetry
.y2
; j
++) {
350 int x
= b
->symmetry
.type
== SYM_DIAG_DOWN
? board_size(b
) - 1 - i
: i
;
353 fprintf(stderr
, "drop %d,%d\n", i
, j
);
358 coord_t c
= coord_xy_otf(i
, j
, t
->board
);
359 if (board_at(b
, c
) != S_NONE
)
361 assert(c
!= node
->coord
); // I have spotted "C3 C3" in some sequence...
362 /* This looks very useful on large boards - weeds out huge amount of crufty moves. */
363 if (b
->hash
/* not empty board */ && radar
&& !board_stone_radar(b
, c
, radar
))
366 struct tree_node
*nj
= tree_init_node(t
, c
, node
->depth
+ 1);
367 nj
->parent
= node
; ni
->sibling
= nj
; ni
= nj
;
370 policy
->prior(policy
, t
, ni
, b
, color
, parity
);
377 flip_coord(struct board
*b
, coord_t c
,
378 bool flip_horiz
, bool flip_vert
, int flip_diag
)
380 int x
= coord_x(c
, b
), y
= coord_y(c
, b
);
382 int z
= x
; x
= y
; y
= z
;
385 x
= board_size(b
) - 1 - x
;
388 y
= board_size(b
) - 1 - y
;
390 return coord_xy_otf(x
, y
, b
);
394 tree_fix_node_symmetry(struct board
*b
, struct tree_node
*node
,
395 bool flip_horiz
, bool flip_vert
, int flip_diag
)
397 node
->coord
= flip_coord(b
, node
->coord
, flip_horiz
, flip_vert
, flip_diag
);
399 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
400 tree_fix_node_symmetry(b
, ni
, flip_horiz
, flip_vert
, flip_diag
);
404 tree_fix_symmetry(struct tree
*tree
, struct board
*b
, coord_t c
)
406 struct board_symmetry
*s
= &tree
->root_symmetry
;
407 int cx
= coord_x(c
, b
), cy
= coord_y(c
, b
);
409 /* playground X->h->v->d normalization
415 bool flip_horiz
= cx
< s
->x1
|| cx
> s
->x2
;
416 bool flip_vert
= cy
< s
->y1
|| cy
> s
->y2
;
420 bool dir
= (s
->type
== SYM_DIAG_DOWN
);
421 int x
= dir
^ flip_horiz
^ flip_vert
? board_size(b
) - 1 - cx
: cx
;
422 if (flip_vert
? x
< cy
: x
> cy
) {
428 fprintf(stderr
, "%s will flip %d %d %d -> %s, sym %d (%d) -> %d (%d)\n",
429 coord2sstr(c
, b
), flip_horiz
, flip_vert
, flip_diag
,
430 coord2sstr(flip_coord(b
, c
, flip_horiz
, flip_vert
, flip_diag
), b
),
431 s
->type
, s
->d
, b
->symmetry
.type
, b
->symmetry
.d
);
433 tree_fix_node_symmetry(b
, tree
->root
, flip_horiz
, flip_vert
, flip_diag
);
438 tree_unlink_node(struct tree_node
*node
)
440 struct tree_node
*ni
= node
->parent
;
441 if (ni
->children
== node
) {
442 ni
->children
= node
->sibling
;
445 while (ni
->sibling
!= node
)
447 ni
->sibling
= node
->sibling
;
452 tree_delete_node(struct tree
*tree
, struct tree_node
*node
)
454 tree_unlink_node(node
);
455 tree_done_node(tree
, node
);
459 tree_promote_node(struct tree
*tree
, struct tree_node
*node
)
461 assert(node
->parent
== tree
->root
);
462 tree_unlink_node(node
);
463 tree_done_node(tree
, tree
->root
);
465 board_symmetry_update(tree
->board
, &tree
->root_symmetry
, node
->coord
);
470 tree_promote_at(struct tree
*tree
, struct board
*b
, coord_t c
)
472 tree_fix_symmetry(tree
, b
, c
);
474 for (struct tree_node
*ni
= tree
->root
->children
; ni
; ni
= ni
->sibling
) {
475 if (ni
->coord
== c
) {
476 tree_promote_node(tree
, ni
);
484 tree_leaf_node(struct tree_node
*node
)
486 return !(node
->children
);
490 tree_update_node_value(struct tree_node
*node
)
492 bool noamaf
= node
->hints
& NODE_HINT_NOAMAF
;
493 node
->u
.value
= (float)(node
->u
.wins
+ node
->prior
.wins
+ (!noamaf
? node
->amaf
.wins
: 0))
494 / (node
->u
.playouts
+ node
->prior
.playouts
+ (!noamaf
? node
->amaf
.playouts
: 0));
496 { struct board b2
; board_size(&b2
) = 9+2;
497 fprintf(stderr
, "%s->%s %d/%d %d/%d %f\n", node
->parent
? coord2sstr(node
->parent
->coord
, &b2
) : NULL
, coord2sstr(node
->coord
, &b2
), node
->u
.wins
, node
->u
.playouts
, node
->prior
.wins
, node
->prior
.playouts
, node
->u
.value
); }