11 #include "montecarlo/hint.h"
12 #include "uct/internal.h"
16 struct uct_policy
*policy_ucb1_init(struct uct
*u
, char *arg
);
17 struct uct_policy
*policy_ucb1tuned_init(struct uct
*u
, char *arg
);
20 #define MC_GAMES 40000
21 #define MC_GAMELEN 400
25 domainhint_policy(void *playout_policy
, struct board
*b
, enum stone my_color
)
27 struct uct
*u
= playout_policy
;
28 return domain_hint(&u
->mc
, b
, my_color
);
32 uct_playout(struct uct
*u
, struct board
*b
, enum stone color
, struct tree
*t
)
37 /* Walk the tree until we find a leaf, then expand it and do
38 * a random playout. */
39 struct tree_node
*n
= t
->root
;
40 enum stone orig_color
= color
;
42 int pass_limit
= (b2
.size
- 2) * (b2
.size
- 2) / 2;
43 int passes
= is_pass(b
->last_move
.coord
);
45 fprintf(stderr
, "--- UCT walk\n");
46 for (; pass
; color
= stone_other(color
)) {
47 if (tree_leaf_node(n
)) {
48 if (n
->playouts
>= u
->expand_p
)
49 tree_expand_node(t
, n
, &b2
);
51 result
= play_random_game(&b2
, stone_other(color
), u
->gamelen
, domainhint_policy
, u
);
52 if (orig_color
== color
&& result
>= 0)
55 fprintf(stderr
, "[%d..%d] %s playout result %d\n", orig_color
, color
, coord2sstr(n
->coord
, t
->board
), result
);
59 n
= u
->policy
->descend(u
->policy
, t
, n
, (color
== orig_color
? 1 : -1), pass_limit
);
61 fprintf(stderr
, "-- UCT sent us to [%s] %f\n", coord2sstr(n
->coord
, t
->board
), n
->value
);
62 struct move m
= { n
->coord
, color
};
63 int res
= board_play(&b2
, &m
);
64 if (res
< 0 || (!is_pass(m
.coord
) && !group_at(&b2
, m
.coord
)) /* suicide */
65 || b2
.superko_violation
) {
67 fprintf(stderr
, "deleting invalid node %d,%d\n", coord_x(n
->coord
,b
), coord_y(n
->coord
,b
));
69 board_done_noalloc(&b2
);
73 if (is_pass(n
->coord
)) {
76 float score
= board_official_score(&b2
);
77 result
= (orig_color
== S_BLACK
) ? score
< 0 : score
> 0;
79 fprintf(stderr
, "[%d..%d] %s playout result %d (W %f)\n", orig_color
, color
, coord2sstr(n
->coord
, t
->board
), result
, score
);
81 board_print(&b2
, stderr
);
90 tree_uct_update(n
, result
);
91 board_done_noalloc(&b2
);
96 uct_genmove(struct engine
*e
, struct board
*b
, enum stone color
)
98 struct uct
*u
= e
->data
;
103 //board_print(b, stderr);
105 /* XXX: We hope that the opponent didn't suddenly play
106 * several moves in the row. */
107 for (struct tree_node
*ni
= u
->t
->root
->children
; ni
; ni
= ni
->sibling
)
108 if (ni
->coord
== b
->last_move
.coord
) {
109 tree_promote_node(u
->t
, ni
);
112 fprintf(stderr
, "CANNOT FIND NODE TO PROMOTE!\n");
119 for (i
= 0; i
< u
->games
; i
++) {
120 int result
= uct_playout(u
, b
, color
, u
->t
);
122 /* Tree descent has hit invalid move. */
126 if (i
> 0 && !(i
% 1000)) {
127 struct tree_node
*best
= u
->policy
->choose(u
->policy
, u
->t
->root
, b
, color
);
128 if (best
&& best
->playouts
>= 500 && best
->value
>= u
->loss_threshold
)
136 struct tree_node
*best
= u
->policy
->choose(u
->policy
, u
->t
->root
, b
, color
);
138 tree_done(u
->t
); u
->t
= NULL
;
139 return coord_copy(pass
);
142 fprintf(stderr
, "*** WINNER is %d,%d with score %1.4f (%d games)\n", coord_x(best
->coord
, b
), coord_y(best
->coord
, b
), best
->value
, i
);
143 if (best
->value
< u
->resign_ratio
&& !is_pass(best
->coord
)) {
144 tree_done(u
->t
); u
->t
= NULL
;
145 return coord_copy(resign
);
147 tree_promote_node(u
->t
, best
);
148 return coord_copy(best
->coord
);
153 uct_state_init(char *arg
)
155 struct uct
*u
= calloc(1, sizeof(struct uct
));
159 u
->gamelen
= MC_GAMELEN
;
161 u
->mc
.capture_rate
= 100;
162 u
->mc
.atari_rate
= 100;
164 // Looking at the actual playouts, this just encourages MC to make
166 u
->mc
.local_rate
= 0;
169 char *optspec
, *next
= arg
;
172 next
+= strcspn(next
, ",");
173 if (*next
) { *next
++ = 0; } else { *next
= 0; }
175 char *optname
= optspec
;
176 char *optval
= strchr(optspec
, '=');
177 if (optval
) *optval
++ = 0;
179 if (!strcasecmp(optname
, "debug")) {
181 u
->debug_level
= atoi(optval
);
184 } else if (!strcasecmp(optname
, "games") && optval
) {
185 u
->games
= atoi(optval
);
186 } else if (!strcasecmp(optname
, "gamelen") && optval
) {
187 u
->gamelen
= atoi(optval
);
188 } else if (!strcasecmp(optname
, "expand_p") && optval
) {
189 u
->expand_p
= atoi(optval
);
190 } else if (!strcasecmp(optname
, "policy") && optval
) {
191 char *policyarg
= strchr(optval
, '+');
194 if (!strcasecmp(optval
, "ucb1")) {
195 u
->policy
= policy_ucb1_init(u
, policyarg
);
196 } else if (!strcasecmp(optval
, "ucb1tuned")) {
197 u
->policy
= policy_ucb1tuned_init(u
, policyarg
);
199 } else if (!strcasecmp(optname
, "pure")) {
200 u
->mc
.capture_rate
= u
->mc
.local_rate
= u
->mc
.cut_rate
= 0;
201 } else if (!strcasecmp(optname
, "capturerate") && optval
) {
202 u
->mc
.capture_rate
= atoi(optval
);
203 } else if (!strcasecmp(optname
, "atarirate") && optval
) {
204 u
->mc
.atari_rate
= atoi(optval
);
205 } else if (!strcasecmp(optname
, "localrate") && optval
) {
206 u
->mc
.local_rate
= atoi(optval
);
207 } else if (!strcasecmp(optname
, "cutrate") && optval
) {
208 u
->mc
.cut_rate
= atoi(optval
);
210 fprintf(stderr
, "uct: Invalid engine argument %s or missing value\n", optname
);
215 u
->resign_ratio
= 0.2; /* Resign when most games are lost. */
216 u
->loss_threshold
= 0.95; /* Stop reading if after at least 500 playouts this is best value. */
217 u
->mc
.debug_level
= u
->debug_level
;
218 u
->policy
= policy_ucb1_init(u
, NULL
);
225 engine_uct_init(char *arg
)
227 struct uct
*u
= uct_state_init(arg
);
228 struct engine
*e
= calloc(1, sizeof(struct engine
));
229 e
->name
= "UCT Engine";
230 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).";
231 e
->genmove
= uct_genmove
;