11 #include "uct/dynkomi.h"
12 #include "uct/internal.h"
17 uct_dynkomi_generic_done(struct uct_dynkomi
*d
)
19 if (d
->data
) free(d
->data
);
24 /* NONE dynkomi strategy - never fiddle with komi values. */
27 uct_dynkomi_init_none(struct uct
*u
, char *arg
, struct board
*b
)
29 struct uct_dynkomi
*d
= calloc(1, sizeof(*d
));
33 d
->done
= uct_dynkomi_generic_done
;
37 fprintf(stderr
, "uct: Dynkomi method none accepts no arguments\n");
45 /* LINEAR dynkomi strategy - Linearly Decreasing Handicap Compensation. */
46 /* At move 0, we impose extra komi of handicap_count*handicap_value, then
47 * we linearly decrease this extra komi throughout the game down to 0
50 struct dynkomi_linear
{
57 uct_dynkomi_linear_permove(struct uct_dynkomi
*d
, struct board
*b
, struct tree
*tree
)
59 struct dynkomi_linear
*l
= d
->data
;
60 if (b
->moves
>= l
->moves
)
63 float base_komi
= board_effective_handicap(b
, l
->handicap_value
);
64 float extra_komi
= base_komi
* (l
->moves
- b
->moves
) / l
->moves
;
69 uct_dynkomi_linear_persim(struct uct_dynkomi
*d
, struct board
*b
, struct tree
*tree
, struct tree_node
*node
)
71 struct dynkomi_linear
*l
= d
->data
;
73 return tree
->extra_komi
;
74 /* We don't reuse computed value from tree->extra_komi,
75 * since we want to use value correct for this node depth.
76 * This also means the values will stay correct after
78 return uct_dynkomi_linear_permove(d
, b
, tree
);
82 uct_dynkomi_init_linear(struct uct
*u
, char *arg
, struct board
*b
)
84 struct uct_dynkomi
*d
= calloc(1, sizeof(*d
));
86 d
->permove
= uct_dynkomi_linear_permove
;
87 d
->persim
= uct_dynkomi_linear_persim
;
88 d
->done
= uct_dynkomi_generic_done
;
90 struct dynkomi_linear
*l
= calloc(1, sizeof(*l
));
93 if (board_size(b
) - 2 >= 19)
95 l
->handicap_value
= 7;
98 char *optspec
, *next
= arg
;
101 next
+= strcspn(next
, ":");
102 if (*next
) { *next
++ = 0; } else { *next
= 0; }
104 char *optname
= optspec
;
105 char *optval
= strchr(optspec
, '=');
106 if (optval
) *optval
++ = 0;
108 if (!strcasecmp(optname
, "moves") && optval
) {
109 /* Dynamic komi in handicap game; linearly
110 * decreases to basic settings until move
112 l
->moves
= atoi(optval
);
113 } else if (!strcasecmp(optname
, "handicap_value") && optval
) {
114 /* Point value of single handicap stone,
115 * for dynkomi computation. */
116 l
->handicap_value
= atoi(optval
);
117 } else if (!strcasecmp(optname
, "rootbased")) {
118 /* If set, the extra komi applied will be
119 * the same for all simulations within a move,
120 * instead of being same for all simulations
121 * within the tree node. */
122 l
->rootbased
= !optval
|| atoi(optval
);
124 fprintf(stderr
, "uct: Invalid dynkomi argument %s or missing value\n", optname
);
134 /* ADAPTIVE dynkomi strategy - Adaptive Situational Compensation */
135 /* We adapt the komi based on current situation:
136 * (i) score-based: We maintain the average score outcome of our
137 * games and adjust the komi by a fractional step towards the expected
139 * (ii) value-based: While winrate is above given threshold, adjust
140 * the komi by a fixed step in the appropriate direction.
141 * These adjustments can be
142 * (a) Move-stepped, new extra komi value is always set only at the
143 * beginning of the tree search for next move;
144 * (b) Continuous, new extra komi value is periodically re-determined
145 * and adjusted throughout a single tree search. [TODO] */
147 struct dynkomi_adaptive
{
148 /* Do not take measured average score into regard for
149 * first @lead_moves - the variance is just too much.
150 * (Instead, we consider the handicap-based komi provided
151 * by linear dynkomi.) */
153 /* Maximum komi to pretend the opponent to give. */
154 float max_losing_komi
;
156 /* Value-based adaptation. */
158 float zone_red
, zone_green
;
160 float komi_latch
; // runtime, not configuration
162 float (*adapter
)(struct dynkomi_adaptive
*a
, struct board
*b
);
163 float adapt_base
; // [0,1)
164 /* Sigmoid adaptation rate parameter; see below for details. */
165 float adapt_phase
; // [0,1]
166 float adapt_rate
; // [1,infty)
167 /* Linear adaptation rate parameter. */
169 float adapt_dir
; // [-1,1]
171 #define TRUSTWORTHY_KOMI_PLAYOUTS 200
174 adapter_sigmoid(struct dynkomi_adaptive
*a
, struct board
*b
)
176 /* Figure out how much to adjust the komi based on the game
177 * stage. The adaptation rate is ~0.9 at the beginning,
178 * at game stage a->adapt_phase crosses though 0.5 and
179 * approaches 0 at the game end; the slope is controlled
180 * by a->adapt_rate. */
181 int total_moves
= b
->moves
+ board_estimated_moves_left(b
);
182 float game_portion
= (float) b
->moves
/ total_moves
;
183 float l
= -game_portion
+ a
->adapt_phase
;
184 return 1.0 / (1.0 + exp(-a
->adapt_rate
* l
));
188 adapter_linear(struct dynkomi_adaptive
*a
, struct board
*b
)
190 /* Figure out how much to adjust the komi based on the game
191 * stage. We just linearly increase/decrease the adaptation
192 * rate for first N moves. */
193 if (b
->moves
> a
->adapt_moves
)
195 if (a
->adapt_dir
< 0)
196 return 1 - (- a
->adapt_dir
) * b
->moves
/ a
->adapt_moves
;
198 return a
->adapt_dir
* b
->moves
/ a
->adapt_moves
;
202 uct_dynkomi_adaptive_permove(struct uct_dynkomi
*d
, struct board
*b
, struct tree
*tree
)
204 struct dynkomi_adaptive
*a
= d
->data
;
206 fprintf(stderr
, "m %d/%d ekomi %f permove %f/%d\n",
207 b
->moves
, a
->lead_moves
, tree
->extra_komi
,
208 tree
->score
.value
, tree
->score
.playouts
);
209 if (b
->moves
<= a
->lead_moves
)
210 return board_effective_handicap(b
, 7 /* XXX */);
212 /* Get lower bound on komi value so that we don't underperform
213 * too much. XXX: We rely on the fact that we don't use dynkomi
214 * as white for now. */
215 float min_komi
= - a
->max_losing_komi
;
217 /* Perhaps we are adaptive value-based, not score-based? */
218 if (a
->value_based
) {
219 /* In that case, we have three zones:
220 * red zone | yellow zone | green zone
222 * red zone: reduce komi
223 * yellow zone: do not touch komi
224 * green zone: enlage komi.
226 * Also, at some point komi will be tuned in such way
227 * that it will be in green zone but increasing it will
228 * be unfeasible. Thus, we have a _latch_ - we will
229 * remember the last komi that has put us into the
230 * red zone, and not use it or go over it. We use the
231 * latch only when giving extra komi, we always want
232 * to try to reduce extra komi we take.
234 * TODO: Make the latch expire after a while. */
235 if (tree
->root
->u
.playouts
< TRUSTWORTHY_KOMI_PLAYOUTS
)
236 return tree
->extra_komi
;
237 float value
= tree
->root
->u
.value
;
238 float extra_komi
= tree
->extra_komi
;
239 if (value
< a
->zone_red
) {
240 /* Red zone. Take extra komi. */
241 if (extra_komi
> 0) a
->komi_latch
= extra_komi
;
242 extra_komi
-= a
->score_step
; // XXX: we depend on being black
243 return extra_komi
> min_komi
? extra_komi
: min_komi
;
244 } else if (value
< a
->zone_green
) {
245 /* Yellow zone, do nothing. */
248 /* Green zone. Give extra komi. */
249 extra_komi
+= a
->score_step
; // XXX: we depend on being black
250 return extra_komi
< a
->komi_latch
? extra_komi
: a
->komi_latch
- 1;
254 if (tree
->score
.playouts
< TRUSTWORTHY_KOMI_PLAYOUTS
)
255 return tree
->extra_komi
;
257 struct move_stats score
= tree
->score
;
258 /* Almost-reset tree->score to gather fresh stats. */
259 tree
->score
.playouts
= 1;
261 /* Look at average score and push extra_komi in that direction. */
262 float p
= a
->adapter(a
, b
);
263 p
= a
->adapt_base
+ p
* (1 - a
->adapt_base
);
264 if (p
> 0.9) p
= 0.9; // don't get too eager!
265 float extra_komi
= tree
->extra_komi
+ p
* score
.value
;
267 fprintf(stderr
, "mC %f + %f * %f = %f\n",
268 tree
->extra_komi
, p
, score
.value
, extra_komi
);
269 return extra_komi
> min_komi
? extra_komi
: min_komi
;
273 uct_dynkomi_adaptive_persim(struct uct_dynkomi
*d
, struct board
*b
, struct tree
*tree
, struct tree_node
*node
)
275 return tree
->extra_komi
;
279 uct_dynkomi_init_adaptive(struct uct
*u
, char *arg
, struct board
*b
)
281 struct uct_dynkomi
*d
= calloc(1, sizeof(*d
));
283 d
->permove
= uct_dynkomi_adaptive_permove
;
284 d
->persim
= uct_dynkomi_adaptive_persim
;
285 d
->done
= uct_dynkomi_generic_done
;
287 struct dynkomi_adaptive
*a
= calloc(1, sizeof(*a
));
290 if (board_size(b
) - 2 >= 19)
293 a
->lead_moves
= 4; // XXX
294 a
->max_losing_komi
= 10;
295 a
->adapter
= adapter_sigmoid
;
297 a
->adapt_phase
= 0.5;
298 a
->adapt_moves
= 200;
305 a
->komi_latch
= -1000;
308 char *optspec
, *next
= arg
;
311 next
+= strcspn(next
, ":");
312 if (*next
) { *next
++ = 0; } else { *next
= 0; }
314 char *optname
= optspec
;
315 char *optval
= strchr(optspec
, '=');
316 if (optval
) *optval
++ = 0;
318 if (!strcasecmp(optname
, "lead_moves") && optval
) {
319 /* Do not adjust komi adaptively for first
321 a
->lead_moves
= atoi(optval
);
322 } else if (!strcasecmp(optname
, "max_losing_komi") && optval
) {
323 a
->max_losing_komi
= atof(optval
);
325 } else if (!strcasecmp(optname
, "value_based")) {
326 a
->value_based
= !optval
|| atoi(optval
);
327 } else if (!strcasecmp(optname
, "zone_red") && optval
) {
328 a
->zone_red
= atof(optval
);
329 } else if (!strcasecmp(optname
, "zone_green") && optval
) {
330 a
->zone_green
= atof(optval
);
331 } else if (!strcasecmp(optname
, "score_step") && optval
) {
332 a
->score_step
= atoi(optval
);
334 } else if (!strcasecmp(optname
, "adapter") && optval
) {
335 /* Adaptatation method. */
336 if (!strcasecmp(optval
, "sigmoid")) {
337 a
->adapter
= adapter_sigmoid
;
338 } else if (!strcasecmp(optval
, "linear")) {
339 a
->adapter
= adapter_linear
;
341 fprintf(stderr
, "UCT: Invalid adapter %s\n", optval
);
344 } else if (!strcasecmp(optname
, "adapt_base") && optval
) {
345 /* Adaptation base rate; see above. */
346 a
->adapt_base
= atof(optval
);
347 } else if (!strcasecmp(optname
, "adapt_rate") && optval
) {
348 /* Adaptation slope; see above. */
349 a
->adapt_rate
= atof(optval
);
350 } else if (!strcasecmp(optname
, "adapt_phase") && optval
) {
351 /* Adaptation phase shift; see above. */
352 a
->adapt_phase
= atof(optval
);
353 } else if (!strcasecmp(optname
, "adapt_moves") && optval
) {
354 /* Adaptation move amount; see above. */
355 a
->adapt_moves
= atoi(optval
);
356 } else if (!strcasecmp(optname
, "adapt_dir") && optval
) {
357 /* Adaptation direction vector; see above. */
358 a
->adapt_dir
= atof(optval
);
360 fprintf(stderr
, "uct: Invalid dynkomi argument %s or missing value\n", optname
);