AI, in GeneralSearchGame PlayingPropositional LogicCPSC420-502 Midterm Exam (10/16/2003, Thu)1Last name: , First name: , ID (last 5 digit):Time: 9:35am–10:50am (75 minutes + α), Total Points: 100Subject ScoreAI General /10Search /40Game Playing /25Propositional Logic /25Total /100• You may use the back of the sheet, but please prominently mark on the front in such a case.• Be as succinct as possible.• Read the questions carefully to see what kind of answer is expected (explain blah in termsof ... blah).• Solve all problems.• Total of 11 pages, including this cover and the Appendix at the end. Before starting, countthe pages and see if you have all 11.• This is a closed-book, closed-note exam.• You may rip off the last page (Appendix) to view it while solving the logic problems.1Instructor: Yoonsuck Choe.11 AI, in GeneralQuestion 1 (4 pts): Among many different academic disciplines related to AI, list two that youthink are most important, and briefly explain why.Question 2 (6 pts): What are the strengths and weaknesses of the Turing test as a test for intelli-gence? Briefly provide one example for each.22 SearchQuestion 3 (4 pts): What role does the queueing function play in a general search algorithm?Explain in terms of the resulting search behavior when the queueing function was altered.Question 4 (5 pts): Explain why Iterative Deepening Depth-First Search can be better than bothBreadth-First Search and also Depth-First Search? Explain in terms of the four evaluation criteria(completeness, optimality, space complexity, and time complexity).Question 5 (6 pts): When you compare the Greedy search and the A∗search algorithm, (1) whichfeature of the queueing operation (i.e., insertion of nodes into the node list) is common in both,and (2) what is different in the two? (3) Why is A∗superior to Greedy search? Explain in terms ofthe four evaluation criteria.3Question 6 (6 pts): Iterative Deepening A∗is superior to A∗in one crucial way, but it can bedisadvantageous in another. Identify what are these two, in terms of the four evaluation criteria,and explain why by contrasting to Depth-First search and Breadth-First search.Question 7 (5 pts): Explain what a dominant heuristic is and explain why a dominant heuristicis better when used in A∗. Discuss in terms of the concept of f-contours and the number of nodesexpanded.Question 8 (4 pts): What is the major difference between uninformed and informed searchmethods?4Question 9 (5 pts): Hill-climbing is a local search method without any memory. (1) Explainhow hill-climbing differs from Greedy search, and (2) explain what is the major drawback of thehill-climbing method.Question 10 (5 pts): In Simulated Annealing, the goal is to move from one state to another byapplying an operator so that the energy E associated with the state is minimized. Given a state,an operator is allowed to be applied only in two cases depending on the ∆E value (the change inenergy E in the two states): (1) Explain what are these two cases, and (2) explain why this canhelp solve the problem of local search methods such as hill-climbing.53 Game PlayingQuestion 11 (3 pts): Minmax search is very similar to one of the uninformed search methods. (1)What is it and (2) why?Question 12 (6 pts): Using the following figure, explain how α−β pruning works. (1) Show eachstage of the search and α/β value updates. (2) Show the cut(s). (3) Show which values should becompared to determine whether or not to cut (i.e., choose a pair from v, α, and β), and the whichcomparison should be used (≤ or ≥). For example v ≤ α.α =β = α =β = 105MINMAXMINMAX12 15Question 13 (6 pts): Repeat the same questions in Question 12 for the following tree.α =β = α =β = MAX10MINMINMAX512−36Question 14 (6 pts): Using the tree below, (1) explain how an α or β value that was set farabove the search tree can affect cuts at deeper depths. (2) Show where a cut can occur. Hint:think about how the α and β values from above are handed over to the children and grandchildred.MIN10MINMIN−374MAXMAXMAX13Question 15 (4 pts): What assumption is necessary for the results from an α − β pruning searchis the same as Minmax search? Explain in terms of the MIN and the MAX player and the propertyof their strategy.74 Propositional LogicUse the laws of propositional logic at the end of the test as necessary (see the last page). You maydetach the last page from the test.Question 18 (4 pts): Convert ¬(P → (Q ∧ R )) to disjunctive normal form, i.e., disjunction ofterms (· ∧ · · · ∧ ·) ∨ (· ∧ · · · ∧ ·) ∨ · · ·. Show every step of the derivation.Question 19 (4 pts): Convert (¬P ∨ S) → (P ∧ Q ∧ R) to conjunctive normal form, i.e., con-junction of clauses (· ∨ · · · ∨ ·) ∧ (· ∨ · · · ∨ ·) ∨ · · ·. Show every step of the derivation.8Question 20 (3 pts): Why do we want to convert logical formulas into these differnt normalforms? Briefly explain in the perspective of AI.Question 18 (8 pts): Using resolution, show that:(P ∨ S) is a logical consequence of (P ∨ Q) ∧ (¬Q ∨ R ∨ S) ∧ (¬R ∨ P ).Show every step of the derivation.9Question 19 (3 pts): When using resolution, why is it critical that all axioms (or premises) in theknowledge base is true?Question 20 (3 pts): What is a Horn clause and why is it particularly suitable for automatedtheorem proving? (Hint: think about implications A → B.)10Appendix: Laws of Propositional LogicNote: There is no exam question on this page.Use the laws of propositional logic below as necessary. You may detach the last page from the test.• P ∨ Q = Q ∨ P ,P ∧ Q = Q ∧ P (commutative)• (P ∨ Q) ∨ H = P ∨ (Q ∨ H),(P ∧ Q) ∧ H = P ∧ (Q ∧ H),(associative)• P ∨ (Q ∧ H) = (P ∨ Q) ∧ (P ∨ H),P ∧ (Q ∨ H) = (P ∧ Q) ∨ (P ∧ H) (distributive)• P ∨ False = P, P ∧ False = False• P ∨ True = TrueP ∧ True = P• P ∨ ¬P = TrueP ∧ ¬P = False• ¬(P ∨ Q) = ¬P ∧ ¬Q,¬(P ∧ Q) = ¬P ∨ ¬Q (DeMorgan’s law)• P → Q = ¬Q → ¬P (contrapositive)• P → Q = ¬P ∨ QThese are the common inference rules:• Modus Ponens:F → G, FG• Unit Resolution:F ∨ G, ¬GF• Resolution:F ∨ G, ¬G ∨ HF ∨ Hor equivalently¬F → G, G → H¬F →