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)
  • 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).
  • HINTS: HINTS

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.

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

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

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)

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.

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