CS 188Fall 2019 Exam Prep 3 SolutionsQ1. Games with Magic(a) Standard Minimax(i) Fill in the values of each of the nodes in the following Minimax tree. The upward pointing trapezoidscorrespond to maximizer nodes (layer 1 and 3), and the downward pointing trapezoids correspondto minimizer nodes (layer 2). Each node has two actions available, Left and Right.(ii) Mark the sequence of actions that correspond to Minimax play.(b) Dark MagicPacman (= maximizer) has mastered some dark magic. With his dark magic skills Pacman can takecontrol over his opponent’s muscles while they execute their move — and in doing so be fully in charge ofthe opponent’s move. But the magic comes at a price: every time Pacman uses his magic, he pays a priceof c—which is measured in the same units as the values at the bottom of the tree.Note: For each of his opponent’s actions, Pacman has the choice to either let his opponent act (optimallyaccording to minimax), or to take control over his opponent’s move at a cost of c.(i) Dark Magic at Cost c = 2Consider the same game as before but now Pacman has access to his magic at cost c = 2. Is it optimalfor Pacman to use his dark magic? If so, mark in the tree below where he will use it. Either way,mark what the outcome of the game will be and the sequence of actions that lead to that outcome.1Pacman goes right and uses dark magic to get 7-2=5. Not using dark magic would result in the normalminimax value of 3. Going left and using dark magic would have resulted in 6-2=4. So, in either case usingmagic benefits Pacman, but using it when going right is best.(ii) Dark Magic at Cost c = 5Consider the same game as before but now Pacman has access to his magic at cost c = 5. Is it optimalfor Pacman to use his dark magic? If so, mark in the tree below where he will use it. Either way,mark what the outcome of the game will be and the sequence of actions that lead to that outcome.Pacman doesn’t use dark magic. Going left and using dark magic would result in 6-5=1, and going right andusing dark magic would result in 7-5=2, while not using dark magic results in 3.(iii) Dark Magic Minimax AlgorithmNow let’s study the general case. Assume that the minimizer player has no idea that Pacman hasthe ability to use dark magic at a cost of c. I.e., the minimizer chooses their actions according tostandard minimax. You get to write the pseudo-code that Pacman uses to compute their strategy.As a starting point / reminder we give you below the pseudo-code for a standard minimax agent.Modify the pseudo-code such that it returns the optimal value for Pacman. Your pseudo-code shouldbe sufficiently general that it works for arbitrary depth games.2function Max-Value(state)if state is leaf thenreturn Utility(state)end ifv ← −∞for successor in Successors(state)dov ←max(v, Min-Value(successor ))end forreturn vend functionfunction Min-Value(state)if state is leaf thenreturn Utility(state)end ifv ← ∞for successor in Successors(state)dov ←min(v, Max-Value(successor ))end forreturn vend functionfunction Max-Value(state)if state is leaf thenreturn (Utility(state), Utility(state))end ifvmin← −∞vmax← −∞for successor in Successors(state) dovNextmin, vNextmax←Min-Value(successor )vmin← max(vmin, vNextmin)vmax← max(vmax, vNextmax)end forreturn (vmin, vmax)end functionfunction Min-Value(state)if state is leaf thenreturn (Utility(state), Utility(state))end ifvmin← ∞min move vmax← −∞vmag icmax← −∞for state in Successors(state) dovNextmin, vNextmax←Max-Value(successor )if vmin> vNextminthenvmin← vNextminmin move vmax← vNextmaxend ifvmag ic max← max(vNextmax, vmag ic max)end forvmax← max(min move vmax, vmag ic max− c)return (vmin, vmax)end functionThe first observation is that the maximizer and minimizer are getting different values from the game.The maximizer gets the value at the leaf minus c*(number of applications of dark magic), which wedenote by vmax. The minimizer, as always, tries to minimize the value at the leaf, which we denoteby vmin.In Max − V alue, we now compute two things.(1) We compute the max of the children’s vmaxvalues, which tells us what the optimal value obtainedby the maximizer would be for this node.(2) We compute the max of the children’s vminvalues, which tells us what the minimizer thinkswould happen in that node.In Min − V alue, we also compute two things.(1) We compute the min of the children’s vminvalues, which tells us what the minimizer’s choicewould be in this node, and is being tracked by the variable vmin. We also keep track of the value themaximizer would get if the minimizer got to make their move, which we denote by min move vmax.(2) We keep track of a variable vmag ic maxwhich computes the maximum of the children’s vmax.3If the maximizer applies dark magic he can guarantee himself vmag ic max− c. We compare thiswith the min move vmaxfrom (1) and set vmaxto the maximum of the two.4(iv) Dark Magic Becomes PredictableThe minimizer has come to the realization that Pacman has the ability to apply magic at cost c. Hencethe minimizer now doesn’t play according the regular minimax strategy anymore, but accounts forPacman’s magic capabilities when making decisions. Pacman in turn, is also aware of the minimizer’snew way of making decisions.You again get to write the pseudo-code that Pacman uses to compute his strategy. As a startingpoint / reminder we give you below the pseudo-code for a standard minimax agent. Modify thepseudocode such that it returns the optimal value for Pacman.function Max-Value(state)if state is leaf thenreturn Utility(state)end ifv ← −∞for successor in Successors(state)dov ←max(v, Min-Value(successor ))end forreturn vend functionfunction Min-Value(state)if state is leaf thenreturn Utility(state)end ifv ← ∞for successor in Successors(state)dov ←min(v, Max-Value(successor ))end forreturn vend functionfunction Min-Value(state)if state is leaf thenreturn Utility(state)end ifv ← ∞vm← −∞for state in Successors(state) dotemp ← Max-Value(successor )v ← min(v, temp)vm← max(vm, temp)end forreturn max(v, vm− c)end function5Q2. Games: Alpha-Beta PruningFor each of the game-trees shown below, state for which values of x the dashed branch with the scissors will bepruned. If the pruning will not happen for any value of x write “none”. If pruning will happen for all values ofx write “all”.61x 3(a) Example Tree. Answer: x ≤ 1.We are