$1.20$ points

State space representation. You want to place $8$ queens on a board, so that no queen attacks any other queen. This requires that no two queens share the same row, column, or diagonal. You need to formulate the problem as a search problem and show two different formu$-$lations: $(1)$ an incremental formulation and $(2)$ a complete state formulation. For each formulation define the states, the initial state, the goal condition, and the actions.

$2.20$ points

You decide to search the state space of your given problem using a tree$-$like and not a graph search, even if the state space is a graph. Answer the questions briefly but precisely:

$1.$ Will the uniform cost search algorithm still work correctly? If not, why not?

$2.$ What would you gain by using a search tree instead of a search graph $($e$.$g$,$ memory, amount of computations, etc$)?$

$3.$ Will the optimality of the solution be guaranteed or not?

$4.$ Will the search terminate when there is no solution?

$3.20$ points

Answer the following questions, justifying briefly but precisely your answers:

$1.$ What would happen to A$*$ if the test for the goal condition was done at the time a

node is generated?

$2.$ Will uniform cost always expand more nodes than A$*?$

$3.$ Does breadth$-$first search always find an optimal solution?

$4.$ In A$*$ will a heuristic that dominates another one expand fewer nodes?

$4.15$ points

In the following game tree show the branches that are pruned by alpha$-$beta pruning. For

each branch pruned, write the condition with the specific values used to do the pruning. Show the values backed up by the search algorithm $($no need to track alpha and beta at each step$).$ At the end indicate which move will be selected by the MAX player. Follow the standard convention to examine the branches in the tree from left to right.

$5.15$ points

Answer the questions briefly and explain your reasoning:

$1.$ Could you replace simulated annealing with a random search?

$2.$ If you use local beam search with k$=1,$ is the search the same as hill$-$climbing?

Turn to the next page for more questions

$3.$ Can you use a genetic algorithm with a population of only two elements?

$6.10$ points

One of the steps in Monte Carlo Tree Search is the expansion of a chosen node.

$1.$ What is the role of expansion and when does it terminate?

$2.$ What happens after the expansion step?

$7.10$ points Extra Credit

This question is on bidirectional search using the uniform cost search algorithm. Do you need to keep track of two different frontiers, one for the forward direction and the other for the backward direction, or can you keep only one frontier and always expand the node with the smallest cost? Do you need to keep track of any other information? Be specific and explain your reasoning.

$4.15$ points

In the following game tree show the branches that are pruned by alpha$-$beta pruning. For each branch pruned, write the condition with the specific values used to do the pruning. Show the values backed up by the search algorithm $($no need to track alpha and beta at each step$).$ At the end indicate which move will be selected by the MAX player. Follow the standard convention to examine the branches in the tree from left to right.