Hi,
I think I'm still a little confused with transposition table.
When my search function hits state S before it enters the loop of recursive call, it makes TT look up.
When found element is useful it handles three cases: score is upper bound, lower bound or exact value.
When it's exact value, function returns best successor along with its score immediately.
If score is lower bound and score>=beta it acts in the same way as with exact score. But if score is between alpha and beta and score>alpha then alpha is replaced with score, best successor is set to successor of S found in TT element. It also sets type of best successor to EXACT because alpha has been improved. Is that right?
If score is upper bound and score<=alpha it acts in the same way as with exact score. But if score is between alpha and beta and score<beta then beta is replaced with score, best successor is set to successor of S found in TT element. It also sets type of best successor to EXACT. But in this case I'm not sure if it's correct behaviour. Value has EXACT type if it's between alpha and beta but I replaced beta with score so in fact score equals beta. Please help!
[Edited by - BitSet on June 30, 2010 1:14:05 PM]
TT - upper bound dilemma
Quote:
Original post by BitSet
I think I'm still a little confused with transposition table.
That's normal. They are confusing.
Quote:
When my search function hits state S before it enters the loop of recursive call, it makes TT look up.
When found element is useful it handles three cases: score is upper bound, lower bound or exact value.
So far so good, assuming you are checking that the depth stored in the TT is at least as high as the depth we are currently searching to.
Quote:
When it's exact value, function returns best successor along with its score immediately.
Yup. But why do you return the best successor? The alpha-beta function should only return a score. I guess you haven't separated the search at the root into a different function, which I strongly recommend.
Quote:
If score is lower bound and score>=beta it acts in the same way as with exact score. But if score is between alpha and beta and score>0 then alpha is replaced with score, best successor is set to successor of S found in TT element. It also sets type of best successor to EXACT because alpha has been improved. Is that right?
If score is upper bound and score<=alpha it acts in the same way as with exact score. But if score is between alpha and beta and score<beta then beta is replaced with score, best successor is set to successor of S found in TT element. It also sets type of best successor to EXACT. But in this case I'm not sure if it's correct behaviour. Value has EXACT type if it's between alpha and beta but I replaced beta with score so in fact score equals beta. Please help!
You can simplify the logic a bit here.
If the score is a lower bound, you improve alpha with it ( `alpha=max(alpha,score)' ). If the score is an upper bound, you improve beta with it ( `beta=min(beta,score)' ). If after doing this alpha>=beta, return score.
In order to know what type of bound to store in the TT, compare the score you are storing with the values of alpha and beta that were passed to the function (before you made any changes to them). I just save them in original_alpha and original_beta at the beginning of the function.
if (score <= original_alpha) bound_type = UPPER_BOUND; // [EDIT: Fixed typo]else if (score >= original_beta) bound_type = LOWER_BOUND;else bound_type = EXACT_SCORE;
[Edited by - alvaro on June 30, 2010 3:53:58 PM]
Quote:
Original post by alvaro
In order to know what type of bound to store in the TT, compare the score you are storing with the values of alpha and beta that were passed to the function (before you made any changes to them). I just save them in original_alpha and original_beta at the beginning of the function.
Thanks! I was trying to avoid additional if statements by initializing bound type to UPPER. When alpha is improved, bound type switches to EXACT and if beta cut off occurs bound type changes to LOWER - no additional ifs needed. Currently my TT look up changes only values of bounds if needed (doesn't change best successor). Seems to work properly.
There is a typo in Your source code example. In first case there should be UPPER instead of LOWER.
Quote:
Original post by BitSet
Thanks! I was trying to avoid additional if statements by initializing bound type to UPPER. When alpha is improved, bound type switches to EXACT and if beta cut off occurs bound type changes to LOWER - no additional ifs needed. Currently my TT look up changes only values of bounds if needed (doesn't change best successor). Seems to work properly.
Oh, yes. I didn't understand what you were doing after your initial description. But now that I understand it, it seems perfectly reasonable.
Quote:
There is a typo in Your source code example. In first case there should be UPPER instead of LOWER.
Ooops! Fixed.
When I improve beta if (score<beta) beta=score; and I know the successor which evaluation quals score, isn't it sure that this successor will cause beta cutoff later in recursive loop? Because I will search the successor and score==beta will occur. If so why don't return the score immediately if (score<beta) return score; instead of entering loop of recursive calls? Am I right or wrong?
Quote:
Original post by BitSet
When I improve beta if (score<beta) beta=score; and I know the successor which evaluation quals score, isn't it sure that this successor will cause beta cutoff later in recursive loop? Because I will search the successor and score==beta will occur. If so why don't return the score immediately if (score<beta) return score; instead of entering loop of recursive calls? Am I right or wrong?
That's wrong. You know that one of the successors would return beta if you were using the same alpha-beta window that was used in the search that stored the info in the TT. But now you probably have a different window, so the only thing you should use is the bound that the old search proved.
Also, notice that TT introduce search instability, which means that performing the same search twice might give back different results.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
Recommended Tutorials
Advertisement