CMSC 471

Artificial Intelligence -- Fall 2012

HOMEWORK THREE
out 10/4/12, due 10/16/12


I. Local Search (10 points)

(2 points each) [R+N 4.1] Give the name of the algorithm that results from each of the following special cases:

  1. Local beam search with k=1.
  2. Local beam search with one initial state and no limit on the number of states retained.
  3. Simulated annealing with T=0 at all times (and omitting the termination test).
  4. Simulated annealing with T=infinity at all times.
  5. Genetic algorithm with population size N=1.

II. Constraint Satisfaction (30 points)

(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)):

  • Rectilinear floor-planning: find non-overlapping places in a large rectangle for a number of smaller rectangles.
  • Class scheduling: There is a fixed number of professors and classrooms, a list of classes to be offered, and a list of possible time slots for classes. Each professor has a set of classes that he or she can teach. Assign every class to a professor.
  • Hamiltonian tour: given a network of cities connected by roads, choose an order to visit all cities in a country without repeating any.

    (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):

    III. Game Playing (40 points)

    (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)).

    1. Approximately how many possible games of tic-tac-toe are there?
    2. Show the whole game tree starting from an empty board down to depth 2 (i.e., one X and one O on the board), taking symmetry into account.
    3. Mark on your tree the evaluations of all the positions at depth 2.
    4. Using the minimax algorithm, mark on your tree the backed-up values for the positions at depths 1 and 0, and use those values to choose the best starting move.
    5. Circle the nodes at depth 2 that would not be evaluated if alpha-beta pruning were applied, assuming that nodes are generated in the optimal order for alpha-beta pruning.

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

    IV. Game Theory (20 points)

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