CMSC 471

Artificial Intelligence -- Spring 2014

HOMEWORK THREE
out 3/2/14, due 3/25/14


NOTE about deadlines: If you wish, you may turn part or all of this homework by class time on Thursday 3/13 (before spring break). If you do so, then that part of the homework will be returned to you, graded, by Thursday 3/27 at the latest, so that you have it available as a study resource before the midterm.

As stated in the course syllabus, you are permitted (nay, 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, with everyone's name on the assignment. 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.


I. Search (20 points)

(a) (10 points) Russell & Norvig Exercise 3.15. 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.

(b) (10 points) Russell & Norvig Exercise 3.26 (a-e only).

II. Constraint Satisfaction (10 points)

Russell & Norvig, Exercise 6.5. You must show and explain clearly each step of the solution in order to receive full credit.

III. Game Playing (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. Bayesian networks and probability (25 points)

A CMSC 471 student notices that people who drive SUVs (S) consume large amounts of gas (G) and are involved in more accidents (A) than the national average.  She has constructed the following Bayesian network:

(a) (3 pts) Compute P(a, ~s, g) using the chain rule.

(b) (4 pts.) Compute P(a) using inference by enumeration.

(c) (5 pts.) Using conditional independence, compute P(~g, a | s) and P(~g, a | ~s).  Then use Bayes' rule to compute P(s | ~g, a).

(d) (3 pts.) The enterprising student notices that two types of people drive SUVs: people from California (C) and people with large families (F). After collecting some statistics, the student arrives at the BN:

Using the chain rule, compute the probability P(~g, a, s, c, ~f).

(e) (5 pts) Write, in summation form, the formula for computing P(a, ~f) using inference by enumeration.  (You do not need to actually compute the probability.)

(h) (5 pts) Using the rules for determining when two variables are (conditionally) independent of each other in a BN, answer the following (T/F) for the BN given in (c):

  1. I(C,G)
  2. I(F,A | S)
  3. I(C,F)
  4. I(C,F | S)
  5. I(C,F | A)

V. Multi-Agent Systems (25 points)

  1. Game Analysis (15 pts) For each of the three normal-form two-player games below, identify the Nash equilibria (if there are any). Explain why these strategy sets are the Nash equilibria of the game, or why no Nash equilibria exist if this is the case. Also indicate the social-welfare-maximizing strategy sets for each game. Given the Nash equilibria that you've identified, will rational players choose the social-welfare-maximizing strategy set?

    (a) Iterated Prisoner's Dilemma (5 pts)

    C D
    C 3,3 0,5
    D 5,0 1,1

    (b) Rock-Paper-Scissors (5 pts)

    Also called "Roshambo," each player chooses to present one of three objects: rock, paper, or scissors. Rock breaks (beats) scissors; paper covers (beats) rock; scissors cuts (beats) paper. Nobody wins (it's a tie) if both players pick the same object.

    R P S
    R 0,0 -1,+1 +1,-1
    P +1,-1 0,0 -1,+1
    R -1,+1 +1,-1 0,0

    (c) Chicken (5 pts)

    Two drivers are headed for a one-lane bridge. If they both swerve out of the way, they "tie" (nobody scores). If one swerves and the other drives straight on, the "chicken" loses a point and the gutsy driver gains a point. If neither swerves, they both lose big.

    Straight Swerve
    Straight -10,-10 +1,-1
    Swerve -1,+1 0,0

  2. Game Creation (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?

    Do you think that the "tit-for-tat" strategy, which has been used successfully with the IPD, would work well for a player in your game? Why or why not?