hash.c

Go to the documentation of this file.

 
#include "bit.h"
#include "hash.h"
#include "options.h"
#include "stats.h"
#include "search.h"
#include "util.h"
#include "settings.h"
 
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
 
unsigned long long hash_rank[16][256];
 
unsigned long long hash_move[64][60];
 
const HashData HASH_DATA_INIT = {0, 0, 0, 0, -SCORE_INF, SCORE_INF, {NOMOVE, NOMOVE}};
 
void hash_code_init(void)
{
        int i, j;
        Random r;
 
        random_seed(&r, 0x5DEECE66Dull);
        for (i = 0; i < 16; ++i)
        for (j = 0; j < 256; ++j) {
                do {
                        hash_rank[i][j] = random_get(&r);
                } while (bit_count(hash_rank[i][j]) < 8); 
        }
}
 
 
void hash_move_init(void)
{
        int i, j;
        Random r;
 
        random_seed(&r, 0x5DEECE66Dull);
        for (i = 0; i < 64; ++i)
        for (j = 0; j < 60; ++j) {
                do {
                        hash_move[i][j] = random_get(&r);
                } while (bit_count(hash_move[i][j]) < 8); 
        }
}
 
void hash_init(HashTable *hash_table, const unsigned long long size)
{
        int i, n_way;
 
        for (n_way = 1; n_way < HASH_N_WAY; n_way <<= 1);
 
        assert(hash_table != NULL);
        assert((n_way & -n_way) == n_way);
 
        info("< init hashtable of %llu entries>\n", size);
        if (hash_table->hash != NULL) free(hash_table->memory);
        hash_table->memory = malloc((size + n_way + 1) * sizeof (Hash));
        if (hash_table->memory == NULL) {
                fatal_error("hash_init: cannot allocate the hash table\n");
        }
 
        if (HASH_ALIGNED) {
                const size_t alignment = n_way * sizeof (Hash) - 1;
                hash_table->hash = (Hash*) (((size_t) hash_table->memory + alignment) & ~alignment);
                hash_table->hash_mask = size - n_way;
        } else {
                hash_table->hash = (Hash*) hash_table->memory;
                hash_table->hash_mask = size - 1;
        }
 
        hash_cleanup(hash_table);
 
        hash_table->n_lock = 256 * MAX(get_cpu_number(), 1);
        hash_table->lock_mask = hash_table->n_lock - 1;
        hash_table->n_lock += n_way + 1;
        hash_table->lock = (HashLock*) malloc(hash_table->n_lock * sizeof (HashLock));
 
        for (i = 0; i < hash_table->n_lock; ++i) spin_init(hash_table->lock + i);
}
 
void hash_cleanup(HashTable *hash_table)
{
        register unsigned int i;
 
        assert(hash_table != NULL && hash_table->hash != NULL);
 
        info("< cleaning hashtable >\n");
        for (i = 0; i <= hash_table->hash_mask + HASH_N_WAY; ++i) {
                HASH_COLLISIONS(hash_table->hash[i].key = 0;)
                hash_table->hash[i].board.player = hash_table->hash[i].board.opponent = 0; 
                hash_table->hash[i].data = HASH_DATA_INIT;
        }
        hash_table->date = 0;
}
 
void hash_clear(HashTable *hash_table)
{
        assert(hash_table != NULL);
 
        if (hash_table->date == 127) hash_cleanup(hash_table);
        ++hash_table->date;
        info("< clearing hashtable -> date = %d>\n", hash_table->date);
        assert(hash_table->date > 0 && hash_table->date <= 127);
}
 
void hash_free(HashTable *hash_table)
{
        int i;
        assert(hash_table != NULL && hash_table->hash != NULL);
        free(hash_table->memory);
        hash_table->hash = NULL;
        for (i = 0; i < hash_table->n_lock; ++i) spin_free(hash_table->lock + i);
        free(hash_table->lock);
}
 
inline unsigned int writeable_level(HashData *data)
{
        if (USE_TYPE_PUNING) { // HACK: depends on little endian.
                return (*(unsigned int*) data);
        } else { // slow but more portable implementation.
                return (((unsigned)data->date) << 24) + (((unsigned)data->cost) << 16) + (data->selectivity << 8) + data->depth;
        }
}
 
static void data_update(HashData *data, const int cost, const int alpha, const int beta, const int score, const int move)
{
        if (score < beta && score < data->upper) data->upper = (signed char) score;
        if (score > alpha && score > data->lower) data->lower = (signed char) score;
        if ((score > alpha || score == SCORE_MIN) && data->move[0] != move) {
                data->move[1] = data->move[0];
                data->move[0] = (unsigned char) move;
        }
        data->cost = (unsigned char) MAX(cost, data->cost);
        HASH_STATS(++statistics.n_hash_update;)
}
 
