### CS4341 Introduction to Artificial Intelligence  SOLUTIONS 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.
• 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 YES, explain why the method is 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

### Solutions - By Weiyang Lin

• Depth 1st Search: not complete and not guaranteed to output the optimal solution. For example, the first branch of the tree is infinitely long and that branch doesn't contain a solution but other branches do.
• Breadth 1st Search: complete but not guaranteed to output the optimal solution. Because it searches nodes level by level, it has the potential to search all the branches, eventually it will find a solution if a solution exists. But it will find a solution with the least levels, but not necessarily the least cost.
• Depth-limited Search: not complete and not guaranteed to output the optimal solution. Considering the case when the depths of all the solutions are greater than the depth limit.
• Iterative Deepening Search: same as Breadth 1st Search, that is complete but not optimal. It has the potential to search all the branches within the level limit, and it will increase the level limit until it eventually finds a solution. Hence, it is complete. But it will find a solution with least levels, not necessarily least cost.
• Branch-and-bound (= Uniform Cost Search): complete and guaranteed to find the optimal solution. It keeps track of open nodes that could lead to all possible branches, and expand the node that has least cost to get to from the source state. So it has the potential to search all the paths to all the nodes in order of their costs, it will keep searching until it finds a path to the goal.  So the path to the goal with least cost will eventually be found and will be found before other paths to the goal.
• A*: complete and guaranteed to find the optimal solution. Because it keeps track of open nodes that could lead to all possible branches and it will do backtracking when it can not reach the goal along current branch, it has the potential to search all the branches. So it is guaranteed to find a solution if there is one, i.e. it is complete. Also, when A* finds a solution, that solution is guaranteed to have the least f value, which is equal to the actual cost of that solution. Since all estimated costs are underestimates, the f value of a path is not greater than the actual cost of a path. So the cost of the solution it has found is less than the f value of other solutions, and hence the actual costs of other solutions.
• Greedy Search(Best 1st Search): Not complete. Consider the following example:
```		S
/ \
h=20 A   B1 h=10
|    |
h=0 G   B2 h=10
|
B3 h=10
...(infinite branch)

```
then Greedy Search will follow the infinite branch and can not find the solution. Greedy search is not guaranteed to output the optimal solution. Consider the following case, Greedy Search will follow path S->B0->B1->G, which is not an optimal path.

•                                                         S  h= 30
10 / \ 20
h=20 A   B0  h=15
25 |      | 10
h=0  G   B1  h=5
| 10
G  h=0
• Hill-climbing: not complete and not guaranteed to output the optimal solution. Because Hill-climbing doesn't do backtracking, considering the case that Hill-climbing follows a path that does not contain a solution.
• Beam Search: same as Hill-climbing, that is not complete and not optimal. Consider the case that all the paths that Beam Search follows do not contain a solution.

### 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)```

### Solutions - By Weiyang Lin and Ganga

Obviously as an extension it can be seen that each player will make the move which will maximize his chances of winning when he gets to play next. Consequently he will compare the options which he has to make taking into account his position . Following this rule and building the game-tree backwards, we get the following solution.
```to move

A                                     (+1 +2 +3)

/                    \
/                      \

B                  (+1 +2 +3)                                 (-1 +5 +2)

/          \                               /          \
/            \                             /            \

C       (+1 +2 +3)            (+6 +1 +2)            (-1 +5 +2)            (+5 +4 +5)

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

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).

### Solutions - By Weiyang Lin

Part 1
Honest Henry's Apple Wine will be selected. The whole process is as follows:

H1: Serve Bond's Champagne?                        (using B1)
|
it is New Year's Eve
|
expensive wine is indicated
|
|                                               (using B9)
guest should be impressed

fails!

H2: Serve Chateau Earl of Bartonville Red?     (using B2)
|
entree is steak

fails!

H3: Serve Toe Lakes Rose?                            (using B4)
|
entree is unknow

fails!

H4: Serve Honest Henry's Apple Wine?       (using B3)
|
guest is not well liked
|
entree is chicken
|
cheap wine is indicated
|
|                                             (using B10)
wine is indicated
|
|                                             (using B11)
guest is sophisticated

Succeeds!
Honest Henry's Apple Wine is chosen!

Part 2
Yes, it could. For example, with facts:
Guest is sophisticated.
Guest should be impressed.
Entree is Mexican.
Entree is Steak.
You will choose Chateau Earl of Bartonville Red.
Part 3
No. Because to choose carrot juice, you need to have at least two facts:
Guest is a health nut.
Carrots are not to be served.
But with the first fact, you could also choose Glop, which is prior to carrots juice in the hypotheses list. Since you will check the hypotheses in the order they appear in the list, Glop will be checked first, and will be chosen. So carrot juice will never be chosen.

### 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.

### Solution - By Ganga

Ex- 9.1

Part-I

Constructing the fish-hook pairs for topological sorting procedure we get the following table.

 Node Fish-hook pairs Crazy Crazy-Professors, Professors-Hackers Professors Professors-Eccentrics, Eccentrics-Teachers Hackers Hackers-Programmers Eccentrics Eccentrics-Dwarfs Teachers Teachers-Dwarfs Programmers Programmers-Dwarfs Dwarfs Dwarfs-Everything

Using this list we can build the class precedence list as follows

Class-precedence list

Crazy
Professors
Eccentrics
Teachers                           - Procedure to be stored here
Hackers                            - Procedure to be stored here
Programmers
Dwarf
Everything

As is obvious from the class precedence list we can now say that Crazys income slot will be filled from the Teacher's Income slot. Hence his income will be Low.

Part-II

We can use the same precedence-list as above to answer this question. Obviously since Eccentric is closer to Crazy than Teachers and Hackers on the class precedence list, the income slot of Crazy wil be fille using the income slot of Eccentric. Hence in this case his income will be Erratic

Ex 9.2

Considering only the relevant portion of the figure (E9.1 - Pg 647) we get the following fish-hook pairs to determine class precedence

 Node Fish-hook pairs John John-Professors, Professors-Weightlifters Professors Professors-Eccentrics, Eccentrics-Teachers Weightlifters Weightlifters-Athletes, Athletes-Endomorphs Eccentrics Eccentrics-Dwarfs Teachers Teachers-Dwarfs Athletes Athletes-Dwarfs Endomorphs Endomorphs-Dwarfs Dwarfs Dwarfs-Everything

Using this table we can construct the class-precedence list for John as follows.

Class precedence list:

John
Professors
Eccentrics
Teachers
Weightlifters
Athletes
Endomorphs
Dwarfs
Everything