src/transpositions.c

   1 /*
   2 Transpositions table and tree implementation.
   3
   4 Doesn't assume states are in reduced form. States contain full information and
   5 are compared after the hash (collisions are impossible). Zobrist hashing with 64
   6 bits is used. Clean-up is available only between turns or between games.
   7
   8 Please note there is no separate 'UCT state information' file. It is mostly
   9 interweaved with the transpositions table.
  10
  11 The table is actually two tables, one for each player. Mixing their statistics
  12 is illegal. The nodes statistics are from the perspective of the respective
  13 table color.
  14 */
  15
  16 #include "config.h"
  17
  18 #include <string.h>
  19 #include <stdio.h>
  20 #include <stdlib.h>
  21 #include <assert.h>
  22 #include <omp.h>
  23
  24 #include "alloc.h"
  25 #include "board.h"
  26 #include "cfg_board.h"
  27 #include "flog.h"
  28 #include "primes.h"
  29 #include "transpositions.h"
  30 #include "types.h"
  31 #include "zobrist.h"
  32
  33 u16 expansion_delay = UCT_EXPANSION_DELAY;
  34 u64 max_size_in_mbs = DEFAULT_UCT_MEMORY;
  35
  36 static u32 max_allocated_states;
  37 static u32 number_of_buckets;
  38
  39 static u32 allocated_states = 0;
  40 static u32 states_in_use = 0;
  41
  42 static omp_lock_t b_table_lock;
  43 static omp_lock_t w_table_lock;
  44 static tt_stats ** b_stats_table = NULL;
  45 static tt_stats ** w_stats_table = NULL;
  46
  47 static omp_lock_t freed_nodes_lock;
  48 static tt_stats * freed_nodes = NULL;
  49
  50 /* value used to mark items for deletion; will cycle eventually but its not a
  51 big deal */
  52 static u8 maintenance_mark = 0;
  53
  54
  55 /*
  56 Initialize the transpositions table structures.
  57 */
  58 void tt_init() {
  59     if (b_stats_table == NULL) {
  60         u64 mbs = max_size_in_mbs;
  61         mbs *= 1048576;
  62
  63         max_allocated_states = mbs / sizeof(tt_stats);
  64         number_of_buckets = get_prime_near(max_allocated_states / 2);
  65
  66         b_stats_table = calloc(number_of_buckets, sizeof(tt_stats *));
  67         if (b_stats_table == NULL) {
  68             flog_crit("tt", "system out of memory");
  69         }
  70
  71         w_stats_table = calloc(number_of_buckets, sizeof(tt_stats *));
  72         if (w_stats_table == NULL) {
  73             flog_crit("tt", "system out of memory");
  74         }
  75
  76         omp_init_lock(&b_table_lock);
  77         omp_init_lock(&w_table_lock);
  78         omp_init_lock(&freed_nodes_lock);
  79     }
  80 }
  81
  82
  83
  84 static u32 fast_bucket(u32 hash, u32 number_of_buckets) {
  85     return (u32)((((u64)hash) * ((u64)number_of_buckets)) >> 32);
  86 }
  87
  88
  89
  90 /*
  91 Searches for a state by hash, in a bucket by key.
  92 RETURNS state found or null.
  93 */
  94 static tt_stats * find_state(
  95     u64 hash,
  96     const board * b,
  97     bool is_black
  98 ) {
  99     u32 key = fast_bucket(hash, number_of_buckets);
 100     tt_stats * p;
 101
 102     if (is_black) {
 103         p = b_stats_table[key];
 104     } else {
 105         p = w_stats_table[key];
 106     }
 107
 108     move last_eaten_passed = (b->last_played == PASS) ? PASS : b->last_eaten;
 109
 110     while (p != NULL) {
 111         if (p->zobrist_hash == hash && memcmp(p->p, b->p, TOTAL_BOARD_SIZ) == 0 &&
 112             p->last_eaten_passed == last_eaten_passed) {
 113             return p;
 114         }
 115
 116         p = p->next;
 117     }
 118
 119     return NULL;
 120 }
 121
 122 static tt_stats * find_state2(
 123     u64 hash,
 124     const cfg_board * cb,
 125     bool is_black
 126 ) {
 127     u32 key = fast_bucket(hash, number_of_buckets);
 128     tt_stats * p;
 129
 130     if (is_black) {
 131         p = b_stats_table[key];
 132     } else {
 133         p = w_stats_table[key];
 134     }
 135
 136     move last_eaten_passed = (cb->last_played == PASS) ? PASS : cb->last_eaten;
 137
 138     while (p != NULL) {
 139         if (p->zobrist_hash == hash && memcmp(p->p, cb->p, TOTAL_BOARD_SIZ) == 0 &&
 140             p->last_eaten_passed == last_eaten_passed) {
 141             return p;
 142         }
 143
 144         p = p->next;
 145     }
 146
 147     return NULL;
 148 }
 149
 150 static tt_stats * create_state(
 151     u64 hash
 152 ) {
 153     tt_stats * ret = NULL;
 154
 155     omp_set_lock(&freed_nodes_lock);
 156
 157     if (freed_nodes != NULL) {
 158         ret = freed_nodes;
 159         freed_nodes = freed_nodes->next;
 160     } else {
 161         ++allocated_states;
 162     }
 163
 164     ++states_in_use;
 165     omp_unset_lock(&freed_nodes_lock);
 166
 167     if (ret == NULL) {
 168         ret = malloc(sizeof(tt_stats));
 169
 170         if (ret == NULL) {
 171             flog_crit("tt", "create_state: system out of memory");
 172         }
 173
 174         omp_init_lock(&ret->lock);
 175     }
 176
 177     /* careful that some fields are not initialized here */
 178     ret->zobrist_hash = hash;
 179     ret->maintenance_mark = maintenance_mark;
 180     ret->plays_count = 0;
 181     ret->expansion_delay = expansion_delay;
 182     return ret;
 183 }
 184
 185 static void release_state(
 186     tt_stats * s
 187 ) {
 188     --states_in_use;
 189     s->next = freed_nodes;
 190     freed_nodes = s;
 191 }
 192
 193 static void release_states_not_marked() {
 194     for (u32 i = 0; i < number_of_buckets; ++i) {
 195         /* black table */
 196         while (b_stats_table[i] != NULL && b_stats_table[i]->maintenance_mark != maintenance_mark) {
 197             tt_stats * tmp = b_stats_table[i]->next;
 198             release_state(b_stats_table[i]);
 199             b_stats_table[i] = tmp;
 200         }
 201
 202         if (b_stats_table[i] != NULL) {
 203             tt_stats * prev = b_stats_table[i];
 204             tt_stats * curr = prev->next;
 205
 206             while (curr != NULL) {
 207                 if (curr->maintenance_mark != maintenance_mark) {
 208                     tt_stats * tmp = curr->next;
 209                     release_state(curr);
 210                     prev->next = tmp;
 211                     curr = tmp;
 212                 } else {
 213                     prev = curr;
 214                     curr = curr->next;
 215                 }
 216             }
 217         }
 218
 219         /* white table */
 220         while (w_stats_table[i] != NULL && w_stats_table[i]->maintenance_mark !=
 221             maintenance_mark) {
 222             tt_stats * tmp = w_stats_table[i]->next;
 223             release_state(w_stats_table[i]);
 224             w_stats_table[i] = tmp;
 225         }
 226
 227         if (w_stats_table[i] != NULL) {
 228             tt_stats * prev = w_stats_table[i];
 229             tt_stats * curr = prev->next;
 230
 231             while (curr != NULL) {
 232                 if (curr->maintenance_mark != maintenance_mark) {
 233                     tt_stats * tmp = curr->next;
 234                     release_state(curr);
 235                     prev->next = tmp;
 236                     curr = tmp;
 237                 } else {
 238                     prev = curr;
 239                     curr = curr->next;
 240                 }
 241             }
 242         }
 243     }
 244 }
 245
 246 static void mark_states_for_keeping(
 247     tt_stats * s
 248 ) {
 249     s->maintenance_mark = maintenance_mark;
 250
 251     for (move i = 0; i < s->plays_count; ++i) {
 252         tt_stats * ns = s->plays[i].next_stats;
 253
 254         if (ns != NULL && ns->maintenance_mark != maintenance_mark) {
 255             mark_states_for_keeping(ns);
 256         }
 257     }
 258 }
 259
 260 /*
 261 Frees states outside of the subtree started at state b. Not thread-safe.
 262 RETURNS number of states freed.
 263 */
 264 u32 tt_clean_unreachable(
 265     const board * b,
 266     bool is_black
 267 ) {
 268     u64 hash = zobrist_new_hash(b);
 269     u32 states_in_use_before = states_in_use;
 270     tt_stats * stats = find_state(hash, b, is_black);
 271
 272     if (stats == NULL) { /* free all */
 273         tt_clean_all();
 274     } else {
 275         /* free outside tree */
 276         ++maintenance_mark;
 277         mark_states_for_keeping(stats);
 278         release_states_not_marked();
 279     }
 280
 281     d32 states_released = states_in_use_before - states_in_use;
 282     assert(states_released >= 0);
 283     return states_released;
 284 }
 285
 286 /*
 287 Looks up a previously stored state, or generates a new one. No assumptions are
 288 made about whether the board state is in reduced form already. Never fails. If
 289 the memory is full it allocates a new state regardless. If the state is found
 290 and returned it's OpenMP lock is first set. Thread-safe.
 291 RETURNS the state information
 292 */
 293 tt_stats * tt_lookup_create(
 294     const board * b,
 295     bool is_black,
 296     u64 hash
 297 ) {
 298     u32 key = fast_bucket(hash, number_of_buckets);
 299     omp_lock_t * bucket_lock = is_black ? &b_table_lock : &w_table_lock;
 300
 301     omp_set_lock(bucket_lock);
 302
 303     tt_stats * ret = find_state(hash, b, is_black);
 304     if (ret == NULL) { /* doesnt exist */
 305         if (states_in_use >= max_allocated_states) {
 306             /*
 307             It is possible in theory for a complex ko to produce a situation
 308             where freeing the game tree that is not reachable doesn't free any
 309             states.
 310             */
 311             tt_log_status();
 312             char * s = alloc();
 313             board_to_string(s, b->p, b->last_played, b->last_eaten);
 314             flog_warn("tt", s);
 315             release(s);
 316             flog_warn("tt", "memory exceeded on root lookup");
 317         }
 318
 319         ret = create_state(hash);
 320         memcpy(ret->p, b->p, TOTAL_BOARD_SIZ);
 321         ret->last_eaten_passed = (b->last_played == PASS) ? PASS : b->last_eaten;
 322
 323         omp_set_lock(&ret->lock);
 324
 325         if (is_black) {
 326             ret->next = b_stats_table[key];
 327             b_stats_table[key] = ret;
 328         } else {
 329             ret->next = w_stats_table[key];
 330             w_stats_table[key] = ret;
 331         }
 332
 333         omp_unset_lock(bucket_lock);
 334     } else { /* update */
 335         omp_set_lock(&ret->lock);
 336         omp_unset_lock(bucket_lock);
 337     }
 338
 339     return ret;
 340 }
 341
 342 /*
 343 Looks up a previously stored state, or generates a new one. No assumptions are
 344 made about whether the board state is in reduced form already. If the limit on
 345 states has been met the function returns NULL. If the state is found and
 346 returned it's OpenMP lock is first set. Thread-safe.
 347 RETURNS the state information or NULL
 348 */
 349 tt_stats * tt_lookup_null(
 350     const cfg_board * cb,
 351     bool is_black,
 352     u64 hash
 353 ) {
 354     u32 key = fast_bucket(hash, number_of_buckets);
 355     omp_lock_t * bucket_lock = is_black ? &b_table_lock : &w_table_lock;
 356
 357     omp_set_lock(bucket_lock);
 358
 359     tt_stats * ret = find_state2(hash, cb, is_black);
 360     if (ret == NULL) { /* doesnt exist */
 361         if (states_in_use >= max_allocated_states) {
 362             omp_unset_lock(bucket_lock);
 363             return NULL;
 364         }
 365
 366         ret = create_state(hash);
 367         memcpy(ret->p, cb->p, TOTAL_BOARD_SIZ);
 368         ret->last_eaten_passed = (cb->last_played == PASS) ? PASS : cb->last_eaten;
 369         omp_set_lock(&ret->lock);
 370
 371         if (is_black) {
 372             ret->next = b_stats_table[key];
 373             b_stats_table[key] = ret;
 374         } else {
 375             ret->next = w_stats_table[key];
 376             w_stats_table[key] = ret;
 377         }
 378
 379         omp_unset_lock(bucket_lock);
 380     } else { /* update */
 381
 382         omp_set_lock(&ret->lock);
 383         omp_unset_lock(bucket_lock);
 384     }
 385
 386     return ret;
 387 }
 388
 389 /*
 390 Frees all game states and resets counters.
 391 */
 392 u32 tt_clean_all() {
 393     u32 states_in_use_before = states_in_use;
 394     maintenance_mark = 0;
 395
 396     for (u32 i = 0; i < number_of_buckets; ++i) {
 397         /* black table */
 398         while (b_stats_table[i] != NULL) {
 399             tt_stats * tmp = b_stats_table[i]->next;
 400             release_state(b_stats_table[i]);
 401             b_stats_table[i] = tmp;
 402         }
 403
 404         /* white table */
 405         while (w_stats_table[i] != NULL) {
 406             tt_stats * tmp = w_stats_table[i]->next;
 407             release_state(w_stats_table[i]);
 408             w_stats_table[i] = tmp;
 409         }
 410     }
 411
 412     d32 states_released = states_in_use_before - states_in_use;
 413     assert(states_released >= 0);
 414     return states_released;
 415 }
 416
 417 /*
 418 Mostly for debugging -- log the current memory status of the transpositions
 419 table to stderr and log file.
 420 */
 421 void tt_log_status() {
 422     char * buf = alloc();
 423     u32 idx = snprintf(buf, MAX_PAGE_SIZ, "\n*** Transpositions table trace start ***\n\n");
 424     idx += snprintf(buf + idx, MAX_PAGE_SIZ - idx, "Max size in MiB: %" PRIu64 "\n", max_size_in_mbs);
 425     idx += snprintf(buf + idx, MAX_PAGE_SIZ - idx, "Max allocated states: %u\n", max_allocated_states);
 426     idx += snprintf(buf + idx, MAX_PAGE_SIZ - idx, "Allocated states: %u\n", allocated_states);
 427     idx += snprintf(buf + idx, MAX_PAGE_SIZ - idx, "States in use: %u\n", states_in_use);
 428     idx += snprintf(buf + idx, MAX_PAGE_SIZ - idx, "Number of buckets: %u\n", number_of_buckets);
 429     snprintf(buf + idx, MAX_PAGE_SIZ - idx, "Maintenance mark: %u\n", maintenance_mark);
 430
 431     flog_warn("tt", buf);
 432     release(buf);
 433 }