NAME: SID#: Section: 1CS 188 Introduction to AISpring 2004 Stuart Russell MidtermYou have 50 minutes. The exam is open-book, open-notes. 100 points total. Panic not.ALL QUESTIONS IN THIS EXAM ARE TRUE/FALSE, MULTIPLE-CHOICE, OR SHORT-ANSWER.Mark your answers ON THE EXAM ITSELF. Write your name, SID, and section number at the top of each page.For true/false questions, CIRCLE True OR False.For multiple-choice questions, CIRCLE ALL CORRECT CHOICES (in some cases, there may be more than one).If you are not sure of your answer you may wish to provide a brief explanation.For official use onlyQ. 1 Q. 2 Q. 3 Q. 4 Q. 5 Q. 6 Total/12 /15 /25 /12 /18 /18 /1001. (12 pts.) Agents and Environments(a) (3) True/False: There exist task environments (PEAS) in which some pure reflex agents behave rationally.(b) (3) True/False: There exist task environments (PEAS) in which all pure reflex agents behave irrationally.(c) (3) True/False: The input to an agent program is the same as the input to the corresponding agentfunction.(d) (3) True/False: Every agent function is implementable by some program/machine combination2. (15 pts.) SearchConsider the problem of moving k knights from k starting squares s1, . . . , skto k goal squares g1, . . . , gk, onan unbounded chessboard, subject to the rule that no two knights can land on the same square at the sametime. Each action consists of moving up to k knights simultaneously. We would like to complete the maneuverin the smallest number of actions.(a) (5) What is the maximum branching factor b in this state space?(i) 8k (ii) 9k (iii) 8k(iv) 9k(b) (6) Suppose hiis an admissible heuristic for the problem of moving knight i to goal giby itself. Which ofthe following heuristics are admissible for the k-knight problem?(i) min{h1, . . . , hk} (ii) max{h1, . . . , hk} (iii)Pki = 1hi(c) (4) Which of these is the best heuristic?(i) min{h1, . . . , hk} (ii) max{h1, . . . , hk} (iii)Pki = 1hi23. (25 pts.) CSPs and local searchConsider the problem of placing k knights on an n × n chessboard such that no two knights are attacking eachother, where k is given and k ≤ n2.(a) (5) Choose a CSP formulation. In your formulation, what are the variables?(b) (5) What are the values of each variable?(c) (5) What sets of variables are constrained, and how?(d) (5) Now consider the problem of putting as many knights as possible on the board without any attacks.We will solve this using local search. Briefly describe in English a sensible successor function.(e) (5) Briefly describe in English a sensible objective function.NAME: SID#: Section: 34. (12 pts.) Propositional logicConsider a propositional language with four symbols, A, B, C, and D. How many models are there for each ofthe following sentences?(a) (4) B ∨ C(b) (4) ¬A ∨ ¬B ∨ ¬C ∨ ¬D(c) (4) (A ⇒ B) ∧ A ∧ ¬B ∧ C ∧ D5. (18 pts.) Propositional logicAccording to political pundits, a person who is radical (R) is electable (E) if he/she is conservative (C), butotherwise is not electable.(a) (12) Which of the following are correct representations of this assertion?i. (R ∧ E) ⇐⇒ Cii. R ⇒ (E ⇐⇒ C)iii. R ⇒ ((C ⇒ E) ∨ ¬E)(b) (6) Which of the sentences in (a) can be expressed in Horn form?(i) (ii) (iii)6. (18 pts.) First-Order Logic(a) (12) Which of the following are correct translations of “No two adjacent countries have the same color”?i. ∀x, y ¬Country(x) ∨ ¬Country(y) ∨ ¬Adjacent(x, y) ∨ ¬(Color(x) = Color(y)).ii. ∀x, y (Country(x) ∧ Country(y) ∧ Adjacent(x, y) ∧ ¬(x = y)) ⇒ ¬(Color(x) = Color(y)).iii. ∀x, y Country(x) ∧ Country(y) ∧ Adjacent(x, y) ∧ ¬(Color(x) = Color(y))iv. ∀x, y (Country(x) ∧ Country(y) ∧ Adjacent(x, y)) ⇒ Color(x 6= y).(b) (6) Which of the following are valid sentences?i. (∃x x = x) ⇒ (∀y ∃z y = z).ii. ∀x P (x) ∨ ¬P (x).iii. ∀x Smart(x) ∨ (x =
View Full Document