Q1 Adversarial/Game Search In the following image, the upward-pointing triangles correspond to maximizer nodes and the downward-pointing triangles correspond to minimizer nodes

Q1 Adversarial/Game Search

In the following image, the upward-pointing triangles correspond to maximizer nodes and the downward-pointing triangles correspond to minimizer nodes. The leaf nodes represent the utility value at each path's respective terminal state in the game (Similarly to how it is constructed in figure 5.2 on page 164 of the Russel&Norvig book). 

Q1.1

1 Point

What is the minimax value at the root node of this tree?

Save Answer

Q1.2

4 Points

List all the branches in the tree that will be pruned by the alpha-beta algorithm.

Save Answer

Q2 Constrained Search Problems

6 Points

Suppose that you work for the CS department and are responsible for scheduling five classes. The timings for these classes have already been chosen:  Your goal is to assign faculty to teach these five classes. The following professors have expressed interest in teaching the listed courses: 

Q2.1

3 Points

Formulate this as a CSP by stating the variables, domains, and all the constraints.

Variables:

Domains:

Constraints:

Save Answer

Q2.2

3 Points

Solve the CSP using backtracking search with the three heuristics discussed in lecture to answer the following questions (Hint: First draw a constraint graph of the problem, then apply each heuristic in the proper order for each step).

Which class is assigned what professor in the first step?

Which class is assigned what professor in the second step?

Which class is assigned what professor in the third step?

Save Answer

Q3 Alpha-Beta Pruning

2 Points

Which of the following are true about alpha–beta pruning? (select all that apply)

 Choice 1 of 4:Its efficiency is highly dependent on the order in which the states are examined

 Choice 2 of 4:In the worst case, it takes longer than Minimax to solve the same tree

 Choice 3 of 4:In the best case, it can solve a tree roughly twice as deep as minimax in the same amount of time

 Choice 4 of 4:Pruning only ever happens with leaves

Save Answer

Q4 Node-consistency

1 Point

A CSP is node-consistent when..

 Choice 1 of 4:Every value in its domain satisfies the variable’s unary constraints Choice 2 of 4:Every value in its domain satisfies the variable’s binary constraints Choice 3 of 4:All of the above

Choice 4 of 4:None of the above

Q5 Arc-consistency

A CSP is arc-consistent when..

 Choice 1 of 4:Every value in its domain satisfies the variable’s unary constraints Choice 2 of 4:Every value in its domain satisfies the variable’s binary constraints Choice 3 of 4:All of the above Choice 4 of 4:None of the above