When does alpha-beta search with memory return cutoff values?

Question

I have implemented an alpha beta search with transposition table.

Do I have the right ideas here about storing cutoffs in the table?

Specifically, is my scheme for returning the cutoffs when a table hit occurs correct? (And likewise, storing them.) My implementation seems to conflict with this one, yet it intuitively seems correct to me.

Also, my algorithm never stores an entry with the at_most flag. When should I be storing these entries?

Here is my (simplified) code demonstrating the main ideas:

int ab(board *b, int alpha, int beta, int ply) {
    evaluation *stored = tt_get(b);
    if (entryExists(stored) && stored->depth >= ply) {
        if (stored->type == at_least) { // lower-bound
            if (stored->score >= beta) return beta;
        } else if (stored->type == at_most) { // upper bound
            if (stored->score <= alpha) return alpha;
        } else { // exact
            if (stored->score >= beta) return beta; // respect fail-hard cutoff
            if (stored->score < alpha) return alpha; // alpha cutoff
            return stored->score;
        }
    }   

    if (ply == 0) return quiesce(b, alpha, beta, ply);

    int num_children = 0;
    move chosen_move = no_move;
    move *moves = board_moves(b, &num_children);

    int localbest = NEG_INFINITY;
    for (int i = 0; i < num_children; i++) {
        apply(b, moves[i]);
        int score = -ab(b, -beta, -alpha, ply - 1);
        unapply(b, moves[i]);
        if (score >= beta) {
            tt_put(b, (evaluation){moves[i], score, at_least, ply});
            return beta; // fail-hard
        }
        if (score >= localbest) {
            localbest = score;
            chosen_move = moves[i];
            if (score > alpha) alpha = score;
        }
    }
    tt_put(b, (evaluation){chosen_move, alpha, exact, ply});
    return alpha;
}

Answer 1

My implementation seems to conflict with this one

The code for transposition table look up seems right to me. It's roughly equivalent to that on wikipedia.

// Code on Wikipedia rewritten using your notation / variable names
if (entryExists(stored) && stored->depth >= ply)
{
  if (stored->type == at_least)
    alpha = max(alpha, stored->score);
  else if (stored->type == at_most)
    beta = min(beta, stored->score);
  else if (stored->type == exact)
    return stored->score;

  if (alpha >= beta)
    return stored->score;
}

That is equivalent to (the check if (alpha >= beta) has been moved inside each node type):

if (entryExists(stored) && stored->depth >= ply)
{
  if (stored->type == at_least)
  {
    alpha = max(alpha, stored->score);
    if (alpha >= beta)  return stored->score;
  }
  else if (stored->type == at_most)
  {
    beta = min(beta, stored->score);
    if (alpha >= beta)  return stored->score;
  }
  else if (stored->type == exact)
    return stored->score;
}

and this can be changed in:

if (entryExists(stored) && stored->depth >= ply)
{
  if (stored->type == at_least)
  {
    // if (max(alpha, stored->score) >= beta) ...
    if (stored->score >= beta)  return stored->score;
  }
  else if (stored->type == at_most)
  {
    // if (min(beta, stored->score) <= alpha) ...
    if (stored->score <= alpha)  return stored->score;
  }
  else if (stored->type == exact)
    return stored->score;
}

The remaining difference is that Wikipedia uses a fail-soft optimization, while your code is the classic alpha-beta pruning (fail-hard). Fail-soft is a small improvement but doesn't change the key points of the algorithms.

---

my algorithm never stores an entry with the at_most flag. When should I be storing these entries?

There is a bug in how you store the exact / at_most node type. Here you're assuming that the node is always of type exact:

tt_put(b, (evaluation){chosen_move, alpha, exact, ply});

actually it can be an at_most node:

if (alpha <= initial_alpha)
{
  // Here we haven't a best move.
  tt_put(b, (evaluation){no_move, initial_alpha, at_most, ply});
}
else
   tt_put(b, (evaluation){chosen_move, alpha, exact, ply});