• This is a open-book, open-notes exam. You are allowed to consult books, information online, etc. However, you are NOT ALLOWED to discuss the exam questions with your friends, classmates, etc. The TAs and I will pay close attention to your submitted answers. We will detect and penalize answers that are clearly copied from others or from the Internet according to the university policy. • There are 8 pages including the cover page. • The total number of points for the exam is 100. Please note the point value of each question and allocate your time accordingly. • Read each question carefully and make sure to show your work. • Please type in your answers and upload them to gradescope for grading by noon, October 27th (US Eastern Time). The turn in instructions are in the last page of this exam. Please allow yourself at least half an hour for turning in, since the website may go down for unexpected reasons. • Please sign the Purdue Honor Pledge below to begin your exam with your full legal name and date. Typing your name in LaTeX in the name line means you accepted and will act in observance to the pledge. Any exam papers without signing the pledge will automatically receive zero points. HONOR PLEDGE I, , (insert full legal name here) agree and hereby will act in observance of the Purdue Honor Pledge: “As a Boilermaker pursuing academic excellence, I pledge to be honest and true in all that I do. Accountable together – We are Purdue.” Name: Date: Introduction to AI Midterm - Page 2 of 8 10/26/2020 1 Multiple choices Only one choice is correct for the following questions. 1. (2 points) Which of the following statements is/are true about a heuristic function h? (i) If h(n) = h∗(n) for all n, then algorithm A∗ will only expand nodes on the optimal path (ignoring ties). (h∗(n) denotes the actual distance from node n to the goal state.) (ii) If h is admissible, the smaller h(n) is, the fewer nodes that A∗ will expand. (iii) If h(n) is always less than or equal to the cost of the cheapest path from n to the goal, then A∗ is guaranteed to find an optimal solution. A. Only (i) is true B. Only (ii) is true C. Only (iii) is true D. Both (i) and (iii) are true E. All (i), (ii), and (iii) are true 2. (2 points) Which of the following differentiates a reflex agent from a planning agent. A. Percepts B. Actions C. Model of current state D. Model of how state evolves in response to actions 3. (2 points) Which search is equal to minimax search but eliminates the branches that cannot influence the final decision? A. Depth-first search B. Breadth-first search C. Alpha-beta pruning D. None of the mentioned 4. (2 points) What are the mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations? A. Constraints Satisfaction Problems B. Uninformed Search Problems C. Local Search Problems D. All of the mentioned 5. (2 points) Translate the following statement into FOL. “For every a, if a is a philosopher, then a is a scholar” A. ∀ a philosopher(a) ⇒ scholar(a) B. ∃ a philosopher(a) ⇒ scholar(a) C. All of the mentioned D. None of the mentioned Introduction to AI Midterm - Page 3 of 8 10/26/2020 2 True or false? You will need to justify your answer with a few sentences. 1. (2 points) Let h1(s) be an admissible A* heuristic. Let h2(s) = 2h1(s). The solution found by A* tree search with h2 as heuristic is guaranteed to be an optimal solution. 2. (2 points) ((p ∧ q) ⇒ s) |= ((p ⇒ q) ⇒ s) 3. (2 points) Is there an assignment to A,B,C that makes this statement true? ¬C ∧(A ⇒ B) ∧ (¬B ∨ C) ∧ (C ∨ A) 4. (2 points) In a game, if you base your moves on the minimax algorithm, you cannot do worse than the minimax score, even if your real opponent is not using minimax as their strategy. 5. (2 points) Iterative-Deepening is faster than normal BFS, allowing its use in environ￾ments where computational power is at a premium. 3 Search Execute Tree Search on this graph (Note tree search does not remember visited nodes). Step costs are given next to each arc. Heuristic values are given in the table on the right. The successors of each node are indicated by the arrows out of that node. Successors are returned in up-to-bottom order, i.e., successors of S are (A, G), successors of A are (B, C), and successors of C are (D, G), in that order. For each search strategy below, show the order in which nodes are expanded (i.e., to expand a node means that its children are expanded into the fringe), ending with the goal node that is found. Show the path from start to goal, and give the cost of the path that is found. When deciding which node to expand, break the tie using alphabetic order (A, B, C, D, G) if every other metric returns a tie. The first one is done for you as an example!!!! 1. (0 points) Depth First Search Introduction to AI Midterm - Page 4 of 8 10/26/2020 • Order of node expansion: S A B D (G) • Path found: S A B D G • Cost of path found: 10 2. (4 points) Uniform Cost Search • Order of node expansion: • Path found: • Cost of path found: 3. (4 points) Greedy Search • Order of node expansion: • Path found: • Cost of path found: 4. (4 points) A* Search with h(n) • Order of node expansion: • Path found: • Cost of path found: 5. (8 points) Prove that this heuristic function is admissible 4 Game tree search You are playing a game with two of your friends. Since you are a brilliant CS471 student, you handily beat your friends each time (after all, they don’t have your AI skills, which are very relevant to this game and to life in general). Since you win so much, your friends decide to team up against you, trying to minimize your score. You are, as in the class, trying to maximize the score. The resulting game tree can be seen below (you see there are two steps marked by O from your friends after your turn marked by 4): ? ? ? ? 7 11 ? 2 5 ? ? 6 4 ? 1 9 ? ? ? 0 16 ? 2 8 ? 3 4 Based on this game tree, answer the following questions: Introduction to AI Midterm - Page 5 of 8 10/26/2020 1. (7 points) What is the final score you can obtain in this system assuming your friends and you are playing perfectly? Show the score values for all intermediate steps (HINT: It would be the easiest to fill out the ? in the tree’s LATEX code. Other form of representation can also be accepted. However, they need to be clear.) 2. (6 points) Rewriting your code for this three-player game would take a very long time. Describe how to convert such a 3-player minimax game tree into an equivalent standard (2-player) tree. Now you can just use the algorithms you learned about in class to solve this game variant! 3. (7 points) Would alpha-beta pruning help in solving this problem efficiently? Specify which branches would be pruned, if any (use your answer to the previous question to help!) 5 Constraint satisfaction problems: simple Sudoku This problem asks you to solve a simplified version of a Sudoku puzzle. The board is a 4-by-4 square, and each box can have a number from 1 through 4. One number can only appear once in each row and column. Furthermore, in each group of 2-by-2 boxes outlined with a solid border, each of the 4 numbers may only appear once as well. For example, in the boxes a, b, e, and f, each of the numbers 1 through 4 may only appear once. Note that the diagonals do not necessarily need to have each of the numbers 1 through 4. Notice that the board already has some boxes filled out: Box b = 4, c = 2, g = 3, l = 2, and o = 1. We represent this simple Sudoku puzzle as a CSP with the following constraints: 1. Each box can only take on values 1, 2, 3, or 4. 2. 1, 2, 3, and 4 may only appear once in each row. 3. 1, 2, 3, and 4 may only appear once in each column. 4. 1, 2, 3, and 4 may only appear once in each set of 2-by-2 boxes with solid borders. Introduction to AI Midterm - Page 6 of 8 10/26/2020 5. b = 4, c = 2, g = 3, l = 2, and o = 1. 1. (4 points) Write down the math representation for the constraint “value 1 must and must only appear once in the first row”. You may use the variables a, b, c, . . . , p and logical connectors (∧, ∨, ¬, etc) to represent the constraint. To give some hints, the constraint “value 1 must appear in the first row” can be represented as “a = 1 ∨ d = 1”. 2. (4 points) Write down the math representation for the constraint “value 3 must and must only appear once in the first column”. You may use the variables a, b, c, . . . , p and logical connectors (∧, ∨, ¬, etc) to represent the constraint. 3. (4 points) Write down the math representation for the constraint “value 2 must and must only appear once in the first group of 2-by-2 boxes”. You may use the variables a, b, c, . . . , p and logical connectors (∧, ∨, ¬, etc) to represent the constraint. 4. (4 points) Consider a naive backtracking algorithm using only forward checking. Assume that the backtracking algorithm solves the board from left to right, top to bottom, and enforces all unary constraints along the way (e.g., b is assigned to 4 already, etc). In the first step, 3 is assigned to box a. Using forward checking, what are the boxes whose domains will be affected by the assignment of box a? (In this problem, d, e, f, . . . , p are the variables represent the values assigned to boxes. You do not need to include the boxes whose values are already fixed in the answer.) 5. (4 points) Following the last question, what are the possible value assignments of each affected box? 6 Constraint satisfaction problem: map coloring Consider coloring the six-region map with three colors: R, G, B so that no two adjacent regions that share a border have the same color. Regions that only meet at a corner are not considered adjacent (e.g., 5 and 1) 1. (5 points) Identify the variables that should be used to set this up as a CSP problem and the domain of each variable. Introduction to AI Midterm - Page 7 of 8 10/26/2020 2. (5 points) Draw the constraint graph with a node for each variable and an edge between two variables if there is a constraint between them 7 First order logic Consider the following first-order inference problem given the rules and facts: • R1: If X is a close relative of Y and Y is a close relative of Z then X is acquainted with Z. • R2: If X is a parent of Y, then X is a close relative of Y. • R3: If X is married to Y, then X is a close relative of Y. • F1: Sam is a parent of Mike. • F2: Mike is married to Alice. 1. (5 points) FOL representation Express the rules R1-R3 and the facts F1,F2 in first-order logic using the following constants and predicates: • c(X,Y) — X is a close relative of Y. • p(X,Y) — X is a parent of Y. • m(X,Y) — X is married to Y. • a(X,Y) — X is acquainted with Y. • Sam, Mike, Alice : Constants. 2. (5 points) FOL reasoning Infer that Sam is acquainted with Alice using either forward or backward chaining. Introduction to AI Midterm - Page 8 of 8 10/26/2020 Submission Instructions: Upload your answers as a pdf in gradescope: https://www.gradescope.com/courses/151538 • To make grading easier, please start a new page in your pdf file for each question (no need to create a new page for each subquestion, i.e., question 3.1, etc.). Hint: use a \newpage command in LaTeX after every question ends. • After uploading to gradescope, mark each page to identify which question is answered on which page. (Gradescope will faciliate this.)