- True or False? You don’t need to explain your answers.
- (2 points) h(n) = 0 is an admissible heuristic for the 8-queens problem.
- (2 points) Assume that a rook can move on a chessboard one square at a time invertically or horizontally, but cannot jump over other pieces. Manhattan distance is an admissible heuristic for the problem of moving the rook from square A to square B in the smallest number of moves.
- (6 points) The heuristic path algorithm is a best-first search in which the evaluation function is f(n) = (2 − w)g(n) + wh(n). What kind of search does this perform for w = 0,w = 1, and w = 2?
- Give the name of the algorithm that results from each of the following cases:
- (2 points) Local beam search with k = 1.
- (2 points) Simulated annealing with T = ∞ at all times.
- Imagine that, one of the friends wants to avoid the other. The problem then becomes atwo-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 move taken. An example is shown in Figure 1.
- (2 points) What is the terminal payoff at the node (1)?
- (2 points) What are the positions of the two players at the node (2) and (2)’schildren?
- (3 points) Can we assume the terminal payoff at the node (2) is less than < −4? Answer yes or no, then explain your answers.
- (3 points) Assume the terminal payoff at the node (4) is less than −4. Do we need expand the node (5) and (6)? Answer yes or no, then explain your answers.
CECS 451 Assignment 5 – Page 2 of 2
Figure 1: (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.
- True or False? You don’t need to explain your answers.
- (2 points) (A ∧ B) |= (A ⇔ B)
- (2 points) (C ∨ (¬A ∧ ¬B)) ≡ ((A ⇒ C) ∧ (B ⇒ C))
- (2 points) (A ∨ B) ∧ (¬C ∨ ¬D ∨ E) |= (A ∨ B) (d) (2 points) (A ∨ B) ∧ ¬(A ⇒ B) is satisfiable.
- (4 points) Prove using Venn diagram, or find a counterexample to the following assertion:
α |= (β ∧ γ) then α |= β and α |= γ
