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
2 3 5 15 0 1 22 9 1 2 4
1
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 T 2 to evaluate e2(n). Assume the branching factor in the tree is b and T1 < T2. The number of nodes at level d is di=1 bi−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