Pg 1/7 Name: _______________________ CS 331 Midterm Spring 2019 You have 50 minutes to complete this midterm. You are only allowed to use your textbook, your notes, your assignments and solutions to those assignments during this midterm. If you find that you are spending a large amount of time on a difficult question, skip it and return to it when you’ve finished some of the easier questions. Total marks for this midterm is 43. Section Marks Agents / 8 Search / 11 Games / 12 Logic / 12 Total / 43 Pg 2/7 Section I: Agents (8 points) 1. Consider an agent solving a Sudoku puzzle. For each part below, circle the choice which best describes the environment for this agent: a) Fully observable or Partially observable [1 point] b) Deterministic or Stochastic [1 point] c) Episodic or Sequential [1 point] d) Static or Dynamic [1 point] e) Discrete or Continuous [1 point] f) Single agent or Multi-agent [1 point] 2. What type of agent is a Sudoku solver? Choose from simple reflex agent, model-based reflex agent, goal-based agent and utility-based agent. Give a one or two sentence justification of your answer. [2 points] Could argue for simple reflex, reacting to the state of the board at a given time and filling in the next number. Could argue for goal-based, reasoning about a sequence of actions to fill in the board. Pg 3/7 II. Search [11 points] 3. The following questions deal with the search algorithms you implemented in Programming Assignment #1. a) If breadth-first search (BFS) is implemented correctly, is it possible for depth-first search (DFS) to find an optimal solution path while expanding fewer nodes than BFS? Why or why not? [2 points] Yes, DFS could get “lucky” and find the optimal goal on the first depth-first pass. b) Suppose we use A* tree search to solve the Wolves and Chickens problem from the first programming assignment with 3 wolves and 3 chickens. If we set ℎ() = 1 for all nodes (except goal nodes, which for which we set ℎ() = 0), does the algorithm find an optimal solution? Why or why not? [2 points] The heuristic is admissible, so optimality is guaranteed. (This is a bad heuristic because it is uninformative, but the negative impact on the algorithm will be in efficiency instead of optimality.) c) Suppose you implement two version of A-star search: one with heuristic h1 and the other using heuristic h2. Both heuristics are admissible, but for all nodes n, h2(n) > h1(n). Which version expands more nodes? h1(n) expands more nodes. Pg 4/7 4. The following questions deal with local search algorithms. a) Name one local search algorithm that is not optimal (i.e., it may find local instead of global optima). Describe how adding an element of stochasticity can improve the algorithm. [3 points] Several answers are possible. For example, hill climbing is not optimal, but random restarts can improve performance. b) Suppose you are considering two options for solving a search problem: (i) A-star search with a good heuristic function, and (ii) a local search algorithm (e.g., simulated annealing). When would you prefer using (ii) over (i)? [2 points] Factors: substantial memory limitations to deal with, an approximate (good but not necessarily optimal) solution would suffice. Pg 5/7 III. Games [12 points] 5. Below is a portion of a game tree. What is the expectiminimax value at the root node? Show your work. [6 points] 6. Suppose that you are running the minimax algorithm with alpha-beta pruning on a game tree. You have come to a subtree, shown below, and the current values of alpha and beta are -4 and 8, respectively. Which branches (if any) are pruned in this subtree? Indicate your answer with Xs and show work for partial credit. [6 points] Pg 6/7 IV. Propositional Logic [12 points] 7. Is the following sentence valid, unsatisfiable, or neither? Justify your answer. [2 points] (¬ ⇒ ) ∧ ¬ ∧ ¬ ≡ ( ∨ ) ∧ ¬ ∧ ¬ We cannot have A or B true as well as both A and B false, so this is unsatisfiable. 8. Convert the following KB into Conjunctive Normal Form. [4 points] ¬( ∧ ) ⇒ ¬( ∧ ) ∨ ∨ ¬ ∨ ¬ Pg 7/7 9. Use the resolution algorithm to determine whether the following KB entails . [6 points] 1. ∨ 2. ¬ ∨ 3. ∨ ¬ ∨ 4. 5. ¬ 6. ∨ ¬ (5 + 3) 7. (6 + 4) 8. ∨ (1 + 2) 9. ∨ (3 + 4) Therefore, KB does not entail .
