1. Give a complete problem formulation in the style of ChapterĀ search-chapter.

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

3. 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?

4. Does the game eventually end, given optimal play? Explain.

(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.

Consider the problem of solving two 8-puzzles.

1. Give a complete problem formulation in the style of
ChapterĀ search-chapter.

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

3. 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?

4. Does the game eventually end, given optimal play? Explain.

(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.