COMP-424: Artificial Intelligence (Winter 2020) Midterm Examination
● Do not turn this page until instructed to do so.
● This is a closed book examination. No books, calculators, or computers.
● You are allowed to bring one double-sided 8.5”x11” page of hand-written or typed
Copyright By PowCoder代写 加微信 powcoder
notes, with your name and student ID clearly visible.
● You may use pages 10 – 11 for rough work. Answers written there will not be
● This examination has 12 pages including this cover page, and is printed on both
sides of the paper.
● MAKE SURE TO WRITE YOUR NAME AND STUDENT ID ON THE EXAM (on
page 1). MARKS WILL BE DEDUCTED IF INFORMATION IS MISSING.
Q1: Search [12 pts] Points on this page: /12
Consider the following search problem, with a start state of S, and a goal state of G. The search graph with the edge costs are indicated on the left. The table on the write gives three different heuristic functions for this problem.
Node h0 h1 h2 S056 A035 B042 C025 D053 G000
(a)(3points)Whichoftheheuristicsshownareadmissible?Circleallthatapply:h0, h1, h2.
(b) (6 points) Give the path that heuristic search will return using each of the three heuristics. In the case of a tie, visit the nodes in alphabetical order. (Hint: you should not actually have to execute the search to know the answer in some cases.)
(c) (3 points) What path will greedy best-first search return using h1?
Q2: Constraint Satisfaction [12 pts] Points on this page: /4 The k-n knights problem involves placing k knights on a n × n chessboard such that no two
2 knights attack each other. Assume k ≤ n.
Preliminaries: Achessboardisasquaregridofalternatingblackandwhitesquares.Knights move on a chessboard in a L-shaped manner. A knight must move either 2 spaces vertically and 1 space horizontally, or 2 spaces horizontally and 1 space vertically. During a move, a knight can jump over other knights in its path to reach its destination. Thus, the knights attack each other if one of them can reach the other in a single move. In the figure below, the grids marked with X are the cells to which the knight can go to in a single move from its current position.
a) (4 points) Specify the k-n knights problem as a CSP.
Points on this page: /8
Now, consider the 3-3 knights problem. In addition to the standard assumptions, also assume that i) there can be only 1 knight per column and ii) there can be only 1 knight per row. Now with these new sets of assumptions, answer the questions below:
b) (4 points) Simplify the CSP in part a) by considering the columns of the chessboard as variables. Draw the constraint graph.
c) (4 points) Write down the constraints explicitly as a list of allowed value pairs for each pair of variables. Further, write down the reduced domains that would result from running the AC-3 algorithm (no need to show the steps of the algorithm).
Q3: Logic [15 pts] Points on this page: /8
(a) (4 points) Assume that the following sentences are in our knowledge base:
ii. ¬A → (¬B∧¬C)
iii. ¬B → (¬D∧¬E)
iv. ¬C → (D∨E∨F)
Using the inference rules of propositional logic, give a derivation to show whether or not F is true. In your derivation, specify the rules used at each step.
(b) (4 points) Convert the following sentences to first-order logic: i. Every AI program that plays games is an agent.
ii. Chess and Go are games.
iii. No agent that plays Go and wins is sad. iv. The agent AlphaZero plays Go.
Points on this page: /7
(c) (4 points) Convert the sentences above into conjunctive normal form.
(d) (3 points) Determine whether the sentence (P → (Q ∨ R)) → ((P ∧ Q) → R) is valid, satisfiable, or unsatisfiable. Show your reasoning with examples and/or counterexamples.
Q4: Game playing [5 pts] Points on this page: /5
Suppose we have the following game search tree.
(a) (4 points) Circle the nodes,including the terminal leaf nodes, which are visited in a minimax search algorithm that uses alpha-beta pruning (ordering nodes from left to right). Cross
out each edgethat leads to a subtree that is pruned.
(b) (1 point) Which initial action should the MAX player take according to minimax?
Q5: Short Answer and Multiple Choice [13 pts] Points on this page: /10
Circle the best answer.
1. 2. 3. 4. 5. 6.
To try to escape local minima, (hill climbing / simulated annealing) allows some bad moves with probability .
(Breadth-first search / Depth-first search / Both) has/have exponential time complexity in the worst case.
In simulated annealing, the value of the temperature parameter should be (decreased / increased) over the training duration.
A sentence is in CNF if it is expressed as a (disjunction / conjunction) of (disjunctions/conjunctions) of literals.
is an inference rule for propositional logic that is complete for KBs in which sentences are in (CNF / DNF / Horn form).
Which of the following is FALSE?
a. α is valid iff ¬α is unsatisfiable
b. α⊨β if and only if (α⇒β) is valid
c. α is satisfiable ⇔ ¬α is not valid
d. ¬α is satisfiable iff α is valid
An inference method is sound if it
a. can derive any sentence that is entailed.
b. only derives entailed sentences.
c. is polynomial in both time and space complexity.
d. works with at least one normal form.
α – β pruning
a. is easy to parallelize, like Monte-Carlo tree search.
b. returns the same optimal solution as minimax search.
c. has worst-case time complexity of O(bm/2).
d. can play optimally even against a suboptimal opponent.
Conformant planning is used in the case of (non-observable states / non-deterministic actions).
In MCTS, it is (exploration / exploitation) when we pick a node that appears to be promising according to the current estimate.
Points on this page: /3
11. An optimal solution path for a search problem with positive costs a. can have repeated states.
b. will never have repeated states.
c. may or may not have repeated states.
d. always has repeated states.
12. Using a constraint propagation method such as forward checking as part of DFS with
backtracking (increases/ never increases) the number of node expansions in the search.
13. Using a constraint propagation method such as forward checking as part of DFS with backtracking (increases/never increases) the time complexity of the search.
Rough work
Rough work
Question 1 /12 Question 2 /12 Question 3 /15 Question 4 /5 Question 5 /13 Total /57
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com