Imagine that, in Exercise $3\mathrm{.}3,$ 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

PURSUIT$$EVASION

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 $5\mathrm{.}16.$

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?