2 Consider the problem of solving two 8-puzzles.

a. Give a complete problem formulation in the style of the chapter Solving Problems by Searching.

b. How large is the reachable state space? Give an exact numerical expression.

c. Suppose we make the problem adversarial as follows: the two players take turns moving;

a coin is flipped to determine the puzzle on which to make a move in that turn; and the winner is the first to solve one puzzle. Which algorithm can be used to choose a move in this setting?

d. Give an informal proof that someone will eventually win if both play perfectly.

(a) b d P E (b) de df cd/ bd ad/ ae af ac dd dd Figure 16 (a) A map where the cost of every edge is 1. Initially the pursuer P is at node b and the evader E is at node d. (b) A partial game tree for this map. Each node is labeled with the P, E positions. P moves first. Branches marked "?" have yet to be explored.