I have hunted around for the quintessential description of how to best implement hash tables, and, as you can imagine, the number of different implementations is about as numerous as the stars in the sky. I think it would be great if those who already have flawless implementations to share their expertise in the matter. My goal is to have a complete understanding of "all things hash table related," and hopefully leave behind this topic that can be revisited by future-seekers-of-information.
My understanding thus far is that the hash table should contain:
1. The hash key to identify the position
2. The score of the position the last time it was searched.
3. A "type of bound" entry denoting if the comparison of the score to alpha and beta. (This is where I get confused. Is it <= alpha, < alpha, <= beta, < beta, >= alpha, > alpha, >= beta, > beta, and is the "exact" score > alpha and < beta?)
4. A "best move" for the position (if one was determined) otherwise an entry to indicate there is no best move to try later on.
5. The depth to which the position was searched.
6. An "aging" implementation of some kind. I will just store a counter indicating how many times the entry was reused. If it is still zero when the hash table is full, it gets replaced.
I have seen implementations dealing with results returned from the root, and from "within" the recursive routine. For now, I would like to focus on what to do "inside" the recursion. It might look something like this:
Code: Select all
int search(YOUR_POSITION the_position, int alpha, int beta, int depth)
{
YOUR_POSITION next_position;
int best_score = -INF;
int i, j, value, best_move;
int history_score_increase;
BOOL king_in_check, at_least_one_move;
unsigned long long hash_code_slot, new_hash_code;
unsigned short hash_table_probe_result, not_deep_enough;
unsigned char type_of_bound;
// if it returns 0, there is no entry. if hash_code_slot is > 0, it is the index of an available slot. new_hash_code is the 64-bit hash number for the position generated by the function just called
hash_table_probe_result = probe_hash_table_during_search(the_position, &hash_code_slot, &new_hash_code);
// a dummy variable used to tell if we actually used the data in the table, or if we should update it, or if it we just ignore it
not_deep_enough = 2;
// we found a hash table entry and we're not just a static leaf node evaluation
if (hash_table_probe_result && (depth > 1))
{
not_deep_enough = 0;
if (GLOBAL_the_hash_table_of_positions[hash_code_slot].depth >= depth)
{
if ((GLOBAL_the_hash_table_of_positions[hash_code_slot].exact_score_upper_bound_or_lower_bound == 1) && (GLOBAL_the_hash_table_of_positions[hash_code_slot].score >= beta))
{
// this is an entry we can use, so we increment the "age" counter to let the program know this should maybe remain in the full table when it is time to be purged
GLOBAL_the_hash_table_of_positions[hash_code_slot].how_many_times_accessed = 1 + GLOBAL_the_hash_table_of_positions[hash_code_slot].how_many_times_accessed;
return beta;
}
if ((GLOBAL_the_hash_table_of_positions[hash_code_slot].exact_score_upper_bound_or_lower_bound == 2) && (GLOBALthe_hash_table_of_positions[hash_code_slot].score < alpha))
{
// this is an entry we can use, so we increment the "age" counter to let the program know this should maybe remain in the full table when it is time to be purged
GLOBAL_the_hash_table_of_positions[hash_code_slot].how_many_times_accessed = 1 + GLOBAL_EVERYTHING.the_hash_table_of_positions[hash_code_slot].how_many_times_accessed;
return alpha;
}
if ((GLOBAL_the_hash_table_of_positions[hash_code_slot].exact_score_upper_bound_or_lower_bound == 3) && (GLOBAL_the_hash_table_of_positions[hash_code_slot].score > alpha) && (GLOBAL_the_hash_table_of_positions[hash_code_slot].score < beta))
{
// this is an EXACT value that can be used, I think, am I using the correct inequality signs above or can it be >= and <= ? please advise
GLOBAL_the_hash_table_of_positions[hash_code_slot].how_many_times_accessed = 1 + GLOBAL_the_hash_table_of_positions[hash_code_slot].how_many_times_accessed;
return GLOBAL_EVERYTHING.the_hash_table_of_positions[hash_code_slot].score;
}
}
else
not_deep_enough = 1;
}
if (depth == 0)
{
best_score = quiesce(alpha, beta);
return best_score;
}
// code for not having a best move yet
best_move = NONE;
type_of_bound = 2;
for (i = 1; i < total_legal_moves; i++)
{
// everybody has their own way of doing this next line of code
next_position = generate_move(i);
at_least_one_move = TRUE;
value = -search(next_position, -beta, -alpha, depth - 1);
if (value > alpha)
{
best_move = i;
if (value > best_score) best_score = value;
// if implementing the history heuristic, you would do this here
history_score_increase = something;
history[from][to] += history_score_increase;
if (value >= beta)
{
best_score = beta;
type_of_bound = 1;
// we have a slot for a position that was not searched deep enough previously, but we can update it now with the deeper search results
if (not_deep_enough == 1)
{
put_hash_data_into_slot(hash_code_slot, new_hash_code, depth, best_move, type_of_bound, best_score);
}
// do we have an empty slot that is waiting for a first time entry? just stuff it in there
if ((hash_code_slot > 0) && (not_deep_enough == 2))
{
put_hash_data_into_slot(hash_code_slot, new_hash_code, depth, best_move, type_of_bound, best_score);
}
return best_score;
}
// do I need an "else" here or is this good stand alone?
{
alpha = value;
type_of_bound = 3;
}
}
}
// test for stalemate, checkmate, draw by repetition, draw by 50-move rule, etc, I am skipping over this here
best_score = alpha;
// we searched deeper than the current hash table entry was, so update it
if (not_deep_enough == 1)
{
put_hash_data_into_slot(hash_code_slot, new_hash_code, depth, best_move, type_of_bound, best_score);
GLOBAL_the_hash_table_of_positions[hash_code_slot].how_many_times_accessed = 1 + GLOBAL_the_hash_table_of_positions[hash_code_slot].how_many_times_accessed;
}
// we found an empty slot but it was a leaf node which is never searched deep enough to care. now we do care since it was searched deeper
if ((hash_code_slot > 0) && (not_deep_enough == 2))
{
put_hash_data_into_slot(hash_code_slot, new_hash_code, depth, best_move, type_of_bound, best_score);
}
return best_score;
}
And how would I extend it to "try the best move" and so on?
Thanks in advance.