Homework 2

Representations and Methods

810:161

Artificial Intelligence

Fall Semester 2001

Due: Friday, October 12, 2:00 PM

1. In Session 3, we discussed the idea of a reflex agent, which does not have to think about what to do next; it just reacts to its environment with a "stored" answer.

   Suppose that we wanted to build a "reflex" agent to play Tic-Tac-Toe. When this agent is given a board position, it will look its move up in a table of moves. How many entries will the agent need to have in its table? How would you go about finding the entries to store in this table?

2. Consider the following diagram, which shows some states in the search space of a simple 3-by-3 crossword puzzle?

   

   How deep are the goal nodes this search space? Are there any states in the this diagram below which you would not expect to find a goal state?

3. Consider the following diagram, which shows an instance of the 3-puzzle where the initial state and the goal state are as shown.

   

   One set of operators for this problem is { move blank right, move blank left, move blank up, move blank down }.

   Draw the search space for this problem, assuming that whenever we have a choice between two operators we prefer to do them in the order listed above. Which goal state in the tree will depth-first search find? Breadth-first search?

4. Give a heuristic function, h( n ) for any two-person game that you like to play. Is your h( n ) always an underestimate of the distance to a goal? Why or why not?

5. Translate the following sentences into predicate logic:

   • Tom is shorter than Karen.

   • No one is taller than Wilt.

   • Someone is taller than Karen.

   • For any x and y, if x is taller than y then y is shorter than x.