git.sesse.net Git - stupid/blob - hash.c

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include <time.h>
   4 #include <sys/time.h>
   5 #include <ctype.h>
   6 #include <math.h>
   7 #include <stdlib.h>
   8 #include <unistd.h>
   9 #include <stdbool.h>
  10 #include <assert.h>
  11
  12 #include "hash.h"
  13
  14 unsigned hash_used;
  15 struct hash_entry *transposition_table[HASH_BUCKETS], *repeat_table[RHASH_BUCKETS];
  16 struct hash_pawn_entry *pawn_eval_table[PHASH_BUCKETS];
  17 unsigned long long zobrist_values[16][NUM_SQUARES];
  18
  19 #ifdef PROFILE_HASHES
  20 unsigned num_lookups[3], num_hits[3], total_chain_length[3];
  21 #endif
  22
  23 void clear_hash(void)
  24 {
  25         unsigned i;
  26         for (i = 0; i < HASH_BUCKETS; ++i) {
  27                 while (transposition_table[i] != NULL) {
  28                         struct hash_entry *he = transposition_table[i];
  29                         transposition_table[i] = he->next;
  30                         free(he);
  31                 }
  32         }
  33
  34 #ifdef PROFILE_HASHES
  35         num_lookups[0] = num_hits[0] = total_chain_length[0] = 0;
  36 #endif
  37
  38         hash_used = 0;
  39 }
  40
  41 void init_hash(void)
  42 {
  43         unsigned i, j;
  44         for (i = 0; i < 16; ++i)
  45                 for (j = 0; j < NUM_SQUARES; ++j)
  46                         zobrist_values[i][j] = (unsigned long long)rand() ^ ((unsigned long long)(rand()) << 15L) ^ ((unsigned long long)(rand()) << 32L);
  47
  48         for (i = 0; i < HASH_BUCKETS; ++i)
  49                 transposition_table[i] = NULL;
  50
  51         for (i = 0; i < RHASH_BUCKETS; ++i)
  52                 repeat_table[i] = NULL;
  53
  54         for (i = 0; i < PHASH_BUCKETS; ++i)
  55                 pawn_eval_table[i] = NULL;
  56
  57 #ifdef PROFILE_HASHES
  58         num_lookups[0] = num_hits[0] = total_chain_length[0] = 0;
  59         num_lookups[1] = num_hits[1] = total_chain_length[1] = 0;
  60         num_lookups[2] = num_hits[2] = total_chain_length[2] = 0;
  61 #endif
  62
  63         hash_used = 0;
  64 }
  65
  66 unsigned hash_position(const struct position * const p)
  67 {
  68         unsigned i;
  69         unsigned hash = (p->white_to_move) ? 0 : 0xbb248d0861beb593ULL;
  70         if (p->wc_short)
  71                 hash ^= 0x4fba418408778d3bULL;
  72         if (p->wc_long)
  73                 hash ^= 0xcb15fc4e648baac4ULL;
  74         if (p->bc_short)
  75                 hash ^= 0xdd6c4ebe58a96ef4ULL;
  76         if (p->bc_long)
  77                 hash ^= 0x9a60651c19fb5c53ULL;
  78
  79         // 4 is unused, use that for en passant square
  80         if (p->ep_square)
  81                 hash ^= zobrist_values[4][p->ep_square];
  82
  83         for (i = 0; i < 16; ++i) {
  84                 if (p->white_pieces[i].type != PIECE_EMPTY)
  85                         hash ^= zobrist_values[p->white_pieces[i].type][p->white_pieces[i].square];
  86         }
  87         for (i = 0; i < 16; ++i) {
  88                 if (p->black_pieces[i].type != PIECE_EMPTY)
  89                         hash ^= zobrist_values[p->black_pieces[i].type + 8][p->black_pieces[i].square];
  90         }
  91
  92         return hash;
  93 }
  94
  95 // same as hash_position, but pawn and king placement only
  96 unsigned long long hash_position_pk(const struct position * const p)
  97 {
  98         unsigned i;
  99         unsigned hash = 0;
 100
 101         hash ^= zobrist_values[PIECE_KING][p->white_pieces[0].square];
 102         hash ^= zobrist_values[PIECE_KING + 8][p->black_pieces[0].square];
 103
 104         for (i = 8; i < 16; ++i) {
 105                 if (p->white_pieces[i].type == PIECE_PAWN)
 106                         hash ^= zobrist_values[PIECE_PAWN][p->white_pieces[i].square];
 107         }
 108         for (i = 8; i < 16; ++i) {
 109                 if (p->black_pieces[i].type == PIECE_PAWN)
 110                         hash ^= zobrist_values[PIECE_PAWN + 8][p->black_pieces[i].square];
 111         }
 112
 113         return hash;
 114 }
 115
 116 bool lookup_hash(const struct position * const pos, unsigned long long phash, unsigned min_depth, unsigned min_seldepth, unsigned *ret_from, unsigned *ret_to, int *ret_score)
 117 {
 118         unsigned bucket = phash % HASH_BUCKETS;
 119         struct hash_entry *he = transposition_table[bucket];
 120 #ifdef PROFILE_HASHES
 121         unsigned chain = 0;
 122 #endif
 123
 124         while (he != NULL) {
 125                 if (he->phash == phash && (he->depth > min_depth || (he->depth == min_depth && he->seldepth >= min_seldepth))) {
 126                         if (ret_from)
 127                                 *ret_from = he->best_from;
 128                         if (ret_to)
 129                                 *ret_to = he->best_to;
 130                         *ret_score = he->score;
 131 #ifdef PROFILE_HASHES
 132                         record_lookup(0, true, ++chain);
 133 #endif
 134                         return true;
 135                 }
 136
 137                 he = he->next;
 138 #ifdef PROFILE_HASHES
 139                 ++chain;
 140 #endif
 141         }
 142
 143 #ifdef PROFILE_HASHES
 144         record_lookup(0, false, chain);
 145 #endif
 146
 147         // not found, sorry
 148         return false;
 149 }
 150
 151 void insert_hash(const struct position * const pos, unsigned long long phash, unsigned depth, unsigned seldepth, unsigned from, unsigned to, int score)
 152 {
 153         unsigned bucket = phash % HASH_BUCKETS;
 154         struct hash_entry *he = (struct hash_entry *)malloc(sizeof(struct hash_entry));
 155
 156         he->phash = phash;
 157         he->depth = depth;
 158         he->seldepth = seldepth;
 159         he->score = score;
 160         he->best_from = from;
 161         he->best_to = to;
 162
 163         he->next = transposition_table[bucket];
 164         transposition_table[bucket] = he;
 165
 166         // FIXME: prune the hash table here
 167         ++hash_used;
 168 }
 169
 170 int lookup_record(unsigned long long phash)
 171 {
 172         unsigned bucket = phash % RHASH_BUCKETS;
 173         struct hash_entry *he = repeat_table[bucket];
 174 #ifdef PROFILE_HASHES
 175         unsigned chain = 0;
 176 #endif
 177
 178         while (he != NULL) {
 179                 if (he->phash == phash) {
 180 #ifdef PROFILE_HASHES
 181                         record_lookup(1, true, ++chain);
 182 #endif
 183                         return he->score;
 184                 }
 185                 he = he->next;
 186 #ifdef PROFILE_HASHES
 187                 ++chain;
 188 #endif
 189         }
 190
 191 #ifdef PROFILE_HASHES
 192         record_lookup(1, false, chain);
 193 #endif
 194
 195         return 0;
 196 }
 197
 198 void record_move(const struct position * const pos)
 199 {
 200         // see if this has happened before
 201         unsigned long long phash = hash_position(pos);
 202         unsigned bucket = phash % RHASH_BUCKETS;
 203         struct hash_entry *he = repeat_table[bucket];
 204
 205         while (he != NULL) {
 206                 if (he->phash == phash) {
 207                         // record another repeat
 208                         ++he->score;
 209                         return;
 210                 }
 211                 he = he->next;
 212         }
 213
 214         // not found before, let's insert it
 215         he = (struct hash_entry *)malloc(sizeof(struct hash_entry));
 216         he->phash = phash;
 217         he->score = 1;
 218         he->next = repeat_table[bucket];
 219         repeat_table[bucket] = he;
 220 }
 221
 222 #ifdef PROFILE_HASHES
 223
 224 void record_lookup(unsigned hash_num, bool hit, unsigned chain_length)
 225 {
 226         ++num_lookups[hash_num];
 227         if (hit)
 228                 ++num_hits[hash_num];
 229         total_chain_length[hash_num] += chain_length;
 230 }
 231
 232 void print_profile(unsigned hash_num)
 233 {
 234         printf("Profiling hash %u:\n", hash_num);
 235         printf("  Total lookups = %u\n", num_lookups[hash_num]);
 236         printf("  Hit rate      = %.3f\n", (double)num_hits[hash_num] / (double)num_lookups[hash_num]);
 237         printf("  Avg chain     = %.2f\n\n", (double)total_chain_length[hash_num] / (double)num_lookups[hash_num]);
 238 }
 239
 240 #endif /* defined(PROFILE_HASHES) */