Assignment #2: Search in Games & Knowledge Representation


Assignment #2 consists of 2 parts: The first part is about adversarial search (chapter 6 in the book) whereas the second part deals with knowledge representation (chapter 10). Total credit of this assignment is 100 points.

Due date: Mo 20.12.2004

Part 1: Two-Player Game (Minmax Algorithm) (40 + 10 optional)


The starting position of a simple game is shown below in figure 1. Player A moves first. The two players take turns moving, and each player must move his token to an open adjacent space in either direction. If the opponent occupies an adjacent space, then a player may jump over the opponent to the next open space if any. (For example, if A is on 3 and B is on 4 and it is A's turn, then A may move back to 2 or jump to 5.) The game ends when one player reaches the opposite end of the board. If player A reaches space 6 first, then the value of the game to A is +1; if player B reaches space 1 first, then the value of the game to A is -1.



Figure 1


  • a) Draw the complete game tree, using the following conventions: (20)
    • Write each state as (sA, sB) where sA and sB denote the token locations.
    • Put each terminal state in a square box and write its game value in a circle.
    • Put loop states (states that already appear on the path to the root) in double square boxes. Since it is not clear how to assign values to loop states, annotate each with “?” in a circle.
  • b) Now mark each node with its backed-up minmax value (also in a circle). Explain how you handled the “?” values and why. (10)
  • c) Explain why the standard minmax algorithm would fail on this game tree and briefly sketch how you might fix it, drawing on your answer to (b). Does your modified algorithm give optimal decisions for all games with loops? (10)
  • d) (optional for additional credit) This 6-square game can be generalized to n squares for any n > 2. Prove that A wins if n is even and loses if n is odd. (10)

What to hand in

  • a) A game tree on paper.
  • b) A textual description of the answer for questions (b), (c) and (d).

Part 2: Knowledge Representation (Ontology Construction) (60)


Your mission is to capture, in logical form, enough knowledge to answer a series of questions about the following very simple sentence:

Yesterday Tom went to the Migros Supermarket in the Glattcenter and bougth one kilo of tomatoes and half a kilo of ground beef.

Start by trying to represent the content of the sentence as a series of assertions. You should write sentences that have straightforward logical structure (e.g., statements that objects have certain properties, that objects are related in certain ways, that objects satisfying one property satisfy another and so on). The following might help you get started:

  • Which classes, objects, and relations would you need? What are their parents, siblings and so on?
  • Where would they fit in a more general hierarchy?
  • What are the constraints and interrelationships among them?
  • How detailed must you be about each of the various concepts?


The knowledge base you construct must be capable of answering a list of questions that we will give below. Some of the questions deal with the material stated explicitly in the story but most of them require to have other background knowledge – to read between the lines. You will have to deal with what kind of things are at a supermarket, what is involved with purchasing the things one selects, what will purchases be used for, and so on. Try to make your representation as general as possible. To give a trivial example: don't say “People buy food from Migros,” because this won't help you with those who shop at another supermarket. Don't say “Tom made spaghetti with the tomatoes and ground beef,” because that won't help you with anything else at all. Also, don't turn the questions into answers; for example, question (b) asks “Did Tom buy any meat?” - not “Did Tom buy half a kilo of ground beef?”

Sketch the chains of reasoning that would answer the questions on a sheet of paper. In the process of doing so, you will no doubt need to create additional concepts, make additional assertions, and so on. Many of the things you write might be only approximately correct in reality, but don't worry too much; the idea of this exercise is to extract the common sense that lets you answer these questions at all. A truly complete answer to this question is extremely difficult, probably beyond the state of the art of current knowledge representation. But you should be able to put together a consistent set of axioms for the limited questions posed here.


  • a) Does Tom now have at least two tomatoes? [Yes]
  • b) Did Tom buy any meat? [Yes]
  • c) Are the tomatoes made in the supermarket? [No]
  • d) What is Tom going to do with the tomatoes? [Eat them]
  • e) Does Glattcenter Migros Supermarket sell deodorant? [Yes]
  • f) Did Tom bring any money to the supermarket? [Yes]
  • g) Are there other people in Migros while Tom is there? [Yes – staff!]
  • h) Is Tom a vegetarian? [No]
  • i) Who owns the deodorant? [Migros]
  • j) Did Tom have 200gr of ground beef? [Yes]
  • k) Does the Shell station next door have any gas? [Yes]
  • l) Do the tomatoes fit in Tom's car trunk? [Yes]


What to hand in

  • a) Write down all your background knowledge and assumptions derived from the sentence above. (10 points)
    An example for such a background assumption is: "Tom is a person."
  • b) A semantic network representation (read pages 350-352 in the book) of your knowledge base showing categories, objects, and relations. (26 points)
    Compare figure 10.9 in the book for an example.
  • c) For every question, write your logical chain of reasoning that answers the question. (24 points = 2 points per question)
    As an example consider the statement "Mary has two legs" in respect to figure 10.9. The reasoning chain looks as follows: Mary --member_of--> Female Person --subset_of--> Persons --Legs--> 2