Take Home Exam, University of Toronto, CSC384 – Intro to AI, Winter 2021 1 Computer Science 384 February 24, 2021
St. George Campus
Policies:
University of Toronto
Take Home Exam: Midterm Assessment
Due: February 26, 2021 by 9:00 PM (EDT)
1. On Piazza, you may not discuss problems on the take home exam.
2. You must work alone on this take home exam. You may not discuss problems on the take home exam with anyone (including other students).
3. You must write your answers clearly and legibly for full marks.
4. You may use whatever study aids you like (your course notes, the textbook, etc).
5. No submissions will be accepted past the due date without approval.
Total Marks: This exam represents 15% of the course grade.
Note that the points for each question are allocated based on a combination of the following criteria:
1. the effort required to answer the question
2. level of understanding of the course material required to answer the question 3. length of the answer.
That is, it’s quite possible that a question with an answer that takes a full page will earn the same mark as a question with short answer.
Handing in this Assignment: Submit written answers in a file called answers.pdf using MarkUs. Your login to MarkUs is your teach.cs username and password. It is your responsibility to include all necessary files in your submission.
Clarification Page: Important corrections (hopefully few or none) and clarifications to the assignment will be posted on the Exam FAQ page on the CSC384 Quercus Instance. You are responsible for monitoring the Exam FAQ page.
Questions: Logistical and/or clarification questions about the exam can be asked on Piazza: https://piazza.com/utoronto.ca/winter2021/csc384/home.
You may also reach out to the TAs or one of the instructors. Please place ”Exam” and ”CSC384” in the subject line of your email.
Take Home Exam, University of Toronto, CSC384 – Intro to AI, Winter 2021 2 Search [40 Marks Total]:
1. Suppose that we are running a variation of A∗ that uses a heuristic function which is not admissible, but is Q-admissible, meaning h(n) ≤ Q + h∗(n) for all nodes n and for some known Q > 0. In this equation, h∗(n) is the true least cost from the state n to a goal. This means h(n) will never be more than Q away from being a perfect estimate of the least cost path between state n to a goal.
a. Will this search be complete? In 2 sentences or less, explain (4 marks).
b. Will this search be optimal? If C∗ is the optimal cost from the start to a goal state, what is the worst cost solution this formulation of A∗ would yield? Justify your answer in the space below (4 marks).
Take Home Exam, University of Toronto, CSC384 – Intro to AI, Winter 2021 3
c. Can you suggest a way to modify a Q-admissible search in order to generate an optimal solution every time? In 2 sentences or less, explain your modification(s) (4 marks).
Take Home Exam, University of Toronto, CSC384 – Intro to AI, Winter 2021 4
2. Consider the search problem that is represented above, where S is the start node and G1, G2, and G3 are goal states. Arcs are labeled with the cost of traversing them and the heuristic estimate of cost to a goal is shown inside the nodes.
a. Is the heuristic provided admissible? Why or why not? (2 marks).
b. Is it monotonic or consistent? Why or why not? (2 marks).
Next, for each of the search strategies on the next page, illustrate the Frontier (or Open) list at each search iteration. Assume that you generate successors and insert them into the Frontier in alphabetical order (i.e. insert S− > C after S− > A). If you encounter ties in values used to organize paths in the Frontier, select the path that was most recently inserted.
Format your answers in a table, according to the template below. In this template, V ali is the value used to organize path i in the Frontier. Note that if all of the values in the template were equal, the path S− > D would be located at the head of the Frontier at outset of iteration 1 (and would be picked in iteration 2). If a value in your list is an f-value, list it as V ali = gvali + hvali. You do not have to fill every row in the tables provided.
3
7
S6C 9 10
A 7
1 3B
3
11
10
G1 0
E63
2 G3 0
5 D
6
10
11 1F
G2 0
7
ITERATION
NODE SELECTED
IN FRONTIER (OPEN) LIST
0
(S,V al0)
1
(S,V al0)
(SD,V al1),(SC,V al2),(SB,V al3),(SA,V al4)
2
…
…
Take Home Exam, University of Toronto, CSC384 – Intro to AI, Winter 2021 5
c. Uniform cost search, with cycle checking. Record visits to states and check for cycles as states are generated (i.e. prior to the insertion of paths in the Fron- tier). When a cycle is detected, 1) discard the path if appropriate and 2) remove redundant/more costly paths from the Frontier. (6 marks).
ITERATION
NODE SELECTED
IN FRONTIER (OPEN) LIST
0
(S,0)
1
(S,0)
2
3
4
5
6
7
8
9
10
d. A* search, with no cycle or path checking (4 marks).
ITERATION
NODE SELECTED
IN FRONTIER (OPEN) LIST
0
(S,0+0)
1
(S,0+0)
2
3
4
5
6
7
8
9
10
Take Home Exam, University of Toronto, CSC384 – Intro to AI, Winter 2021 6
3. We have been asked to encode a game as a search problem. In it, there are n pigs, each located at a square si on a board of dimension X by Y . Each pig (pigi) has its own pen at location peni. Finally, at every board location (including the location of pens), there may or may not be a single truffle. The goal is to steer each pig to its pen, but all truffles must be eaten by the pigs along the way.
At every time step, each pig may move one square North, South, East or West and all pigs must move at the same time. No pig can wait for a time step in any square (even when that square is a pen) and no pig can move into a wall or another pig. Pigs will eat a truffle if the pig and truffle are in the same square, and eating is instantaneous (no extra action is required). The goal of the game is to find a path for the pigs that collectively minimizes the steps required for them to both eat the truffles and arrive in their pens.
a. Define the smallest possible state space for this problem. What are the variables in this state space? (2 marks).
b. How many states are in the state space you have defined? (2 marks).
c. What is the largest branching factor in your state space? (2 marks).
d. Consider the following heuristics. For each, indicate if they are admissible or not
and explain why or why not in a single sentence. In these heuristics, M anhattanDistance(x, y) defines the Manhattan distance between squares x and y. Also, t ≤ X ∗ Y repre-
sents the t remaining truffles on the board at any one time (2 marks each).
(i) max(ManhattanDistance(pigi, peni) : i = 1…n)
(ii) max(ManhattanDistance(pigi,trufflej) : i = 1…n,j = 1…t) (iii) min(ManhattanDistance(pigi,trufflej) : i = 1…n,j = 1…t)
(iv) 1/n∗i=1…n ManhattanDistance(pigi,peni)
Take Home Exam, University of Toronto, CSC384 – Intro to AI, Winter 2021 7 Game Tree Search [23 Marks Total]:
4. Consider the game tree in the diagram above.
Assuming that the numbers in each node represents the node’s utility value, fill in the
empty nodes in the diagram above with the missing values (4 marks).
5. Consider the Monte Carlo search tree shown above.
a. On the diagram, fill in the empty nodes with the missing values. Assume that
the node values show the win tallies from the Max perspective (3 marks).
b. On the diagram, circle the node that will be expanded in the next iteration of the MCTS algorithm, assuming a bias value of sqrt(2) (2 marks).
Take Home Exam, University of Toronto, CSC384 – Intro to AI, Winter 2021 8
6. Consider the game tree shown above.
a. On the diagram, fill in the utility value for the root of this tree (2 marks).
b. Assuming that the branches are expanded using depth-first search from left to right, which branches (labeled e1-e26 here) will be pruned using the alpha-beta pruning algorithm presented in class? List the pruned branches in the spaces provided below (5 marks).
Note: only include the highest pruned branches when answering this question (for example, if e7 is being pruned, do not include e14 as well).
c. On the diagram, highlight the path from the root to the terminal node that would be produced by the alpha-beta algorithm in part 2 above (2 marks).
d. Which branches would be pruned if this tree was explored right to left instead? Provide your answer in the spaces provided below (5 marks).