Fall 2018
Assignment #4
Out: 11/5 Due: 11/19
Q1. Suppose that the wumpus world agent has progressed to the point shown in Fig 7.4(a) and is now concerned with [1,3], [2,2] and [3,1]. Following the example of Fig 7.5 do the following:
(a) Construct the set of 32 possible worlds
(b) Mark the worlds in which the KB is true
(c) Mark the worlds in which a2: “there is no pit in [1,3]”
(d) Mark the worlds in which a3: “there is a wumpus in [3,1] and a pit in [2,2]” are true
(e) Show whether KB entails a2.
(f) Show whether KB entails a3.
Q2. Consider the game tree below with terminal nodes labeled.
(a) Label max and min levels in the tree,
(b) Carry out minimax search, labeling the values at ALL the nodes,
(c) Carry out alpha-beta pruning and indicate which nodes are note expanded,
(d) What is the order for successor nodes that produces the best savings with alpha-beta search?
Q3. Explain how (a) entailment by model-checking differs from (b) entailment by inference. Your answer must define and use the set of models for a statement, logical entailment and logical inference and must conclude with a single logic statement that defines each of these two by entailment.
Q4. (a) Given a propositional knowledge base KB and some proposition what logical sentence should be shown to be unsatisfiable to show that KB |= by resolution and why?
(b) Given the following knowledge base KB in Horn Clause form and , use resolution (not chaining or inference) to show that KB |= . Begin by changing the Horn clauses to Conjunctive Normal Form.
KB: B2 P3, P1 B2, P3 B1, P3False, B1False
: P1
2 8 8 3 7 6 12 3 8 6 8 4 10 2