static void data_upgrade(HashData *data, const int depth, const int selectivity, const int cost, const int alpha, const int beta, const int score, const int move)
{
        if (score < beta) data->upper = (signed char) score; else data->upper = SCORE_MAX;
        if (score > alpha) data->lower =(signed char) score; else data->lower = SCORE_MIN;
        if ((score > alpha || score == SCORE_MIN) && data->move[0] != move) {
                data->move[1] = data->move[0];
                data->move[0] = (unsigned char) move;
        }
        data->depth = depth;
        data->selectivity = selectivity;
        data->cost = (unsigned char) MAX(cost, data->cost);  // this may not work well in parallel search.
        HASH_STATS(++statistics.n_hash_upgrade;)
 
        assert(data->upper >= data->lower);
}
 
static void data_new(HashData *data, const int date, const int depth, const int selectivity, const int cost, const int alpha, const int beta, const int score, const int move)
{
        if (score < beta) data->upper = (signed char) score; else data->upper = SCORE_MAX;
        if (score > alpha) data->lower = (signed char) score; else data->lower = SCORE_MIN;
        if (score > alpha || score == SCORE_MIN) data->move[0] = (unsigned char) move;
        else data->move[0] = NOMOVE;
        data->move[1] = NOMOVE;
        data->depth = depth;
        data->selectivity = selectivity;
        data->cost = cost;
        data->date = date;
        assert(data->upper >= data->lower);
}
 
#if (HASH_COLLISIONS(1)+0)
static void hash_new(Hash *hash, HashLock *lock, const unsigned long long hash_code, const Board* board, const int date, const int depth, const int selectivity, const int cost, const int alpha, const int beta, const int score, const int move)
#else
static void hash_new(Hash *hash, HashLock *lock, const Board* board, const int date, const int depth, const int selectivity, const int cost, const int alpha, const int beta, const int score, const int move)
#endif
{
        spin_lock(lock);
        HASH_STATS(if (date == hash->data.date) ++statistics.n_hash_remove;)
        HASH_STATS(++statistics.n_hash_new;)
        HASH_COLLISIONS(hash->key = hash_code;)
        hash->board = *board;
        data_new(&hash->data, date, depth, selectivity, cost, alpha, beta, score, move);
        spin_unlock(lock);
}
 
#if (HASH_COLLISIONS(1)+0)
static void hash_set(Hash *hash, HashLock *lock, const unsigned long long hash_code, const Board *board, const int date, const int depth, const int selectivity, const int cost, const int lower, const int upper, const int move)
#else
static void hash_set(Hash *hash, HashLock *lock, const Board *board, const int date, const int depth, const int selectivity, const int cost, const int lower, const int upper, const int move)
#endif
{
        spin_lock(lock);
        HASH_STATS(if (date == hash->data.date) ++statistics.n_hash_remove;)
        HASH_STATS(++statistics.n_hash_new;)
        HASH_COLLISIONS(hash->key = hash_code;)
        hash->board = *board;
        hash->data.upper = (signed char) upper;
        hash->data.lower = (signed char) lower;
        hash->data.move[0] = (unsigned char) move;
        hash->data.move[1] = NOMOVE;
        hash->data.depth = (unsigned char) depth;
        hash->data.selectivity = (unsigned char) selectivity;
        hash->data.cost = (unsigned char) cost;
        hash->data.date = (unsigned char) date;
        assert(hash->data.upper >= hash->data.lower);
        spin_unlock(lock);
}
 
 
static bool hash_update(Hash *hash, HashLock *lock, const Board *board, const int date, const int depth, const int selectivity, const int cost, const int alpha, const int beta, const int score, const int move)
{
        bool ok = false;
        HashData *data;
 
        if (hash->board.player == board->player && hash->board.opponent == board->opponent) {
                spin_lock(lock);
                if (hash->board.player == board->player && hash->board.opponent == board->opponent) {
                        data = &hash->data;
                        if (data->selectivity == selectivity && data->depth == depth) data_update(data, cost, alpha, beta, score, move);
                        else data_upgrade(data, depth, selectivity, cost, alpha, beta, score, move);
                        data->date = (unsigned char) date;
                        if (data->lower > data->upper) { // reset the hash-table...
                                data_new(data, date, depth, selectivity, cost, alpha, beta, score, move);
                        }
                        ok = true;
                } 
                spin_unlock(lock);
        }
        return ok;
}
 
