4

Can someone explain to me why it is possible to eliminate the rest of the middle branch in this image for alpha-beta pruning? I am confused because it seems the only information you know is that Helen would pick at least a 2 at the top (considering if we iterate from left to right in DFS), and Stavros would absolutely not pick anything above 7. This leaves 5 possible numbers that the rest of the branch could take on that Helen could potentially end up picking, but can't because we've eliminated those possibilities via pruning.

enter image description here

nbro
  • 42,615
  • 12
  • 119
  • 217
Victor
  • 41
  • 2

1 Answers1

1

You can't prune the nodes that are cross out if we search from left-to-right in the tree using alpha-beta pruning. To do this analysis we can pretend the right branch of the tree doesn't exist. (Branch C from the root.)

In the left branch (A) of the root Helen will get 2 or more.

In the middle branch (B) from the root after going down the left, Stavros will get 7 or less.

Now, we can ask what happens if we put different values for the crossed out branches. If putting different values doesn't change the value at the root, then pruning is correct.

Suppose that after the 7 on branch A at the second level we make the value of branch B to be -10. In this case the value of the second branch will be -10, and Helen will prefer the first branch at the root.

Suppose that after the 7 on branch A at the second level we make the value of branch B to be 100. In this case the value of the second branch will be 7, and Helen will prefer this branch.

Thus, the value of the crossed off nodes matters, and they cannot be pruned.

You may find this tool useful for exploring alpha-beta on binary trees:

https://movingai.com/ab/

Nathan S.
  • 371
  • 2
  • 9