//
// transpositions.cpp
// fornax3
//
// Created by Anders on 19/06/2019.
//
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "transpositions.hpp"
#include "../libs/require.h"
#include "../libs/stopwatch.h"
#include "../libs/iolog.hpp"
#include "../parsing.hpp"
static const int max_age = 12;
static const int maintenance_freq_dividend = 24;
static const int max_offset = 16;
static const int put_age_limit = 3;
static uint32_t maintenance_freq;
static int size = TRANSPOSITIONS_SIZE_PER_MB * TRANSPOSITIONS_SIZE_MB_DEFAULT;
static Bucket* array;
static uint32_t put_counter = 0;
static uint32_t put_collisions = 0;
static int get_natural_index(ttkey hash) {
assert(hash % (uint32_t) size >= 0);
return (int) (hash % (uint32_t) size);
}
static inline void transpositions_increment_age(Bucket* b) {
if (b->age < max_age) b->age += 2;
}
static inline bool transpositions_decrement_age(Bucket* b) {
bool survives = b->age > 1;
if (b->age) b->age -= 1;
return survives;
}
static int find_index(int natural, ttkey hash, int min_age = 0) {
int end = natural + max_offset;
if (end >= size) end = end - size;
int candidate = natural;
while (candidate != end) {
Bucket* prev = array + candidate;
if (prev->hash == hash) {
return candidate;
}
else if (prev->age <= min_age) {
return candidate;
}
candidate++;
if (candidate == size) {
candidate = 0;
}
}
return candidate;
}
static int find_better_index(int natural, int current) {
int candidate = natural;
while (candidate != current) {
Bucket* prev = array + candidate;
if (prev->age == 0) {
return candidate;
}
candidate++;
if (candidate == size) {
candidate = 0;
}
}
return candidate;
}
static void transpositions_deteriorate(void) {
#if DEBUGLOG
long start = stopwatch_wall_start();
#endif
int shifts = 0;
int entries = 0;
for (int i = 0; i < size; ++i) {
Bucket* b = array + i;
bool survives = transpositions_decrement_age(b);
entries += b->age > 0;
if (survives) {
int natural = get_natural_index(b->hash);
int shifted = find_better_index(natural, i);
if (shifted != i) {
*(array + shifted) = *b;
b->age = 0;
shifts++;
}
}
}
#if DEBUGLOG
IO_PRINT("info hashfull %d string - tt maintenance (shifted %d) (collisions in cycle %d%% (%d/%d) time %.3fs\n",
entries / (size / 100),
shifts,
(put_counter < 100 ? 0 : put_collisions / (put_counter / 100)),
put_collisions, put_counter,
(double) stopwatch_wall_stop(start) / 1000);
#endif
put_counter = 0;
put_collisions = 0;
}
void transpositions_maintenance(void) {
transpositions_deteriorate();
}
void transpositions_put(ttkey hash, uint8_t depth, eval score, move m, tttype type) {
put_counter++;
if (put_counter == maintenance_freq) {
transpositions_deteriorate();
}
Bucket bucket = {hash, m, score, type, depth, max_age};
int natural = get_natural_index(bucket.hash);
int index = find_index(natural, bucket.hash, put_age_limit);
if (natural != index) put_collisions++;
array[index] = bucket;
}
Bucket* transpositions_get(ttkey hash) {
Bucket* b = array + find_index(get_natural_index(hash), hash);
if (b->hash == hash) transpositions_increment_age(b);
return b;
}
void transpositions_clear(void) {
for (int i = 0; i < size; ++i) {
Bucket empty = {0,0,0,0,0,0};
array[i] = empty;
}
put_counter = 0;
put_collisions = 0;
}
void transpositions_status() {
int entries = 0;
int natural = 0;
int largest_offset = 0;
int average_offset = 0;
int average_age = 0;
for (int i = 0; i < size; ++i) {
Bucket* b = array + i;
if (b->age > 0) {
entries++;
average_age += b->age;
int nat = get_natural_index(b->hash);
if (nat == i) natural++;
else {
int ii = i;
if (ii < nat) ii = size + i;
int offset = ii - nat;
if (offset > largest_offset) largest_offset = offset;
average_offset += offset;
}
}
}
average_offset = entries > 0 ? average_offset / entries : 0;
average_age = entries > 0 ? average_age / entries : 0;
IO_PRINT("entries = %d/%d (%d%%)\n", entries, size, entries / (size / 100));
IO_PRINT("natural = %d/%d (%d%%)\n", natural, entries, entries > 0 ? (natural / (entries / 100)) : 0);
IO_PRINT("average offset = %d, largest = %d\n", average_offset, largest_offset);
IO_PRINT("average age = %d\n", average_age);
}
void transpositions_print_line(int i) {
Bucket* b = array + i;
IO_PRINT("[ %c %c | i: %6d | nat: %6d | age: %7d | d: %2d | ",
(b->depth > 0 ? b->age != 0 ? 'A' : 'O' : ' '),
(get_natural_index(b->hash) == i && b->age != 0 ? 'N' : ' '),
i,
get_natural_index(b->hash),
b->age,
b->depth);
IO_PRINT(" | hash: %20" PRIu64 "] ",b->hash);
parsing_printmove(b->ttmove);
IO_PRINT(" eval %d\n", b->tteval);
}
void transpositions_print(long rows) {
if (rows == 0) {
rows = size;
}
for (int i = 0; i < rows; ++i) {
transpositions_print_line(i);
}
}
void transpositions_print_bucket(ttkey hash, long offset) {
int i = find_index(get_natural_index(hash), hash) + (int) offset;
transpositions_print_line(i > 3 ? i - 4 : size - 4);
transpositions_print_line(i > 2 ? i - 3 : size - 3);
transpositions_print_line(i > 1 ? i - 2 : size - 2);
transpositions_print_line(i > 0 ? i - 1 : size - 1);
IO_PRINT("*\n");
transpositions_print_line(i);
IO_PRINT("*\n");
transpositions_print_line(i < size - 1 ? i + 1 : 0);
transpositions_print_line(i < size - 2 ? i + 2 : 2);
transpositions_print_line(i < size - 3 ? i + 3 : 3);
transpositions_print_line(i < size - 4 ? i + 4 : 4);
}
void transpositions_init(void) {
maintenance_freq = (uint32_t) (size / maintenance_freq_dividend);
array = (Bucket*) malloc(sizeof(struct bucket) * (unsigned long) size);
transpositions_clear();
}
void transpositions_destroy(void) {
free(array);
}
void transpositions_set_hash_size(long MB) {
require(MB <= TRANSPOSITIONS_SIZE_MB_MAX, "hash size was too big %lu vs max %d\n", MB, TRANSPOSITIONS_SIZE_MB_MAX);
require(MB >= TRANSPOSITIONS_SIZE_MB_MIN, "hash size was too small %lu vs min %d\n", MB, TRANSPOSITIONS_SIZE_MB_MIN);
transpositions_destroy();
size = TRANSPOSITIONS_SIZE_PER_MB * (int) MB;
transpositions_init();
#if DEBUGLOG
IO_PRINT("ok Hash size = %lu\n", MB);
#endif
}