12 #include "playout/moggy.h"
13 #include "playout/old.h"
14 #include "playout/light.h"
15 #include "uct/internal.h"
19 struct uct_policy
*policy_ucb1_init(struct uct
*u
, char *arg
);
20 struct uct_policy
*policy_ucb1tuned_init(struct uct
*u
, char *arg
);
21 struct uct_policy
*policy_ucb1amaf_init(struct uct
*u
, char *arg
);
24 #define MC_GAMES 40000
25 #define MC_GAMELEN 400
29 progress_status(struct uct
*u
, struct tree
*t
, enum stone color
, int playouts
)
35 struct tree_node
*best
= u
->policy
->choose(u
->policy
, t
->root
, t
->board
, color
);
37 fprintf(stderr
, "... No moves left\n");
40 fprintf(stderr
, "[%d] ", playouts
);
41 fprintf(stderr
, "best %f ", best
->u
.value
);
44 fprintf(stderr
, "deepest % 2d ", t
->max_depth
- t
->root
->depth
);
47 fprintf(stderr
, "| seq ");
48 for (int depth
= 0; depth
< 6; depth
++) {
49 if (best
&& best
->u
.playouts
>= 25) {
50 fprintf(stderr
, "%3s ", coord2sstr(best
->coord
, t
->board
));
51 best
= u
->policy
->choose(u
->policy
, best
, t
->board
, color
);
58 fprintf(stderr
, "| can ");
60 struct tree_node
*can
[cans
];
61 memset(can
, 0, sizeof(can
));
62 best
= t
->root
->children
;
65 while ((!can
[c
] || best
->u
.playouts
> can
[c
]->u
.playouts
) && ++c
< cans
);
66 for (int d
= 0; d
< c
; d
++) can
[d
] = can
[d
+ 1];
67 if (c
> 0) can
[c
- 1] = best
;
72 fprintf(stderr
, "%3s(%.3f) ", coord2sstr(can
[cans
]->coord
, t
->board
), can
[cans
]->u
.value
);
78 fprintf(stderr
, "\n");
83 uct_playout(struct uct
*u
, struct board
*b
, enum stone color
, struct tree
*t
)
88 struct playout_amafmap
*amaf
= NULL
;
89 if (u
->policy
->wants_amaf
) {
90 amaf
= calloc(1, sizeof(*amaf
));
91 amaf
->map
= calloc(board_size2(&b2
) + 1, sizeof(*amaf
->map
));
92 amaf
->map
++; // -1 is pass
95 /* Walk the tree until we find a leaf, then expand it and do
96 * a random playout. */
97 struct tree_node
*n
= t
->root
;
98 enum stone orig_color
= color
;
100 int pass_limit
= (board_size(&b2
) - 2) * (board_size(&b2
) - 2) / 2;
101 int passes
= is_pass(b
->last_move
.coord
);
103 fprintf(stderr
, "--- UCT walk with color %d\n", color
);
104 for (; pass
; color
= stone_other(color
)) {
105 if (tree_leaf_node(n
)) {
106 if (n
->u
.playouts
>= u
->expand_p
)
107 tree_expand_node(t
, n
, &b2
, color
, u
->radar_d
, u
->policy
, (color
== orig_color
? 1 : -1));
109 result
= play_random_game(&b2
, color
, u
->gamelen
, u
->playout_amaf
? amaf
: NULL
, u
->playout
);
110 if (orig_color
!= color
&& result
>= 0)
113 fprintf(stderr
, "[%d..%d] %s random playout result %d\n", orig_color
, color
, coord2sstr(n
->coord
, t
->board
), result
);
115 /* Reset color to the @n color. */
116 color
= stone_other(color
);
120 n
= u
->policy
->descend(u
->policy
, t
, n
, (color
== orig_color
? 1 : -1), pass_limit
);
121 assert(n
== t
->root
|| n
->parent
);
123 fprintf(stderr
, "-- UCT sent us to [%s] %f\n", coord2sstr(n
->coord
, t
->board
), n
->u
.value
);
124 if (amaf
&& n
->coord
>= -1)
125 amaf
->map
[n
->coord
] = color
;
126 struct move m
= { n
->coord
, color
};
127 int res
= board_play(&b2
, &m
);
128 if (res
< 0 || (!is_pass(m
.coord
) && !group_at(&b2
, m
.coord
)) /* suicide */
129 || b2
.superko_violation
) {
131 fprintf(stderr
, "deleting invalid node %d,%d\n", coord_x(n
->coord
,b
), coord_y(n
->coord
,b
));
132 tree_delete_node(t
, n
);
137 if (is_pass(n
->coord
)) {
140 float score
= board_official_score(&b2
);
141 result
= (orig_color
== S_BLACK
) ? score
< 0 : score
> 0;
143 fprintf(stderr
, "[%d..%d] %s p-p scoring playout result %d (W %f)\n", orig_color
, color
, coord2sstr(n
->coord
, t
->board
), result
, score
);
145 board_print(&b2
, stderr
);
153 assert(n
== t
->root
|| n
->parent
);
155 u
->policy
->update(u
->policy
, t
, n
, color
, amaf
, result
);
162 board_done_noalloc(&b2
);
167 uct_genmove(struct engine
*e
, struct board
*b
, enum stone color
)
169 struct uct
*u
= e
->data
;
172 if (b
->moves
< 2 && u
->t
) {
173 /* Stale state from last game */
180 u
->t
= tree_init(b
, color
);
181 //board_print(b, stderr);
185 } else if (b
->moves
== 1 && !loaded
) {
191 /* XXX: We hope that the opponent didn't suddenly play
192 * several moves in the row. */
194 for (struct tree_node
*ni
= u
->t
->root
->children
; ni
; ni
= ni
->sibling
)
195 if (ni
->coord
== b
->last_move
.coord
) {
196 tree_promote_node(u
->t
, ni
);
199 fprintf(stderr
, "CANNOT FIND NODE TO PROMOTE!\n");
205 int i
, games
= u
->games
- (u
->t
->root
->u
.playouts
/ 1.5);
206 for (i
= 0; i
< games
; i
++) {
207 int result
= uct_playout(u
, b
, color
, u
->t
);
209 /* Tree descent has hit invalid move. */
213 if (i
> 0 && !(i
% 10000)) {
214 progress_status(u
, u
->t
, color
, i
);
217 if (i
> 0 && !(i
% 500)) {
218 struct tree_node
*best
= u
->policy
->choose(u
->policy
, u
->t
->root
, b
, color
);
219 if (best
&& best
->u
.playouts
>= 1000 && best
->u
.value
>= u
->loss_threshold
)
224 progress_status(u
, u
->t
, color
, i
);
226 tree_dump(u
->t
, u
->dumpthres
);
228 struct tree_node
*best
= u
->policy
->choose(u
->policy
, u
->t
->root
, b
, color
);
230 tree_done(u
->t
); u
->t
= NULL
;
231 return coord_copy(pass
);
234 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
, i
);
235 if (best
->u
.value
< u
->resign_ratio
&& !is_pass(best
->coord
)) {
236 tree_done(u
->t
); u
->t
= NULL
;
237 return coord_copy(resign
);
239 tree_promote_node(u
->t
, best
);
240 return coord_copy(best
->coord
);
244 uct_genbook(struct engine
*e
, struct board
*b
, enum stone color
)
246 struct uct
*u
= e
->data
;
247 u
->t
= tree_init(b
, color
);
251 for (i
= 0; i
< u
->games
; i
++) {
252 int result
= uct_playout(u
, b
, color
, u
->t
);
254 /* Tree descent has hit invalid move. */
258 if (i
> 0 && !(i
% 10000)) {
259 progress_status(u
, u
->t
, color
, i
);
262 progress_status(u
, u
->t
, color
, i
);
264 tree_save(u
->t
, b
, u
->games
/ 1000);
272 uct_dumpbook(struct engine
*e
, struct board
*b
, enum stone color
)
274 struct uct
*u
= e
->data
;
275 u
->t
= tree_init(b
, color
);
283 uct_state_init(char *arg
)
285 struct uct
*u
= calloc(1, sizeof(struct uct
));
289 u
->gamelen
= MC_GAMELEN
;
294 char *optspec
, *next
= arg
;
297 next
+= strcspn(next
, ",");
298 if (*next
) { *next
++ = 0; } else { *next
= 0; }
300 char *optname
= optspec
;
301 char *optval
= strchr(optspec
, '=');
302 if (optval
) *optval
++ = 0;
304 if (!strcasecmp(optname
, "debug")) {
306 u
->debug_level
= atoi(optval
);
309 } else if (!strcasecmp(optname
, "games") && optval
) {
310 u
->games
= atoi(optval
);
311 } else if (!strcasecmp(optname
, "gamelen") && optval
) {
312 u
->gamelen
= atoi(optval
);
313 } else if (!strcasecmp(optname
, "expand_p") && optval
) {
314 u
->expand_p
= atoi(optval
);
315 } else if (!strcasecmp(optname
, "radar_d") && optval
) {
316 /* For 19x19, it is good idea to set this to 3. */
317 u
->radar_d
= atoi(optval
);
318 } else if (!strcasecmp(optname
, "dumpthres") && optval
) {
319 u
->dumpthres
= atoi(optval
);
320 } else if (!strcasecmp(optname
, "playout_amaf")) {
321 /* Whether to include random playout moves in
322 * AMAF as well. (Otherwise, only tree moves
323 * are included in AMAF. Of course makes sense
324 * only in connection with an AMAF policy.) */
325 u
->playout_amaf
= true;
326 } else if (!strcasecmp(optname
, "policy") && optval
) {
327 char *policyarg
= strchr(optval
, ':');
330 if (!strcasecmp(optval
, "ucb1")) {
331 u
->policy
= policy_ucb1_init(u
, policyarg
);
332 } else if (!strcasecmp(optval
, "ucb1tuned")) {
333 u
->policy
= policy_ucb1tuned_init(u
, policyarg
);
334 } else if (!strcasecmp(optval
, "ucb1amaf")) {
335 u
->policy
= policy_ucb1amaf_init(u
, policyarg
);
337 fprintf(stderr
, "UCT: Invalid tree policy %s\n", optval
);
339 } else if (!strcasecmp(optname
, "playout") && optval
) {
340 char *playoutarg
= strchr(optval
, ':');
343 if (!strcasecmp(optval
, "old")) {
344 u
->playout
= playout_old_init(playoutarg
);
345 } else if (!strcasecmp(optval
, "moggy")) {
346 u
->playout
= playout_moggy_init(playoutarg
);
347 } else if (!strcasecmp(optval
, "light")) {
348 u
->playout
= playout_light_init(playoutarg
);
350 fprintf(stderr
, "UCT: Invalid playout policy %s\n", optval
);
353 fprintf(stderr
, "uct: Invalid engine argument %s or missing value\n", optname
);
358 u
->resign_ratio
= 0.2; /* Resign when most games are lost. */
359 u
->loss_threshold
= 0.95; /* Stop reading if after at least 500 playouts this is best value. */
361 u
->policy
= policy_ucb1_init(u
, NULL
);
364 u
->playout
= playout_moggy_init(NULL
);
365 u
->playout
->debug_level
= u
->debug_level
;
372 engine_uct_init(char *arg
)
374 struct uct
*u
= uct_state_init(arg
);
375 struct engine
*e
= calloc(1, sizeof(struct engine
));
376 e
->name
= "UCT Engine";
377 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).";
378 e
->genmove
= uct_genmove
;