Sign in to follow this  
crypto_rsa

Transposition table performance

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this