Jump to content
  • Advertisement
Sign in to follow this  
crypto_rsa

Correct usage of transposition table records

This topic is 3154 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

Hi, The question: I have a pretty well performing game algorithm but one thing puzzles me. I use a transposition table and I sort moves in each node using values stored in it. But the entries in the table may represent subtrees of different depths. Is it safe to use them for sorting in the same node? A more specific example: Consider node A with two possible moves, B and C. In the TT I have results for both of them. However, for B I have a result 2 plies deep and for C only 1 ply deep. It means the score stored for B will likely be worse than for C because it's an evaluation of the board after playing a white move (B) AND the best black move resulting from that position. The stored value for C is only the evaluation after playing C. If I sorted the move list using this information, move C would be placed before move B, even if B was "better" (that means, if the evaluation after playing C AND the best black move would be less than the stored value for B). Hope it's clear now :-) One possible solution is to use only TT entries of odd/even depth at each nodes, so that I won't end up comparing apples and oranges. Any suggestions?

Share this post


Link to post
Share on other sites
Advertisement
I suggest you fix your evaluation function so it doesn't oscillate too much between odd and even depths. In some games it makes sense to add some bonus to the side to move, which might help. The value of that bonus is related to the concept of "temperature" in combinatorial game theory.

Anyway, fixing the disparity between odd- and even-depth scores also will allow you to do single-depth extensions or reductions, where some branches are explored deeper than others.

Share this post


Link to post
Share on other sites
Thanks for your reply. I was thinking too about fixing the evaluation function but I was curious what the general practice is. I'll try it.

Share this post


Link to post
Share on other sites
I was thinking about it a bit more and I think adding a bonus to the side which is to move makes sense. The game which I am writing an algorithm for starts with an empty board. Its evaluation could be zero, but the side to move has an advantage, so a bonus should be added. Or maybe a better example: let's say the game is in state S where white is only a move from winning the game. But if black was to move in this state, the advantage for white is not as good. So we have a single state S but with two different "sub-states" depending on the side to move. Sure, it would eventually be discovered by 1-ply search but I think the bonus should be part of the evaluation function.

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!