14 #include "playout/moggy.h"
15 #include "playout/light.h"
17 #include "uct/internal.h"
21 struct uct_policy
*policy_ucb1_init(struct uct
*u
, char *arg
);
22 struct uct_policy
*policy_ucb1tuned_init(struct uct
*u
, char *arg
);
23 struct uct_policy
*policy_ucb1amaf_init(struct uct
*u
, char *arg
);
26 #define MC_GAMES 80000
27 #define MC_GAMELEN 400
31 progress_status(struct uct
*u
, struct tree
*t
, enum stone color
, int playouts
)
37 struct tree_node
*best
= u
->policy
->choose(u
->policy
, t
->root
, t
->board
, color
);
39 fprintf(stderr
, "... No moves left\n");
42 fprintf(stderr
, "[%d] ", playouts
);
43 fprintf(stderr
, "best %f ", best
->u
.value
);
46 fprintf(stderr
, "deepest % 2d ", t
->max_depth
- t
->root
->depth
);
49 fprintf(stderr
, "| seq ");
50 for (int depth
= 0; depth
< 6; depth
++) {
51 if (best
&& best
->u
.playouts
>= 25) {
52 fprintf(stderr
, "%3s ", coord2sstr(best
->coord
, t
->board
));
53 best
= u
->policy
->choose(u
->policy
, best
, t
->board
, color
);
60 fprintf(stderr
, "| can ");
62 struct tree_node
*can
[cans
];
63 memset(can
, 0, sizeof(can
));
64 best
= t
->root
->children
;
67 while ((!can
[c
] || best
->u
.playouts
> can
[c
]->u
.playouts
) && ++c
< cans
);
68 for (int d
= 0; d
< c
; d
++) can
[d
] = can
[d
+ 1];
69 if (c
> 0) can
[c
- 1] = best
;
74 fprintf(stderr
, "%3s(%.3f) ", coord2sstr(can
[cans
]->coord
, t
->board
), can
[cans
]->u
.value
);
80 fprintf(stderr
, "\n");
85 uct_leaf_node(struct uct
*u
, struct board
*b
, enum stone player_color
,
86 struct playout_amafmap
*amaf
,
87 struct tree
*t
, struct tree_node
*n
, enum stone node_color
,
90 enum stone next_color
= stone_other(node_color
);
91 if (n
->u
.playouts
>= u
->expand_p
)
92 tree_expand_node(t
, n
, b
, next_color
, u
->radar_d
, u
->policy
,
93 (next_color
== player_color
? 1 : -1));
95 fprintf(stderr
, "%s*-- UCT playout #%d start [%s] %f\n",
96 spaces
, n
->u
.playouts
, coord2sstr(n
->coord
, t
->board
), n
->u
.value
);
98 int result
= play_random_game(b
, next_color
, u
->gamelen
, u
->playout_amaf
? amaf
: NULL
, u
->playout
);
99 if (player_color
!= next_color
&& result
>= 0)
102 fprintf(stderr
, "%s -- [%d..%d] %s random playout result %d\n",
103 spaces
, player_color
, next_color
, coord2sstr(n
->coord
, t
->board
), result
);
109 uct_playout(struct uct
*u
, struct board
*b
, enum stone player_color
, struct tree
*t
)
114 struct playout_amafmap
*amaf
= NULL
;
115 if (u
->policy
->wants_amaf
) {
116 amaf
= calloc(1, sizeof(*amaf
));
117 amaf
->map
= calloc(board_size2(&b2
) + 1, sizeof(*amaf
->map
));
118 amaf
->map
++; // -1 is pass
121 /* Walk the tree until we find a leaf, then expand it and do
122 * a random playout. */
123 struct tree_node
*n
= t
->root
;
124 enum stone node_color
= stone_other(player_color
);
126 int pass_limit
= (board_size(&b2
) - 2) * (board_size(&b2
) - 2) / 2;
127 int passes
= is_pass(b
->last_move
.coord
);
130 static char spaces
[] = "\0 ";
133 fprintf(stderr
, "--- UCT walk with color %d\n", player_color
);
135 while (!tree_leaf_node(n
) && passes
< 2) {
136 spaces
[depth
++] = ' '; spaces
[depth
] = 0;
138 /* Parity is chosen already according to the child color, since
139 * it is applied to children. */
140 node_color
= stone_other(node_color
);
141 n
= u
->policy
->descend(u
->policy
, t
, n
, (node_color
== player_color
? 1 : -1), pass_limit
);
143 assert(n
== t
->root
|| n
->parent
);
145 fprintf(stderr
, "%s+-- UCT sent us to [%s:%d] %f\n",
146 spaces
, coord2sstr(n
->coord
, t
->board
), n
->coord
, n
->u
.value
);
148 if (amaf
&& n
->coord
>= -1 && !is_pass(n
->coord
)) {
149 if (amaf
->map
[n
->coord
] == S_NONE
) {
150 amaf
->map
[n
->coord
] = node_color
;
152 amaf_op(amaf
->map
[n
->coord
], +);
156 struct move m
= { n
->coord
, node_color
};
157 int res
= board_play(&b2
, &m
);
159 if (res
< 0 || (!is_pass(m
.coord
) && !group_at(&b2
, m
.coord
)) /* suicide */
160 || b2
.superko_violation
) {
162 for (struct tree_node
*ni
= n
; ni
; ni
= ni
->parent
)
163 fprintf(stderr
, "%s ", coord2sstr(ni
->coord
, t
->board
));
164 fprintf(stderr
, "deleting invalid %s node %d,%d res %d group %d spk %d\n",
165 stone2str(node_color
), coord_x(n
->coord
,b
), coord_y(n
->coord
,b
),
166 res
, group_at(&b2
, m
.coord
), b2
.superko_violation
);
168 tree_delete_node(t
, n
);
173 if (is_pass(n
->coord
))
179 if (tree_leaf_node(n
)) {
180 result
= uct_leaf_node(u
, &b2
, player_color
, amaf
, t
, n
, node_color
, spaces
);
182 } else { assert(passes
>= 2);
184 float score
= board_official_score(&b2
);
185 result
= (player_color
== S_BLACK
) ? score
< 0 : score
> 0;
188 fprintf(stderr
, "[%d..%d] %s p-p scoring playout result %d (W %f)\n",
189 player_color
, node_color
, coord2sstr(n
->coord
, t
->board
), result
, score
);
191 board_print(&b2
, stderr
);
194 assert(n
== t
->root
|| n
->parent
);
196 u
->policy
->update(u
->policy
, t
, n
, node_color
, player_color
, amaf
, result
);
203 board_done_noalloc(&b2
);
208 prepare_move(struct engine
*e
, struct board
*b
, enum stone color
, coord_t promote
)
210 struct uct
*u
= e
->data
;
212 if (!b
->moves
&& u
->t
) {
213 /* Stale state from last game */
219 u
->t
= tree_init(b
, color
);
221 fast_srandom(u
->force_seed
);
223 fprintf(stderr
, "Fresh board with random seed %lu\n", fast_getseed());
224 //board_print(b, stderr);
225 tree_load(u
->t
, b
, color
);
228 /* XXX: We hope that the opponent didn't suddenly play
229 * several moves in the row. */
230 if (!is_resign(promote
) && !tree_promote_at(u
->t
, b
, promote
)) {
232 fprintf(stderr
, "<cannot find node to promote>\n");
235 u
->t
= tree_init(b
, color
);
239 /* Set in main thread in case the playouts should stop. */
240 static volatile sig_atomic_t halt
= 0;
243 uct_playouts(struct uct
*u
, struct board
*b
, enum stone color
, struct tree
*t
)
245 int i
, games
= u
->games
;
246 if (t
->root
->children
)
247 games
-= t
->root
->u
.playouts
/ 1.5;
248 /* else this is highly read-out but dead-end branch of opening book;
249 * we need to start from scratch; XXX: Maybe actually base the readout
250 * count based on number of playouts of best node? */
251 for (i
= 0; i
< games
; i
++) {
252 int result
= uct_playout(u
, b
, color
, t
);
254 /* Tree descent has hit invalid move. */
258 if (i
> 0 && !(i
% 10000)) {
259 progress_status(u
, t
, color
, i
);
262 if (i
> 0 && !(i
% 500)) {
263 struct tree_node
*best
= u
->policy
->choose(u
->policy
, t
->root
, b
, color
);
264 if (best
&& best
->u
.playouts
>= 1500 && best
->u
.value
>= u
->loss_threshold
)
270 fprintf(stderr
, "<halting early, %d games skipped>\n", games
- i
);
275 progress_status(u
, t
, color
, i
);
277 tree_dump(t
, u
->dumpthres
);
281 static pthread_mutex_t finish_mutex
= PTHREAD_MUTEX_INITIALIZER
;
282 static pthread_cond_t finish_cond
= PTHREAD_COND_INITIALIZER
;
283 static volatile int finish_thread
;
284 static pthread_mutex_t finish_serializer
= PTHREAD_MUTEX_INITIALIZER
;
297 spawn_helper(void *ctx_
)
299 struct spawn_ctx
*ctx
= ctx_
;
301 fast_srandom(ctx
->seed
);
303 ctx
->games
= uct_playouts(ctx
->u
, ctx
->b
, ctx
->color
, ctx
->t
);
305 pthread_mutex_lock(&finish_serializer
);
306 pthread_mutex_lock(&finish_mutex
);
307 finish_thread
= ctx
->tid
;
308 pthread_cond_signal(&finish_cond
);
309 pthread_mutex_unlock(&finish_mutex
);
314 uct_notify_play(struct engine
*e
, struct board
*b
, struct move
*m
)
316 prepare_move(e
, b
, stone_other(m
->color
), m
->coord
);
320 uct_genmove(struct engine
*e
, struct board
*b
, enum stone color
)
322 struct uct
*u
= e
->data
;
325 prepare_move(e
, b
, color
, resign
);
327 int played_games
= 0;
329 played_games
= uct_playouts(u
, b
, color
, u
->t
);
331 pthread_t threads
[u
->threads
];
334 pthread_mutex_lock(&finish_mutex
);
335 /* Spawn threads... */
336 for (int ti
= 0; ti
< u
->threads
; ti
++) {
337 struct spawn_ctx
*ctx
= malloc(sizeof(*ctx
));
338 ctx
->u
= u
; ctx
->b
= b
; ctx
->color
= color
;
339 ctx
->t
= tree_copy(u
->t
); ctx
->tid
= ti
;
340 ctx
->seed
= fast_random(65536) + ti
;
341 pthread_create(&threads
[ti
], NULL
, spawn_helper
, ctx
);
343 fprintf(stderr
, "Spawned thread %d\n", ti
);
345 /* ...and collect them back: */
346 while (joined
< u
->threads
) {
347 /* Wait for some thread to finish... */
348 pthread_cond_wait(&finish_cond
, &finish_mutex
);
349 /* ...and gather its remnants. */
350 struct spawn_ctx
*ctx
;
351 pthread_join(threads
[finish_thread
], (void **) &ctx
);
352 played_games
+= ctx
->games
;
354 tree_merge(u
->t
, ctx
->t
);
358 fprintf(stderr
, "Joined thread %d\n", finish_thread
);
359 /* Do not get stalled by slow threads. */
360 if (joined
>= u
->threads
/ 2)
362 pthread_mutex_unlock(&finish_serializer
);
364 pthread_mutex_unlock(&finish_mutex
);
368 tree_dump(u
->t
, u
->dumpthres
);
370 struct tree_node
*best
= u
->policy
->choose(u
->policy
, u
->t
->root
, b
, color
);
372 tree_done(u
->t
); u
->t
= NULL
;
373 return coord_copy(pass
);
376 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
);
377 if (best
->u
.value
< u
->resign_ratio
&& !is_pass(best
->coord
)) {
378 tree_done(u
->t
); u
->t
= NULL
;
379 return coord_copy(resign
);
381 tree_promote_node(u
->t
, best
);
382 return coord_copy(best
->coord
);
386 uct_genbook(struct engine
*e
, struct board
*b
, enum stone color
)
388 struct uct
*u
= e
->data
;
389 u
->t
= tree_init(b
, color
);
390 tree_load(u
->t
, b
, color
);
393 for (i
= 0; i
< u
->games
; i
++) {
394 int result
= uct_playout(u
, b
, color
, u
->t
);
396 /* Tree descent has hit invalid move. */
400 if (i
> 0 && !(i
% 10000)) {
401 progress_status(u
, u
->t
, color
, i
);
404 progress_status(u
, u
->t
, color
, i
);
406 tree_save(u
->t
, b
, u
->games
/ 100);
414 uct_dumpbook(struct engine
*e
, struct board
*b
, enum stone color
)
416 struct uct
*u
= e
->data
;
417 u
->t
= tree_init(b
, color
);
418 tree_load(u
->t
, b
, color
);
425 uct_state_init(char *arg
)
427 struct uct
*u
= calloc(1, sizeof(struct uct
));
431 u
->gamelen
= MC_GAMELEN
;
434 u
->playout_amaf
= false;
437 char *optspec
, *next
= arg
;
440 next
+= strcspn(next
, ",");
441 if (*next
) { *next
++ = 0; } else { *next
= 0; }
443 char *optname
= optspec
;
444 char *optval
= strchr(optspec
, '=');
445 if (optval
) *optval
++ = 0;
447 if (!strcasecmp(optname
, "debug")) {
449 u
->debug_level
= atoi(optval
);
452 } else if (!strcasecmp(optname
, "games") && optval
) {
453 u
->games
= atoi(optval
);
454 } else if (!strcasecmp(optname
, "gamelen") && optval
) {
455 u
->gamelen
= atoi(optval
);
456 } else if (!strcasecmp(optname
, "expand_p") && optval
) {
457 u
->expand_p
= atoi(optval
);
458 } else if (!strcasecmp(optname
, "radar_d") && optval
) {
459 /* For 19x19, it is good idea to set this to 3. */
460 u
->radar_d
= atoi(optval
);
461 } else if (!strcasecmp(optname
, "dumpthres") && optval
) {
462 u
->dumpthres
= atoi(optval
);
463 } else if (!strcasecmp(optname
, "playout_amaf")) {
464 /* Whether to include random playout moves in
465 * AMAF as well. (Otherwise, only tree moves
466 * are included in AMAF. Of course makes sense
467 * only in connection with an AMAF policy.) */
468 /* with-without: 55.5% (+-4.1) */
469 if (optval
&& *optval
== '0')
470 u
->playout_amaf
= false;
472 u
->playout_amaf
= true;
473 } else if (!strcasecmp(optname
, "policy") && optval
) {
474 char *policyarg
= strchr(optval
, ':');
477 if (!strcasecmp(optval
, "ucb1")) {
478 u
->policy
= policy_ucb1_init(u
, policyarg
);
479 } else if (!strcasecmp(optval
, "ucb1tuned")) {
480 u
->policy
= policy_ucb1tuned_init(u
, policyarg
);
481 } else if (!strcasecmp(optval
, "ucb1amaf")) {
482 u
->policy
= policy_ucb1amaf_init(u
, policyarg
);
484 fprintf(stderr
, "UCT: Invalid tree policy %s\n", optval
);
486 } else if (!strcasecmp(optname
, "playout") && optval
) {
487 char *playoutarg
= strchr(optval
, ':');
490 if (!strcasecmp(optval
, "moggy")) {
491 u
->playout
= playout_moggy_init(playoutarg
);
492 } else if (!strcasecmp(optval
, "light")) {
493 u
->playout
= playout_light_init(playoutarg
);
495 fprintf(stderr
, "UCT: Invalid playout policy %s\n", optval
);
497 } else if (!strcasecmp(optname
, "threads") && optval
) {
498 u
->threads
= atoi(optval
);
499 } else if (!strcasecmp(optname
, "force_seed") && optval
) {
500 u
->force_seed
= atoi(optval
);
502 fprintf(stderr
, "uct: Invalid engine argument %s or missing value\n", optname
);
507 u
->resign_ratio
= 0.2; /* Resign when most games are lost. */
508 u
->loss_threshold
= 0.85; /* Stop reading if after at least 1500 playouts this is best value. */
510 u
->policy
= policy_ucb1amaf_init(u
, NULL
);
513 u
->playout
= playout_moggy_init(NULL
);
514 u
->playout
->debug_level
= u
->debug_level
;
521 engine_uct_init(char *arg
)
523 struct uct
*u
= uct_state_init(arg
);
524 struct engine
*e
= calloc(1, sizeof(struct engine
));
525 e
->name
= "UCT Engine";
526 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).";
527 e
->genmove
= uct_genmove
;
528 e
->notify_play
= uct_notify_play
;