0
$\begingroup$

I'm trying to understand if the node with value 5 would be pruned if doing left-to-right alpha-beta pruning in a minimax game. I can see two interpretations:

  1. Initialize $\alpha = -\infty$ and $\beta = \infty$. When you reach the leaf node of 15, $\alpha$ gets updated to 15. The algorithm stops if $\alpha \geq \beta$, and it is not. So, the node with value 5 is searched.

  2. The leaf node 15 is searched from the perspective of the MAX player (colored blue). Since the parent node of MAX is MIN (colored green), it is trying to minimize the value, there is no need to search the right child of the MAX player. That node would be chosen if it is >15. But MIN already has a 10 available to it, and the 5 node can be pruned.

enter image description here

$\endgroup$

1 Answer 1

0
$\begingroup$

I think your confusion stems from forgetting that minimax and alphabeta is almost exclusively implemented as a depth first search.

As a result, the node valued 5 would not be pruned, simply because we will explore it before ever getting to the node valued 10.

If the tree structure was such that the children of the green node were flipped, then we would encounter the 10 node first. In this case, the 5 node would indeed be pruned.

This illustrates a key aspect of alpha beta pruning, how the order we explore nodes is very important.

If this is confusing, I suggest looking into depth first search and the order of when nodes are explored.

$\endgroup$
2
  • $\begingroup$ Thanks, I just realized this after posting and thinking for 10 more minutes. I understand DFS, and the 10 node would not have been discovered yet. $\endgroup$
    – maxutil
    Dec 9, 2022 at 15:28
  • $\begingroup$ @maxutil no problem. I added some more info as well. If this answers your question please mark it with the green check. $\endgroup$ Dec 9, 2022 at 15:29

You must log in to answer this question.

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