1
$\begingroup$

Picture

So I know that 'h' and 'f' will be pruned, but I'm not sure about 'k' and 'l'.

When we visit 'j', technically there is no need for us to visit 'k' and 'l' because there are 2 options:

  1. one or two of them might be higher than 8 ('j')
  2. both of them less than 8

But no matter what, the decision of the max(root) will not change, the max will choose the right side no matter what 'k' and 'l' are, because the right side will either be 8 or 9, which is still higher than 4 (returned value from left side)

so will alpha beta prune 'k' and 'l' or not? if not, then it means alpha beta is not "optimal" overall right? considering it will not prune all the unnecessary paths.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

If you prune k and L then you could miss the optimal solution. Assume L=9, if you prune L then the value of the tree is 8. If you don't prune L then the value of the tree is 9. Now I will try and address what I think your actual question is

But no matter what, the decision of the max(root) will not change, the max will choose the right side no matter what 'k' and 'l' are, because the right side will either be 8 or 9, which is still higher than 4 (returned value from left side).

From this sentence it seems like you don't care about the value of the tree, you only want to find the optimal first move based on alpha beta. You are correct in saying that the correct first move will always contain the right most child of the root, but oftentimes that is not the only information we want. Sometimes we want to know the value of the tree as well or what the complete correct path is, but if we had pruned k and L we would not know these.

Edit: I have changed all 'L's to uppercase, because lower case 'L' looks to much like uppercase 'i'

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the answer, also i think one of my mistakes was i assumed that alpha beta knows that we are in the right most subtree, but the default implementation of alpha beta does not know whether we are in the last tree or not correct? because if we are not in the right most tree, the value of that sub tree is important because we might need to compare it with other trees so in this case we need to check L and K because we might need to compare that value with some other sub tree which we have not checked yet, am i correct? $\endgroup$
    – John Pence
    Apr 21, 2018 at 7:30
  • $\begingroup$ You are correct in both cases. $\endgroup$
    – Andrew Butler
    Apr 21, 2018 at 16:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .