Merge branch 'master' into jmhack
[pachi/nmclean.git] / uct / dynkomi.c
blob86ef673b67b2f41b9ac5ceccd3e336f5693bae02
1 #define DEBUG
2 #include <assert.h>
3 #include <math.h>
4 #include <stdio.h>
5 #include <stdlib.h>
6 #include <string.h>
8 #include "board.h"
9 #include "debug.h"
10 #include "tactics/util.h"
11 #include "uct/dynkomi.h"
12 #include "uct/internal.h"
13 #include "uct/tree.h"
16 static void
17 generic_done(struct uct_dynkomi *d)
19 if (d->data) free(d->data);
20 free(d);
24 /* NONE dynkomi strategy - never fiddle with komi values. */
26 struct uct_dynkomi *
27 uct_dynkomi_init_none(struct uct *u, char *arg, struct board *b)
29 struct uct_dynkomi *d = calloc2(1, sizeof(*d));
30 d->uct = u;
31 d->permove = NULL;
32 d->persim = NULL;
33 d->done = generic_done;
34 d->data = NULL;
36 if (arg) {
37 fprintf(stderr, "uct: Dynkomi method none accepts no arguments\n");
38 exit(1);
41 return d;
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];
54 int moves[S_MAX];
55 bool rootbased;
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;
66 floating_t drop_step;
69 static floating_t
70 linear_permove(struct uct_dynkomi *d, struct board *b, struct tree *tree)
72 struct dynkomi_linear *l = d->data;
73 enum stone color = d->uct->pondering ? tree->root_color : stone_other(tree->root_color);
74 int lmoves = l->moves[color];
75 floating_t extra_komi;
77 if (b->moves < lmoves) {
78 floating_t base_komi = board_effective_handicap(b, l->handicap_value[color]);
79 extra_komi = base_komi * (lmoves - b->moves) / lmoves;
80 return extra_komi;
81 } else {
82 extra_komi = floor(tree->extra_komi);
85 /* Do not take decisions on unstable value. */
86 if (tree->root->u.playouts < GJ_MINGAMES) return extra_komi;
88 floating_t my_value = tree_node_get_value(tree, 1, tree->root->u.value);
89 /* We normalize komi as in komi_by_value(), > 0 when winning. */
90 extra_komi = komi_by_color(extra_komi, color);
91 if (extra_komi < 0 && DEBUGL(3))
92 fprintf(stderr, "XXX: extra_komi %.3f < 0 (color %s tree ek %.3f)\n", extra_komi, stone2str(color), tree->extra_komi);
93 // assert(extra_komi >= 0);
94 floating_t orig_komi = extra_komi;
96 if (my_value < 0.5 && l->komi_ratchet > 0 && l->komi_ratchet != INFINITY) {
97 if (DEBUGL(0))
98 fprintf(stderr, "losing %f extra komi %.1f ratchet %.1f -> 0\n",
99 my_value, extra_komi, l->komi_ratchet);
100 /* Disable dynkomi completely, too dangerous in this game. */
101 extra_komi = l->komi_ratchet = 0;
103 } else if (my_value < l->orange_zone && extra_komi > 0) {
104 extra_komi = l->komi_ratchet = fmax(extra_komi - l->drop_step, 0.0);
105 if (extra_komi != orig_komi && DEBUGL(3))
106 fprintf(stderr, "dropping to %f, extra komi %.1f -> ratchet %.1f\n",
107 my_value, orig_komi, extra_komi);
109 } else if (my_value > l->green_zone && extra_komi + 1 <= l->komi_ratchet) {
110 extra_komi += 1;
111 if (extra_komi != orig_komi && DEBUGL(3))
112 fprintf(stderr, "winning %f extra_komi %.1f -> %.1f, ratchet %.1f\n",
113 my_value, orig_komi, extra_komi, l->komi_ratchet);
115 return komi_by_color(extra_komi, color);
118 static floating_t
119 linear_persim(struct uct_dynkomi *d, struct board *b, struct tree *tree, struct tree_node *node)
121 struct dynkomi_linear *l = d->data;
122 if (l->rootbased)
123 return tree->extra_komi;
124 /* We don't reuse computed value from tree->extra_komi,
125 * since we want to use value correct for this node depth.
126 * This also means the values will stay correct after
127 * node promotion. */
128 return linear_permove(d, b, tree);
131 struct uct_dynkomi *
132 uct_dynkomi_init_linear(struct uct *u, char *arg, struct board *b)
134 struct uct_dynkomi *d = calloc2(1, sizeof(*d));
135 d->uct = u;
136 d->permove = linear_permove;
137 d->persim = linear_persim;
138 d->done = generic_done;
140 struct dynkomi_linear *l = calloc2(1, sizeof(*l));
141 d->data = l;
143 /* Force white to feel behind and try harder, but not to the
144 * point of resigning immediately in high handicap games.
145 * By move 100 white should still be behind but should have
146 * caught up enough to avoid resigning. */
147 if (board_large(b)) {
148 l->moves[S_BLACK] = 100;
149 l->moves[S_WHITE] = 50;
151 /* The real value of one stone is twice the komi so about 15 points.
152 * But use a lower value to avoid being too pessimistic as black
153 * or too optimistic as white. */
154 l->handicap_value[S_BLACK] = 8;
155 l->handicap_value[S_WHITE] = 1;
157 l->komi_ratchet = INFINITY;
158 l->green_zone = 0.85;
159 l->orange_zone = 0.8;
160 l->drop_step = 4.0;
162 if (arg) {
163 char *optspec, *next = arg;
164 while (*next) {
165 optspec = next;
166 next += strcspn(next, ":");
167 if (*next) { *next++ = 0; } else { *next = 0; }
169 char *optname = optspec;
170 char *optval = strchr(optspec, '=');
171 if (optval) *optval++ = 0;
173 if (!strcasecmp(optname, "moves") && optval) {
174 /* Dynamic komi in handicap game; linearly
175 * decreases to basic settings until move
176 * #optval. moves=blackmoves%whitemoves */
177 for (int i = S_BLACK; *optval && i <= S_WHITE; i++) {
178 l->moves[i] = atoi(optval);
179 optval += strcspn(optval, "%");
180 if (*optval) optval++;
182 } else if (!strcasecmp(optname, "handicap_value") && optval) {
183 /* Point value of single handicap stone,
184 * for dynkomi computation. */
185 for (int i = S_BLACK; *optval && i <= S_WHITE; i++) {
186 l->handicap_value[i] = atoi(optval);
187 optval += strcspn(optval, "%");
188 if (*optval) optval++;
190 } else if (!strcasecmp(optname, "rootbased")) {
191 /* If set, the extra komi applied will be
192 * the same for all simulations within a move,
193 * instead of being same for all simulations
194 * within the tree node. */
195 l->rootbased = !optval || atoi(optval);
196 } else if (!strcasecmp(optname, "green_zone") && optval) {
197 /* Increase komi when win ratio is above green_zone */
198 l->green_zone = atof(optval);
199 } else if (!strcasecmp(optname, "orange_zone") && optval) {
200 /* Decrease komi when > 0 and win ratio is below orange_zone */
201 l->orange_zone = atof(optval);
202 } else if (!strcasecmp(optname, "drop_step") && optval) {
203 /* Decrease komi by drop_step points */
204 l->drop_step = atof(optval);
205 } else {
206 fprintf(stderr, "uct: Invalid dynkomi argument %s or missing value\n", optname);
207 exit(1);
212 return d;
216 /* ADAPTIVE dynkomi strategy - Adaptive Situational Compensation */
217 /* We adapt the komi based on current situation:
218 * (i) score-based: We maintain the average score outcome of our
219 * games and adjust the komi by a fractional step towards the expected
220 * score;
221 * (ii) value-based: While winrate is above given threshold, adjust
222 * the komi by a fixed step in the appropriate direction.
223 * These adjustments can be
224 * (a) Move-stepped, new extra komi value is always set only at the
225 * beginning of the tree search for next move;
226 * (b) Continuous, new extra komi value is periodically re-determined
227 * and adjusted throughout a single tree search. */
229 struct dynkomi_adaptive {
230 /* Do not take measured average score into regard for
231 * first @lead_moves - the variance is just too much.
232 * (Instead, we consider the handicap-based komi provided
233 * by linear dynkomi.) */
234 int lead_moves;
235 /* Maximum komi to pretend the opponent to give. */
236 floating_t max_losing_komi;
237 /* Game portion at which losing komi is not allowed anymore. */
238 floating_t losing_komi_stop;
239 /* Alternative game portion determination. */
240 bool adapt_aport;
241 floating_t (*indicator)(struct uct_dynkomi *d, struct board *b, struct tree *tree, enum stone color);
243 /* Value-based adaptation. */
244 floating_t zone_red, zone_green;
245 int score_step;
246 floating_t score_step_byavg; // use portion of average score as increment
247 bool use_komi_ratchet;
248 bool losing_komi_ratchet; // ratchet even losing komi
249 int komi_ratchet_maxage;
250 // runtime, not configuration:
251 int komi_ratchet_age;
252 floating_t komi_ratchet;
254 /* Score-based adaptation. */
255 floating_t (*adapter)(struct uct_dynkomi *d, struct board *b);
256 floating_t adapt_base; // [0,1)
257 /* Sigmoid adaptation rate parameter; see below for details. */
258 floating_t adapt_phase; // [0,1]
259 floating_t adapt_rate; // [1,infty)
260 /* Linear adaptation rate parameter. */
261 int adapt_moves;
262 floating_t adapt_dir; // [-1,1]
264 #define TRUSTWORTHY_KOMI_PLAYOUTS 200
266 static floating_t
267 board_game_portion(struct dynkomi_adaptive *a, struct board *b)
269 if (!a->adapt_aport) {
270 int total_moves = b->moves + 2 * board_estimated_moves_left(b);
271 return (floating_t) b->moves / total_moves;
272 } else {
273 int brsize = board_size(b) - 2;
274 return 1.0 - (floating_t) b->flen / (brsize * brsize);
278 static floating_t
279 adapter_sigmoid(struct uct_dynkomi *d, struct board *b)
281 struct dynkomi_adaptive *a = d->data;
282 /* Figure out how much to adjust the komi based on the game
283 * stage. The adaptation rate is 0 at the beginning,
284 * at game stage a->adapt_phase crosses though 0.5 and
285 * approaches 1 at the game end; the slope is controlled
286 * by a->adapt_rate. */
287 floating_t game_portion = board_game_portion(a, b);
288 floating_t l = game_portion - a->adapt_phase;
289 return 1.0 / (1.0 + exp(-a->adapt_rate * l));
292 static floating_t
293 adapter_linear(struct uct_dynkomi *d, struct board *b)
295 struct dynkomi_adaptive *a = d->data;
296 /* Figure out how much to adjust the komi based on the game
297 * stage. We just linearly increase/decrease the adaptation
298 * rate for first N moves. */
299 if (b->moves > a->adapt_moves)
300 return 0;
301 if (a->adapt_dir < 0)
302 return 1 - (- a->adapt_dir) * b->moves / a->adapt_moves;
303 else
304 return a->adapt_dir * b->moves / a->adapt_moves;
307 static floating_t
308 komi_by_score(struct uct_dynkomi *d, struct board *b, struct tree *tree, enum stone color)
310 struct dynkomi_adaptive *a = d->data;
311 if (d->score.playouts < TRUSTWORTHY_KOMI_PLAYOUTS)
312 return tree->extra_komi;
314 struct move_stats score = d->score;
315 /* Almost-reset tree->score to gather fresh stats. */
316 d->score.playouts = 1;
318 /* Look at average score and push extra_komi in that direction. */
319 floating_t p = a->adapter(d, b);
320 p = a->adapt_base + p * (1 - a->adapt_base);
321 if (p > 0.9) p = 0.9; // don't get too eager!
322 floating_t extra_komi = tree->extra_komi + p * score.value;
323 if (DEBUGL(3))
324 fprintf(stderr, "mC += %f * %f\n", p, score.value);
325 return extra_komi;
328 static floating_t
329 komi_by_value(struct uct_dynkomi *d, struct board *b, struct tree *tree, enum stone color)
331 struct dynkomi_adaptive *a = d->data;
332 if (d->value.playouts < TRUSTWORTHY_KOMI_PLAYOUTS)
333 return tree->extra_komi;
335 struct move_stats value = d->value;
336 /* Almost-reset tree->value to gather fresh stats. */
337 d->value.playouts = 1;
338 /* Correct color POV. */
339 if (color == S_WHITE)
340 value.value = 1 - value.value;
342 /* We have three "value zones":
343 * red zone | yellow zone | green zone
344 * ~45% ~60%
345 * red zone: reduce komi
346 * yellow zone: do not touch komi
347 * green zone: enlage komi.
349 * Also, at some point komi will be tuned in such way
350 * that it will be in green zone but increasing it will
351 * be unfeasible. Thus, we have a _ratchet_ - we will
352 * remember the last komi that has put us into the
353 * red zone, and not use it or go over it. We use the
354 * ratchet only when giving extra komi, we always want
355 * to try to reduce extra komi we take.
357 * TODO: Make the ratchet expire after a while. */
359 /* We use komi_by_color() first to normalize komi
360 * additions/subtractions, then apply it again on
361 * return value to restore original komi parity. */
362 /* Positive extra_komi means that we are _giving_
363 * komi (winning), negative extra_komi is _taking_
364 * komi (losing). */
365 floating_t extra_komi = komi_by_color(tree->extra_komi, color);
366 int score_step_red = -a->score_step;
367 int score_step_green = a->score_step;
369 if (a->score_step_byavg != 0) {
370 struct move_stats score = d->score;
371 /* Almost-reset tree->score to gather fresh stats. */
372 d->score.playouts = 1;
373 /* Correct color POV. */
374 if (color == S_WHITE)
375 score.value = - score.value;
376 if (score.value > 0)
377 score_step_green = round(score.value * a->score_step_byavg);
378 else
379 score_step_red = round(-score.value * a->score_step_byavg);
380 if (score_step_green < 0 || score_step_red > 0) {
381 /* The steps are in bad direction - keep still. */
382 return komi_by_color(extra_komi, color);
386 /* Wear out the ratchet. */
387 if (a->use_komi_ratchet && a->komi_ratchet_maxage > 0) {
388 a->komi_ratchet_age += value.playouts;
389 if (a->komi_ratchet_age > a->komi_ratchet_maxage) {
390 a->komi_ratchet = 1000;
391 a->komi_ratchet_age = 0;
395 if (value.value < a->zone_red) {
396 /* Red zone. Take extra komi. */
397 if (DEBUGL(3))
398 fprintf(stderr, "[red] %f, step %d | komi ratchet %f age %d/%d -> %f\n",
399 value.value, score_step_red, a->komi_ratchet, a->komi_ratchet_age, a->komi_ratchet_maxage, extra_komi);
400 if (a->losing_komi_ratchet || extra_komi > 0) {
401 a->komi_ratchet = extra_komi;
402 a->komi_ratchet_age = 0;
404 extra_komi += score_step_red;
405 return komi_by_color(extra_komi, color);
407 } else if (value.value < a->zone_green) {
408 /* Yellow zone, do nothing. */
409 return komi_by_color(extra_komi, color);
411 } else {
412 /* Green zone. Give extra komi. */
413 if (DEBUGL(3))
414 fprintf(stderr, "[green] %f, step %d | komi ratchet %f age %d/%d\n",
415 value.value, score_step_green, a->komi_ratchet, a->komi_ratchet_age, a->komi_ratchet_maxage);
416 extra_komi += score_step_green;
417 if (a->use_komi_ratchet && extra_komi >= a->komi_ratchet)
418 extra_komi = a->komi_ratchet - 1;
419 return komi_by_color(extra_komi, color);
423 static floating_t
424 bounded_komi(struct dynkomi_adaptive *a, struct board *b,
425 enum stone color, floating_t komi, floating_t max_losing_komi)
427 /* At the end of game, disallow losing komi. */
428 if (komi_by_color(komi, color) < 0
429 && board_game_portion(a, b) > a->losing_komi_stop)
430 return 0;
432 /* Get lower bound on komi we take so that we don't underperform
433 * too much. */
434 floating_t min_komi = komi_by_color(- max_losing_komi, color);
436 if (komi_by_color(komi - min_komi, color) > 0)
437 return komi;
438 else
439 return min_komi;
442 static floating_t
443 adaptive_permove(struct uct_dynkomi *d, struct board *b, struct tree *tree)
445 /* We do not use extra komi at the game end - we are not
446 * to fool ourselves at this point. */
447 if (board_estimated_moves_left(b) <= MIN_MOVES_LEFT) {
448 tree->use_extra_komi = false;
449 return 0;
451 struct dynkomi_adaptive *a = d->data;
452 enum stone color = stone_other(tree->root_color);
453 if (DEBUGL(3))
454 fprintf(stderr, "m %d/%d ekomi %f permove %f/%d\n",
455 b->moves, a->lead_moves, tree->extra_komi,
456 d->score.value, d->score.playouts);
458 if (b->moves <= a->lead_moves)
459 return bounded_komi(a, b, color,
460 board_effective_handicap(b, 7 /* XXX */),
461 a->max_losing_komi);
463 floating_t komi = a->indicator(d, b, tree, color);
464 if (DEBUGL(3))
465 fprintf(stderr, "dynkomi: %f -> %f\n", tree->extra_komi, komi);
466 return bounded_komi(a, b, color, komi, a->max_losing_komi);
469 static floating_t
470 adaptive_persim(struct uct_dynkomi *d, struct board *b, struct tree *tree, struct tree_node *node)
472 return tree->extra_komi;
475 struct uct_dynkomi *
476 uct_dynkomi_init_adaptive(struct uct *u, char *arg, struct board *b)
478 struct uct_dynkomi *d = calloc2(1, sizeof(*d));
479 d->uct = u;
480 d->permove = adaptive_permove;
481 d->persim = adaptive_persim;
482 d->done = generic_done;
484 struct dynkomi_adaptive *a = calloc2(1, sizeof(*a));
485 d->data = a;
487 a->lead_moves = board_large(b) ? 20 : 4; // XXX
488 a->max_losing_komi = 30;
489 a->losing_komi_stop = 1.0f;
490 a->indicator = komi_by_value;
492 a->adapter = adapter_sigmoid;
493 a->adapt_rate = -18;
494 a->adapt_phase = 0.65;
495 a->adapt_moves = 200;
496 a->adapt_dir = -0.5;
498 a->zone_red = 0.45;
499 a->zone_green = 0.50;
500 a->score_step = 1;
501 a->use_komi_ratchet = true;
502 a->komi_ratchet_maxage = 0;
503 a->komi_ratchet = 1000;
505 if (arg) {
506 char *optspec, *next = arg;
507 while (*next) {
508 optspec = next;
509 next += strcspn(next, ":");
510 if (*next) { *next++ = 0; } else { *next = 0; }
512 char *optname = optspec;
513 char *optval = strchr(optspec, '=');
514 if (optval) *optval++ = 0;
516 if (!strcasecmp(optname, "lead_moves") && optval) {
517 /* Do not adjust komi adaptively for first
518 * N moves. */
519 a->lead_moves = atoi(optval);
520 } else if (!strcasecmp(optname, "max_losing_komi") && optval) {
521 a->max_losing_komi = atof(optval);
522 } else if (!strcasecmp(optname, "losing_komi_stop") && optval) {
523 a->losing_komi_stop = atof(optval);
524 } else if (!strcasecmp(optname, "indicator")) {
525 /* Adaptatation indicator - how to decide
526 * the adaptation rate and direction. */
527 if (!strcasecmp(optval, "value")) {
528 /* Winrate w/ komi so far. */
529 a->indicator = komi_by_value;
530 } else if (!strcasecmp(optval, "score")) {
531 /* Expected score w/ current komi. */
532 a->indicator = komi_by_score;
533 } else {
534 fprintf(stderr, "UCT: Invalid indicator %s\n", optval);
535 exit(1);
538 /* value indicator settings */
539 } else if (!strcasecmp(optname, "zone_red") && optval) {
540 a->zone_red = atof(optval);
541 } else if (!strcasecmp(optname, "zone_green") && optval) {
542 a->zone_green = atof(optval);
543 } else if (!strcasecmp(optname, "score_step") && optval) {
544 a->score_step = atoi(optval);
545 } else if (!strcasecmp(optname, "score_step_byavg") && optval) {
546 a->score_step_byavg = atof(optval);
547 } else if (!strcasecmp(optname, "use_komi_ratchet")) {
548 a->use_komi_ratchet = !optval || atoi(optval);
549 } else if (!strcasecmp(optname, "losing_komi_ratchet")) {
550 a->losing_komi_ratchet = !optval || atoi(optval);
551 } else if (!strcasecmp(optname, "komi_ratchet_age") && optval) {
552 a->komi_ratchet_maxage = atoi(optval);
554 /* score indicator settings */
555 } else if (!strcasecmp(optname, "adapter") && optval) {
556 /* Adaptatation method. */
557 if (!strcasecmp(optval, "sigmoid")) {
558 a->adapter = adapter_sigmoid;
559 } else if (!strcasecmp(optval, "linear")) {
560 a->adapter = adapter_linear;
561 } else {
562 fprintf(stderr, "UCT: Invalid adapter %s\n", optval);
563 exit(1);
565 } else if (!strcasecmp(optname, "adapt_base") && optval) {
566 /* Adaptation base rate; see above. */
567 a->adapt_base = atof(optval);
568 } else if (!strcasecmp(optname, "adapt_rate") && optval) {
569 /* Adaptation slope; see above. */
570 a->adapt_rate = atof(optval);
571 } else if (!strcasecmp(optname, "adapt_phase") && optval) {
572 /* Adaptation phase shift; see above. */
573 a->adapt_phase = atof(optval);
574 } else if (!strcasecmp(optname, "adapt_moves") && optval) {
575 /* Adaptation move amount; see above. */
576 a->adapt_moves = atoi(optval);
577 } else if (!strcasecmp(optname, "adapt_aport")) {
578 a->adapt_aport = !optval || atoi(optval);
579 } else if (!strcasecmp(optname, "adapt_dir") && optval) {
580 /* Adaptation direction vector; see above. */
581 a->adapt_dir = atof(optval);
583 } else {
584 fprintf(stderr, "uct: Invalid dynkomi argument %s or missing value\n", optname);
585 exit(1);
590 return d;