# CS代考程序代写 Intuition (using inequalities):

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