Spring ‘22 AI Homework 3: solutions
Adversarial Search
As in class, assume low to high lexicographical node evaluation, so b, b1, b1a is the initial path searched etc.
Using the attached example tree with terminal score in range [-30, 30]:
Copyright By PowCoder代写 加微信 powcoder
1. [3 pts.] Assuming the root player is max, using variables as shown in class, write out the minimax solution for this tree; e.g. x1=max(2, -19, 8); b = min(b1, b2, b3); etc
2. [2 pts.] Which branch should the max player take from root?
3. [2 pts.] Which branch should the min player take from root?
4. [3 pts.] Assuming the root player is max, using alpha-beta pruning which nodes will be
pruned. This includes nodes partially visited but then pruned. Just a list, order does not matter.
1. In order visited – slightly different to class (ok if yours looks bfs-y) root = max(b, c, d)
b = min(b1, b2, b3)
b1 = max(2, -19, 8) = 8
b2 = max(11, 15, -8) = 15 b3 = max(13, 3, 14) = 14 # back to
b = min(8, 15, 14) = 8
c = min(c1, c2, c3)
c1 = max(8, 13, -2) = 13 c2 = max(-7, 15, -28) = 15 c3 = max(-10, 27, 10) = 27 # back to
c = min(13, 15, 27) = 13
d = min(d1, d2, d3)
d1 = max(-19, -5, 15) = 15 d2 = max(-22, 20, 23) = 23 d3 = max(-12, 26, -2) = 26 # back to
d = min(15, 23, 26) = 15
root = max(8, 13, 15) = 15
Using the equations from 1, max(root) should choose branch ‘d’ for an expected value of 15 3. First writing the same equations
root = min(b, c, d)
b = max(b1, b2, b3)
b1 = min(2, -19, 8) = -19 b2 = min(11, 15, -8) = -8 b3 = min(13, 3, 14) = 3 # back to
b = max(-19, -8, 3) = 3
c = max(c1, c2, c3)
c1 = min(8, 13, -2) = -2
c2 = min(-7, 15, -28) = -28 c3 = min(-10, 27, 10) = -10 # back to
c = max(-2, -28, -10) = -2
d = max(d1, d2, d3)
d1 = min(-19, -5, 15) = -19 d2 = min(-22, 20, 23) = -22 d3 = min(-12, 26, -2) = -12 # back to
d = max(-19, -22, -12) = -12
root = min(3, -2, -12) = -12
min(root) should choose branch ‘d’ for an expected value of -12 4. (corrected)
b is started and then max(b1) is solved for 8 with no alpha or beta, then: Entering b2 with beta=8 b2a=11 and
b2 is pruned
b continues to solve calling b3 with beta=8
b3a=13 and b3 is pruned
min(b) returns 8 (just as in #1) despite the pruning
c enters with alpha=8
max(c1) solves for 13 (no beta), better than alpha so continue max(c2) enters with beta=13, c2b=15 and c2 is pruned max(c3) enters with beta=13, c3b=27 and c3 is pruned
min(c) returns 13 (just as in #1) despite the pruning
d (min) enters with alpha=13 (improved by c)
max(d1) = 15, better than alpha so continues
max(d2) enters with beta=15, d2b=22 and is pruned
max(d3) enters with beta=15, d3b=26 and is pruned
min(d) returns 15
List of Pruned(all you were asked for): b2, b3, c2, c3, d2, d3 [all beta-pruned] Also acceptable to include children of the above
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com