Let α = -∞ and β = +∞. At MAX, we will use α and at MIN, we will use β.
-
The initial call starts from A. The value of α = -∞ and β = +∞. These values are passed down to subsequent nodes in the tree. At A the maximizer must choose MAX of B and C, so A calls B first.
-
At B it the minimizer must choose min of D and E and hence calls D first.
-
At D, it looks at its left child which is a leaf node. This node returns a value of 3. Now at D the value of alpha is α = MAX(-∞, 3) = 3.
-
To decide whether it's worth looking at its right node or not, it checks the condition β<=α. This is false since β = +∞ and α = 3. So it continues the search.
-
D now looks at its right child which returns a value of 5.At D, α = MAX(3, 5) which is 5. Now the value of node D is 5
-
D returns a value of 5 to B. At B, β = MIN( +∞, 5) which is 5. The minimizer is now guaranteed a value of 5 or lesser. B now calls E to see if he can get a lower value than 5.
-
At E the values of alpha and beta is not -∞ and +∞ but instead -∞ and 5 respectively, because the value of β was changed at B and that is what B passed down to E.
-
Now E looks at its left child which is 6. At E,α = MAX(-∞, 6) which is 6. Here the condition becomes true. beta is 5 and alpha is 6. So β<=α is true. Hence it breaks and E returns 6 to B.
-
Note how it did not matter what the value of E‘s right child is. It could have been +∞ or -∞ , it still wouldn’t matter, we never even had to look at it because the minimizer was guaranteed a value of 5 or lesser. So as soon as the maximizer saw the 6 he knew the minimizer would never come this way because he can get a 5 on the left side of B. This way we didn’t have to look at that 9 and hence saved computation time.
-
E returns a value of 6 to B. At B, β = MIN( 5, 6) which is 5. The value of node B is also 5.
-
B returns 5 to A. At A, α = MAX(-∞, 5) which is 5. Now the maximizer is guaranteed a value of 5 or greater. A now calls C to see if it can get a higher value than 5.
-
At C, α = 5 and β = +∞. C calls F
-
At F, α = 5 and β = +∞. F looks at its left child which is a 1. α = MAX( 5, 1) which is still 5.
-
F looks at its right child which is a 2. Hence the best value of this node is 2. α still remains 5
-
F returns a value of 2 to C. At C, β = MIN(+∞, 2). The condition β <= α becomes true as β = 2 and α= 5. So, it breaks, and it does not even have to compute the entire sub-tree of G.
-
The intuition behind this break-off is that, at C the minimizer was guaranteed a value of 2 or lesser. But the maximizer was already guaranteed a value of 5 if he chooses B.
-
C now returns a value of 2 to A. Therefore, the best value at A is MAX (5, 2) which is a 5.
Hence the optimal value that the maximizer can get is 5.
