2e 2. Adversarial Search (25 points) Consider the following game tree below 6 94
ID: 3734083 • Letter: 2
Question
2e 2. Adversarial Search (25 points) Consider the following game tree below 6 9482 5 39 11 12 5 9 B 1 8 a. Label each node with its minimax value. b. Determine which move would be selected by MAX? c. List the nodes that the alpha-beta algorithm would prune. (Assume the children of a node are d. In general (iLe, not just for the tree shown above), if we traverse a game tree by visiting visited from left-to-right) instead of left-to-right, can this result in a change to. i The minimax value computed at each root? ii The number of nodes pruned by the alpha-beta algorithm?Explanation / Answer
Solution:
The first two subparts have been answered as per Chegg guidelines, please repost others.
I am writing the labeling against the alphabets in the given node
H: 6
I: 2
J: 3
K: 9
L: 5
M: 8
N: 7
O: 1
P: 7
D: 6
E: 9
F: 8
G: 7
B: 6
C: 7
A: 7
b)
7 will be selected by MAX, right move is selected.
Pseudocode for alpha beta pruning:
function alphabeta(node, depth, a, ß, maximizingPlayer)
if depth = 0 or node is a terminal node
return the heuristic value of node
if maximizingPlayer
v := -8
for each child of node
v := max(v, alphabeta(child, depth – 1, a, ß, FALSE))
a := max(a, v)
if ß = a
break (* ß cut-off *)
return v
else
v := +8
for each child of node
v := min(v, alphabeta(child, depth – 1, a, ß, TRUE))
ß := min(ß, v)
if ß = a
break (* a cut-off *)
return v
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.