transposition.cpp

超强国际象棋引擎

// trans.cpp

// includes

#include <cstdlib>

#include "hash.h"
#include "move.h"
#include "config.h"
#include "interface.h"
#include "transposition.h"
#include "util.h"
#include "values.h"

#pragma warning( disable : 4244 )
// Level 2 conversion from 'int' to 'short', possible loss of data ->

// macros

#define MIN(a,b) ((a)<=(b)?(a):(b))
#define MAX(a,b) ((a)>=(b)?(a):(b))

#define ENTRY_DATE(entry)  ((entry)->date_flags>>4)
#define ENTRY_FLAGS(entry) ((entry)->date_flags&3)

// types

struct trans
    {
    entry_t *table;
    uint32 size;
    uint32 mask;
    int date;
    int age[16];
    uint32 used;
    sint64 read_nb;
    sint64 read_hit;
    sint64 write_nb;
    sint64 write_hit;
    sint64 write_collision;
    };

// variables

trans_t Trans[1];
static uint32 hash_size = 16;

// prototypes

static void trans_set_date(trans_t *trans, int date);
static int trans_age(const trans_t *trans, int date);

static entry_t *trans_entry(trans_t *trans, uint64 key);

// functions

// trans_parameter()

void trans_parameter()
    {
    static bool DynamicHash = false;
    static bool ManualHash = false;
    static int spm = 5;
    static int nps = 500000;
    static int npm = 2500000;

    // UCI options

    DynamicHash = (option_get_bool("Dynamic Hash"));
    ManualHash = (option_get_bool("Manual Hash"));

    if(DynamicHash)
        {
        nps = (option_get_int("Nodes Per Second"));
        spm = (option_get_int("Seconds Per Move"));
        npm = spm * nps;
        hash_size = abs(npm * 32 / 1024 / 1024);
        trans_free(Trans);
        trans_alloc(Trans);
        }
    else if(ManualHash)
        {
        hash_size = option_get_int("Manual Hash Size");
        trans_free(Trans);
        trans_alloc(Trans);
        }
    else
        {
        hash_size = 64;
        trans_free(Trans);
        trans_alloc(Trans);
        }
    }

// trans_is_ok()

bool trans_is_ok(const trans_t *trans)
    {

    int date;

    if(trans == NULL)
        return false;

    if(trans->table == NULL)
        return false;

    if(trans->size == 0)
        return false;

    if(trans->mask == 0 || trans->mask >= trans->size)
        return false;

    if(trans->date >= 16)
        return false;

    for ( date = 0; date < 16; date++ )
        {
        if(trans->age[date] != trans_age(trans, date))
            return false;
        }

    return true;
    }

// trans_init()

void trans_init(trans_t *trans)
    {

    trans->size = 0;
    trans->mask = 0;
    trans->table = NULL;

    trans_set_date(trans, 0);

    trans_clear(trans);
    }

// trans_alloc()

void trans_alloc(trans_t *trans)
    {

    uint32 size, target;

    // calculate size

    target = hash_size;

    if(target < 8)
        target = 8;

    if(target > 1024)
        target = 1024;

    target *= 1024 * 1024;

    for ( size = 1; size != 0 && size <= target; size *= 2 )
    ;

    size /= 2;

    // allocate table

    size /= sizeof(entry_t);

    trans->size = size + (4 - 1);
    trans->mask = size - 1;

    trans->table = (entry_t *)malloc(trans->size * sizeof(entry_t));
    send("hash: %d MB\n", trans->size * sizeof(entry_t) / 1024 / 1024);

    trans_clear(trans);
    }

// trans_free()

void trans_free(trans_t *trans)
    {

    free(trans->table);

    trans->table = NULL;
    trans->size = 0;
    trans->mask = 0;
    }

// trans_clear()

void trans_clear(trans_t *trans)
    {

    entry_t clear_entry[1];
    entry_t *entry;
    uint32 index;

    trans_set_date(trans, 0);

    clear_entry->key = 0;
    clear_entry->move = 0;
    clear_entry->depth = -128;
    clear_entry->date_flags = (trans->date << 4);

    entry = trans->table;

    for ( index = 0; index < trans->size; index++ )
        {
        *entry++ = *clear_entry;
        }
    }

// trans_inc_date()

void trans_inc_date(trans_t *trans)
    {

    trans_set_date(trans, (trans->date + 1) % 16);
    }

// trans_set_date()

static void trans_set_date(trans_t *trans, int date)
    {

    trans->date = date;

    for ( date = 0; date < 16; date++ )
        {
        trans->age[date] = trans_age(trans, date);
        }

    trans->used = 0;
    trans->read_nb = 0;
    trans->read_hit = 0;
    trans->write_nb = 0;
    trans->write_hit = 0;
    trans->write_collision = 0;
    }

// trans_age()

static int trans_age(const trans_t *trans, int date)
    {

    int age;

    age = trans->date - date;

    if(age < 0)
        age += 16;

    return age;
    }

// trans_store()

void trans_store(trans_t *trans, uint64 key, int move, int depth, int flags, int value)
    {

    entry_t *entry, *best_entry;
    int score, best_score;
    int i;

    // init

    trans->write_nb++;

    // probe

    best_entry = NULL;
    best_score = -32767;

    entry = trans_entry(trans, key);

    for ( i = 0; i < 4; i++, entry++ )
        {
        if(entry->key == key)
            {

            // hash hit => update existing entry

            trans->write_hit++;

            if(ENTRY_DATE(entry) != trans->date)
                trans->used++;

            if(entry->depth <= depth)
                {
                if(move == 0)
                    move = entry->move;

                entry->move = move;
                entry->depth = depth;
                entry->date_flags = (trans->date << 4) | flags;
                entry->value = value;
                }
            else
                { // deeper entry
                if(entry->move == 0)
                    entry->move = move;
                entry->date_flags = (trans->date << 4) | ENTRY_FLAGS(entry);
                }

            return;
            }

        // evaluate replacement score

        score = trans->age[ENTRY_DATE(entry)] * 256 - entry->depth;

        score = score * 4 - ENTRY_FLAGS(entry);

        if(score > best_score)
            {
            best_entry = entry;
            best_score = score;
            }
        }

    // "best" entry found

    entry = best_entry;

    if(ENTRY_DATE(entry) == trans->date)
        {
        trans->write_collision++;
        }
    else
        {
        trans->used++;
        }

    // store

    entry->key = key;
    entry->move = move;
    entry->depth = depth;
    entry->date_flags = (trans->date << 4) | flags;
    entry->value = value;
    }

// trans_retrieve()

bool trans_retrieve(trans_t *trans, entry_t ** found_entry, uint64 key, int *move, int *depth, int *flags, int *value)
    {

    int i;
    entry_t *entry;

    // init

    trans->read_nb++;

    // probe

    entry = trans_entry(trans, key);

    for ( i = 0; i < 4; i++, entry++ )
        {
        if(entry->key == key)
            {

            // found

            trans->read_hit++;

            *move = entry->move;
            *depth = entry->depth;
            *flags = ENTRY_FLAGS(entry);
            *value = entry->value;

            *found_entry = entry;
            return true;
            }
        }

    // not found

    *found_entry = entry;
    return false;
    }

// trans_stats()

void trans_stats(const trans_t *trans)
    {

    double full;

    full = double(trans->used) / double(trans->size);

    send("info hashfull %.0f", full * 1000.0);
    }

// trans_entry()

static entry_t *trans_entry(trans_t *trans, uint64 key)
    {

    uint32 index;

    index = key & trans->mask;

    return &trans->table[index];
    }

// end of trans.cpp