out 10/4/11, due 10/18/11

*You are encouraged to work on this homework assignment in groups
of up to three students. If you work in a group, you only need to turn in one shared
solution. All students in the group will receive the same grade on the
assignment. If you choose to work in a group, you must actually
produce group solutions, not have each member
work independently on one part of the assignment, then submit the
collection of independent solutions. To acknowledge that you have
worked as intended, you must include the
following statement at the top of the submitted assignment:
*

"We,<students' names>, worked equally as a group on this assignment, and each of us fully understands and acknowledges the group solutions that we are submitting. We understand that we will receive a common grade for this assignment."

(b) (15 points) Russell & Norvig Exercise 3.15 (b,c,e), page 115. Hints: For (b), assume that when a node is expanded, the successor nodes are generated in numerical order. For (e), think about how to reformulate the representation of the goal state in such a way that the action sequence becomes apparent.

(a) (15 points) Explain *in your own words* the terms
*constraint satisfaction
problem*, *constraint*, *backtracking search*, *arc consistency*,
and *min-conflicts*. Full credit will be given only for complete
and well written definitions.

(b) (15 points) Russell & Norvig, Exercise 6.7, page 231.
You should include at least two alternative representations, and
you must include *precise* (mathematical) formulations of your proposed
representations. (A CSP representation specifies the set of variables, the
domains for the variables, and the way in which the constraints will
be represented (intensionally and/or extensionally; you do not have
to enumerate all of the constraints, but should give an illustrative
set of the constraints).)

(a) (20 points) Russell & Norvig Exercise 5.9, pages 197-198.

(b) (20 points) Consider a two-player coin-flipping game where two players alternate flipping a 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. On their turn, a 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 expectiminimax tree for this problem (two moves for each
player). 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?