13 #include "uct/internal.h"
17 static struct tree_node
*
18 tree_init_node(struct tree
*t
, coord_t coord
, int depth
)
20 struct tree_node
*n
= calloc(1, sizeof(*n
));
23 if (depth
> t
->max_depth
)
29 tree_init(struct board
*board
, enum stone color
)
31 struct tree
*t
= calloc(1, sizeof(*t
));
33 /* The root PASS move is only virtual, we never play it. */
34 t
->root
= tree_init_node(t
, pass
, 0);
35 t
->root_symmetry
= board
->symmetry
;
41 tree_done_node(struct tree
*t
, struct tree_node
*n
)
43 struct tree_node
*ni
= n
->children
;
45 struct tree_node
*nj
= ni
->sibling
;
46 tree_done_node(t
, ni
);
53 tree_done(struct tree
*t
)
55 tree_done_node(t
, t
->root
);
61 tree_node_dump(struct tree
*tree
, struct tree_node
*node
, int l
, int thres
)
63 for (int i
= 0; i
< l
; i
++) fputc(' ', stderr
);
65 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
67 fprintf(stderr
, "[%s] %f (%d/%d playouts [prior %d/%d amaf %d/%d]; hints %x; %d children)\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
);
69 /* Print nodes sorted by #playouts. */
71 struct tree_node
*nbox
[1000]; int nboxl
= 0;
72 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
73 if (ni
->u
.playouts
> thres
)
78 for (int i
= 0; i
< nboxl
; i
++)
79 if (nbox
[i
] && (best
< 0 || nbox
[i
]->u
.playouts
> nbox
[best
]->u
.playouts
))
83 tree_node_dump(tree
, nbox
[best
], l
+ 1, thres
);
89 tree_dump(struct tree
*tree
, int thres
)
91 tree_node_dump(tree
, tree
->root
, 0, thres
);
96 tree_book_name(struct board
*b
)
99 sprintf(buf
, "uctbook-%d-%02.01f.pachitree", b
->size
- 2, b
->komi
);
104 tree_node_save(FILE *f
, struct tree_node
*node
, int thres
)
107 fwrite(((void *) node
) + offsetof(struct tree_node
, depth
),
108 sizeof(struct tree_node
) - offsetof(struct tree_node
, depth
),
111 if (node
->u
.playouts
< thres
) {
116 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
) {
117 tree_node_save(f
, ni
, thres
);
124 tree_save(struct tree
*tree
, struct board
*b
, int thres
)
126 char *filename
= tree_book_name(b
);
127 FILE *f
= fopen(filename
, "wb");
132 tree_node_save(f
, tree
->root
, thres
);
139 tree_node_load(FILE *f
, struct tree
*tree
, struct board
*b
,
140 struct tree_node
*node
, int *num
,
141 enum stone color
, int parity
,
142 tree_load_expander expander
, void *expander_data
)
146 fread(((void *) node
) + offsetof(struct tree_node
, depth
),
147 sizeof(struct tree_node
) - offsetof(struct tree_node
, depth
),
152 struct move m
= { node
->coord
, color
};
153 int res
= board_play(&b2
, &m
);
156 struct tree_node
*ni
= NULL
, *ni_prev
= NULL
;
158 while ((s
= fgetc(f
))) {
161 expander(tree
, node
, &b2
, color
, parity
, expander_data
);
164 ni_prev
= ni
; ni
= calloc(1, sizeof(*ni
));
168 ni_prev
->sibling
= ni
;
170 tree_node_load(f
, tree
, &b2
, ni
, num
, stone_other(color
), - parity
, expander
, expander_data
);
175 tree_load(struct tree
*tree
, struct board
*b
, enum stone color
,
176 tree_load_expander expander
, void *expander_data
)
178 char *filename
= tree_book_name(b
);
179 FILE *f
= fopen(filename
, "rb");
183 fprintf(stderr
, "Loading opening book %s...\n", filename
);
187 tree_node_load(f
, tree
, b
, tree
->root
, &num
, color
, 1, expander
, expander_data
);
188 fprintf(stderr
, "Loaded %d nodes.\n", num
);
194 /* Tree symmetry: When possible, we will localize the tree to a single part
195 * of the board in tree_expand_node() and possibly flip along symmetry axes
196 * to another part of the board in tree_promote_at(). We follow b->symmetry
197 * guidelines here. */
201 tree_expand_node(struct tree
*t
, struct tree_node
*node
, struct board
*b
, enum stone color
, int radar
, struct uct_policy
*policy
, int parity
)
203 struct tree_node
*ni
= tree_init_node(t
, pass
, node
->depth
+ 1);
204 ni
->parent
= node
; node
->children
= ni
;
206 /* The loop considers only the symmetry playground. */
208 fprintf(stderr
, "expanding %s within [%d,%d],[%d,%d] %d-%d\n",
209 coord2sstr(node
->coord
, b
),
210 b
->symmetry
.x1
, b
->symmetry
.y1
,
211 b
->symmetry
.x2
, b
->symmetry
.y2
,
212 b
->symmetry
.type
, b
->symmetry
.d
);
214 for (int i
= b
->symmetry
.x1
; i
<= b
->symmetry
.x2
; i
++) {
215 for (int j
= b
->symmetry
.y1
; j
<= b
->symmetry
.y2
; j
++) {
217 int x
= b
->symmetry
.type
== SYM_DIAG_DOWN
? board_size(b
) - 1 - i
: i
;
220 fprintf(stderr
, "drop %d,%d\n", i
, j
);
225 coord_t c
= coord_xy_otf(i
, j
, t
->board
);
226 if (board_at(b
, c
) != S_NONE
)
228 /* This looks very useful on large boards - weeds out huge amount of crufty moves. */
229 if (b
->hash
/* not empty board */ && radar
&& !board_stone_radar(b
, c
, radar
))
232 struct tree_node
*nj
= tree_init_node(t
, c
, node
->depth
+ 1);
233 nj
->parent
= node
; ni
->sibling
= nj
; ni
= nj
;
236 policy
->prior(policy
, t
, ni
, b
, color
, parity
);
243 flip_coord(struct board
*b
, coord_t c
,
244 bool flip_horiz
, bool flip_vert
, int flip_diag
)
246 int x
= coord_x(c
, b
), y
= coord_y(c
, b
);
248 int z
= x
; x
= y
; y
= z
;
251 x
= board_size(b
) - 1 - x
;
254 y
= board_size(b
) - 1 - y
;
256 return coord_xy_otf(x
, y
, b
);
260 tree_fix_node_symmetry(struct board
*b
, struct tree_node
*node
,
261 bool flip_horiz
, bool flip_vert
, int flip_diag
)
263 node
->coord
= flip_coord(b
, node
->coord
, flip_horiz
, flip_vert
, flip_diag
);
265 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
266 tree_fix_node_symmetry(b
, ni
, flip_horiz
, flip_vert
, flip_diag
);
270 tree_fix_symmetry(struct tree
*tree
, struct board
*b
, coord_t c
)
272 struct board_symmetry
*s
= &tree
->root_symmetry
;
273 int cx
= coord_x(c
, b
), cy
= coord_y(c
, b
);
275 /* playground X->h->v->d normalization
281 bool flip_horiz
= cx
< s
->x1
|| cx
> s
->x2
;
282 bool flip_vert
= cy
< s
->y1
|| cy
> s
->y2
;
286 bool dir
= (s
->type
== SYM_DIAG_DOWN
);
287 int x
= dir
^ flip_horiz
^ flip_vert
? board_size(b
) - 1 - cx
: cx
;
288 if (flip_vert
? x
< cy
: x
> cy
) {
294 fprintf(stderr
, "%s will flip %d %d %d -> %s, sym %d (%d) -> %d (%d)\n",
295 coord2sstr(c
, b
), flip_horiz
, flip_vert
, flip_diag
,
296 coord2sstr(flip_coord(b
, c
, flip_horiz
, flip_vert
, flip_diag
), b
),
297 s
->type
, s
->d
, b
->symmetry
.type
, b
->symmetry
.d
);
299 tree_fix_node_symmetry(b
, tree
->root
, flip_horiz
, flip_vert
, flip_diag
);
304 tree_unlink_node(struct tree_node
*node
)
306 struct tree_node
*ni
= node
->parent
;
307 if (ni
->children
== node
) {
308 ni
->children
= node
->sibling
;
311 while (ni
->sibling
!= node
)
313 ni
->sibling
= node
->sibling
;
318 tree_delete_node(struct tree
*tree
, struct tree_node
*node
)
320 tree_unlink_node(node
);
321 tree_done_node(tree
, node
);
325 tree_promote_node(struct tree
*tree
, struct tree_node
*node
)
327 assert(node
->parent
== tree
->root
);
328 tree_unlink_node(node
);
329 tree_done_node(tree
, tree
->root
);
331 board_symmetry_update(tree
->board
, &tree
->root_symmetry
, node
->coord
);
336 tree_promote_at(struct tree
*tree
, struct board
*b
, coord_t c
)
338 tree_fix_symmetry(tree
, b
, c
);
340 for (struct tree_node
*ni
= tree
->root
->children
; ni
; ni
= ni
->sibling
) {
341 if (ni
->coord
== c
) {
342 tree_promote_node(tree
, ni
);
350 tree_leaf_node(struct tree_node
*node
)
352 return !(node
->children
);
356 tree_update_node_value(struct tree_node
*node
, bool add_amaf
)
358 node
->u
.value
= (float)(node
->u
.wins
+ node
->prior
.wins
+ (add_amaf
? node
->amaf
.wins
: 0))
359 / (node
->u
.playouts
+ node
->prior
.playouts
+ (add_amaf
? node
->amaf
.playouts
: 0));
361 { struct board b2
; board_size(&b2
) = 9+2;
362 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
); }