uct_player: orig_color -> player_color
[pachi.git] / uct / uct.c
blobf52759428f437d25cfc7ea47b122b00ff06e2517
1 #include <assert.h>
2 #include <pthread.h>
3 #include <signal.h>
4 #include <stdio.h>
5 #include <stdlib.h>
6 #include <string.h>
8 #define DEBUG
10 #include "debug.h"
11 #include "board.h"
12 #include "move.h"
13 #include "playout.h"
14 #include "playout/moggy.h"
15 #include "playout/old.h"
16 #include "playout/light.h"
17 #include "random.h"
18 #include "uct/internal.h"
19 #include "uct/tree.h"
20 #include "uct/uct.h"
22 struct uct_policy *policy_ucb1_init(struct uct *u, char *arg);
23 struct uct_policy *policy_ucb1tuned_init(struct uct *u, char *arg);
24 struct uct_policy *policy_ucb1amaf_init(struct uct *u, char *arg);
27 #define MC_GAMES 80000
28 #define MC_GAMELEN 400
31 static void
32 progress_status(struct uct *u, struct tree *t, enum stone color, int playouts)
34 if (!UDEBUGL(0))
35 return;
37 /* Best move */
38 struct tree_node *best = u->policy->choose(u->policy, t->root, t->board, color);
39 if (!best) {
40 fprintf(stderr, "... No moves left\n");
41 return;
43 fprintf(stderr, "[%d] ", playouts);
44 fprintf(stderr, "best %f ", best->u.value);
46 /* Max depth */
47 fprintf(stderr, "deepest % 2d ", t->max_depth - t->root->depth);
49 /* Best sequence */
50 fprintf(stderr, "| seq ");
51 for (int depth = 0; depth < 6; depth++) {
52 if (best && best->u.playouts >= 25) {
53 fprintf(stderr, "%3s ", coord2sstr(best->coord, t->board));
54 best = u->policy->choose(u->policy, best, t->board, color);
55 } else {
56 fprintf(stderr, " ");
60 /* Best candidates */
61 fprintf(stderr, "| can ");
62 int cans = 4;
63 struct tree_node *can[cans];
64 memset(can, 0, sizeof(can));
65 best = t->root->children;
66 while (best) {
67 int c = 0;
68 while ((!can[c] || best->u.playouts > can[c]->u.playouts) && ++c < cans);
69 for (int d = 0; d < c; d++) can[d] = can[d + 1];
70 if (c > 0) can[c - 1] = best;
71 best = best->sibling;
73 while (--cans >= 0) {
74 if (can[cans]) {
75 fprintf(stderr, "%3s(%.3f) ", coord2sstr(can[cans]->coord, t->board), can[cans]->u.value);
76 } else {
77 fprintf(stderr, " ");
81 fprintf(stderr, "\n");
85 static int
86 uct_playout(struct uct *u, struct board *b, enum stone player_color, struct tree *t)
88 struct board b2;
89 board_copy(&b2, b);
91 struct playout_amafmap *amaf = NULL;
92 if (u->policy->wants_amaf) {
93 amaf = calloc(1, sizeof(*amaf));
94 amaf->map = calloc(board_size2(&b2) + 1, sizeof(*amaf->map));
95 amaf->map++; // -1 is pass
98 /* Walk the tree until we find a leaf, then expand it and do
99 * a random playout. */
100 struct tree_node *n = t->root;
101 enum stone color = player_color;
102 int result;
103 int pass_limit = (board_size(&b2) - 2) * (board_size(&b2) - 2) / 2;
104 int passes = is_pass(b->last_move.coord);
105 /* debug */
106 int depth = 0;
107 static char spaces[] = "\0 ";
108 /* /debug */
109 if (UDEBUGL(8))
110 fprintf(stderr, "--- UCT walk with color %d\n", color);
111 for (; pass; color = stone_other(color)) {
112 if (tree_leaf_node(n)) {
113 if (n->u.playouts >= u->expand_p)
114 tree_expand_node(t, n, &b2, color, u->radar_d, u->policy, (color == player_color ? 1 : -1));
115 if (UDEBUGL(7))
116 fprintf(stderr, "%s*-- UCT playout #%d start [%s] %f\n", spaces, n->u.playouts, coord2sstr(n->coord, t->board), n->u.value);
118 result = play_random_game(&b2, color, u->gamelen, u->playout_amaf ? amaf : NULL, u->playout);
119 if (player_color != color && result >= 0)
120 result = !result;
121 if (UDEBUGL(7))
122 fprintf(stderr, "%s -- [%d..%d] %s random playout result %d\n", spaces, player_color, color, coord2sstr(n->coord, t->board), result);
124 /* Reset color to the @n color. */
125 color = stone_other(color);
126 break;
128 spaces[depth++] = ' '; spaces[depth] = 0;
130 n = u->policy->descend(u->policy, t, n, (color == player_color ? 1 : -1), pass_limit);
131 assert(n == t->root || n->parent);
132 if (UDEBUGL(7))
133 fprintf(stderr, "%s+-- UCT sent us to [%s:%d] %f\n", spaces, coord2sstr(n->coord, t->board), n->coord, n->u.value);
134 if (amaf && n->coord >= -1 && !is_pass(n->coord)) {
135 if (amaf->map[n->coord] == S_NONE) {
136 amaf->map[n->coord] = color;
137 } else {
138 amaf_op(amaf->map[n->coord], +);
141 struct move m = { n->coord, color };
142 int res = board_play(&b2, &m);
144 if (res < 0 || (!is_pass(m.coord) && !group_at(&b2, m.coord)) /* suicide */
145 || b2.superko_violation) {
146 if (UDEBUGL(3)) {
147 for (struct tree_node *ni = n; ni; ni = ni->parent)
148 fprintf(stderr, "%s ", coord2sstr(ni->coord, t->board));
149 fprintf(stderr, "deleting invalid %s node %d,%d res %d group %d spk %d\n",
150 stone2str(color), coord_x(n->coord,b), coord_y(n->coord,b),
151 res, group_at(&b2, m.coord), b2.superko_violation);
153 tree_delete_node(t, n);
154 result = -1;
155 goto end;
158 if (is_pass(n->coord)) {
159 passes++;
160 if (passes >= 2) {
161 float score = board_official_score(&b2);
162 result = (player_color == S_BLACK) ? score < 0 : score > 0;
163 if (UDEBUGL(5))
164 fprintf(stderr, "[%d..%d] %s p-p scoring playout result %d (W %f)\n", player_color, color, coord2sstr(n->coord, t->board), result, score);
165 if (UDEBUGL(6))
166 board_print(&b2, stderr);
167 break;
169 } else {
170 passes = 0;
174 assert(n == t->root || n->parent);
175 if (result >= 0)
176 u->policy->update(u->policy, t, n, color, player_color, amaf, result);
178 end:
179 if (amaf) {
180 free(amaf->map - 1);
181 free(amaf);
183 board_done_noalloc(&b2);
184 return result;
187 static void
188 prepare_move(struct engine *e, struct board *b, enum stone color, coord_t promote)
190 struct uct *u = e->data;
192 if (!b->moves && u->t) {
193 /* Stale state from last game */
194 tree_done(u->t);
195 u->t = NULL;
198 if (!u->t) {
199 u->t = tree_init(b, color);
200 if (u->force_seed)
201 fast_srandom(u->force_seed);
202 if (UDEBUGL(0))
203 fprintf(stderr, "Fresh board with random seed %lu\n", fast_getseed());
204 //board_print(b, stderr);
205 tree_load(u->t, b, color);
208 /* XXX: We hope that the opponent didn't suddenly play
209 * several moves in the row. */
210 if (!is_resign(promote) && !tree_promote_at(u->t, b, promote)) {
211 if (UDEBUGL(2))
212 fprintf(stderr, "<cannot find node to promote>\n");
213 /* Reset tree */
214 tree_done(u->t);
215 u->t = tree_init(b, color);
219 /* Set in main thread in case the playouts should stop. */
220 static volatile sig_atomic_t halt = 0;
222 static int
223 uct_playouts(struct uct *u, struct board *b, enum stone color, struct tree *t)
225 int i, games = u->games;
226 if (t->root->children)
227 games -= t->root->u.playouts / 1.5;
228 /* else this is highly read-out but dead-end branch of opening book;
229 * we need to start from scratch; XXX: Maybe actually base the readout
230 * count based on number of playouts of best node? */
231 for (i = 0; i < games; i++) {
232 int result = uct_playout(u, b, color, t);
233 if (result < 0) {
234 /* Tree descent has hit invalid move. */
235 continue;
238 if (i > 0 && !(i % 10000)) {
239 progress_status(u, t, color, i);
242 if (i > 0 && !(i % 500)) {
243 struct tree_node *best = u->policy->choose(u->policy, t->root, b, color);
244 if (best && best->u.playouts >= 1500 && best->u.value >= u->loss_threshold)
245 break;
248 if (halt) {
249 if (UDEBUGL(2))
250 fprintf(stderr, "<halting early, %d games skipped>\n", games - i);
251 break;
255 progress_status(u, t, color, i);
256 if (UDEBUGL(3))
257 tree_dump(t, u->dumpthres);
258 return i;
261 static pthread_mutex_t finish_mutex = PTHREAD_MUTEX_INITIALIZER;
262 static pthread_cond_t finish_cond = PTHREAD_COND_INITIALIZER;
263 static volatile int finish_thread;
264 static pthread_mutex_t finish_serializer = PTHREAD_MUTEX_INITIALIZER;
266 struct spawn_ctx {
267 int tid;
268 struct uct *u;
269 struct board *b;
270 enum stone color;
271 struct tree *t;
272 unsigned long seed;
273 int games;
276 static void *
277 spawn_helper(void *ctx_)
279 struct spawn_ctx *ctx = ctx_;
280 /* Setup */
281 fast_srandom(ctx->seed);
282 /* Run */
283 ctx->games = uct_playouts(ctx->u, ctx->b, ctx->color, ctx->t);
284 /* Finish */
285 pthread_mutex_lock(&finish_serializer);
286 pthread_mutex_lock(&finish_mutex);
287 finish_thread = ctx->tid;
288 pthread_cond_signal(&finish_cond);
289 pthread_mutex_unlock(&finish_mutex);
290 return ctx;
293 static void
294 uct_notify_play(struct engine *e, struct board *b, struct move *m)
296 prepare_move(e, b, stone_other(m->color), m->coord);
299 static coord_t *
300 uct_genmove(struct engine *e, struct board *b, enum stone color)
302 struct uct *u = e->data;
304 /* Seed the tree. */
305 prepare_move(e, b, color, resign);
307 int played_games = 0;
308 if (!u->threads) {
309 played_games = uct_playouts(u, b, color, u->t);
310 } else {
311 pthread_t threads[u->threads];
312 int joined = 0;
313 halt = 0;
314 pthread_mutex_lock(&finish_mutex);
315 /* Spawn threads... */
316 for (int ti = 0; ti < u->threads; ti++) {
317 struct spawn_ctx *ctx = malloc(sizeof(*ctx));
318 ctx->u = u; ctx->b = b; ctx->color = color;
319 ctx->t = tree_copy(u->t); ctx->tid = ti;
320 ctx->seed = fast_random(65536) + ti;
321 pthread_create(&threads[ti], NULL, spawn_helper, ctx);
322 if (UDEBUGL(2))
323 fprintf(stderr, "Spawned thread %d\n", ti);
325 /* ...and collect them back: */
326 while (joined < u->threads) {
327 /* Wait for some thread to finish... */
328 pthread_cond_wait(&finish_cond, &finish_mutex);
329 /* ...and gather its remnants. */
330 struct spawn_ctx *ctx;
331 pthread_join(threads[finish_thread], (void **) &ctx);
332 played_games += ctx->games;
333 joined++;
334 tree_merge(u->t, ctx->t);
335 tree_done(ctx->t);
336 free(ctx);
337 if (UDEBUGL(2))
338 fprintf(stderr, "Joined thread %d\n", finish_thread);
339 /* Do not get stalled by slow threads. */
340 if (joined >= u->threads / 2)
341 halt = 1;
342 pthread_mutex_unlock(&finish_serializer);
344 pthread_mutex_unlock(&finish_mutex);
347 if (UDEBUGL(2))
348 tree_dump(u->t, u->dumpthres);
350 struct tree_node *best = u->policy->choose(u->policy, u->t->root, b, color);
351 if (!best) {
352 tree_done(u->t); u->t = NULL;
353 return coord_copy(pass);
355 if (UDEBUGL(0))
356 fprintf(stderr, "*** WINNER is %s (%d,%d) with score %1.4f (%d/%d:%d games)\n", coord2sstr(best->coord, b), coord_x(best->coord, b), coord_y(best->coord, b), best->u.value, best->u.playouts, u->t->root->u.playouts, played_games);
357 if (best->u.value < u->resign_ratio && !is_pass(best->coord)) {
358 tree_done(u->t); u->t = NULL;
359 return coord_copy(resign);
361 tree_promote_node(u->t, best);
362 return coord_copy(best->coord);
365 bool
366 uct_genbook(struct engine *e, struct board *b, enum stone color)
368 struct uct *u = e->data;
369 u->t = tree_init(b, color);
370 tree_load(u->t, b, color);
372 int i;
373 for (i = 0; i < u->games; i++) {
374 int result = uct_playout(u, b, color, u->t);
375 if (result < 0) {
376 /* Tree descent has hit invalid move. */
377 continue;
380 if (i > 0 && !(i % 10000)) {
381 progress_status(u, u->t, color, i);
384 progress_status(u, u->t, color, i);
386 tree_save(u->t, b, u->games / 100);
388 tree_done(u->t);
390 return true;
393 void
394 uct_dumpbook(struct engine *e, struct board *b, enum stone color)
396 struct uct *u = e->data;
397 u->t = tree_init(b, color);
398 tree_load(u->t, b, color);
399 tree_dump(u->t, 0);
400 tree_done(u->t);
404 struct uct *
405 uct_state_init(char *arg)
407 struct uct *u = calloc(1, sizeof(struct uct));
409 u->debug_level = 1;
410 u->games = MC_GAMES;
411 u->gamelen = MC_GAMELEN;
412 u->expand_p = 2;
413 u->dumpthres = 1000;
414 u->playout_amaf = false;
416 if (arg) {
417 char *optspec, *next = arg;
418 while (*next) {
419 optspec = next;
420 next += strcspn(next, ",");
421 if (*next) { *next++ = 0; } else { *next = 0; }
423 char *optname = optspec;
424 char *optval = strchr(optspec, '=');
425 if (optval) *optval++ = 0;
427 if (!strcasecmp(optname, "debug")) {
428 if (optval)
429 u->debug_level = atoi(optval);
430 else
431 u->debug_level++;
432 } else if (!strcasecmp(optname, "games") && optval) {
433 u->games = atoi(optval);
434 } else if (!strcasecmp(optname, "gamelen") && optval) {
435 u->gamelen = atoi(optval);
436 } else if (!strcasecmp(optname, "expand_p") && optval) {
437 u->expand_p = atoi(optval);
438 } else if (!strcasecmp(optname, "radar_d") && optval) {
439 /* For 19x19, it is good idea to set this to 3. */
440 u->radar_d = atoi(optval);
441 } else if (!strcasecmp(optname, "dumpthres") && optval) {
442 u->dumpthres = atoi(optval);
443 } else if (!strcasecmp(optname, "playout_amaf")) {
444 /* Whether to include random playout moves in
445 * AMAF as well. (Otherwise, only tree moves
446 * are included in AMAF. Of course makes sense
447 * only in connection with an AMAF policy.) */
448 /* with-without: 55.5% (+-4.1) */
449 if (optval && *optval == '0')
450 u->playout_amaf = false;
451 else
452 u->playout_amaf = true;
453 } else if (!strcasecmp(optname, "policy") && optval) {
454 char *policyarg = strchr(optval, ':');
455 if (policyarg)
456 *policyarg++ = 0;
457 if (!strcasecmp(optval, "ucb1")) {
458 u->policy = policy_ucb1_init(u, policyarg);
459 } else if (!strcasecmp(optval, "ucb1tuned")) {
460 u->policy = policy_ucb1tuned_init(u, policyarg);
461 } else if (!strcasecmp(optval, "ucb1amaf")) {
462 u->policy = policy_ucb1amaf_init(u, policyarg);
463 } else {
464 fprintf(stderr, "UCT: Invalid tree policy %s\n", optval);
466 } else if (!strcasecmp(optname, "playout") && optval) {
467 char *playoutarg = strchr(optval, ':');
468 if (playoutarg)
469 *playoutarg++ = 0;
470 if (!strcasecmp(optval, "old")) {
471 u->playout = playout_old_init(playoutarg);
472 } else if (!strcasecmp(optval, "moggy")) {
473 u->playout = playout_moggy_init(playoutarg);
474 } else if (!strcasecmp(optval, "light")) {
475 u->playout = playout_light_init(playoutarg);
476 } else {
477 fprintf(stderr, "UCT: Invalid playout policy %s\n", optval);
479 } else if (!strcasecmp(optname, "threads") && optval) {
480 u->threads = atoi(optval);
481 } else if (!strcasecmp(optname, "force_seed") && optval) {
482 u->force_seed = atoi(optval);
483 } else {
484 fprintf(stderr, "uct: Invalid engine argument %s or missing value\n", optname);
489 u->resign_ratio = 0.2; /* Resign when most games are lost. */
490 u->loss_threshold = 0.85; /* Stop reading if after at least 1500 playouts this is best value. */
491 if (!u->policy)
492 u->policy = policy_ucb1amaf_init(u, NULL);
494 if (!u->playout)
495 u->playout = playout_moggy_init(NULL);
496 u->playout->debug_level = u->debug_level;
498 return u;
502 struct engine *
503 engine_uct_init(char *arg)
505 struct uct *u = uct_state_init(arg);
506 struct engine *e = calloc(1, sizeof(struct engine));
507 e->name = "UCT Engine";
508 e->comment = "I'm playing UCT. When we both pass, I will consider all the stones on the board alive. If you are reading this, write 'yes'. Please bear with me at the game end, I need to fill the whole board; if you help me, we will both be happier. Filling the board will not lose points (NZ rules).";
509 e->genmove = uct_genmove;
510 e->notify_play = uct_notify_play;
511 e->data = u;
513 return e;