# Transposition table performance

This topic is 3830 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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?

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by crypto_rsaI 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.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 11
• 15
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
634151
• Total Posts
3015825
×