11 #include "uct/dynkomi.h"
12 #include "uct/internal.h"
17 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
= calloc2(1, sizeof(*d
));
33 d
->done
= 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 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 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 linear_permove(d
, b
, tree
);
82 uct_dynkomi_init_linear(struct uct
*u
, char *arg
, struct board
*b
)
84 struct uct_dynkomi
*d
= calloc2(1, sizeof(*d
));
86 d
->permove
= linear_permove
;
87 d
->persim
= linear_persim
;
88 d
->done
= generic_done
;
90 struct dynkomi_linear
*l
= calloc2(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. */
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
;
155 /* Game portion at which losing komi is not allowed anymore. */
156 float losing_komi_stop
;
157 /* Alternative game portion determination. */
159 float (*indicator
)(struct uct_dynkomi
*d
, struct board
*b
, struct tree
*tree
, enum stone color
);
161 /* Value-based adaptation. */
162 float zone_red
, zone_green
;
164 float score_step_byavg
; // use portion of average score as increment
165 bool use_komi_ratchet
;
166 bool losing_komi_ratchet
; // ratchet even losing komi
167 int komi_ratchet_maxage
;
168 // runtime, not configuration:
169 int komi_ratchet_age
;
172 /* Score-based adaptation. */
173 float (*adapter
)(struct uct_dynkomi
*d
, struct board
*b
);
174 float adapt_base
; // [0,1)
175 /* Sigmoid adaptation rate parameter; see below for details. */
176 float adapt_phase
; // [0,1]
177 float adapt_rate
; // [1,infty)
178 /* Linear adaptation rate parameter. */
180 float adapt_dir
; // [-1,1]
182 #define TRUSTWORTHY_KOMI_PLAYOUTS 200
185 board_game_portion(struct dynkomi_adaptive
*a
, struct board
*b
)
187 if (!a
->adapt_aport
) {
188 int total_moves
= b
->moves
+ 2 * board_estimated_moves_left(b
);
189 return (float) b
->moves
/ total_moves
;
191 int brsize
= board_size(b
) - 2;
192 return 1.0 - (float) b
->flen
/ (brsize
* brsize
);
197 adapter_sigmoid(struct uct_dynkomi
*d
, struct board
*b
)
199 struct dynkomi_adaptive
*a
= d
->data
;
200 /* Figure out how much to adjust the komi based on the game
201 * stage. The adaptation rate is 0 at the beginning,
202 * at game stage a->adapt_phase crosses though 0.5 and
203 * approaches 1 at the game end; the slope is controlled
204 * by a->adapt_rate. */
205 float game_portion
= board_game_portion(a
, b
);
206 float l
= game_portion
- a
->adapt_phase
;
207 return 1.0 / (1.0 + exp(-a
->adapt_rate
* l
));
211 adapter_linear(struct uct_dynkomi
*d
, struct board
*b
)
213 struct dynkomi_adaptive
*a
= d
->data
;
214 /* Figure out how much to adjust the komi based on the game
215 * stage. We just linearly increase/decrease the adaptation
216 * rate for first N moves. */
217 if (b
->moves
> a
->adapt_moves
)
219 if (a
->adapt_dir
< 0)
220 return 1 - (- a
->adapt_dir
) * b
->moves
/ a
->adapt_moves
;
222 return a
->adapt_dir
* b
->moves
/ a
->adapt_moves
;
226 komi_by_score(struct uct_dynkomi
*d
, struct board
*b
, struct tree
*tree
, enum stone color
)
228 struct dynkomi_adaptive
*a
= d
->data
;
229 if (d
->score
.playouts
< TRUSTWORTHY_KOMI_PLAYOUTS
)
230 return tree
->extra_komi
;
232 struct move_stats score
= d
->score
;
233 /* Almost-reset tree->score to gather fresh stats. */
234 d
->score
.playouts
= 1;
236 /* Look at average score and push extra_komi in that direction. */
237 float p
= a
->adapter(d
, b
);
238 p
= a
->adapt_base
+ p
* (1 - a
->adapt_base
);
239 if (p
> 0.9) p
= 0.9; // don't get too eager!
240 float extra_komi
= tree
->extra_komi
+ p
* score
.value
;
242 fprintf(stderr
, "mC += %f * %f\n", p
, score
.value
);
247 komi_by_value(struct uct_dynkomi
*d
, struct board
*b
, struct tree
*tree
, enum stone color
)
249 struct dynkomi_adaptive
*a
= d
->data
;
250 if (d
->value
.playouts
< TRUSTWORTHY_KOMI_PLAYOUTS
)
251 return tree
->extra_komi
;
253 struct move_stats value
= d
->value
;
254 /* Almost-reset tree->value to gather fresh stats. */
255 d
->value
.playouts
= 1;
256 /* Correct color POV. */
257 if (color
== S_WHITE
)
258 value
.value
= 1 - value
.value
;
260 /* We have three "value zones":
261 * red zone | yellow zone | green zone
263 * red zone: reduce komi
264 * yellow zone: do not touch komi
265 * green zone: enlage komi.
267 * Also, at some point komi will be tuned in such way
268 * that it will be in green zone but increasing it will
269 * be unfeasible. Thus, we have a _ratchet_ - we will
270 * remember the last komi that has put us into the
271 * red zone, and not use it or go over it. We use the
272 * ratchet only when giving extra komi, we always want
273 * to try to reduce extra komi we take.
275 * TODO: Make the ratchet expire after a while. */
277 /* We use komi_by_color() first to normalize komi
278 * additions/subtractions, then apply it again on
279 * return value to restore original komi parity. */
280 /* Positive extra_komi means that we are _giving_
281 * komi (winning), negative extra_komi is _taking_
283 float extra_komi
= komi_by_color(tree
->extra_komi
, color
);
284 int score_step_red
= -a
->score_step
;
285 int score_step_green
= a
->score_step
;
287 if (a
->score_step_byavg
!= 0) {
288 struct move_stats score
= d
->score
;
289 /* Almost-reset tree->score to gather fresh stats. */
290 d
->score
.playouts
= 1;
291 /* Correct color POV. */
292 if (color
== S_WHITE
)
293 score
.value
= - score
.value
;
295 score_step_green
= round(score
.value
* a
->score_step_byavg
);
297 score_step_red
= round(-score
.value
* a
->score_step_byavg
);
298 if (score_step_green
< 0 || score_step_red
> 0) {
299 /* The steps are in bad direction - keep still. */
300 return komi_by_color(extra_komi
, color
);
304 /* Wear out the ratchet. */
305 if (a
->use_komi_ratchet
&& a
->komi_ratchet_maxage
> 0) {
306 a
->komi_ratchet_age
+= value
.playouts
;
307 if (a
->komi_ratchet_age
> a
->komi_ratchet_maxage
) {
308 a
->komi_ratchet
= 1000;
309 a
->komi_ratchet_age
= 0;
313 if (value
.value
< a
->zone_red
) {
314 /* Red zone. Take extra komi. */
316 fprintf(stderr
, "[red] %f, step %d | komi ratchet %f age %d/%d -> %f\n",
317 value
.value
, score_step_red
, a
->komi_ratchet
, a
->komi_ratchet_age
, a
->komi_ratchet_maxage
, extra_komi
);
318 if (a
->losing_komi_ratchet
|| extra_komi
> 0) {
319 /* extra_komi must be within existing bounds,
320 * except when it has been reset to zero by
322 assert(extra_komi
< a
->komi_ratchet
|| fabsf(extra_komi
) < 1);
323 a
->komi_ratchet
= extra_komi
;
324 a
->komi_ratchet_age
= 0;
326 extra_komi
+= score_step_red
;
327 return komi_by_color(extra_komi
, color
);
329 } else if (value
.value
< a
->zone_green
) {
330 /* Yellow zone, do nothing. */
331 return komi_by_color(extra_komi
, color
);
334 /* Green zone. Give extra komi. */
336 fprintf(stderr
, "[green] %f, step %d | komi ratchet %f age %d/%d\n",
337 value
.value
, score_step_green
, a
->komi_ratchet
, a
->komi_ratchet_age
, a
->komi_ratchet_maxage
);
338 extra_komi
+= score_step_green
;
339 if (a
->use_komi_ratchet
&& extra_komi
>= a
->komi_ratchet
)
340 extra_komi
= a
->komi_ratchet
- 1;
341 return komi_by_color(extra_komi
, color
);
346 bounded_komi(struct dynkomi_adaptive
*a
, struct board
*b
,
347 enum stone color
, float komi
, float max_losing_komi
)
349 /* At the end of game, disallow losing komi. */
350 if (komi_by_color(komi
, color
) < 0
351 && board_game_portion(a
, b
) > a
->losing_komi_stop
)
354 /* Get lower bound on komi we take so that we don't underperform
356 float min_komi
= komi_by_color(- max_losing_komi
, color
);
358 if (komi_by_color(komi
- min_komi
, color
) > 0)
365 adaptive_permove(struct uct_dynkomi
*d
, struct board
*b
, struct tree
*tree
)
367 struct dynkomi_adaptive
*a
= d
->data
;
368 enum stone color
= stone_other(tree
->root_color
);
370 fprintf(stderr
, "m %d/%d ekomi %f permove %f/%d\n",
371 b
->moves
, a
->lead_moves
, tree
->extra_komi
,
372 d
->score
.value
, d
->score
.playouts
);
374 if (b
->moves
<= a
->lead_moves
)
375 return bounded_komi(a
, b
, color
,
376 board_effective_handicap(b
, 7 /* XXX */),
379 float komi
= a
->indicator(d
, b
, tree
, color
);
381 fprintf(stderr
, "dynkomi: %f -> %f\n", tree
->extra_komi
, komi
);
382 return bounded_komi(a
, b
, color
, komi
, a
->max_losing_komi
);
386 adaptive_persim(struct uct_dynkomi
*d
, struct board
*b
, struct tree
*tree
, struct tree_node
*node
)
388 return tree
->extra_komi
;
392 uct_dynkomi_init_adaptive(struct uct
*u
, char *arg
, struct board
*b
)
394 struct uct_dynkomi
*d
= calloc2(1, sizeof(*d
));
396 d
->permove
= adaptive_permove
;
397 d
->persim
= adaptive_persim
;
398 d
->done
= generic_done
;
400 struct dynkomi_adaptive
*a
= calloc2(1, sizeof(*a
));
403 if (board_size(b
) - 2 >= 19)
406 a
->lead_moves
= 4; // XXX
407 a
->max_losing_komi
= 100;
408 a
->losing_komi_stop
= 1.0f
;
409 a
->indicator
= komi_by_value
;
411 a
->adapter
= adapter_sigmoid
;
413 a
->adapt_phase
= 0.65;
414 a
->adapt_moves
= 200;
418 a
->zone_green
= 0.50;
420 a
->use_komi_ratchet
= true;
421 a
->komi_ratchet_maxage
= 25000;
422 a
->komi_ratchet
= 1000;
425 char *optspec
, *next
= arg
;
428 next
+= strcspn(next
, ":");
429 if (*next
) { *next
++ = 0; } else { *next
= 0; }
431 char *optname
= optspec
;
432 char *optval
= strchr(optspec
, '=');
433 if (optval
) *optval
++ = 0;
435 if (!strcasecmp(optname
, "lead_moves") && optval
) {
436 /* Do not adjust komi adaptively for first
438 a
->lead_moves
= atoi(optval
);
439 } else if (!strcasecmp(optname
, "max_losing_komi") && optval
) {
440 a
->max_losing_komi
= atof(optval
);
441 } else if (!strcasecmp(optname
, "losing_komi_stop") && optval
) {
442 a
->losing_komi_stop
= atof(optval
);
443 } else if (!strcasecmp(optname
, "indicator")) {
444 /* Adaptatation indicator - how to decide
445 * the adaptation rate and direction. */
446 if (!strcasecmp(optval
, "value")) {
447 /* Winrate w/ komi so far. */
448 a
->indicator
= komi_by_value
;
449 } else if (!strcasecmp(optval
, "score")) {
450 /* Expected score w/ current komi. */
451 a
->indicator
= komi_by_score
;
453 fprintf(stderr
, "UCT: Invalid indicator %s\n", optval
);
457 /* value indicator settings */
458 } else if (!strcasecmp(optname
, "zone_red") && optval
) {
459 a
->zone_red
= atof(optval
);
460 } else if (!strcasecmp(optname
, "zone_green") && optval
) {
461 a
->zone_green
= atof(optval
);
462 } else if (!strcasecmp(optname
, "score_step") && optval
) {
463 a
->score_step
= atoi(optval
);
464 } else if (!strcasecmp(optname
, "score_step_byavg") && optval
) {
465 a
->score_step_byavg
= atof(optval
);
466 } else if (!strcasecmp(optname
, "use_komi_ratchet")) {
467 a
->use_komi_ratchet
= !optval
|| atoi(optval
);
468 } else if (!strcasecmp(optname
, "losing_komi_ratchet")) {
469 a
->losing_komi_ratchet
= !optval
|| atoi(optval
);
470 } else if (!strcasecmp(optname
, "komi_ratchet_age") && optval
) {
471 a
->komi_ratchet_maxage
= atoi(optval
);
473 /* score indicator settings */
474 } else if (!strcasecmp(optname
, "adapter") && optval
) {
475 /* Adaptatation method. */
476 if (!strcasecmp(optval
, "sigmoid")) {
477 a
->adapter
= adapter_sigmoid
;
478 } else if (!strcasecmp(optval
, "linear")) {
479 a
->adapter
= adapter_linear
;
481 fprintf(stderr
, "UCT: Invalid adapter %s\n", optval
);
484 } else if (!strcasecmp(optname
, "adapt_base") && optval
) {
485 /* Adaptation base rate; see above. */
486 a
->adapt_base
= atof(optval
);
487 } else if (!strcasecmp(optname
, "adapt_rate") && optval
) {
488 /* Adaptation slope; see above. */
489 a
->adapt_rate
= atof(optval
);
490 } else if (!strcasecmp(optname
, "adapt_phase") && optval
) {
491 /* Adaptation phase shift; see above. */
492 a
->adapt_phase
= atof(optval
);
493 } else if (!strcasecmp(optname
, "adapt_moves") && optval
) {
494 /* Adaptation move amount; see above. */
495 a
->adapt_moves
= atoi(optval
);
496 } else if (!strcasecmp(optname
, "adapt_aport")) {
497 a
->adapt_aport
= !optval
|| atoi(optval
);
498 } else if (!strcasecmp(optname
, "adapt_dir") && optval
) {
499 /* Adaptation direction vector; see above. */
500 a
->adapt_dir
= atof(optval
);
503 fprintf(stderr
, "uct: Invalid dynkomi argument %s or missing value\n", optname
);