# 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?