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."
Please be sure to include all group members' names on the 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?