Imagine that the problem in Exercise 3.ROMF, in which two friends try to meet up on the map of Romania, is modified so that one of the friends wants to avoid the other. The problem then becomes a two-player pursuit–evasion game. We assume now that the players take turns moving. The game ends only when the players are on the same node; the terminal payoff to the pursuer is minus the total time taken. (The evader “wins” by never losing.) An example is shown in Figure ??. 

a. Copy the game tree and mark the values of the terminal nodes. 

b. Next to each internal node, write the strongest fact you can infer about its value (a number, one or more inequalities such as “≥ 14”, or a “?”). 

c. Beneath each question mark, write the name of the node reached by that branch. 

d. Explain how a bound on the value of the nodes in (c) can be derived from consideration of shortest-path lengths on the map, and derive such bounds for these nodes. Remember the cost to get to each leaf as well as the cost to solve it. 

e. Now suppose that the tree as given, with the leaf bounds from (d), is evaluated from left to right. Circle those “?” nodes that would not need to be expanded further, given the bounds from part (d), and cross out those that need not be considered at all. 

f. Can you prove anything in general about who wins the game on a map that is a tree?

Transcribed Image Text:

de dd ce -4 be <=-6 df dd ed cf bd сс -2 Figure S5.1 Pursuit-evasion solution tree. T ae <=-6 =-6ad