CS 63

I. Game Playing (18 points)

Consider a two-player coin-flipping game where two players alternate flipping a fair 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.  During their respective turns, 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 (two moves for each player) expecti-minimax tree for this problem.  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? (Hint: Write small, since this tree is big, and start near a corner of the page.)

II. Knowledge-based Agents (12 points)

(a) Russell & Norvig Exercise 7.11 (a).  (5 pts)   Note: assume that (1,1) is a corner.

(b) Russell & Norvig Exercise 8.16.  (7 pts)

III. Resolution Theorem Proving (25 points)

(a) (8 points) Represent the following knowledge base in first-order logic.  Use the predicates

• attend(x)
• fail(x,t)
• fair(t)
• pass(x,t)
• prepared(x)
• smart(x)
• study(x)
• swarthmore-student(x)

1. Everyone who is smart, studies, and attends class will be prepared.
2. Everyone who is prepared will pass a test if it is fair.
3.  A student passes a test if and only if they don't fail it.
4.  Every Swarthmore student is smart.
5.  If a test isn't fair, everyone will fail the test.
6.  Aidan is a Swarthmore student.
7.  Sandy passed the CS 63 exam.
8.  Aidan attends class.

(b) (7 points) Convert the KB to conjunctive normal form.

(c) (2 points) We wish to prove that

study(Aidan) -> pass(Aidan, CS63-exam)

Express the negation of this goal in conjunctive normal form.

(d) (8 points) Add the negated goal to the KB, and use resolution refutation to prove that it is true. You may show your proof as a series of sentences to be added to the KB or as a proof tree.  In either case, you must clearly show which sentences are resolved to produce each new sentence, and what the unifier is for each resolution step.

IV. Planning Representations (25 pts.)

Our agent is hungry and unhappy, and wants to go on a vacation, sunbathe, and eat well. Our agent starts out rich, but only has limited options, some of which will consume a substantial part of its wealth.

• The static predicates for the domain are:
  • have(car)                   (The agent has a car)
  • distance(x,y,d)          (The distance from x to y is d; distance is assumed to be reflexive; i.e., distance(x,y,d) <=> distance(y,x,d))
  • temp(x,t)                    (The temperature at location x is t)
  • in(r,x)                          (Restaurant r is in city x)
  • beach(x)                    (There is a beach in location x)
  • fastfood(r)                  (r is a fast-food restaurant)
  • swanky(r)                   (r is a swanky restaurant)
• The dynamic predicates for the domain are:
  • at(x,s)                        (The agent is at x in situation s)
  • happy(s)                    (The agent is happy in situation s)
  • hungry(s)                   (The agent is hungry in situation s)
  • rich(s)                        (The agent is rich in situation s)
• (Note that the situation variables will only be used in part (a) of this problem.)
• The constants in the domain are:
  • Phl                          (Philadelphia)
  • Berm                        (Bermuda)
  • OC                            (Ocean City)
  • McDs                        (McDonald's)
  • BK                             (Burger King)
  • CTC                          (Chez Tres Cher)
  • MC                            (Molto Caro).
• The initial state is:
  • at(Phl, s0) ^ ~happy(s0) ^ hungry(s0) ^ rich(s0).
• The static predicates in the KB are:
  • distance (Phl,OC,150)
  • distance(Phl,Berm,500)
  • in(McDs,Berm)
  • in(BK,OC)
  • in(CTC,Berm)
  • in(MC,OC)
  • fastfood(McDs)
  • fastfood(BK)
  • swanky(CTC)
  • swanky(MC)
  • have(car)
  • beach(OC)
  • beach(Berm)
  • temp(Phl,50)
  • temp(OC,60)
  • temp(Berm,80)
• The actions in the domain are as follows:
  • drive(x,y) : The agent can drive from location x to location y if it has a car and the distance from x to y is less than or equal to 200.
  • fly(x,y) : The agent can fly from location x to location y if it is rich and the distance from x to y is greater than 200. Flights are expensive, so after flying, the agent is no longer rich.
  • sunbathe(x) The agent can sunbathe if it is in a location (x) with a beach. The agent will end up happy after sunbathing if the temperature is equal to or above 75, but unhappy if the temperature is below 75.
  • eat(r): If the agent is hungry [i.e., hunger is a precondition], it can eat at a restaurant r that is In the same location as the agent. The agent will end up not hungry, and will be happy if the restaurant is a swanky restaurant. However, it can only eat at a swanky restaurant if it is rich, and at the end of the action, will not be rich any more. (Fast food restaurants don't require richness, and don't change the status of the richness predicate.)

(a) (7 pts.) Describe only the Happy predicate using the situation calculus. You should have one or more possibility axioms (one for each relevant action)  and one or more successor-state axioms (one for each relevant action). Be careful NOT to formulate these as effects axioms. These possibility axioms should characterize how the state of the Happy predicate changes as a result of the actions in the domain, in terms of the domain predicates listed above.
(You may want to refer to pages 330-333 in the book.)

(b) (7 pts.) Describe the actions in this domain as STRIPS operators. Be sure to include all preconditions, add lists, and delete lists.  (See pages 377-378.) You are welcome to use (temp < 75) and other inequalities as valid predicates, even though these are not part of the original STRIPS specification.

(c) (5 pts.) Show two different legal plans (sequences of actions) for achieving the goal described above from the given initial state. (Hint: what is the goal? Frame it in terms of the agent's properties, i.e., happy, hungry, etc.)

(d) (6 pts.) How many legal plans are there for this goal? Explain your answer.  Does the answer change depending on whether or not repeated states are allowed?

V. Partial-Order Planning (20 pts.)

Now suppose that the agent decides to satisfy its Happiness goal using the Sunbathe action. Insert this action into the plan, showing all dependencies. Will this plan succeed? If so, complete the partial plan, resolving any threats that arise. If not, complete the partial plan to the point where planning fails, and explain the source of the failure.