Intuition (using inequalities):
(a) backed up values: Remember that root node is max (see text of the question). So value(A) is max(value(B), value(C), value(D)), and so on. We get:
E=3, F=8, G=7, H=1, I=5, J=8, K=10, then
B=3, C=1, D=8, and finally
A=8
(b) the backed-up values are the same, except that some will not be computed (they will be pruned). Here, E is computed, with E=3. Then, moving to F, we evaluate N=8 and then realize F >= 8, so it will not be selected by Min at B, who will instead select E=3. Hence we do not need to evaluate O (O is pruned). Likewise with G: we evaluate P=7 and realize that G >= 7 will not be selected by Min at B, since E=3 will be instead. Hence Q is pruned. Then we also compute H=1. This tells us C <= 1 since C is a min node. Because B=3, A >= 3 since A is a max node. Since C <= 1, it will not be chosen since we can make 3 by choosing B; hence, we do not need to compute I (so you would cross out I in your answer, and also possibly T and U if you want). We then compute J=8 and thus we know D <= 8. This is potentially still better than 3, so we do need to look at K. We evaluate X=10 hence K >= 10, so we can safely prune Y since Min at D will not select K >= 10 given that we also know that J=8. We end up with D=8, and finally A=8.
So, nodes O, Q, I (and children T, U), and Y were pruned in this example.
(c) At the root, max will choose the move that goes to state D since this guarantees 8 (or more if the opponent does not deploy perfect play), which is higher than if we chose B (worth 3) or C (worth 1 or less).
Full alpha-beta run:
Below we do a detailed run of alpha-beta on this example.
Call AlphaBetaSearch(A)
Starts with a = -£¤ and b = +£¤
MaxValue(A, a = -£¤, b = +£¤) v = -£¤
Loop over B, C, D:
Start with B:
MinValue(B, a = -£¤, b = +£¤)
v = +£¤
Loop over E, F, G:
Note: v is a local variable (not same here as the other v above)
Start with E:
MaxValue(E, a = -£¤, b = +£¤)
v = -£¤
Loop over L, M:
Start with L:
MinValue(L, a = -£¤, b = +£¤)
L is terminal; return 2 Done with L.
v=max(v=-£¤,2fromL)=2 Valuesofaris2
v ¡Ý b fails No pruning
a = max(a=-£¤, v) = 2 Update a=2 best so far
Start with M:
MinValue(M, a = 2, b = +£¤)
M is terminal; return 3 Done with M.
v=max(v=2,3fromM)=3 Valuesofaris3
v ¡Ý b fails
a = max(a=2, v) = 3
Done with loop over L, M.
return v = 3 Done with E.
v = min(v=+£¤, 3 from E) = 3 v ¡ê a fails
b = min(b=+£¤, v) = 3
No pruning
Update a=3 best so far
Start with F:
MaxValue(F, a = -£¤, b = 3)
v = -£¤
Loop over N, O:
Start with N:
MinValue(N, a = -£¤, b = 3)
N is terminal; return 8 Done with N.
v=max(v=-£¤,8fromN)=8 Valuesofaris8
v ¡Ý b passes!
Done with loop over N, O.
return v = 8 Done with F.
v = min(v=3, 8 from F) = 3 v ¡ê a fails
b = min(b=3, v) = 3
Start with G:
MaxValue(G, a = -£¤, b = 3)
v = -£¤
Loop over P, Q:
End loop, prune O
Start with P:
MinValue(P, a = -£¤, b = 3)
P is terminal; return 7 Done with P.
v=max(v=-£¤,7fromP)=7 Valuesofaris7
v ¡Ý b passes!
Done with loop over P, Q.
return v = 7 Done with G.
v = min(v=3, 7 from G) = 3 v ¡ê a fails
b = min(b=3, v) = 3
Done with loop over E, F, G.
return v = 3 Done with B.
End loop, prune Q
v=max(v=-£¤,3fromB)=3 Valuesofaris3
v ¡Ý b fails
a = max(a=-£¤, v) = 3
Start with C:
MinValue(C, a = 3, b = +£¤)
v = +£¤
Loop over H, I:
No pruning
Update a=3 best so far
Start with H:
MaxValue(H, a = 3, b = +£¤)
v = -£¤
Loop over R, S:
Start with R:
MinValue(R, a = 3, b = +£¤)
R is terminal; return 0 Done with R.
v=max(v=-£¤,0fromR)=0 v ¡Ý b fails
a = max(a=3, v) = 3
Valuesofaris0 No pruning
a=3 still best so far
Start with S:
MinValue(S, a = 3, b = +£¤)
S is terminal; return 1 Done with S.
v=max(v=0,1fromS)=1 v ¡Ý b fails
a = max(a=3, v) = 3
Done with loop over R, S.
return v = 1 Done with H.
v = min(v=+£¤, 1 from H) = 1 v ¡ê a passes!
Done with loop over H, I. return v = 1
Done with C.
v = max(v=3, 1 from C) = 3 v ¡Ý b fails
a = max(a=3, v) = 3
Value so far is 1 No pruning
a=3 still best so far
End loop, prune I (and T, U)
Value so far is still 3 No pruning
a=3 still best so far
Start with D:
MinValue(D, a = 3, b = +£¤)
v = +£¤
Loop over J, K:
Start with J:
MaxValue(J, a = 3, b = +£¤)
v = -£¤
Loop over V, W:
Start with V:
MinValue(V, a = 3, b = +£¤)
V is terminal; return 8 Done with V.
v=max(v=-£¤,8fromV)=8 Valuesofaris8
v ¡Ý b fails No pruning
a = max(a=3, v) = 8 Update a=8 best so far
Start with W:
MinValue(W, a = 8, b = +£¤)
W is terminal; return 4 Done with W.
v=max(v=8,4fromW)=8 Valuesofaris8
v ¡Ý b fails
a = max(a=8, v) = 8
Done with loop over V, W.
return v = 8 Done with J.
v = min(v=+£¤, 8 from J) = 8 v ¡ê a fails
b = min(b=+£¤, v) = 8
No pruning
a=8 still best so far
Start with K: MaxValue(F, a = 3, b = 8)
v = -£¤
Loop over X, Y:
Start with X:
MinValue(X, a = 3, b = 8)
X is terminal; return 10 Done with N.
v = max(v=-£¤, 10 from N) = 10 v ¡Ý b passes!
Done with loop over X, Y.
return v = 10 Done with K.
v = min(v=8, 10 from K) = 8 v ¡ê a fails
b = min(b=8, v) = 8
Done with loop over J, K.
return v = 8 Done with D.
v = max(v=3, 8 from D) = 8 v ¡Ý b fails
a = max(a=3, v) = 8
Done with loop over B, C, D return v = 8
Value so far is 10
End loop, prune Y
v=8 (max value over B, C, D)
return an action with value 8 (i.e., select D)
Value so far is 8
No pruning
Update a=8 best so far