How to use transposition tables with MTD(f)

Question

I'm writing an AI for a card game and after some testing I've discovered that using MTD(f) on my alpha beta algorithm - a series of zero-window searches - is faster than just using alpha-beta by itself.

The MTD(f) algorithm is described well here http://people.csail.mit.edu/plaat/mtdf.html

The problem I have is that for each pass in the MTD(f) search (for each guess) I don't reuse any of the previous positions I have stored even though the write up on the link suggests that I should (in fact clearing the table between iterations speeds up the algorithm).

My problem is that when I store a position and a value in my transposition table I also store the alpha and beta values for which it is valid. Therefore a second pass through the tree with a different guess (and therefore alpha and beta) can't possibly reuse any information. Is this what is to be expected or am I missing something fundamental here?

For instance if for alpha=3 beta=4 we come to a result of 7 (obviously a cut-off) should I store that in the table as valid for alpha=3 to beta=6? Or beta=7?

(Copied from stack overflow in hope of answers)

Answer 1

The reason you're storing things in the transposition table is to fetch the prior-found alpha and beta, to save yourself a new evaluation. If you're a C++ programmer, the board's ID hash is the key, and the alpha/beta are the value.

lookup_board(hash, alpha, beta) -> return (isset(some_global_assoc_array['hash']))? some_global_assoc_array['hash'] : false;

store_board(hash, alpha, beta) -> some_global_assoc_array['hash'] = { alpha, beta };

You should be storing the alpha and beta, yes, but not as part of the identifier - they're the associated data, instead.

Answer 2

When storing values in the transposition table, you have three possibilities:

1. alpha < value < beta: you have an exact value, and can store it: lb = ub = value;
2. value <= alpha: you failed low. value is an upper limit on the true value: ub = value;
3. value >= beta: you failed high. value is a lower limit on the true value: lb = value;

On subsequent visits at the same depth, you can use code along these lines to check the cache: if (entry.lb >= beta) return entry.lb; if (entry.ub <= alpha) return entry.ub; alpha = Math.max(alpha, entry.lb); beta = Math.min(beta, entry.ub);

I have found it best to ignore values from lower search depths, though.