Description

Q1. One Wish Pacman
(a) Power Search. Pacman has a special power: once in the entire game when a ghost is selecting an action, Pacman can make the ghost choose any desired action instead of the min-action which the ghost would normally take. The ghosts know about this special power and act accordingly.

(i) Similar to the minimax algorithm, where the value of each node is determined by the game subtree hanging from that node, we define a value pair (u,v) for each node: u is the value of the subtree if the power is not used in that subtree; v is the value of the subtree if the power is used once in that subtree. For example, in the below subtree with values (-3, 5), if Pacman does not use the power, the ghost acting as a minimizer would choose -3; however, with the special power, Pacman can make the ghost choose the value more desirable to Pacman, in this case 5.
Reminder: Being allowed to use the power once during the game is different from being allowed to use the power in only one node in the game tree below. For example, if Pacman’s strategy was to always use the special power on the second ghost then that would only use the power once during execution of the game, but the power would be used in four possible different nodes in the game tree.
For the terminal states we set u = v = Utility(State).
Fill in the (u,v) values in the modified minimax tree below. Pacman is the root and there are two ghosts.

(ii) Complete the algorithm below, which is a modification of the minimax algorithm, to work in the general case: Pacman can use the power at most once in the game but Pacman and ghosts can have multiple turns in the game.

function Value(state) if state is leaf then u ← Utility(state) v ← Utility(state) return (u,v)
end if if state is Max-Node then
return Max-Value(state)
else return Min-Value(state)
end if
end function
function Max-Value(state)
uList ← [ ],vList ← [ ] for successor in Successors(state) do (u0,v0) ← Value(successor) uList.append(u0) vList.append(v0) end for u ← max(uList) v ← max(vList) return (u,v) end function
function Min-Value(state)
uList ← [ ],vList ← [ ] for successor in Successors(state) do (u0,v0) ← Value(successor) uList.append(u0) vList.append(v0) end for u ← min(uList) v ← max(max(uList), min(vList))

return (u,v) end function
(b) Weak-Power Search. Now, rather than giving Pacman control over a ghost move once in the game, the special power allows Pacman to once make a ghost act randomly. The ghosts know about Pacman’s power and act accordingly.
(i) The propagated values (u,v) are defined similarly as in the preceding question: u is the value of the subtree if the power is not used in that subtree; v is the value of the subtree if the power is used once in that subtree.
Fill in the (u,v) values in the modified minimax tree below, where there are two ghosts.

(ii) Complete the algorithm below, which is a modification of the minimax algorithm, to work in the general case: Pacman can use the weak power at most once in the game but Pacman and ghosts can have multiple turns in the game.
Hint: you can make use of a min, max, and average function
function Value(state) if state is leaf then u ← Utility(state) v ← Utility(state) return (u,v)
end if if state is Max-Node then
return Max-Value(state)
else return Min-Value(state)
end if
end function
function Max-Value(state)
uList ← [ ],vList ← [ ] for successor in Successors(state) do (u0,v0) ← Value(successor) uList.append(u0) vList.append(v0) end for u ← max(uList) v ← max(vList) return (u,v) end function
function Min-Value(state)
uList ← [ ],vList ← [ ] for successor in Successors(state) do (u0,v0) ← Value(successor) uList.append(u0) vList.append(v0) end for u ← min(uList)
v ← max(average(uList), min(vList))
return (u,v) end function

Q2. Lotteries in Ghost Kingdom
(a) Diverse Utilities. Ghost-King (GK) was once great friends with Pacman (P) because he observed that Pacman and he shared the same preference order among all possible event outcomes. Ghost-King, therefore, assumed that he and Pacman shared the same utility function. However, he soon started realizing that he and Pacman had a different preference order when it came to lotteries and, alas, this was the end of their friendship.
Let Ghost-King and Pacman’s utility functions be denoted by UGK and UP respectively. Assume both UGK and UP are guaranteed to output non-negative values.
(i) Which of the following relations between UGK and UP are consistent with Ghost King’s observation that UGK and UP agree, with respect to all event outcomes but not all lotteries?

(ii) In addition to the above, Ghost-King also realized that Pacman was more risk-taking than him. Which of the relations between UGK and UP are possible?

(b) Guaranteed Return. Pacman often enters lotteries in the Ghost Kingdom. A particular Ghost vendor offers a lottery (for free) with three possible outcomes that are each equally likely: winning $1, $4, or $5.
Let UP(m) denote Pacman’s utility function for $m. Assume that Pacman always acts rationally.
(i) The vendor offers Pacman a special deal – if Pacman pays $1, the vendor will manipulate the lottery such that Pacman always gets the highest reward possible. For which of these utility functions would Pacman choose to pay the $1 to the vendor for the manipulated lottery over the original lottery? (Note that if Pacman pays $1 and wins $m in the lottery, his actual winnings are $m-1.)
✓ UP(m) = m
22✓ UP(m) = m2
(ii) Now assume that the ghost vendor can only manipulate the lottery such that Pacman never gets the lowest reward and the remaining two outcomes become equally likely. For which of these utility functions would Pacman choose to pay the $1 to the vendor for the manipulated lottery over the original lottery?
✓ UP(m) = m
22 UP(m) = m2