10 #include "tactics/util.h"
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
48 * at @moves moves. Towards the end of the game the linear compensation
49 * becomes zero but we increase the extra komi when winning big. This reduces
50 * the number of point-wasting moves and makes the game more enjoyable for humans. */
52 struct dynkomi_linear
{
53 int handicap_value
[S_MAX
];
56 /* Increase the extra komi if my win ratio > green_zone but always
57 * keep extra_komi <= komi_ratchet. komi_ratchet starts infinite but decreases
58 * when we give too much extra komi and this puts us back < orange_zone.
59 * This is meant only to increase the territory margin when playing against
60 * weaker opponents. We never take negative komi when losing. The ratchet helps
61 * avoiding oscillations and keeping us above orange_zone.
62 * To disable the adaptive phase, set green_zone=2. */
63 floating_t komi_ratchet
;
64 floating_t green_zone
;
65 floating_t orange_zone
;
70 linear_simple(struct dynkomi_linear
*l
, struct board
*b
, enum stone color
)
72 int lmoves
= l
->moves
[color
];
73 floating_t base_komi
= board_effective_handicap(b
, l
->handicap_value
[color
]);
74 return base_komi
* (lmoves
- b
->moves
) / lmoves
;
78 linear_permove(struct uct_dynkomi
*d
, struct board
*b
, struct tree
*tree
)
80 struct dynkomi_linear
*l
= d
->data
;
81 enum stone color
= d
->uct
->pondering
? tree
->root_color
: stone_other(tree
->root_color
);
82 int lmoves
= l
->moves
[color
];
84 if (b
->moves
< lmoves
)
85 return linear_simple(l
, b
, color
);
87 /* Allow simple adaptation in extreme endgame situations. */
89 floating_t extra_komi
= floor(tree
->extra_komi
);
91 /* Do not take decisions on unstable value. */
92 if (tree
->root
->u
.playouts
< GJ_MINGAMES
)
95 floating_t my_value
= tree_node_get_value(tree
, 1, tree
->root
->u
.value
);
96 /* We normalize komi as in komi_by_value(), > 0 when winning. */
97 extra_komi
= komi_by_color(extra_komi
, color
);
98 if (extra_komi
< 0 && DEBUGL(3))
99 fprintf(stderr
, "XXX: extra_komi %.3f < 0 (color %s tree ek %.3f)\n", extra_komi
, stone2str(color
), tree
->extra_komi
);
100 // assert(extra_komi >= 0);
101 floating_t orig_komi
= extra_komi
;
103 if (my_value
< 0.5 && l
->komi_ratchet
> 0 && l
->komi_ratchet
!= INFINITY
) {
105 fprintf(stderr
, "losing %f extra komi %.1f ratchet %.1f -> 0\n",
106 my_value
, extra_komi
, l
->komi_ratchet
);
107 /* Disable dynkomi completely, too dangerous in this game. */
108 extra_komi
= l
->komi_ratchet
= 0;
109 tree
->untrustworthy_tree
= true;
111 } else if (my_value
< l
->orange_zone
&& extra_komi
> 0) {
112 extra_komi
= l
->komi_ratchet
= fmax(extra_komi
- l
->drop_step
, 0.0);
113 if (extra_komi
!= orig_komi
&& DEBUGL(3)) {
114 fprintf(stderr
, "dropping to %f, extra komi %.1f -> %.1f\n",
115 my_value
, orig_komi
, extra_komi
);
116 tree
->untrustworthy_tree
= true;
119 } else if (my_value
> l
->green_zone
&& extra_komi
+ 1 <= l
->komi_ratchet
) {
121 if (extra_komi
!= orig_komi
&& DEBUGL(3))
122 fprintf(stderr
, "winning %f extra_komi %.1f -> %.1f, ratchet %.1f\n",
123 my_value
, orig_komi
, extra_komi
, l
->komi_ratchet
);
125 return komi_by_color(extra_komi
, color
);
129 linear_persim(struct uct_dynkomi
*d
, struct board
*b
, struct tree
*tree
, struct tree_node
*node
)
131 struct dynkomi_linear
*l
= d
->data
;
133 return tree
->extra_komi
;
135 /* We don't reuse computed value from tree->extra_komi,
136 * since we want to use value correct for this node depth.
137 * This also means the values will stay correct after
140 enum stone color
= d
->uct
->pondering
? tree
->root_color
: stone_other(tree
->root_color
);
141 int lmoves
= l
->moves
[color
];
142 if (b
->moves
< lmoves
)
143 return linear_simple(l
, b
, color
);
144 return tree
->extra_komi
;
148 uct_dynkomi_init_linear(struct uct
*u
, char *arg
, struct board
*b
)
150 struct uct_dynkomi
*d
= calloc2(1, sizeof(*d
));
152 d
->permove
= linear_permove
;
153 d
->persim
= linear_persim
;
154 d
->done
= generic_done
;
156 struct dynkomi_linear
*l
= calloc2(1, sizeof(*l
));
159 /* Force white to feel behind and try harder, but not to the
160 * point of resigning immediately in high handicap games.
161 * By move 100 white should still be behind but should have
162 * caught up enough to avoid resigning. */
163 int moves
= board_large(b
) ? 100 : 50;
164 if (!board_small(b
)) {
165 l
->moves
[S_BLACK
] = moves
;
166 l
->moves
[S_WHITE
] = moves
;
169 /* The real value of one stone is twice the komi so about 15 points.
170 * But use a lower value to avoid being too pessimistic as black
171 * or too optimistic as white. */
172 l
->handicap_value
[S_BLACK
] = 8;
173 l
->handicap_value
[S_WHITE
] = 1;
175 l
->komi_ratchet
= INFINITY
;
176 l
->green_zone
= 0.85;
177 l
->orange_zone
= 0.8;
181 char *optspec
, *next
= arg
;
184 next
+= strcspn(next
, ":");
185 if (*next
) { *next
++ = 0; } else { *next
= 0; }
187 char *optname
= optspec
;
188 char *optval
= strchr(optspec
, '=');
189 if (optval
) *optval
++ = 0;
191 if (!strcasecmp(optname
, "moves") && optval
) {
192 /* Dynamic komi in handicap game; linearly
193 * decreases to basic settings until move
194 * #optval. moves=blackmoves%whitemoves */
195 for (int i
= S_BLACK
; *optval
&& i
<= S_WHITE
; i
++) {
196 l
->moves
[i
] = atoi(optval
);
197 optval
+= strcspn(optval
, "%");
198 if (*optval
) optval
++;
200 } else if (!strcasecmp(optname
, "handicap_value") && optval
) {
201 /* Point value of single handicap stone,
202 * for dynkomi computation. */
203 for (int i
= S_BLACK
; *optval
&& i
<= S_WHITE
; i
++) {
204 l
->handicap_value
[i
] = atoi(optval
);
205 optval
+= strcspn(optval
, "%");
206 if (*optval
) optval
++;
208 } else if (!strcasecmp(optname
, "rootbased")) {
209 /* If set, the extra komi applied will be
210 * the same for all simulations within a move,
211 * instead of being same for all simulations
212 * within the tree node. */
213 l
->rootbased
= !optval
|| atoi(optval
);
214 } else if (!strcasecmp(optname
, "green_zone") && optval
) {
215 /* Increase komi when win ratio is above green_zone */
216 l
->green_zone
= atof(optval
);
217 } else if (!strcasecmp(optname
, "orange_zone") && optval
) {
218 /* Decrease komi when > 0 and win ratio is below orange_zone */
219 l
->orange_zone
= atof(optval
);
220 } else if (!strcasecmp(optname
, "drop_step") && optval
) {
221 /* Decrease komi by drop_step points */
222 l
->drop_step
= atof(optval
);
224 fprintf(stderr
, "uct: Invalid dynkomi argument %s or missing value\n", optname
);
234 /* ADAPTIVE dynkomi strategy - Adaptive Situational Compensation */
235 /* We adapt the komi based on current situation:
236 * (i) score-based: We maintain the average score outcome of our
237 * games and adjust the komi by a fractional step towards the expected
239 * (ii) value-based: While winrate is above given threshold, adjust
240 * the komi by a fixed step in the appropriate direction.
241 * These adjustments can be
242 * (a) Move-stepped, new extra komi value is always set only at the
243 * beginning of the tree search for next move;
244 * (b) Continuous, new extra komi value is periodically re-determined
245 * and adjusted throughout a single tree search. */
247 struct dynkomi_adaptive
{
248 /* Do not take measured average score into regard for
249 * first @lead_moves - the variance is just too much.
250 * (Instead, we consider the handicap-based komi provided
251 * by linear dynkomi.) */
253 /* Maximum komi to pretend the opponent to give. */
254 floating_t max_losing_komi
;
255 /* Game portion at which losing komi is not allowed anymore. */
256 floating_t losing_komi_stop
;
257 /* Turn off dynkomi at the (perceived) closing of the game
258 * (last few moves). */
259 bool no_komi_at_game_end
;
260 /* Alternative game portion determination. */
262 floating_t (*indicator
)(struct uct_dynkomi
*d
, struct board
*b
, struct tree
*tree
, enum stone color
);
264 /* Value-based adaptation. */
265 floating_t zone_red
, zone_green
;
267 floating_t score_step_byavg
; // use portion of average score as increment
268 bool use_komi_ratchet
;
269 bool losing_komi_ratchet
; // ratchet even losing komi
270 int komi_ratchet_maxage
;
271 // runtime, not configuration:
272 int komi_ratchet_age
;
273 floating_t komi_ratchet
;
275 /* Score-based adaptation. */
276 floating_t (*adapter
)(struct uct_dynkomi
*d
, struct board
*b
);
277 floating_t adapt_base
; // [0,1)
278 /* Sigmoid adaptation rate parameter; see below for details. */
279 floating_t adapt_phase
; // [0,1]
280 floating_t adapt_rate
; // [1,infty)
281 /* Linear adaptation rate parameter. */
283 floating_t adapt_dir
; // [-1,1]
285 #define TRUSTWORTHY_KOMI_PLAYOUTS 200
288 board_game_portion(struct dynkomi_adaptive
*a
, struct board
*b
)
290 if (!a
->adapt_aport
) {
291 int total_moves
= b
->moves
+ 2 * board_estimated_moves_left(b
);
292 return (floating_t
) b
->moves
/ total_moves
;
294 int brsize
= board_size(b
) - 2;
295 return 1.0 - (floating_t
) b
->flen
/ (brsize
* brsize
);
300 adapter_sigmoid(struct uct_dynkomi
*d
, struct board
*b
)
302 struct dynkomi_adaptive
*a
= d
->data
;
303 /* Figure out how much to adjust the komi based on the game
304 * stage. The adaptation rate is 0 at the beginning,
305 * at game stage a->adapt_phase crosses though 0.5 and
306 * approaches 1 at the game end; the slope is controlled
307 * by a->adapt_rate. */
308 floating_t game_portion
= board_game_portion(a
, b
);
309 floating_t l
= game_portion
- a
->adapt_phase
;
310 return 1.0 / (1.0 + exp(-a
->adapt_rate
* l
));
314 adapter_linear(struct uct_dynkomi
*d
, struct board
*b
)
316 struct dynkomi_adaptive
*a
= d
->data
;
317 /* Figure out how much to adjust the komi based on the game
318 * stage. We just linearly increase/decrease the adaptation
319 * rate for first N moves. */
320 if (b
->moves
> a
->adapt_moves
)
322 if (a
->adapt_dir
< 0)
323 return 1 - (- a
->adapt_dir
) * b
->moves
/ a
->adapt_moves
;
325 return a
->adapt_dir
* b
->moves
/ a
->adapt_moves
;
329 komi_by_score(struct uct_dynkomi
*d
, struct board
*b
, struct tree
*tree
, enum stone color
)
331 struct dynkomi_adaptive
*a
= d
->data
;
332 if (d
->score
.playouts
< TRUSTWORTHY_KOMI_PLAYOUTS
)
333 return tree
->extra_komi
;
335 struct move_stats score
= d
->score
;
336 /* Almost-reset tree->score to gather fresh stats. */
337 d
->score
.playouts
= 1;
339 /* Look at average score and push extra_komi in that direction. */
340 floating_t p
= a
->adapter(d
, b
);
341 p
= a
->adapt_base
+ p
* (1 - a
->adapt_base
);
342 if (p
> 0.9) p
= 0.9; // don't get too eager!
343 floating_t extra_komi
= tree
->extra_komi
+ p
* score
.value
;
345 fprintf(stderr
, "mC += %f * %f\n", p
, score
.value
);
350 komi_by_value(struct uct_dynkomi
*d
, struct board
*b
, struct tree
*tree
, enum stone color
)
352 struct dynkomi_adaptive
*a
= d
->data
;
353 if (d
->value
.playouts
< TRUSTWORTHY_KOMI_PLAYOUTS
)
354 return tree
->extra_komi
;
356 struct move_stats value
= d
->value
;
357 /* Almost-reset tree->value to gather fresh stats. */
358 d
->value
.playouts
= 1;
359 /* Correct color POV. */
360 if (color
== S_WHITE
)
361 value
.value
= 1 - value
.value
;
363 /* We have three "value zones":
364 * red zone | yellow zone | green zone
366 * red zone: reduce komi
367 * yellow zone: do not touch komi
368 * green zone: enlage komi.
370 * Also, at some point komi will be tuned in such way
371 * that it will be in green zone but increasing it will
372 * be unfeasible. Thus, we have a _ratchet_ - we will
373 * remember the last komi that has put us into the
374 * red zone, and not use it or go over it. We use the
375 * ratchet only when giving extra komi, we always want
376 * to try to reduce extra komi we take.
378 * TODO: Make the ratchet expire after a while. */
380 /* We use komi_by_color() first to normalize komi
381 * additions/subtractions, then apply it again on
382 * return value to restore original komi parity. */
383 /* Positive extra_komi means that we are _giving_
384 * komi (winning), negative extra_komi is _taking_
386 floating_t extra_komi
= komi_by_color(tree
->extra_komi
, color
);
387 int score_step_red
= -a
->score_step
;
388 int score_step_green
= a
->score_step
;
390 if (a
->score_step_byavg
!= 0) {
391 struct move_stats score
= d
->score
;
392 /* Almost-reset tree->score to gather fresh stats. */
393 d
->score
.playouts
= 1;
394 /* Correct color POV. */
395 if (color
== S_WHITE
)
396 score
.value
= - score
.value
;
398 score_step_green
= round(score
.value
* a
->score_step_byavg
);
400 score_step_red
= round(-score
.value
* a
->score_step_byavg
);
401 if (score_step_green
< 0 || score_step_red
> 0) {
402 /* The steps are in bad direction - keep still. */
403 return komi_by_color(extra_komi
, color
);
407 /* Wear out the ratchet. */
408 if (a
->use_komi_ratchet
&& a
->komi_ratchet_maxage
> 0) {
409 a
->komi_ratchet_age
+= value
.playouts
;
410 if (a
->komi_ratchet_age
> a
->komi_ratchet_maxage
) {
411 a
->komi_ratchet
= 1000;
412 a
->komi_ratchet_age
= 0;
416 if (value
.value
< a
->zone_red
) {
417 /* Red zone. Take extra komi. */
419 fprintf(stderr
, "[red] %f, step %d | komi ratchet %f age %d/%d -> %f\n",
420 value
.value
, score_step_red
, a
->komi_ratchet
, a
->komi_ratchet_age
, a
->komi_ratchet_maxage
, extra_komi
);
421 if (a
->losing_komi_ratchet
|| extra_komi
> 0) {
422 a
->komi_ratchet
= extra_komi
;
423 a
->komi_ratchet_age
= 0;
425 extra_komi
+= score_step_red
;
426 return komi_by_color(extra_komi
, color
);
428 } else if (value
.value
< a
->zone_green
) {
429 /* Yellow zone, do nothing. */
430 return komi_by_color(extra_komi
, color
);
433 /* Green zone. Give extra komi. */
435 fprintf(stderr
, "[green] %f, step %d | komi ratchet %f age %d/%d\n",
436 value
.value
, score_step_green
, a
->komi_ratchet
, a
->komi_ratchet_age
, a
->komi_ratchet_maxage
);
437 extra_komi
+= score_step_green
;
438 if (a
->use_komi_ratchet
&& extra_komi
>= a
->komi_ratchet
)
439 extra_komi
= a
->komi_ratchet
- 1;
440 return komi_by_color(extra_komi
, color
);
445 bounded_komi(struct dynkomi_adaptive
*a
, struct board
*b
,
446 enum stone color
, floating_t komi
, floating_t max_losing_komi
)
448 /* At the end of game, disallow losing komi. */
449 if (komi_by_color(komi
, color
) < 0
450 && board_game_portion(a
, b
) > a
->losing_komi_stop
)
453 /* Get lower bound on komi we take so that we don't underperform
455 floating_t min_komi
= komi_by_color(- max_losing_komi
, color
);
457 if (komi_by_color(komi
- min_komi
, color
) > 0)
464 adaptive_permove(struct uct_dynkomi
*d
, struct board
*b
, struct tree
*tree
)
466 struct dynkomi_adaptive
*a
= d
->data
;
467 enum stone color
= stone_other(tree
->root_color
);
469 /* We do not use extra komi at the game end - we are not
470 * to fool ourselves at this point. */
471 if (a
->no_komi_at_game_end
&& board_estimated_moves_left(b
) <= MIN_MOVES_LEFT
) {
472 tree
->use_extra_komi
= false;
477 fprintf(stderr
, "m %d/%d ekomi %f permove %f/%d\n",
478 b
->moves
, a
->lead_moves
, tree
->extra_komi
,
479 d
->score
.value
, d
->score
.playouts
);
481 if (b
->moves
<= a
->lead_moves
)
482 return bounded_komi(a
, b
, color
,
483 board_effective_handicap(b
, 7 /* XXX */),
486 floating_t komi
= a
->indicator(d
, b
, tree
, color
);
488 fprintf(stderr
, "dynkomi: %f -> %f\n", tree
->extra_komi
, komi
);
489 return bounded_komi(a
, b
, color
, komi
, a
->max_losing_komi
);
493 adaptive_persim(struct uct_dynkomi
*d
, struct board
*b
, struct tree
*tree
, struct tree_node
*node
)
495 return tree
->extra_komi
;
499 uct_dynkomi_init_adaptive(struct uct
*u
, char *arg
, struct board
*b
)
501 struct uct_dynkomi
*d
= calloc2(1, sizeof(*d
));
503 d
->permove
= adaptive_permove
;
504 d
->persim
= adaptive_persim
;
505 d
->done
= generic_done
;
507 struct dynkomi_adaptive
*a
= calloc2(1, sizeof(*a
));
510 a
->lead_moves
= board_large(b
) ? 20 : 4; // XXX
511 a
->max_losing_komi
= 30;
512 a
->losing_komi_stop
= 1.0f
;
513 a
->no_komi_at_game_end
= true;
514 a
->indicator
= komi_by_value
;
516 a
->adapter
= adapter_sigmoid
;
518 a
->adapt_phase
= 0.65;
519 a
->adapt_moves
= 200;
523 a
->zone_green
= 0.50;
525 a
->use_komi_ratchet
= true;
526 a
->komi_ratchet_maxage
= 0;
527 a
->komi_ratchet
= 1000;
530 char *optspec
, *next
= arg
;
533 next
+= strcspn(next
, ":");
534 if (*next
) { *next
++ = 0; } else { *next
= 0; }
536 char *optname
= optspec
;
537 char *optval
= strchr(optspec
, '=');
538 if (optval
) *optval
++ = 0;
540 if (!strcasecmp(optname
, "lead_moves") && optval
) {
541 /* Do not adjust komi adaptively for first
543 a
->lead_moves
= atoi(optval
);
544 } else if (!strcasecmp(optname
, "max_losing_komi") && optval
) {
545 a
->max_losing_komi
= atof(optval
);
546 } else if (!strcasecmp(optname
, "losing_komi_stop") && optval
) {
547 a
->losing_komi_stop
= atof(optval
);
548 } else if (!strcasecmp(optname
, "no_komi_at_game_end")) {
549 a
->no_komi_at_game_end
= !optval
|| atoi(optval
);
550 } else if (!strcasecmp(optname
, "indicator")) {
551 /* Adaptatation indicator - how to decide
552 * the adaptation rate and direction. */
553 if (!strcasecmp(optval
, "value")) {
554 /* Winrate w/ komi so far. */
555 a
->indicator
= komi_by_value
;
556 } else if (!strcasecmp(optval
, "score")) {
557 /* Expected score w/ current komi. */
558 a
->indicator
= komi_by_score
;
560 fprintf(stderr
, "UCT: Invalid indicator %s\n", optval
);
564 /* value indicator settings */
565 } else if (!strcasecmp(optname
, "zone_red") && optval
) {
566 a
->zone_red
= atof(optval
);
567 } else if (!strcasecmp(optname
, "zone_green") && optval
) {
568 a
->zone_green
= atof(optval
);
569 } else if (!strcasecmp(optname
, "score_step") && optval
) {
570 a
->score_step
= atoi(optval
);
571 } else if (!strcasecmp(optname
, "score_step_byavg") && optval
) {
572 a
->score_step_byavg
= atof(optval
);
573 } else if (!strcasecmp(optname
, "use_komi_ratchet")) {
574 a
->use_komi_ratchet
= !optval
|| atoi(optval
);
575 } else if (!strcasecmp(optname
, "losing_komi_ratchet")) {
576 a
->losing_komi_ratchet
= !optval
|| atoi(optval
);
577 } else if (!strcasecmp(optname
, "komi_ratchet_age") && optval
) {
578 a
->komi_ratchet_maxage
= atoi(optval
);
580 /* score indicator settings */
581 } else if (!strcasecmp(optname
, "adapter") && optval
) {
582 /* Adaptatation method. */
583 if (!strcasecmp(optval
, "sigmoid")) {
584 a
->adapter
= adapter_sigmoid
;
585 } else if (!strcasecmp(optval
, "linear")) {
586 a
->adapter
= adapter_linear
;
588 fprintf(stderr
, "UCT: Invalid adapter %s\n", optval
);
591 } else if (!strcasecmp(optname
, "adapt_base") && optval
) {
592 /* Adaptation base rate; see above. */
593 a
->adapt_base
= atof(optval
);
594 } else if (!strcasecmp(optname
, "adapt_rate") && optval
) {
595 /* Adaptation slope; see above. */
596 a
->adapt_rate
= atof(optval
);
597 } else if (!strcasecmp(optname
, "adapt_phase") && optval
) {
598 /* Adaptation phase shift; see above. */
599 a
->adapt_phase
= atof(optval
);
600 } else if (!strcasecmp(optname
, "adapt_moves") && optval
) {
601 /* Adaptation move amount; see above. */
602 a
->adapt_moves
= atoi(optval
);
603 } else if (!strcasecmp(optname
, "adapt_aport")) {
604 a
->adapt_aport
= !optval
|| atoi(optval
);
605 } else if (!strcasecmp(optname
, "adapt_dir") && optval
) {
606 /* Adaptation direction vector; see above. */
607 a
->adapt_dir
= atof(optval
);
610 fprintf(stderr
, "uct: Invalid dynkomi argument %s or missing value\n", optname
);