CS 188 Introduction to AIFall 2005 Stuart Russell Midterm Solution1. (12 pts.) True/False(a) (2) True; both because it is often possible to make changes to an environment without affecting optimalaction choices (e.g., small changes to outcome probabilities, monotonic transformations in determinis-tic game payoffs) and because a single agent (e.g., a minimax game player) can act optimally in twoenvironments by responding appropriately to the different percepts the two environments supply.(b) (2) False; Ch. 3 gives examples of solving the sensorless vacuum world. Solutions to sensorless problemsare actions sequences, just as for fully observable deterministic problems.(c) (2) False; although the circuit-based agent does not have to be replicated over time, its circuit may beexponentially larger than the propositional KB.(d) (2) False; e.g., ∃ x P (x) ∧ ¬P (x).(e) (2) False; it might be unlucky with the dice. (A perfectly rational agent never loses at chess when playingWhite, we assume.)(f) (2) False; a lucky DFS might expand exactly d nodes to reach the goal. A∗largely dominates any graph-search algorithm that is guaranteed to find optimal solutions.2. (16 pts.) Problem solving(a) (6) Initial state: two arbitrary 8-puzzle states. Successor function: one move on an unsolved puzzle. (Youcould also have actions that change both puzzles at the same time; this is OK but technically you haveto say what happens when one is solved but not the other.) Goal test: both puzzles in goal state. Pathcost: 1 per move.(b) (4) Each puzzle has 9!/2 reachable states (remember that half the states are unreachable). The joint statespace has (9!)2/4 states.(c) (2) This is like backgammon; expectiminimax works.(d) (4) Actually the statement in the question is not true (it applies to a previous version of part (c) in whichthe opponent is just trying to prevent you from winning—in that case, the coin tosses will eventually allowyou to solve one puzzle without interruptions). For the game described in (c), consider a state in whichthe coin has come up heads, say, and you get to work on a puzzle that is 2 steps from the goal. Shouldyou move one step closer? If you do, your opponent wins if he tosses heads; or if he tosses tails, you tosstails, and he tosses heads; or any sequence where both toss tails n times and then he tosses heads. So hisprobability of winning is at least 1/2 + 1/8 + 1/32 + · · · = 2/3. So it seems you’re better off moving awayfrom the goal. (There’s no way to stay the same distance from the goal.) This problem unintentionallyseems to have the same kind of solution as suicide tictactoe with passing. So everyone got full credit forthis question, and extra credit if they made progress towards the right answer.3. (16 pts.) Propositional logic(a) (5) If the clauses have no complementary literals, they have no resolvents. If they have one pair ofcomplementary literals, they have one resolvent, which is logically equivalent to itself. If they have morethan one pair, then one pair resolves away and the other pair appears in the resolvent as (. . . A ∨ ¬A . . .)which renders the resolvent logically equivalent to T rue.(b) (3) True. (C ∨ (¬A ∧ ¬B)) ≡ (C ∨ ¬A) ∧ (C ∨ ¬B)) ≡ ((A ⇒ C) ∧ (B ⇒ C)).(c) (4) True (simple argument from models).(d) (4) False. α can entail the disjunction without committing to either disjunct. Consider the trivial casewhere α is just β ∨ γ.14. (16 pts.) Logical knowledge representation(a) (8) (b) and (c). (a) makes no sense because it uses Child as a function. (d) uses ⇒ with ∃.(b) (8) “Everyone’s DNA is unique and is derived from their parents’ DNA.”DN A(x) is the string of DNA characters of person x. (Notice that English is a bit loose: if two people“have the same DNA,” it means shared character strings, not shared molecules!)DerivedF rom(u, v, w) means string u is derived from v and w. (No need to go deeper here.)∀ x, y (¬(x = y) ⇒ ¬(DNA(x) = DNA(y)))∧DerivedF rom(DNA(x), DNA(Mother(x)), DNA(F ather(x)))5. (18 pts.) Logical inference(a) (12)i. (3) Ancestor(Mother(y), John): Yes, {y/John} (immediate).ii. (3) Ancestor(Mother(M other(y)), John): Yes, {y/John} (second iteration).iii. (3) Ancestor(Mother(M other(M other(y))), M other(y)): Yes, {} (second iteration).iv. (3) Ancestor(Mother(John), M other(M other(John))): Does not terminate.(b) (3) Although resolution is complete, it cannot prove this because it does not follow. Nothing in the axiomsrules out the possibility of everything being the ancestor of everything else.(c) (3) Same answer.6. (22 pts.) Game playing(a) (6)XX X XOOO0 0 1 −1 0MAXMIN 0 −10(b) (4) See tree.(c) (4) See tree. (If your tree is in a different order, it might have no pruned leaf.)(d) (4) Minimax will loop forever. Because alpha-beta, with the right move ordering, prunes the no-movenode as soon as it finds a sure win for X, it avoids the loop.(e) (4) In the suicide case, the no-move solution is optimal for both players. Minimax cannot return this isa solution because it requires going into the infinite loop! We can avoid the infinite loop in minimax byrecognizing that the current node is identical to an earlier node. But we need a way to give it a “value”so we can choose a move. We could assign 0 for “draw”, but this is not right in cases where the game iswinnable by one player or another from the repeated position. Instead, we can assign “?” and use thefact that a win is better than or equal to “?” which is better than or equal to a loss. This can be encodeddirectly into the inequality tests in the Min-Value and Max-Value
View Full Document
Unlocking...