Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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)

share|improve this question
add comment

1 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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.