(2 points each) [R+N 4.1] Give the name of the algorithm that results from each of the following special cases:
(a) (15 points, 5 points each) [R+N 6.4] Give precise formulations for each of the following as constraint
satisfaction problems (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)):
(b) (15 points) [R+N 6.5] Solve the following cryptarithmetic problem by hand, using the strategy of back-tracking with forward checking and the MRV and least-constraining-value heuristics (the formulation of the problem is discussed on page 206 of the R+N textbook):
(a) (20 points) [R+N 5.9] This problem exercises the basic concepts of game-playing, using tic-tac-toe as an example. We define Xn as the number of rows, columns, or diagonals with exactly n X's and no O's. Similarly, On is the number of rows, columns, or diagonals with just n O's. The utility function assigns +1 to any position with X3 = 1 and -1 to any position with O3 = 1. All other terminal positions have utility 0. For nonterminal positions, we use a linear evaluation function defined as Eval(s) = 3X2(s) + X1(s) - (3O2(s) + O1(s)).
(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?
(a) (10 points) Identify any nash equilibria, pareto-optimal solutions, dominating strategies, and social welfare maximizing solutions in the following 2 player game:
27,80 | 74,21 | 14,80 | 41,33 |
10,90 | 81,77 | 9,99 | 42,10 |
71,59 | 84,61 | 22,72 | 56,44 |
54,61 | 5,13 | 10,41 | 36,16 |
(b) (10 points) Create your own game for two or more players by specifying a normal form table. Explain the game in English (you don't have to have a great story, but it shouldn't just consist of random payoffs).
State the Nash equilibria of your game and explain why they are the equilibria. Also indicate what the social welfare maximizing strategy sets are for your game. Will rational players maximize social welfare in your game?