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.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;
  52         int moves;
  53         bool rootbased;
  54 };
  55
  56 static float
  57 linear_permove(struct uct_dynkomi *d, struct board *b, struct tree *tree)
  58 {
  59         struct dynkomi_linear *l = d->data;
  60         if (b->moves >= l->moves)
  61                 return 0;
  62
  63         float base_komi = board_effective_handicap(b, l->handicap_value);
  64         float extra_komi = base_komi * (l->moves - b->moves) / l->moves;
  65         return extra_komi;
  66 }
  67
  68 static float
  69 linear_persim(struct uct_dynkomi *d, struct board *b, struct tree *tree, struct tree_node *node)
  70 {
  71         struct dynkomi_linear *l = d->data;
  72         if (l->rootbased)
  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
  77          * node promotion. */
  78         return linear_permove(d, b, tree);
  79 }
  80
  81 struct uct_dynkomi *
  82 uct_dynkomi_init_linear(struct uct *u, char *arg, struct board *b)
  83 {
  84         struct uct_dynkomi *d = calloc2(1, sizeof(*d));
  85         d->uct = u;
  86         d->permove = linear_permove;
  87         d->persim = linear_persim;
  88         d->done = generic_done;
  89
  90         struct dynkomi_linear *l = calloc2(1, sizeof(*l));
  91         d->data = l;
  92
  93         if (board_size(b) - 2 >= 19)
  94                 l->moves = 200;
  95         l->handicap_value = 7;
  96
  97         if (arg) {
  98                 char *optspec, *next = arg;
  99                 while (*next) {
 100                         optspec = next;
 101                         next += strcspn(next, ":");
 102                         if (*next) { *next++ = 0; } else { *next = 0; }
 103
 104                         char *optname = optspec;
 105                         char *optval = strchr(optspec, '=');
 106                         if (optval) *optval++ = 0;
 107
 108                         if (!strcasecmp(optname, "moves") && optval) {
 109                                 /* Dynamic komi in handicap game; linearly
 110                                  * decreases to basic settings until move
 111                                  * #optval. */
 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);
 123                         } else {
 124                                 fprintf(stderr, "uct: Invalid dynkomi argument %s or missing value\n", optname);
 125                                 exit(1);
 126                         }
 127                 }
 128         }
 129
 130         return d;
 131 }
 132
 133
 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
 138  * score;
 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. */
 146
 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.) */
 152         int lead_moves;
 153         /* Maximum komi to pretend the opponent to give. */
 154         float max_losing_komi;
 155         float (*indicator)(struct uct_dynkomi *d, struct board *b, struct tree *tree, enum stone color);
 156
 157         /* Value-based adaptation. */
 158         float zone_red, zone_green;
 159         int score_step;
 160         float score_step_byavg; // use portion of average score as increment
 161         bool use_komi_ratchet;
 162         bool losing_komi_ratchet; // ratchet even losing komi
 163         int komi_ratchet_maxage;
 164         // runtime, not configuration:
 165         int komi_ratchet_age;
 166         float komi_ratchet;
 167
 168         /* Score-based adaptation. */
 169         float (*adapter)(struct uct_dynkomi *d, struct board *b);
 170         float adapt_base; // [0,1)
 171         /* Sigmoid adaptation rate parameter; see below for details. */
 172         float adapt_phase; // [0,1]
 173         float adapt_rate; // [1,infty)
 174         bool adapt_aport; // alternative game portion determination
 175         /* Linear adaptation rate parameter. */
 176         int adapt_moves;
 177         float adapt_dir; // [-1,1]
 178 };
 179 #define TRUSTWORTHY_KOMI_PLAYOUTS 200
 180
 181 static float
 182 adapter_sigmoid(struct uct_dynkomi *d, struct board *b)
 183 {
 184         struct dynkomi_adaptive *a = d->data;
 185         /* Figure out how much to adjust the komi based on the game
 186          * stage. The adaptation rate is 0 at the beginning,
 187          * at game stage a->adapt_phase crosses though 0.5 and
 188          * approaches 1 at the game end; the slope is controlled
 189          * by a->adapt_rate. */
 190         float game_portion;
 191         if (!a->adapt_aport) {
 192                 int total_moves = b->moves + 2 * board_estimated_moves_left(b);
 193                 game_portion = (float) b->moves / total_moves;
 194         } else {
 195                 int brsize = board_size(b) - 2;
 196                 game_portion = 1.0 - (float) b->flen / (brsize * brsize);
 197         }
 198         float l = game_portion - a->adapt_phase;
 199         return 1.0 / (1.0 + exp(-a->adapt_rate * l));
 200 }
 201
 202 static float
 203 adapter_linear(struct uct_dynkomi *d, struct board *b)
 204 {
 205         struct dynkomi_adaptive *a = d->data;
 206         /* Figure out how much to adjust the komi based on the game
 207          * stage. We just linearly increase/decrease the adaptation
 208          * rate for first N moves. */
 209         if (b->moves > a->adapt_moves)
 210                 return 0;
 211         if (a->adapt_dir < 0)
 212                 return 1 - (- a->adapt_dir) * b->moves / a->adapt_moves;
 213         else
 214                 return a->adapt_dir * b->moves / a->adapt_moves;
 215 }
 216
 217 static float
 218 komi_by_score(struct uct_dynkomi *d, struct board *b, struct tree *tree, enum stone color)
 219 {
 220         struct dynkomi_adaptive *a = d->data;
 221         if (d->score.playouts < TRUSTWORTHY_KOMI_PLAYOUTS)
 222                 return tree->extra_komi;
 223
 224         struct move_stats score = d->score;
 225         /* Almost-reset tree->score to gather fresh stats. */
 226         d->score.playouts = 1;
 227
 228         /* Look at average score and push extra_komi in that direction. */
 229         float p = a->adapter(d, b);
 230         p = a->adapt_base + p * (1 - a->adapt_base);
 231         if (p > 0.9) p = 0.9; // don't get too eager!
 232         float extra_komi = tree->extra_komi + p * score.value;
 233         if (DEBUGL(3))
 234                 fprintf(stderr, "mC += %f * %f\n", p, score.value);
 235         return extra_komi;
 236 }
 237
 238 static float
 239 komi_by_value(struct uct_dynkomi *d, struct board *b, struct tree *tree, enum stone color)
 240 {
 241         struct dynkomi_adaptive *a = d->data;
 242         if (d->value.playouts < TRUSTWORTHY_KOMI_PLAYOUTS)
 243                 return tree->extra_komi;
 244
 245         struct move_stats value = d->value;
 246         /* Almost-reset tree->value to gather fresh stats. */
 247         d->value.playouts = 1;
 248         /* Correct color POV. */
 249         if (color == S_WHITE)
 250                 value.value = 1 - value.value;
 251
 252         /* We have three "value zones":
 253          * red zone | yellow zone | green zone
 254          *        ~45%           ~60%
 255          * red zone: reduce komi
 256          * yellow zone: do not touch komi
 257          * green zone: enlage komi.
 258          *
 259          * Also, at some point komi will be tuned in such way
 260          * that it will be in green zone but increasing it will
 261          * be unfeasible. Thus, we have a _ratchet_ - we will
 262          * remember the last komi that has put us into the
 263          * red zone, and not use it or go over it. We use the
 264          * ratchet only when giving extra komi, we always want
 265          * to try to reduce extra komi we take.
 266          *
 267          * TODO: Make the ratchet expire after a while. */
 268
 269         /* We use komi_by_color() first to normalize komi
 270          * additions/subtractions, then apply it again on
 271          * return value to restore original komi parity. */
 272         /* Positive extra_komi means that we are _giving_
 273          * komi (winning), negative extra_komi is _taking_
 274          * komi (losing). */
 275         float extra_komi = komi_by_color(tree->extra_komi, color);
 276         int score_step_red = -a->score_step;
 277         int score_step_green = a->score_step;
 278
 279         if (a->score_step_byavg != 0) {
 280                 struct move_stats score = d->score;
 281                 /* Almost-reset tree->score to gather fresh stats. */
 282                 d->score.playouts = 1;
 283                 /* Correct color POV. */
 284                 if (color == S_WHITE)
 285                         score.value = - score.value;
 286                 if (score.value > 0)
 287                         score_step_green = round(score.value * a->score_step_byavg);
 288                 else
 289                         score_step_red = round(-score.value * a->score_step_byavg);
 290                 if (score_step_green < 0 || score_step_red > 0) {
 291                         /* The steps are in bad direction - keep still. */
 292                         return komi_by_color(extra_komi, color);
 293                 }
 294         }
 295
 296         /* Wear out the ratchet. */
 297         if (a->use_komi_ratchet && a->komi_ratchet_maxage > 0) {
 298                 a->komi_ratchet_age += value.playouts;
 299                 if (a->komi_ratchet_age > a->komi_ratchet_maxage) {
 300                         a->komi_ratchet = 1000;
 301                         a->komi_ratchet_age = 0;
 302                 }
 303         }
 304
 305         if (value.value < a->zone_red) {
 306                 /* Red zone. Take extra komi. */
 307                 if (DEBUGL(3))
 308                         fprintf(stderr, "[red] %f, step %d | komi ratchet %f age %d/%d -> %f\n",
 309                                 value.value, score_step_red, a->komi_ratchet, a->komi_ratchet_age, a->komi_ratchet_maxage, extra_komi);
 310                 if (a->losing_komi_ratchet || extra_komi > 0) {
 311                         assert(extra_komi < a->komi_ratchet);
 312                         a->komi_ratchet = extra_komi;
 313                         a->komi_ratchet_age = 0;
 314                 }
 315                 extra_komi += score_step_red;
 316                 return komi_by_color(extra_komi, color);
 317
 318         } else if (value.value < a->zone_green) {
 319                 /* Yellow zone, do nothing. */
 320                 return komi_by_color(extra_komi, color);
 321
 322         } else {
 323                 /* Green zone. Give extra komi. */
 324                 if (DEBUGL(3))
 325                         fprintf(stderr, "[green] %f, step %d | komi ratchet %f age %d/%d\n",
 326                                 value.value, score_step_green, a->komi_ratchet, a->komi_ratchet_age, a->komi_ratchet_maxage);
 327                 extra_komi += score_step_green;
 328                 if (a->use_komi_ratchet && extra_komi >= a->komi_ratchet)
 329                         extra_komi = a->komi_ratchet - 1;
 330                 return komi_by_color(extra_komi, color);
 331         }
 332 }
 333
 334 static float
 335 bounded_komi(enum stone color, float komi, float max_losing_komi)
 336 {
 337         /* Get lower bound on komi we take so that we don't underperform
 338          * too much. */
 339         float min_komi = komi_by_color(- max_losing_komi, color);
 340
 341         if (komi_by_color(komi - min_komi, color) > 0)
 342                 return komi;
 343         else
 344                 return min_komi;
 345 }
 346
 347 static float
 348 adaptive_permove(struct uct_dynkomi *d, struct board *b, struct tree *tree)
 349 {
 350         struct dynkomi_adaptive *a = d->data;
 351         enum stone color = stone_other(tree->root_color);
 352         if (DEBUGL(3))
 353                 fprintf(stderr, "m %d/%d ekomi %f permove %f/%d\n",
 354                         b->moves, a->lead_moves, tree->extra_komi,
 355                         d->score.value, d->score.playouts);
 356
 357         if (b->moves <= a->lead_moves)
 358                 return bounded_komi(color, board_effective_handicap(b, 7 /* XXX */), a->max_losing_komi);
 359
 360         float komi = a->indicator(d, b, tree, color);
 361         if (DEBUGL(3))
 362                 fprintf(stderr, "dynkomi: %f -> %f\n", tree->extra_komi, komi);
 363         return bounded_komi(color, komi, a->max_losing_komi);
 364 }
 365
 366 static float
 367 adaptive_persim(struct uct_dynkomi *d, struct board *b, struct tree *tree, struct tree_node *node)
 368 {
 369         return tree->extra_komi;
 370 }
 371
 372 struct uct_dynkomi *
 373 uct_dynkomi_init_adaptive(struct uct *u, char *arg, struct board *b)
 374 {
 375         struct uct_dynkomi *d = calloc2(1, sizeof(*d));
 376         d->uct = u;
 377         d->permove = adaptive_permove;
 378         d->persim = adaptive_persim;
 379         d->done = generic_done;
 380
 381         struct dynkomi_adaptive *a = calloc2(1, sizeof(*a));
 382         d->data = a;
 383
 384         if (board_size(b) - 2 >= 19)
 385                 a->lead_moves = 20;
 386         else
 387                 a->lead_moves = 4; // XXX
 388         a->max_losing_komi = 0;
 389         a->indicator = komi_by_score;
 390
 391         a->adapter = adapter_sigmoid;
 392         a->adapt_rate = -18;
 393         a->adapt_phase = 0.65;
 394         a->adapt_moves = 200;
 395         a->adapt_dir = -0.5;
 396
 397         a->zone_red = 0.45;
 398         a->zone_green = 0.55;
 399         a->score_step = 2;
 400         a->use_komi_ratchet = true;
 401         a->komi_ratchet_maxage = 0;
 402         a->komi_ratchet = 1000;
 403
 404         if (arg) {
 405                 char *optspec, *next = arg;
 406                 while (*next) {
 407                         optspec = next;
 408                         next += strcspn(next, ":");
 409                         if (*next) { *next++ = 0; } else { *next = 0; }
 410
 411                         char *optname = optspec;
 412                         char *optval = strchr(optspec, '=');
 413                         if (optval) *optval++ = 0;
 414
 415                         if (!strcasecmp(optname, "lead_moves") && optval) {
 416                                 /* Do not adjust komi adaptively for first
 417                                  * N moves. */
 418                                 a->lead_moves = atoi(optval);
 419                         } else if (!strcasecmp(optname, "max_losing_komi") && optval) {
 420                                 a->max_losing_komi = atof(optval);
 421                         } else if (!strcasecmp(optname, "indicator")) {
 422                                 /* Adaptatation indicator - how to decide
 423                                  * the adaptation rate and direction. */
 424                                 if (!strcasecmp(optval, "value")) {
 425                                         /* Winrate w/ komi so far. */
 426                                         a->indicator = komi_by_value;
 427                                 } else if (!strcasecmp(optval, "score")) {
 428                                         /* Expected score w/ current komi. */
 429                                         a->indicator = komi_by_score;
 430                                 } else {
 431                                         fprintf(stderr, "UCT: Invalid indicator %s\n", optval);
 432                                         exit(1);
 433                                 }
 434
 435                                 /* value indicator settings */
 436                         } else if (!strcasecmp(optname, "zone_red") && optval) {
 437                                 a->zone_red = atof(optval);
 438                         } else if (!strcasecmp(optname, "zone_green") && optval) {
 439                                 a->zone_green = atof(optval);
 440                         } else if (!strcasecmp(optname, "score_step") && optval) {
 441                                 a->score_step = atoi(optval);
 442                         } else if (!strcasecmp(optname, "score_step_byavg") && optval) {
 443                                 a->score_step_byavg = atof(optval);
 444                         } else if (!strcasecmp(optname, "use_komi_ratchet")) {
 445                                 a->use_komi_ratchet = !optval || atoi(optval);
 446                         } else if (!strcasecmp(optname, "losing_komi_ratchet")) {
 447                                 a->losing_komi_ratchet = !optval || atoi(optval);
 448                         } else if (!strcasecmp(optname, "komi_ratchet_age") && optval) {
 449                                 a->komi_ratchet_maxage = atoi(optval);
 450
 451                                 /* score indicator settings */
 452                         } else if (!strcasecmp(optname, "adapter") && optval) {
 453                                 /* Adaptatation method. */
 454                                 if (!strcasecmp(optval, "sigmoid")) {
 455                                         a->adapter = adapter_sigmoid;
 456                                 } else if (!strcasecmp(optval, "linear")) {
 457                                         a->adapter = adapter_linear;
 458                                 } else {
 459                                         fprintf(stderr, "UCT: Invalid adapter %s\n", optval);
 460                                         exit(1);
 461                                 }
 462                         } else if (!strcasecmp(optname, "adapt_base") && optval) {
 463                                 /* Adaptation base rate; see above. */
 464                                 a->adapt_base = atof(optval);
 465                         } else if (!strcasecmp(optname, "adapt_rate") && optval) {
 466                                 /* Adaptation slope; see above. */
 467                                 a->adapt_rate = atof(optval);
 468                         } else if (!strcasecmp(optname, "adapt_phase") && optval) {
 469                                 /* Adaptation phase shift; see above. */
 470                                 a->adapt_phase = atof(optval);
 471                         } else if (!strcasecmp(optname, "adapt_moves") && optval) {
 472                                 /* Adaptation move amount; see above. */
 473                                 a->adapt_moves = atoi(optval);
 474                         } else if (!strcasecmp(optname, "adapt_aport")) {
 475                                 a->adapt_aport = !optval || atoi(optval);
 476                         } else if (!strcasecmp(optname, "adapt_dir") && optval) {
 477                                 /* Adaptation direction vector; see above. */
 478                                 a->adapt_dir = atof(optval);
 479
 480                         } else {
 481                                 fprintf(stderr, "uct: Invalid dynkomi argument %s or missing value\n", optname);
 482                                 exit(1);
 483                         }
 484                 }
 485         }
 486
 487         return d;
 488 }