CSci 4511 Spring 2020
1st Midterm Exam
Wednesday February 26
75 minutes – open book and notes
100 points plus 10 points extra credit
1. 20 points
You are organizing a dinner and have to assign seats to n guests around a round ta-
ble with N places. For every pair of guests there is a positive value Dislike(i, j) that
measures how much guest i dislikes sitting next to guest j. For simplicity assume that
Dislike(i, j) = Dislike(j, i). Your objective is to find the seat assignment that minimizes
the total displeasure of your guests.
1. Formulate the problem as a search problem by defining the state space using an
incremental formulation. Specify how you would represent the states, then specify
the initial state, the goal condition, and the actions.
2. Repeat the previous part but this time using a complete state space formulation.
3. Describe what are the advantages/disadvantages of the two choices for the represen-
atation.
Turn to the next page for more questions
2. 15 points
Suppose you have two admissible heuristics, h1 and h2. You decide to create the following
new heuristic functions defined as follows:
h3(n) = max(h1(n), h2(n))
h4(n) = max(h1(n), 1.1 × h2(n))
h5(n) = min(h1(n), 3 × h2(n))
h6(n) = h1(n) + h2(n)
h7(n) =
h1(n) + h2(n)
2
For each of the new heuristics specify of it is admissible or not. Justify your answer. Would
you use any of these heuristics instead of using h1 or h2?
Turn to the next page for more questions
3. 10 points
In the game of chess, assume a rook can move on the chessboard any number of squares
in a straight line, vertically or horizontally, but cannot jump over other pieces.
Is Manhattan distance an admissible heuristic for the problem of moving the rook from
square A to square B in the smallest number of moves? If yes, explain why, if not why
not.
Turn to the next page for more questions
4. 20 points
1. Are there conditions under which depth-limited search is guaranteed to find an op-
timal (i.e., minimum cost) solution? What about iterative deepening depth-first
search?
2. Under what conditions is breadth-first search guaranteed to find an optimal (i.e.,
minimum cost) solution? Why?
Turn to the next page for more questions
3. Is it possible for alpha-beta pruning and minimax to return different values at the
root of the game tree for the same problem? Explain.
4. Is it more important to have an evaluation function that can be computed fast for
minimax or for minimax with alpha-beta pruning? Why?
Turn to the next page for more questions
5. 15 points
Show the backed-up values for the nodes in the following game tree and show the branches
that are pruned by alpha-beta pruning. For each branch pruned, write down the condition
that is used to do the pruning. Follow the standard convention to examine the branches
in the tree from left to right.
max
min
max
22 91 1 2 4 1015532
Turn to the next page for more questions
6. 10 points
Suppose you decide to use the following strategy to compute the value of a state in a
two-player game: the player plays against itself many times, each time making a random
move until one side wins. Count the number of wins and use it as the value for the state.
Is this a reasonable strategy or not? Explain your reasoning.
Turn to the next page for more questions
7. 10 points
Can a genetic algorithm work if there is no fitness function? Explain briefly what is the
role of the fitness function.
Turn to the next page for more questions
8. 10 points Extra Credit
Assume that generating the children of a node in a game tree takes time C. You are
considering using two evaluation functions, e1 and e2. For any node n, it takes time T1
to evaluate e1(n) and time T2 to evaluate e2(n). Assume the branching factor in the tree
is b and T1 < T2. The number of nodes at level d is
∑d
i=1 b
i−1.
Under what conditions the time neded to search to depth d using e1 will be the same as
the time to search to depth d− 1 using e2?
You reached the end of the exam