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)
• Problem 2: Game Playing (20 points)
• Problem 3: Rule-Based Systems (20 points)
• Problem 4: Frames & Inheritance (20 points)
• Problem G: Additional Graduate Credit Problem (20 points).

Problem 1: Search (40 points)

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 YES, explain why.
If your answer is NO, show an example in which the method fails to find an optimal solution even though several solutions exists.

1. Depth 1st Search
2. Breadth 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

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

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

Solutions - By Weiyang Lin

                                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

1. (10 points) Exercise 9.1 (both parts).
2. (10 points) Exercise 9.2.

Solution - By Ganga

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

Problem G: Additional Graduate Credit Problem (20 points)

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.

Solution - By Ganga

A more detailed explanation to be posted soon.