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
S6C 9 10
A 7
31B 5 10
3
11
10
G1 0
D 6
2 G3
7
11 F1
E630
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 tru✏e. The goal is to steer each pig to its pen, but all tru✏es 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 tru✏e if the pig and tru✏e 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 tru✏es 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 tru✏es 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⇤Pi=1…n ManhattanDistance(pigi,peni)
Take Home Exam, University of Toronto, CSC384 – Intro to AI, Winter 2021 7 Game Tree Search [23 Marks Total]:
Consider the game tree in the diagram above.
4. 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).