# How to use transposition tables with MTD(f)

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)

-

## 1 Answer

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.

-
You're definitely correct but I'm not sure you've answered the question. If I evaluate a position with alpha=x and beta=x+1 in what situations can I use the evaluation for differing alpha and beta? – Daniel Jul 25 '10 at 22:26