OpenChess

Posted: **Wed Mar 28, 2018 8:34 pm**

Hello fellow programmers,

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;
}

I know I left out somet stuff, like trying the best move if there is one. But, so far, does this look like a "correct" implementation?

And how would I extend it to "try the best move" and so on?

Thanks in advance.

OpenChess

A Complete Explanation of Hash Table Usage

A Complete Explanation of Hash Table Usage