### CS4341 Introduction to Artificial Intelligence  HOMEWORK 2 - C 2000

#### PROF. CAROLINA RUIZ

DUE DATE: Tuesday, Feb. 1 at 5 pm.

• Instructions for Homework 2:
• This is an INDIVIDUAL homework.
• The homework is due Tuesday, February 1, 2000 at 5 pm.
Please turn in the homework using the turnin system OR hand in the homework on paper.

• Homework Problems: This homework consists of four (plus an additional problem for students who are taking this course for graduate credit) problems:

### Problem 1: Search (40 points)

A search method is called complete when it is guaranteed to find a solution if there is one.
A search method is said to produce optimal solutions when the method is guaranteed to output the highest-quality solution (in our case, the least expensive path from the start state to the goal state) when there are several different solutions.

For EACH of the following search methods below, answer both of the following questions two questions:

• Completeness: Is the search method complete?
If your answer is NO, show an example in which the method fails to find a solution even though a solution exists.

• Optimality: Does the search method output optimal solutions?
If your answer is NO, show an example in which the method fails to find an optimal solution even though several solutions exists.

EXPLAIN YOUR ANSWER - No credit will be given to a plain YES/NO answer without the corresponding explanation.

1. Depth 1st Search
3. Depth-limited Search
4. Iterative Deepening Search
5. Branch-and-bound (= Uniform Cost Search)
6. Greedy Search (= Best 1st Search)
7. A*
8. Hill-climbing
9. Beam Search

### Problem 2 (20 points): Game Playing

(Taken from Russell and Norvig's textbook.)

Let us consider the problem of search in a three-player game. You can assume that no alliances are allowed. We will call the players A, B, and C for convenience. The first change is that the evaluation function will return a list of three values indicating (say) the likelihood of winning for players A, B, and C, respectively.

Complete the following game tree by filling out the backed-up value triples (i.e. find correct values for the "??") for all remaining nodes, including the root:

```
to move

A                                     (?? ?? ??)

/                    \
/                      \

B                  (?? ?? ??)                                 (?? ?? ??)

/          \                               /          \
/            \                             /            \

C       (?? ?? ??)            (?? ?? ??)            (?? ?? ??)            (?? ?? ??)

/        \            /        \            /        \            /        \
/          \          /          \          /          \          /          \

A (+1 +2 +3) (+4 +2 +1) (+6 +1 +2) (+7 +4 -1) (+5 -1 -1) (-1 +5 +2) (+7 +7 -1) (+5 +4 +5)
```

### Problem 3 (20 points): Rule-Based Systems

Solve the three parts of Exercise 7.2 of your textbook (p. 639).

### Problem 4 (20 points): Frames & Inheritance

Solve the following Exercises of your textbook (pp. 647-648):
1. (10 points) Exercise 9.1 (both parts).

2. (10 points) Exercise 9.2.

1. (15 points) Propose a general ALPHA-BETA procedure for a three-player game as the one described in Problem 2 of this homework assignment.

2. (5 points) Apply your ALPHA-BETA procedure to the game tree displayed in Problem 2 of this homework assignment.

### HINTS

```
- Problem 1: Remember that the search methods described in class
assume the following things:
- Each node in the search tree has a finite number of children.
- No branch in the search tree contains the same node more than once.
- The search tree may have branches that are infinitely long.
- All costs are positive numbers. In fact you can assume for this
HW that all costs are positive integer numbers.

- Problem 2: The idea of the 3-player game described in this problem
is that each player selects the move that MAXIMIZES his/her own gain
(without worrying about minimizing the other players' gain).
That is, player B selects the move with the highest 2nd component
among all his/her options.

- Problem 3: Notice that:
- The problem statement tell you that BARTENDER uses backward chaining.
- Note that BARTENDER tries to prove the conjectures/hypotheses
in the order in which they appear in the list. That is,

if BARTENDER is expected to serve Bond's Champagne
then it recommends Bond's Champagne
else if it is expected to serve Chateau...Red
then it recommends Chateau...Red
else if it is expected to serve Toe Lakes Rose
then it recommends Toe Lakes Rose
else if  ...

- For Part 2: Note that the working memory should INITIALLY
consist of basic assertions, i.e. assertions that do NOT
appear as the consequence of any of the rules.

- Problem G: A perfectly legal answer to this question is to PROVE
that no such procedure is possible.

```