static bool hash_replace(Hash *hash, HashLock *lock, const Board *board, const int date, const int depth, const int selectivity, const int cost, const int alpha, const int beta, const int score, const int move)
{
        bool ok = false;
        
        if (hash->board.player == board->player && hash->board.opponent == board->opponent) {
                spin_lock(lock);
                if (hash->board.player == board->player && hash->board.opponent == board->opponent) {
                        data_new(&hash->data, date, depth, selectivity, cost, alpha, beta, score, move);
                        ok = true;
                }
                spin_unlock(lock);
        }
        return ok;
}
 
static bool hash_reset(Hash *hash, HashLock *lock, const Board *board, const int date, const int depth, const int selectivity, const int lower, const int upper, const int move)
{
        bool ok = false;
        HashData *data;
        
        if (hash->board.player == board->player && hash->board.opponent == board->opponent) {
                spin_lock(lock);
                if (hash->board.player == board->player && hash->board.opponent == board->opponent) {
                        data = &hash->data;
                        if (data->selectivity == selectivity && data->depth == depth) {
                                if (data->lower < lower) data->lower = (signed char) lower;
                                if (data->upper > upper) data->upper = (signed char) upper;
                        } else {
                                data->depth = (unsigned char) depth;
                                data->selectivity = (unsigned char) selectivity;
                                data->lower = (signed char) lower;
                                data->upper = (signed char) upper;              
                        }
                        data->cost = 0;
                        data->date = (unsigned char) date;
                        if (move != NOMOVE) {
                                if (data->move[0] != move) {
                                        data->move[1] = data->move[0];
                                        data->move[0] = (unsigned char) move;
                                } else {
                                        data->move[1] = (unsigned char) move;
                                }
                        }
                        ok = true;
                }
                spin_unlock(lock);
        }
        return ok;
}
 
 
void hash_feed(HashTable *hash_table, const Board *board, const unsigned long long hash_code, const int depth, const int selectivity, const int lower, const int upper, const int move)
{
        Hash *hash, *worst;
        HashLock *lock; 
        int i;
        int date = hash_table->date ? hash_table->date : 1;
 
        worst = hash = hash_table->hash + (hash_code & hash_table->hash_mask);
        lock = hash_table->lock + (hash_code & hash_table->lock_mask);
        if (hash_reset(hash, lock, board, date, depth, selectivity, lower, upper, move)) return;
 
        for (i = 1; i < HASH_N_WAY; ++i) {
                ++hash;
                if (hash_reset(hash, lock, board, date, depth, selectivity, lower, upper, move)) return;
                if (writeable_level(&worst->data) > writeable_level(&hash->data)) {
                        worst = hash;
                }
        }
 
        // new entry
#if (HASH_COLLISIONS(1)+0) 
        hash_set(worst, lock, hash_code, board, date, depth, selectivity, 0, lower, upper, move);
#else 
        hash_set(worst, lock, board, date, depth, selectivity, 0, lower, upper, move);
#endif
}
 
void hash_store(HashTable *hash_table, const Board *board, const unsigned long long hash_code, const int depth, const int selectivity, const int cost, const int alpha, const int beta, const int score, const int move)
{
        register int i;
        Hash *worst, *hash;
        HashLock *lock;
 
        worst = hash = hash_table->hash + (hash_code & hash_table->hash_mask);
        lock = hash_table->lock + (hash_code & hash_table->lock_mask);
        if (hash_update(hash, lock, board, hash_table->date, depth, selectivity, cost, alpha, beta, score, move)) return;
 
        for (i = 1; i < HASH_N_WAY; ++i) {
                ++hash;
                if (hash_update(hash, lock, board, hash_table->date, depth, selectivity, cost, alpha, beta, score, move)) return;
                if (writeable_level(&worst->data) > writeable_level(&hash->data)) {
                        worst = hash;
                }
        }
#if (HASH_COLLISIONS(1)+0) 
        hash_new(worst, lock, hash_code, board, hash_table->date, depth, selectivity, cost, alpha, beta, score, move);
#else 
        hash_new(worst, lock, board, hash_table->date, depth, selectivity, cost, alpha, beta, score, move);
#endif
}
 
