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.