PartI: Select the best option. Write your final answer in the boxes. [5 points]

i) Breadth-first search is optimal in which of the following settings? Choose the most general answer.

A. Unit step cost, admissible heuristic

B. Unit step cost, any heuristic

C. General step cost, admissible heuristic

D. General step cost, any heuristic

E. All search settings

ii) Hill climbing is susceptible to which of the following issues?

A. Global optima

B. Local optima

C. Randomized restarts

D. Randomized steps

E. All of the above

iii) Which of the following methods does NOT rely on randomness?

A. Genetic algorithms

B. Contingency planning

C. Monte Carlo tree search

D. Simulated annealing

E. All of the above

iv) STRIPS planning is:

A. Sound

B. Complete

C. Optimal

D. Efficient

E. All of the above

v) Which of the following games has the largest branching factor?

A. Backgammon

B. Checkers

C. Chess

D. Go

E. Tic-Tac-Toe

Part II: Circle the correct answer. [12 points]

i)         A* search is optimally efficient, which means that it always expands fewer nodes in the search tree than other search algorithms. ( True / False )

ii)        A high temperature in simulated annealing favours the strategy of ( exploration / exploitation ).

iii)       ¬“ is ( satisfiable / unsatisfiable / valid ) iff “ is unsatisfiable

iv)       ( Propositionalization / generalized modus ponens / resolution ) is a ( sound / complete )

inference procedure for first-order logic [circle one or more options from each set of options such that the entire statement is true] .

v)        ( Breadth-first-search / depth-first-search ) is preferable to ( breadth-first-search / depth- first-search ) when we expect the tree depth to be deep.

vi)       Simulated annealing is preferable to hill-climbing when we expect a ( low / high ) number of local optima.

vii)      Simulated annealing is ( guaranteed / not guaranteed ) to reach the optimal solution.

viii)     In backtracking search, if an assignment is found to violate the constraints, continue the

search at the ( first / previous ) variable.

ix)       In Minimax, amax player heuristic assumes themin opponent acts ( optimally / sub- optimally / identically to max).

x)        In MCTS’ descent phase, leaf nodes are selected by ( default policy / tree policy / monte carlo ).

xi)       Increasing the UCT scaling constant will ( increase / decrease / not affect ) exploration.

xii)      A statement is said to be satisfiable if it is true in ( a minimum number of interpretations

/ all interpretations / at least one interpretation ).

Question 2: Short Answer [7 points]

a) What is the role of elitism in genetic algorithms?  [2 points]

b) Given the following knowledge base, prove “X” by forward chaining. [3 points]

D ∧ G  X

A ∧ D  F

A

A ∧ C  D

D ∧ F  G

C

Consider the search problem represented by this graph, in which nodes represent locations and edges  represent possible paths between them. Edge weights correspond to the cost of traversing between the nodes attached to that edge, while values above nodes correspond to their heuristic values. The start    node is A and the goal nodes are G1 and G2. Note the search terminates once a single goal node is reached

a)  What is the order of the nodes visited by an iterative depth-first search algorithm with max depth 2? Show the order for each iteration. Assume that the algorithm breaks ties by visiting nodes in alphabetical order. [3 points]

b)  What is the order of the nodes visited by the A* search algorithm? [3 points]

c)   Is the heuristic admissible? Explain your answer. If so, indicate one change in the heuristic function that would make the heuristic inadmissible. If not, indicate changes in the heuristic function that would make the heuristic admissible. [3 points]

Question 4: Game Playing [9 points]

Suppose we have the following game search tree.

a)   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 edge that leads to a subtree that is pruned. [3 points]

b)  Which action should the MAX player take according to minimax strategy, B, C or D? [2 points]

c)   Does the current action order (nodes B,C,D) maximize pruning? If not, how would you order the actions and what additional pruning would be gained? [4 points]

Question 5: Logic [12 points]

a) Translate the following sentences into first-order logic. [4 points]

All wugs are a dreck or apfithy.

Some dreck is apfithy.

b) Convert the above sentences into conjunctive normal form. [4 points]

d) Given the above statements as the knowledge base, show that the claim “Some wug is apfithy” is satisfiable. [4 points]

Question 6: Planning [6 points]

Recall the blocks world setting which we saw in the lecture. In this setting, we can use our mechanical claw to pickup exactly one block at a time. Recall the following predicates and definitions.

Move(b,x, y): Move block b from location x to location y

Clear(x):         Location x is clear.

On(x,y):           x is on top of y

The table can be referred to by the constant TABLE.

We have recently acquired an upgraded claw, which can pickup one block at a time (as before) or pick up and move the top two blocks from a stack at the sametime!

a) Using the STRIPS language, describe the operator MoveTwoBlocks(top, bot,x, y), which represents the action of moving blocks top and bot from location x to location y, where top is the block on top. [4 points]

b) Consider the goal state On(A, B) ∧ On(B,C). If we are using regression planning, what is the search state we would be in after one step in regression planning if the operator applied is a MoveTwoBlocks operator? [2 points]