I am wondering if it is possible for an algorithm using a transposition table (A) to occasionally visit more nodes of the game tree than an algorithm not using it (B) while searching the same subtree. I think it is possible - sometimes the algorithm A gets from the TT an evaluation which is different from the evaluation calculated by algorithm B for the same node (the evaluation in the TT could be a result from a deeper subtree). The search window (alpha, beta) could then be wider than in case of B and the algorithm A therefore must visit more nodes. (see my previous post http://www.gamedev.net/community/forums/topic.asp?topic_id=497535 for details) Any thoughts about this? Did you experience lower performance with TT than without it?

I could definitely see this happening, though I've never experienced it myself, or at least noticed it. I really doubt it would significantly impact performance except in specially contrived circumstances, (though I'm sure that three seconds after I post this Timkin will show how it happens 99% of the time with checkers [wink]). The solution would seem to be to mark in the transition table the expansion depth, and re-expand if the node is reached at a shallower depth later on. Offhand, I think that wouldn't impact performance very much, for the same reason that iterative deepening doesn't.

Quote: Original post by crypto_rsa
I am wondering if it is possible for an algorithm using a transposition table (A) to occasionally visit more nodes of the game tree than an algorithm not using it (B) while searching the same subtree. I think it is possible - sometimes the algorithm A gets from the TT an evaluation which is different from the evaluation calculated by algorithm B for the same node (the evaluation in the TT could be a result from a deeper subtree). The search window (alpha, beta) could then be wider than in case of B and the algorithm A therefore must visit more nodes.

(see my previous post http://www.gamedev.net/community/forums/topic.asp?topic_id=497535 for details)

Any thoughts about this? Did you experience lower performance with TT than without it?

I solved this issue. In my original implementation there was a bug which sometimes allowed the transposition table to return results for the black player even if the stored record was for the white player and vice versa. After fixing it the TT behaves correctly - I get performance gains even when returning results from all depths.