Jump to content
  • Advertisement
Sign in to follow this  
crypto_rsa

Transposition table performance

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!