1

Note: I understand how min-max works and I understand alpha beta pruning

Even if you can only answer one of my questions below I would be infinitely appreciative

No matter how much I try look at it and research I just cannot understand tranposition tables, specifically why we cannot always use the exact value for the SAME position.

I am referring to the psuedocode here here

I read that we also cannot store a move for the UPPERBOUND. Why would this be the case? We already explored ALL the children for that node so can't we be guaranteed to know the optimal move? Why would we not be able to store the best move?

On the contrary we can store the best move for the LOWERBOUND? The branch was pruned and we weren't able to get the best possible response so why would this be the case?

Finally, I understand why we can only use a table at a depth closer to the leaf than the root (since we have more accurate information from a deeper search). What I don't get is for a node that is the SAME as the previously computed (same hash) node why we can't return the value that was found? At least in the case of the UPPERBOUND don't we already have the optimal score we will achieve (since we explored all the child nodes)?

Thanks for any help, this has been frustrating me for so long and I cannot seem to find anything that clarifies these for me online

marc_s
  • 732,580
  • 175
  • 1,330
  • 1,459
NightShade
  • 422
  • 5
  • 19
  • Where do you read that "we cannot store a move for the UPPERBOUND"? In your link, every move is stored, regardless of their type. – Vintarel Sep 03 '21 at 09:18
  • 1
    You can read about it in the answer here point (2) https://stackoverflow.com/a/30002765/7058803 It makes sense too, because the scores returned when score < alpha aren't exact scores. They are upperbounds as a result of pruning, meaning while you might think the score is good for you - your opponent might be able to refute it if you reach this move, so the move might not be as good as you previously thought Edit: Also the link only always stores the score, I don't think that version stores the optimal move – NightShade Sep 03 '21 at 10:57
  • OK. This is the first time i see this (i a newbie though). This is interesting. However, i'm not sure that's a loss to store the bestmove so far, even if it's a lower/upper bound, because it's still probably better than the other moves already checked. It does not hurt the move ordering that much, like you say in your answer. – Vintarel Sep 03 '21 at 11:23

1 Answers1

1

After hours of thinking about it and a little more research I was finally able to understand so I will put the answer here for anyone who was confused as I was.

For upperbounds (where we do not improve our alpha value - the best score we can hope to attain) the key observation is that the score returned from EACH of the children is an upper-bound that the opponent can hope to attain. I'll say this a different way. We can be guaranteed the score returned may not be the best score the opponent could respond with (all child nodesare pruned when score <= alpha).

This means

a) We cannot assume this is the best move when returned from an upperbound (it might be the WORST move, the other moves were just pruned and not considered). So we cannot store this move in our transposition table, we would just be hurting any move ordering by using that move.

b)

Similarly, it also means that perhaps the opponent can do BETTER. Consider a situation in chess or any other game where the first variation you already had a very powerful set of moves that could be played which would refute your opponents move (why it was pruned in the first place).

Now imagine yet another path to the same position / node. This path you might not have the same opportunity to get a powerful set of moves, that might be semi-good this time. Now our opponents response actually matters (even though it is the same position). So we are forced to analyse this node again but setting the beta value we had previously attained since we know the opponent will do at worst that well.

So in answering my own question the value returned is NOT the optimal value even though all nodes are explored. The child nodes were pruned, but now analysing them matters.

Similar logic can be applied for LOWER BOUND. But this one is much more trivial to see, in my opinion. If we encounter the same node again but we didn't fully explore it last time, then we should explore it again. Computing this node will tell us if we can actually use it to do even better.

This is a lot of detail but this confused me for a very long time so thought I would leave my answer to hopefully save somebody else the confusion. If there is something that is slightly incorrect here feel free to comment it although I am fairly confident. Also feel free to ask me any questions and I will try answer as best I can.

NightShade
  • 422
  • 5
  • 19