CMSC 471

HOMEWORK THREE
Due 10/15/07 

 

For any problems requiring you to draw the search space or game tree, you can (neatly!) hand-draw these diagrams. However, the rest of your homework should be typed.
Don't forget your statement of sources.

II. Search (30 points)

(1) (10 points) Russell & Norvig Exercise 3.8(a,b). For (b), assume that when a node is expanded, the successor nodes are generated in numerical order.

(2) (10 points) Russell & Norvig Exercise 3.17(a,c).

(2) (10 points) A* terminates when a goal node is selected for expansion. Why shouldn't the search be stopped when a goal node is first generated? Illustrate your answer with an example.

III. Constraint Satisfaction (30 points)

(a) (10 points) Russell & Norvig Exercise 5.1.

(b) (20 points) Russell & Norvig Exercise 5.5. Your formulation should clearly state what the variables are, the domain of each variable, and the set of constraints on the variables.  Your formulation should be general (i.e., it should apply to any set of rectangles, classes, professors, etc.).

IV. Game Playing (40 points)

(1) (20 points) Russell & Norvig Exercise 6.1(a-e).

(2) (20 points) Consider a two-player coin-flipping game where two players alternate flipping a fair two-sided coin.  If the coin lands heads up, the player who flipped gains one point.  If the coin lands tails up, they gain two points.  If a player exceeds three points, they automatically lose all of their points, and the game ends.  At any point, either player can choose to stop the game, in which case both players keep their current scores.  The goal is to beat the other player by as many points as possible.

For example, if Player 1's coin lands tails up, she gets two points.  Player 2 then takes her turn, gets heads, and now has one point. Player 1 decides to stop the game, and wins, beating Player 2 by one point.

Draw the 4-ply (two moves for each player) expecti-minimax tree for this problem.  Using the static evaluation function (score(player1) - score(player2)), back up the leaf values to the root of the tree.  What is the best action for the first player to take?  (Play or stop?)  If player 1 flips tails, what should player 2 do? Why?