(1) (10 points) Russell & Norvig Exercise 3.8(a,b). Note: For (b), assume that when a node is expanded, the successor nodes are generated in numerical order.
(2) (20 points) Russell & Norvig Exercise 3.17(a,c,e).
(a) (15 points) Define in your own words the terms constraint satisfaction
problem, constraint, backtracking search, arc consistency,
and min-conflicts. (Adapted from Russell & Norvig Exercise
5.1.)
(b) (15 points) Russell & Norvig Exercise 5.13.
(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 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?