Description
- True or False? You don’t need to explain your answers.
- h(n) = 0 is an admissible heuristic for the 8-queens problem.
- 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.
- (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:
- Local beam search with k = 1.
- 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.
- What is the terminal payoff at the node (1)?
- What are the positions of the two players at the node (2) and (2)’schildren?
- Can we assume the terminal payoff at the node (2) is less than < −4? Answer yes or no, then explain your answers.
- 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.
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.
- (A ∧ B) |= (A ⇔ B)
- ) (C ∨ (¬A ∧ ¬B)) ≡ ((A ⇒ C) ∧ (B ⇒ C))
- (A ∨ B) ∧ (¬C ∨ ¬D ∨ E) |= (A ∨ B) (d) (2 points) (A ∨ B) ∧ ¬(A ⇒ B) is satisfiable.
- Prove using Venn diagram, or find a counterexample to the following assertion:
α |= (β ∧ γ) then α |= β and α |= γ
