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];
20 unsigned num_lookups[3], num_hits[3], total_chain_length[3];
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;
35 num_lookups[0] = num_hits[0] = total_chain_length[0] = 0;
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);
48 for (i = 0; i < HASH_BUCKETS; ++i)
49 transposition_table[i] = NULL;
51 for (i = 0; i < RHASH_BUCKETS; ++i)
52 repeat_table[i] = NULL;
54 for (i = 0; i < PHASH_BUCKETS; ++i)
55 pawn_eval_table[i] = NULL;
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;
66 unsigned hash_position(const struct position * const p)
69 unsigned hash = (p->white_to_move) ? 0 : 0xbb248d0861beb593ULL;
71 hash ^= 0x4fba418408778d3bULL;
73 hash ^= 0xcb15fc4e648baac4ULL;
75 hash ^= 0xdd6c4ebe58a96ef4ULL;
77 hash ^= 0x9a60651c19fb5c53ULL;
79 // 4 is unused, use that for en passant square
81 hash ^= zobrist_values[4][p->ep_square];
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];
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];
95 // same as hash_position, but pawn and king placement only
96 unsigned long long hash_position_pk(const struct position * const p)
101 hash ^= zobrist_values[PIECE_KING][p->white_pieces[0].square];
102 hash ^= zobrist_values[PIECE_KING + 8][p->black_pieces[0].square];
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];
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];
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)
118 unsigned bucket = phash % HASH_BUCKETS;
119 struct hash_entry *he = transposition_table[bucket];
120 #ifdef PROFILE_HASHES
125 if (he->phash == phash && (he->depth > min_depth || (he->depth == min_depth && he->seldepth >= min_seldepth))) {
127 *ret_from = he->best_from;
129 *ret_to = he->best_to;
130 *ret_score = he->score;
131 #ifdef PROFILE_HASHES
132 record_lookup(0, true, ++chain);
138 #ifdef PROFILE_HASHES
143 #ifdef PROFILE_HASHES
144 record_lookup(0, false, chain);
151 void insert_hash(const struct position * const pos, unsigned long long phash, unsigned depth, unsigned seldepth, unsigned from, unsigned to, int score)
153 unsigned bucket = phash % HASH_BUCKETS;
154 struct hash_entry *he = (struct hash_entry *)malloc(sizeof(struct hash_entry));
158 he->seldepth = seldepth;
160 he->best_from = from;
163 he->next = transposition_table[bucket];
164 transposition_table[bucket] = he;
166 // FIXME: prune the hash table here
170 int lookup_record(unsigned long long phash)
172 unsigned bucket = phash % RHASH_BUCKETS;
173 struct hash_entry *he = repeat_table[bucket];
174 #ifdef PROFILE_HASHES
179 if (he->phash == phash) {
180 #ifdef PROFILE_HASHES
181 record_lookup(1, true, ++chain);
186 #ifdef PROFILE_HASHES
191 #ifdef PROFILE_HASHES
192 record_lookup(1, false, chain);
198 void record_move(const struct position * const pos)
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];
206 if (he->phash == phash) {
207 // record another repeat
214 // not found before, let's insert it
215 he = (struct hash_entry *)malloc(sizeof(struct hash_entry));
218 he->next = repeat_table[bucket];
219 repeat_table[bucket] = he;
222 #ifdef PROFILE_HASHES
224 void record_lookup(unsigned hash_num, bool hit, unsigned chain_length)
226 ++num_lookups[hash_num];
228 ++num_hits[hash_num];
229 total_chain_length[hash_num] += chain_length;
232 void print_profile(unsigned hash_num)
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]);
240 #endif /* defined(PROFILE_HASHES) */