Question 1 (10 marks)

Pick the most appropriate answer to each of the following questions.  Please write your answer to each question in the boxes below. Each question is worth 2 marks.

(a) Which of the following statements is true in general:

1. Depth-first search always expands at least as many nodes as A* search with an admissible heuristic.

2. A perfectly rational backgammon agent never loses.

3. An advantage of Hill Climbing search is that it requires minimal memory.

4. Bi-directional search is always more efficient than uni-directional search.

(b) In a general CSP with n variables, each taking d possible values, what is the maxi- mum number of times a backtracking search algorithm might have to backtrack, if it is running arc consistency and applying the Minimum Remaining Values (MRV) and (Least Constraining Value) LCV heuristics?

1.  O(1)

2.  O(nd2 )

3.  O(n2 d3 )

4.  O(dn )

(c) You are given a game-tree for which you are the maximizer, and in the nodes in which you don’t get to make a decision an action is chosen uniformly at random amongst the available options. Your objective is to maximize the probability that you win $10 or more (rather than the usual objective to maximize your expected value). Note that Expectimax is a variant of Expectiminimax where nodes alternate between max nodes and chance nodes at di↵erent layers of the search tree (there are no min nodes). Then which of the following statements is true:

1. Running Expectimax will result in finding the optimal strategy to maximize the probability of winning $10 or more.

2. Running Minimax, where chance nodes are considered minimizers, will result in finding the optimal strategy to maximize the probability of winning $10 or more.

3. Running Expectimax in a modified game tree where every pay-o↵ of $10 or more is given a value of 1, and every pay-o↵ lower than $10 is given a value of 0 will result in finding the optimal strategy to maximize the probability of winning $10 or more.

4. Running Minimax in a modified game tree where every pay-o↵ of $10 or more is given a value of 1, and every pay-o↵ lower than $10 is given a value of 0 will result in finding the optimal strategy to maximize the probability of winning $10 or more.

(d) Consider that you need to run four auctions labelled (A), (B), (C) and (D), where the most important property for each auction is as follows:

(A) Hard to collude, (B) Winner pays second highest price, (C) Open-cry, (D) Decending

Which set of auction types below is the best match for these four auctions based on their respective desired properties?

1. (A) Vickery, (B) Dutch, (C) English, (D) First-price sealed-bid

2. (A) Vickery, (B) English, (C) Dutch, (D) First-price sealed-bid

3. (A) First-price sealed-bid, (B) Dutch, (C) English, (D) Vickery

4. (A) First-price sealed-bid, (B) Vickery, (C) English, (D) Dutch

(e) Figure 1-1 shows a robot arm that is made up of two sections Arm1 and Arm2 . Arm1 can rotate around the shoulder joint A, while Arm2  is connected to Arm1  at the elbow joint B, and can rotate around the joint B.  The configuration of the robot arm can be specified by the angle ✓ 1 between the horizontal axis and Arm1, and the angle ✓2 between Arm1  and Arm2.  Both angles are measured in radians.  There is also 1 fixed obstacle shown, which restricts the movement of the robot arm.

Question 2 (10 marks)

For each part of the following question you should write a brief answer in the box provided.

(a) [2 marks] The following is the weight update rule for gradient decent learning as described in the lectures

wi        wi − ⌘(z − t)fi(s)

where ⌘ is the learning rate, and w is the vector of weights in the evaluation function. Why it is important to get the learning rate parameter ⌘ right?

(b) [2 marks] In the weight update rule in part (a), what does a small di↵erence between z and t indicate about the current weight wi?

Question 2 (continued)

(c) [6 marks] For each of the following three environments, what is the most appropriate type of agent (simple reflex agent, model-based reflex agent, goal-based agent, or utility- based agent)? Briefly justify your answer.

(i) An automated system that translates text from one language to another, e.g., Google translate

(ii) A movie recommendation system

(iii) An automated taxi driver that is required to reach the airport on time

Question 3 (10 marks)

Consider the 3-ply game tree shown in Figure 3-1. Each node has an identifier (e.g., the root of the tree is node 1; it has three successor nodes 2, 12 and 22), and each terminal node has an associated value (e.g., the value of node 4 is 8).

MAX

16

4        5        7        8       10

VALUE 46 45 0 61      63     2 9 5

Figure 3-1

In the following questions, you are NOT required to redraw the search tree in your answer.

(a) [1 mark] What is the minimax value at node 1 after applying the minimax algorithm

to this search tree?

(b) [4 marks] If the nodes are examined in the order shown by the identifier in each node in Figure 3-1, which nodes would be pruned if alpha-beta pruning is used? For each node that would be pruned, place a cross in the corresponding box below.

(c) [2 marks] If we come up with the perfect ordering of the nodes, what is the maximum number of nodes that we can prune? Answer:

Question 3 (continued)

(d) [3 marks] What are three properties that characterise an e↵ective mechanism design for an auction? Note: you should briefly define each property that you give in your answer.

Write your answer in the space provided below. If you require more space, please use the last page of the exam paper, and clearly indicate on this page that you have used the last page.