uct/dynkomi.c

   1 #define DEBUG
   2 #include <assert.h>
   3 #include <math.h>
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include <string.h>
   7
   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"
  14
  15
  16 static void
  17 generic_done(struct uct_dynkomi *d)
  18 {
  19         if (d->data) free(d->data);
  20         free(d);
  21 }
  22
  23
  24 /* NONE dynkomi strategy - never fiddle with komi values. */
  25
  26 struct uct_dynkomi *
  27 uct_dynkomi_init_none(struct uct *u, char *arg, struct board *b)
  28 {
  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;
  35
  36         if (arg) {
  37                 fprintf(stderr, "uct: Dynkomi method none accepts no arguments\n");
  38                 exit(1);
  39         }
  40
  41         return d;
  42 }
  43
  44
  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. */
  49
  50 struct dynkomi_linear {
  51         int handicap_value[S_MAX];
  52         int moves[S_MAX];
  53         bool rootbased;
  54 };
  55
  56 static floating_t
  57 linear_permove(struct uct_dynkomi *d, struct board *b, struct tree *tree)
  58 {
  59         struct dynkomi_linear *l = d->data;
  60         enum stone color = d->uct->pondering ? tree->root_color : stone_other(tree->root_color);
  61         int lmoves = l->moves[color];
  62         if (b->moves >= lmoves)
  63                 return 0;
  64
  65         floating_t base_komi = board_effective_handicap(b, l->handicap_value[color]);
  66         floating_t extra_komi = base_komi * (lmoves - b->moves) / lmoves;
  67         return extra_komi;
  68 }
  69
  70 static floating_t
  71 linear_persim(struct uct_dynkomi *d, struct board *b, struct tree *tree, struct tree_node *node)
  72 {
  73         struct dynkomi_linear *l = d->data;
  74         if (l->rootbased)
  75                 return tree->extra_komi;
  76         /* We don't reuse computed value from tree->extra_komi,
  77          * since we want to use value correct for this node depth.
  78          * This also means the values will stay correct after
  79          * node promotion. */
  80         return linear_permove(d, b, tree);
  81 }
  82
  83 struct uct_dynkomi *
  84 uct_dynkomi_init_linear(struct uct *u, char *arg, struct board *b)
  85 {
  86         struct uct_dynkomi *d = calloc2(1, sizeof(*d));
  87         d->uct = u;
  88         d->permove = linear_permove;
  89         d->persim = linear_persim;
  90         d->done = generic_done;
  91
  92         struct dynkomi_linear *l = calloc2(1, sizeof(*l));
  93         d->data = l;
  94
  95         /* Force white to feel behind and try harder, but not to the
  96          * point of resigning immediately in high handicap games.
  97          * By move 100 white should still be behind but should have
  98          * caught up enough to avoid resigning. */
  99         if (board_large(b)) {
 100                 l->moves[S_BLACK] = 200;
 101                 l->moves[S_WHITE] = 100;
 102         }
 103         /* The real value of one stone is twice the komi so about 15 points.
 104          * But use a lower value to avoid being too pessimistic as black
 105          * or too optimistic as white. */
 106         l->handicap_value[S_BLACK] = 7;
 107         l->handicap_value[S_WHITE] = 5;
 108
 109         if (arg) {
 110                 char *optspec, *next = arg;
 111                 while (*next) {
 112                         optspec = next;
 113                         next += strcspn(next, ":");
 114                         if (*next) { *next++ = 0; } else { *next = 0; }
 115
 116                         char *optname = optspec;
 117                         char *optval = strchr(optspec, '=');
 118                         if (optval) *optval++ = 0;
 119
 120                         if (!strcasecmp(optname, "moves") && optval) {
 121                                 /* Dynamic komi in handicap game; linearly
 122                                  * decreases to basic settings until move
 123                                  * #optval. moves=blackmoves%whitemoves */
 124                                 for (int i = S_BLACK; *optval && i <= S_WHITE; i++) {
 125                                         l->moves[i] = atoi(optval);
 126                                         optval += strcspn(optval, "%");
 127                                         if (*optval) optval++;
 128                                 }
 129                         } else if (!strcasecmp(optname, "handicap_value") && optval) {
 130                                 /* Point value of single handicap stone,
 131                                  * for dynkomi computation. */
 132                                 for (int i = S_BLACK; *optval && i <= S_WHITE; i++) {
 133                                         l->handicap_value[i] = atoi(optval);
 134                                         optval += strcspn(optval, "%");
 135                                         if (*optval) optval++;
 136                                 }
 137                         } else if (!strcasecmp(optname, "rootbased")) {
 138                                 /* If set, the extra komi applied will be
 139                                  * the same for all simulations within a move,
 140                                  * instead of being same for all simulations
 141                                  * within the tree node. */
 142                                 l->rootbased = !optval || atoi(optval);
 143                         } else {
 144                                 fprintf(stderr, "uct: Invalid dynkomi argument %s or missing value\n", optname);
 145                                 exit(1);
 146                         }
 147                 }
 148         }
 149
 150         return d;
 151 }
 152
 153
 154 /* ADAPTIVE dynkomi strategy - Adaptive Situational Compensation */
 155 /* We adapt the komi based on current situation:
 156  * (i) score-based: We maintain the average score outcome of our
 157  * games and adjust the komi by a fractional step towards the expected
 158  * score;
 159  * (ii) value-based: While winrate is above given threshold, adjust
 160  * the komi by a fixed step in the appropriate direction.
 161  * These adjustments can be
 162  * (a) Move-stepped, new extra komi value is always set only at the
 163  * beginning of the tree search for next move;
 164  * (b) Continuous, new extra komi value is periodically re-determined
 165  * and adjusted throughout a single tree search. */
 166
 167 struct dynkomi_adaptive {
 168         /* Do not take measured average score into regard for
 169          * first @lead_moves - the variance is just too much.
 170          * (Instead, we consider the handicap-based komi provided
 171          * by linear dynkomi.) */
 172         int lead_moves;
 173         /* Maximum komi to pretend the opponent to give. */
 174         floating_t max_losing_komi;
 175         /* Game portion at which losing komi is not allowed anymore. */
 176         floating_t losing_komi_stop;
 177         /* Alternative game portion determination. */
 178         bool adapt_aport;
 179         floating_t (*indicator)(struct uct_dynkomi *d, struct board *b, struct tree *tree, enum stone color);
 180
 181         /* Value-based adaptation. */
 182         floating_t zone_red, zone_green;
 183         int score_step;
 184         floating_t score_step_byavg; // use portion of average score as increment
 185         bool use_komi_ratchet;
 186         bool losing_komi_ratchet; // ratchet even losing komi
 187         int komi_ratchet_maxage;
 188         // runtime, not configuration:
 189         int komi_ratchet_age;
 190         floating_t komi_ratchet;
 191
 192         /* Score-based adaptation. */
 193         floating_t (*adapter)(struct uct_dynkomi *d, struct board *b);
 194         floating_t adapt_base; // [0,1)
 195         /* Sigmoid adaptation rate parameter; see below for details. */
 196         floating_t adapt_phase; // [0,1]
 197         floating_t adapt_rate; // [1,infty)
 198         /* Linear adaptation rate parameter. */
 199         int adapt_moves;
 200         floating_t adapt_dir; // [-1,1]
 201 };
 202 #define TRUSTWORTHY_KOMI_PLAYOUTS 200
 203
 204 static floating_t
 205 board_game_portion(struct dynkomi_adaptive *a, struct board *b)
 206 {
 207         if (!a->adapt_aport) {
 208                 int total_moves = b->moves + 2 * board_estimated_moves_left(b);
 209                 return (floating_t) b->moves / total_moves;
 210         } else {
 211                 int brsize = board_size(b) - 2;
 212                 return 1.0 - (floating_t) b->flen / (brsize * brsize);
 213         }
 214 }
 215
 216 static floating_t
 217 adapter_sigmoid(struct uct_dynkomi *d, struct board *b)
 218 {
 219         struct dynkomi_adaptive *a = d->data;
 220         /* Figure out how much to adjust the komi based on the game
 221          * stage. The adaptation rate is 0 at the beginning,
 222          * at game stage a->adapt_phase crosses though 0.5 and
 223          * approaches 1 at the game end; the slope is controlled
 224          * by a->adapt_rate. */
 225         floating_t game_portion = board_game_portion(a, b);
 226         floating_t l = game_portion - a->adapt_phase;
 227         return 1.0 / (1.0 + exp(-a->adapt_rate * l));
 228 }
 229
 230 static floating_t
 231 adapter_linear(struct uct_dynkomi *d, struct board *b)
 232 {
 233         struct dynkomi_adaptive *a = d->data;
 234         /* Figure out how much to adjust the komi based on the game
 235          * stage. We just linearly increase/decrease the adaptation
 236          * rate for first N moves. */
 237         if (b->moves > a->adapt_moves)
 238                 return 0;
 239         if (a->adapt_dir < 0)
 240                 return 1 - (- a->adapt_dir) * b->moves / a->adapt_moves;
 241         else
 242                 return a->adapt_dir * b->moves / a->adapt_moves;
 243 }
 244
 245 static floating_t
 246 komi_by_score(struct uct_dynkomi *d, struct board *b, struct tree *tree, enum stone color)
 247 {
 248         struct dynkomi_adaptive *a = d->data;
 249         if (d->score.playouts < TRUSTWORTHY_KOMI_PLAYOUTS)
 250                 return tree->extra_komi;
 251
 252         struct move_stats score = d->score;
 253         /* Almost-reset tree->score to gather fresh stats. */
 254         d->score.playouts = 1;
 255
 256         /* Look at average score and push extra_komi in that direction. */
 257         floating_t p = a->adapter(d, b);
 258         p = a->adapt_base + p * (1 - a->adapt_base);
 259         if (p > 0.9) p = 0.9; // don't get too eager!
 260         floating_t extra_komi = tree->extra_komi + p * score.value;
 261         if (DEBUGL(3))
 262                 fprintf(stderr, "mC += %f * %f\n", p, score.value);
 263         return extra_komi;
 264 }
 265
 266 static floating_t
 267 komi_by_value(struct uct_dynkomi *d, struct board *b, struct tree *tree, enum stone color)
 268 {
 269         struct dynkomi_adaptive *a = d->data;
 270         if (d->value.playouts < TRUSTWORTHY_KOMI_PLAYOUTS)
 271                 return tree->extra_komi;
 272
 273         struct move_stats value = d->value;
 274         /* Almost-reset tree->value to gather fresh stats. */
 275         d->value.playouts = 1;
 276         /* Correct color POV. */
 277         if (color == S_WHITE)
 278                 value.value = 1 - value.value;
 279
 280         /* We have three "value zones":
 281          * red zone | yellow zone | green zone
 282          *        ~45%           ~60%
 283          * red zone: reduce komi
 284          * yellow zone: do not touch komi
 285          * green zone: enlage komi.
 286          *
 287          * Also, at some point komi will be tuned in such way
 288          * that it will be in green zone but increasing it will
 289          * be unfeasible. Thus, we have a _ratchet_ - we will
 290          * remember the last komi that has put us into the
 291          * red zone, and not use it or go over it. We use the
 292          * ratchet only when giving extra komi, we always want
 293          * to try to reduce extra komi we take.
 294          *
 295          * TODO: Make the ratchet expire after a while. */
 296
 297         /* We use komi_by_color() first to normalize komi
 298          * additions/subtractions, then apply it again on
 299          * return value to restore original komi parity. */
 300         /* Positive extra_komi means that we are _giving_
 301          * komi (winning), negative extra_komi is _taking_
 302          * komi (losing). */
 303         floating_t extra_komi = komi_by_color(tree->extra_komi, color);
 304         int score_step_red = -a->score_step;
 305         int score_step_green = a->score_step;
 306
 307         if (a->score_step_byavg != 0) {
 308                 struct move_stats score = d->score;
 309                 /* Almost-reset tree->score to gather fresh stats. */
 310                 d->score.playouts = 1;
 311                 /* Correct color POV. */
 312                 if (color == S_WHITE)
 313                         score.value = - score.value;
 314                 if (score.value > 0)
 315                         score_step_green = round(score.value * a->score_step_byavg);
 316                 else
 317                         score_step_red = round(-score.value * a->score_step_byavg);
 318                 if (score_step_green < 0 || score_step_red > 0) {
 319                         /* The steps are in bad direction - keep still. */
 320                         return komi_by_color(extra_komi, color);
 321                 }
 322         }
 323
 324         /* Wear out the ratchet. */
 325         if (a->use_komi_ratchet && a->komi_ratchet_maxage > 0) {
 326                 a->komi_ratchet_age += value.playouts;
 327                 if (a->komi_ratchet_age > a->komi_ratchet_maxage) {
 328                         a->komi_ratchet = 1000;
 329                         a->komi_ratchet_age = 0;
 330                 }
 331         }
 332
 333         if (value.value < a->zone_red) {
 334                 /* Red zone. Take extra komi. */
 335                 if (DEBUGL(3))
 336                         fprintf(stderr, "[red] %f, step %d | komi ratchet %f age %d/%d -> %f\n",
 337                                 value.value, score_step_red, a->komi_ratchet, a->komi_ratchet_age, a->komi_ratchet_maxage, extra_komi);
 338                 if (a->losing_komi_ratchet || extra_komi > 0) {
 339                         a->komi_ratchet = extra_komi;
 340                         a->komi_ratchet_age = 0;
 341                 }
 342                 extra_komi += score_step_red;
 343                 return komi_by_color(extra_komi, color);
 344
 345         } else if (value.value < a->zone_green) {
 346                 /* Yellow zone, do nothing. */
 347                 return komi_by_color(extra_komi, color);
 348
 349         } else {
 350                 /* Green zone. Give extra komi. */
 351                 if (DEBUGL(3))
 352                         fprintf(stderr, "[green] %f, step %d | komi ratchet %f age %d/%d\n",
 353                                 value.value, score_step_green, a->komi_ratchet, a->komi_ratchet_age, a->komi_ratchet_maxage);
 354                 extra_komi += score_step_green;
 355                 if (a->use_komi_ratchet && extra_komi >= a->komi_ratchet)
 356                         extra_komi = a->komi_ratchet - 1;
 357                 return komi_by_color(extra_komi, color);
 358         }
 359 }
 360
 361 static floating_t
 362 bounded_komi(struct dynkomi_adaptive *a, struct board *b,
 363              enum stone color, floating_t komi, floating_t max_losing_komi)
 364 {
 365         /* At the end of game, disallow losing komi. */
 366         if (komi_by_color(komi, color) < 0
 367             && board_game_portion(a, b) > a->losing_komi_stop)
 368                 return 0;
 369
 370         /* Get lower bound on komi we take so that we don't underperform
 371          * too much. */
 372         floating_t min_komi = komi_by_color(- max_losing_komi, color);
 373
 374         if (komi_by_color(komi - min_komi, color) > 0)
 375                 return komi;
 376         else
 377                 return min_komi;
 378 }
 379
 380 static floating_t
 381 adaptive_permove(struct uct_dynkomi *d, struct board *b, struct tree *tree)
 382 {
 383         struct dynkomi_adaptive *a = d->data;
 384         enum stone color = stone_other(tree->root_color);
 385         if (DEBUGL(3))
 386                 fprintf(stderr, "m %d/%d ekomi %f permove %f/%d\n",
 387                         b->moves, a->lead_moves, tree->extra_komi,
 388                         d->score.value, d->score.playouts);
 389
 390         if (b->moves <= a->lead_moves)
 391                 return bounded_komi(a, b, color,
 392                                     board_effective_handicap(b, 7 /* XXX */),
 393                                     a->max_losing_komi);
 394
 395         floating_t komi = a->indicator(d, b, tree, color);
 396         if (DEBUGL(3))
 397                 fprintf(stderr, "dynkomi: %f -> %f\n", tree->extra_komi, komi);
 398         return bounded_komi(a, b, color, komi, a->max_losing_komi);
 399 }
 400
 401 static floating_t
 402 adaptive_persim(struct uct_dynkomi *d, struct board *b, struct tree *tree, struct tree_node *node)
 403 {
 404         return tree->extra_komi;
 405 }
 406
 407 struct uct_dynkomi *
 408 uct_dynkomi_init_adaptive(struct uct *u, char *arg, struct board *b)
 409 {
 410         struct uct_dynkomi *d = calloc2(1, sizeof(*d));
 411         d->uct = u;
 412         d->permove = adaptive_permove;
 413         d->persim = adaptive_persim;
 414         d->done = generic_done;
 415
 416         struct dynkomi_adaptive *a = calloc2(1, sizeof(*a));
 417         d->data = a;
 418
 419         a->lead_moves = board_large(b) ? 20 : 4; // XXX
 420         a->max_losing_komi = 30;
 421         a->losing_komi_stop = 1.0f;
 422         a->indicator = komi_by_value;
 423
 424         a->adapter = adapter_sigmoid;
 425         a->adapt_rate = -18;
 426         a->adapt_phase = 0.65;
 427         a->adapt_moves = 200;
 428         a->adapt_dir = -0.5;
 429
 430         a->zone_red = 0.45;
 431         a->zone_green = 0.50;
 432         a->score_step = 1;
 433         a->use_komi_ratchet = true;
 434         a->komi_ratchet_maxage = 0;
 435         a->komi_ratchet = 1000;
 436
 437         if (arg) {
 438                 char *optspec, *next = arg;
 439                 while (*next) {
 440                         optspec = next;
 441                         next += strcspn(next, ":");
 442                         if (*next) { *next++ = 0; } else { *next = 0; }
 443
 444                         char *optname = optspec;
 445                         char *optval = strchr(optspec, '=');
 446                         if (optval) *optval++ = 0;
 447
 448                         if (!strcasecmp(optname, "lead_moves") && optval) {
 449                                 /* Do not adjust komi adaptively for first
 450                                  * N moves. */
 451                                 a->lead_moves = atoi(optval);
 452                         } else if (!strcasecmp(optname, "max_losing_komi") && optval) {
 453                                 a->max_losing_komi = atof(optval);
 454                         } else if (!strcasecmp(optname, "losing_komi_stop") && optval) {
 455                                 a->losing_komi_stop = atof(optval);
 456                         } else if (!strcasecmp(optname, "indicator")) {
 457                                 /* Adaptatation indicator - how to decide
 458                                  * the adaptation rate and direction. */
 459                                 if (!strcasecmp(optval, "value")) {
 460                                         /* Winrate w/ komi so far. */
 461                                         a->indicator = komi_by_value;
 462                                 } else if (!strcasecmp(optval, "score")) {
 463                                         /* Expected score w/ current komi. */
 464                                         a->indicator = komi_by_score;
 465                                 } else {
 466                                         fprintf(stderr, "UCT: Invalid indicator %s\n", optval);
 467                                         exit(1);
 468                                 }
 469
 470                                 /* value indicator settings */
 471                         } else if (!strcasecmp(optname, "zone_red") && optval) {
 472                                 a->zone_red = atof(optval);
 473                         } else if (!strcasecmp(optname, "zone_green") && optval) {
 474                                 a->zone_green = atof(optval);
 475                         } else if (!strcasecmp(optname, "score_step") && optval) {
 476                                 a->score_step = atoi(optval);
 477                         } else if (!strcasecmp(optname, "score_step_byavg") && optval) {
 478                                 a->score_step_byavg = atof(optval);
 479                         } else if (!strcasecmp(optname, "use_komi_ratchet")) {
 480                                 a->use_komi_ratchet = !optval || atoi(optval);
 481                         } else if (!strcasecmp(optname, "losing_komi_ratchet")) {
 482                                 a->losing_komi_ratchet = !optval || atoi(optval);
 483                         } else if (!strcasecmp(optname, "komi_ratchet_age") && optval) {
 484                                 a->komi_ratchet_maxage = atoi(optval);
 485
 486                                 /* score indicator settings */
 487                         } else if (!strcasecmp(optname, "adapter") && optval) {
 488                                 /* Adaptatation method. */
 489                                 if (!strcasecmp(optval, "sigmoid")) {
 490                                         a->adapter = adapter_sigmoid;
 491                                 } else if (!strcasecmp(optval, "linear")) {
 492                                         a->adapter = adapter_linear;
 493                                 } else {
 494                                         fprintf(stderr, "UCT: Invalid adapter %s\n", optval);
 495                                         exit(1);
 496                                 }
 497                         } else if (!strcasecmp(optname, "adapt_base") && optval) {
 498                                 /* Adaptation base rate; see above. */
 499                                 a->adapt_base = atof(optval);
 500                         } else if (!strcasecmp(optname, "adapt_rate") && optval) {
 501                                 /* Adaptation slope; see above. */
 502                                 a->adapt_rate = atof(optval);
 503                         } else if (!strcasecmp(optname, "adapt_phase") && optval) {
 504                                 /* Adaptation phase shift; see above. */
 505                                 a->adapt_phase = atof(optval);
 506                         } else if (!strcasecmp(optname, "adapt_moves") && optval) {
 507                                 /* Adaptation move amount; see above. */
 508                                 a->adapt_moves = atoi(optval);
 509                         } else if (!strcasecmp(optname, "adapt_aport")) {
 510                                 a->adapt_aport = !optval || atoi(optval);
 511                         } else if (!strcasecmp(optname, "adapt_dir") && optval) {
 512                                 /* Adaptation direction vector; see above. */
 513                                 a->adapt_dir = atof(optval);
 514
 515                         } else {
 516                                 fprintf(stderr, "uct: Invalid dynkomi argument %s or missing value\n", optname);
 517                                 exit(1);
 518                         }
 519                 }
 520         }
 521
 522         return d;
 523 }