tree_node_load(): Copy board through loading
[pachi.git] / uct / tree.c
blobdf80db9c5de9dfe91a7cddb12e950c2d57e85202
1 #include <assert.h>
2 #include <math.h>
3 #include <stddef.h>
4 #include <stdio.h>
5 #include <stdlib.h>
6 #include <string.h>
8 #include "board.h"
9 #include "debug.h"
10 #include "engine.h"
11 #include "move.h"
12 #include "playout.h"
13 #include "uct/internal.h"
14 #include "uct/tree.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));
21 n->coord = coord;
22 n->depth = depth;
23 if (depth > t->max_depth)
24 t->max_depth = depth;
25 return n;
28 struct tree *
29 tree_init(struct board *board, enum stone color)
31 struct tree *t = calloc(1, sizeof(*t));
32 t->board = board;
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;
36 return t;
40 static void
41 tree_done_node(struct tree *t, struct tree_node *n)
43 struct tree_node *ni = n->children;
44 while (ni) {
45 struct tree_node *nj = ni->sibling;
46 tree_done_node(t, ni);
47 ni = nj;
49 free(n);
52 void
53 tree_done(struct tree *t)
55 tree_done_node(t, t->root);
56 free(t);
60 static void
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);
64 int children = 0;
65 for (struct tree_node *ni = node->children; ni; ni = ni->sibling)
66 children++;
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)
74 nbox[nboxl++] = ni;
76 while (true) {
77 int best = -1;
78 for (int i = 0; i < nboxl; i++)
79 if (nbox[i] && (best < 0 || nbox[i]->u.playouts > nbox[best]->u.playouts))
80 best = i;
81 if (best < 0)
82 break;
83 tree_node_dump(tree, nbox[best], l + 1, thres);
84 nbox[best] = NULL;
88 void
89 tree_dump(struct tree *tree, int thres)
91 tree_node_dump(tree, tree->root, 0, thres);
95 static char *
96 tree_book_name(struct board *b)
98 static char buf[256];
99 sprintf(buf, "uctbook-%d-%02.01f.pachitree", b->size - 2, b->komi);
100 return buf;
103 static void
104 tree_node_save(FILE *f, struct tree_node *node, int thres)
106 fputc(1, f);
107 fwrite(((void *) node) + offsetof(struct tree_node, depth),
108 sizeof(struct tree_node) - offsetof(struct tree_node, depth),
109 1, f);
111 if (node->u.playouts < thres) {
112 fputc(2, f);
113 return;
116 for (struct tree_node *ni = node->children; ni; ni = ni->sibling) {
117 tree_node_save(f, ni, thres);
120 fputc(0, f);
123 void
124 tree_save(struct tree *tree, struct board *b, int thres)
126 char *filename = tree_book_name(b);
127 FILE *f = fopen(filename, "wb");
128 if (!f) {
129 perror("fopen");
130 return;
132 tree_node_save(f, tree->root, thres);
133 fputc(0, f);
134 fclose(f);
138 void
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)
144 (*num)++;
146 fread(((void *) node) + offsetof(struct tree_node, depth),
147 sizeof(struct tree_node) - offsetof(struct tree_node, depth),
148 1, f);
150 struct board b2;
151 board_copy(&b2, b);
152 struct move m = { node->coord, color };
153 int res = board_play(&b2, &m);
154 assert(!res);
156 struct tree_node *ni = NULL, *ni_prev = NULL;
157 int s;
158 while ((s = fgetc(f))) {
159 if (s == 2) {
160 if (expander)
161 expander(tree, node, &b2, color, parity, expander_data);
162 break;
164 ni_prev = ni; ni = calloc(1, sizeof(*ni));
165 if (!node->children)
166 node->children = ni;
167 else
168 ni_prev->sibling = ni;
169 ni->parent = node;
170 tree_node_load(f, tree, &b2, ni, num, stone_other(color), - parity, expander, expander_data);
174 void
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");
180 if (!f)
181 return;
183 fprintf(stderr, "Loading opening book %s...\n", filename);
185 int num = 0;
186 if (fgetc(f))
187 tree_node_load(f, tree, b, tree->root, &num, color, 1, expander, expander_data);
188 fprintf(stderr, "Loaded %d nodes.\n", num);
190 fclose(f);
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. */
200 void
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. */
207 if (UDEBUGL(6)) {
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++) {
216 if (b->symmetry.d) {
217 int x = b->symmetry.type == SYM_DIAG_DOWN ? board_size(b) - 1 - i : i;
218 if (x > j) {
219 if (UDEBUGL(7))
220 fprintf(stderr, "drop %d,%d\n", i, j);
221 continue;
225 coord_t c = coord_xy_otf(i, j, t->board);
226 if (board_at(b, c) != S_NONE)
227 continue;
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))
230 continue;
232 struct tree_node *nj = tree_init_node(t, c, node->depth + 1);
233 nj->parent = node; ni->sibling = nj; ni = nj;
235 if (policy->prior)
236 policy->prior(policy, t, ni, b, color, parity);
242 static coord_t
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);
247 if (flip_diag) {
248 int z = x; x = y; y = z;
250 if (flip_horiz) {
251 x = board_size(b) - 1 - x;
253 if (flip_vert) {
254 y = board_size(b) - 1 - y;
256 return coord_xy_otf(x, y, b);
259 static void
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);
269 static void
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
276 * :::.. .d...
277 * .::.. v....
278 * ..:.. .....
279 * ..... h...X
280 * ..... ..... */
281 bool flip_horiz = cx < s->x1 || cx > s->x2;
282 bool flip_vert = cy < s->y1 || cy > s->y2;
284 bool flip_diag = 0;
285 if (s->d) {
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) {
289 flip_diag = 1;
293 if (UDEBUGL(4)) {
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);
303 static void
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;
309 } else {
310 ni = ni->children;
311 while (ni->sibling != node)
312 ni = ni->sibling;
313 ni->sibling = node->sibling;
317 void
318 tree_delete_node(struct tree *tree, struct tree_node *node)
320 tree_unlink_node(node);
321 tree_done_node(tree, node);
324 void
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);
330 tree->root = node;
331 board_symmetry_update(tree->board, &tree->root_symmetry, node->coord);
332 node->parent = NULL;
335 bool
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);
343 return true;
346 return false;
349 bool
350 tree_leaf_node(struct tree_node *node)
352 return !(node->children);
355 void
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));
360 #if 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); }
363 #endif