WPI Worcester Polytechnic Institute

Computer Science Department
------------------------------------------

CS4341 Introduction to Artificial Intelligence 
HOMEWORK 2 - C 2000

PROF. CAROLINA RUIZ 

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


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:

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

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.

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.

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.