void hash_force(HashTable *hash_table, const Board *board, const unsigned long long hash_code, const int depth, const int selectivity, const int cost, const int alpha, const int beta, const int score, const int move)
{
        register int i;
        Hash *worst, *hash;
        HashLock *lock;
        
        worst = hash = hash_table->hash + (hash_code & hash_table->hash_mask);
        lock = hash_table->lock + (hash_code & hash_table->lock_mask);
        if (hash_replace(hash, lock, board, hash_table->date, depth, selectivity, cost, alpha, beta, score, move)) return;
        
        for (i = 1; i < HASH_N_WAY; ++i) {
                ++hash;
                if (hash_replace(hash, lock, board, hash_table->date, depth, selectivity, cost, alpha, beta, score, move)) return;
                if (writeable_level(&worst->data) > writeable_level(&hash->data)) {
                        worst = hash;
                }
        }
        
#if (HASH_COLLISIONS(1)+0) 
        hash_new(worst, lock, hash_code, board, hash_table->date, depth, selectivity, cost, alpha, beta, score, move);
#else 
        hash_new(worst, lock, board, hash_table->date, depth, selectivity, cost, alpha, beta, score, move);
#endif
}
 
bool hash_get(HashTable *hash_table, const Board *board, const unsigned long long hash_code, HashData *data)
{
        register int i;
        Hash *hash;
        HashLock *lock;
        bool ok = false;
 
        HASH_STATS(++statistics.n_hash_search;)
        HASH_COLLISIONS(++statistics.n_hash_n;)
        hash = hash_table->hash + (hash_code & hash_table->hash_mask);
        lock = hash_table->lock + (hash_code & hash_table->lock_mask);
        for (i = 0; i < HASH_N_WAY; ++i) {
                HASH_COLLISIONS(if (hash->key == hash_code) {)
                HASH_COLLISIONS(        spin_lock(lock);)
                HASH_COLLISIONS(        if (hash->key == hash_code && (hash->board.player != board->player || hash->board.opponent != board->opponent)) {)
                HASH_COLLISIONS(                ++statistics.n_hash_collision;)
                HASH_COLLISIONS(                printf("key = %llu\n", hash_code);)
                HASH_COLLISIONS(                board_print(board, WHITE, stdout);)
                HASH_COLLISIONS(                board_print(&hash->board, WHITE, stdout);)
                HASH_COLLISIONS(        })
                HASH_COLLISIONS(        spin_unlock(lock);)
                HASH_COLLISIONS(})
                if (hash->board.player == board->player && hash->board.opponent == board->opponent) {
                        spin_lock(lock);
                        if (hash->board.player == board->player && hash->board.opponent == board->opponent) {
                                *data = hash->data;
                                HASH_STATS(++statistics.n_hash_found;)
                                hash->data.date = hash_table->date;
                                ok = true;
                        }
                        spin_unlock(lock);
                        if (ok) return true;
                }
                ++hash;
        }
        *data = HASH_DATA_INIT;
        return false;
}
 
void hash_exclude_move(HashTable *hash_table, const Board *board, const unsigned long long hash_code, const int move)
{
        register int i;
        Hash *hash;
        HashLock *lock;
 
        hash = hash_table->hash + (hash_code & hash_table->hash_mask);
        lock = hash_table->lock + (hash_code & hash_table->lock_mask);
        for (i = 0; i < HASH_N_WAY; ++i) {
                if (hash->board.player == board->player && hash->board.opponent == board->opponent) {
                        spin_lock(lock);
                        if (hash->board.player == board->player && hash->board.opponent == board->opponent) {
                                if (hash->data.move[0] == move) {
                                        hash->data.move[0] = hash->data.move[1];
                                        hash->data.move[1] = NOMOVE;
                                } else if (hash->data.move[1] == move) {
                                        hash->data.move[1] = NOMOVE;
                                }
                                hash->data.lower = SCORE_MIN;
                        }
                        spin_unlock(lock);
                        return;
                }
                ++hash;
        }
}
 
void hash_copy(const HashTable *src, HashTable *dest)
{
        register unsigned int i;
 
        assert(src->hash_mask == dest->hash_mask);
        info("<hash copy>\n");
        for (i = 0; i <= src->hash_mask + HASH_N_WAY; ++i) {
                dest->hash[i] = src->hash[i];
        }
        dest->date = src->date;
}
 
void hash_print(const HashData *data, FILE *f)
{
        char s_move[4];
        int p_selectivity[] = {72, 87, 95, 98, 99, 100};
 
        fprintf(f, "moves = %s, ", move_to_string(data->move[0], WHITE, s_move));
        fprintf(f, "%s ; ", move_to_string(data->move[1], WHITE, s_move));
        fprintf(f, "score = [%+02d, %+02d] ; ", data->lower, data->upper);
        fprintf(f, "level = %2d:%2d:%2d@%3d%%", data->date, data->cost, data->depth, p_selectivity[data->selectivity]);
}