CS4341 Introduction to Artificial Intelligence. B-2003
SOLUTIONS Exam 1 - November 24, 2003

By Prof. Carolina Ruiz, Matt Jarvis, and Peter Mardziel
Department of Computer Science
Worcester Polytechnic Institute

Instructions

Problem I. Search (20 points)

Suppose that you need to find a path between S and G in the following graph. The number attached to each edge in the graph represents the COST of traversing the edge. The number inside each node represents a heuristic under-estimate of the distance of the node to the goal G.

For EACH of the following search methods list the nodes in the order in which they are EXPANDED by the search method while looking for a solution. Also, show the search tree (or show the sequence of queue states instead if you prefer) as it is constructed by the search method. When everything else is equal, order the nodes in alphabetical order.

  1. (9 points) A*
  2. (8 points) Greedy Search (= Best 1st Search)
  3. (8 points) Hill-climbing

Problem II. Search (15 points)

In this problem, you are asked to state an exhaustive list of conditions under which one would prefer a search strategy over another. An illustration is provided below.
  1. (0 points) Prefer breadth-first search over depth-1st search 
      

    •  A shallow solution (path from initial state to goal state) is preferred.

    •  or the search tree may contain large or possibly infinite branches

    •  or if abundant  memory space to store  the search tree (or the queue)
  is  available.
  2. (5 points) Prefer A* over branch-and-bound 
      

    • A good heuristic that underestimates the distance to the goal is available.

    • Runtime matters.

    • Space is a concern.
  3. (5 points) Prefer hill-climbing over greedy search 
      

    • Very little memory is available to store the search tree.

    • Backtracking isn't necessary to find the solution.
  4. (5 points) Prefer iterative deepening over depth-first search 
      

    • A shallow solution is preferred.

    • The search tree may contain large or infinite branches.

    • There is a time limit on the search.

Problem III. Game Playing (20 points)

Assume that your are playing 2 dimensional tic-tac-toe on a 3x3 board. You are the "X" player, it is your turn to move, and the current board configuration is depicted below: 
              |   |
           ------------
            X | O |  
           ------------
            X | O  | O
Assume also that the utility function is given by: 
                                              /
                                              |  10,  if "X" wins
  utility of a terminal board configuration = |   0,  if it is a draw
                                              | -10,  if "O" wins
                                              \

Use the minimax procedure TOGETHER WITH ALPHA-BETA PRUNING to select your next move. Mark with the word "PRUNE" the nodes/branches that don't need to be evaluated (and don't expand those unnecessary branches) . Show your work on an adversarial search tree and explain your answer.

Solutions by Peter Mardziel

  • red boards are maximizers
  • blue boards are minimizers

    10
         
    x o  
    x o o
    10
    x    
    x o  
    x o o
    -10
      x  
    x o  
    x o o
    -10
    o x  
    x o  
    x o o
    PRUNE
      x o
    x o  
    x o o
    PRUNE
      x  
    x o o
    x o o
    -10
        x
    x o  
    x o o
    -10
    o   x
    x o  
    x o o
    PRUNE
      o x
    x o  
    x o o
    PRUNE
        x
    x o o
    x o o
    -10
         
    x o x
    x o o
    -10
    o    
    x o x
    x o o
    PRUNE
      o  
    x o x
    x o o
    PRUNE
        o
    x o x
    x o o

    Problem IV. Rule-Based Systems (20 points)

    Consider the following set of rules for identifying animals.

    The working memory contains the following assertions: Solve the following problems. Show your work.

    1. (10 points) Use backward chaining to determine whether or not hobbes is a tiger. Construct a tree showing the steps followed by backward chaining and show when and how the working memory is updated during the depth 1st search. 
      
BACKWARD CHAINING:

  hobbes is a tiger                ?x is a tiger
          |
          |  R4       
          |
  hobbes has black stripes         ?x has black stripes 
          |
          |  succeeds due to A1
          |
  hobbes is a carnivore            ?x is a carnivore 
          |
          |  R3 
          |
  hobbes eats meat                 ?x eats meat 
          |
          |  succeeds due to A2
          |
  hobbes is a mammal               ?x is a mammal 
          |
          |  R1 
          |
  hobbes gives milk                ?x gives milk 

             succeeds due to A4


hence the working memory is updated with:
   A6: hobbes is a mammal  
   A7: hobbes is a carnivore
   A8: hobbes is a tiger

    2. (10 points) Use forward chaining to derive ALL assertions that are derivable from this knowledge base (that is, from the set of rules together with the assertions in the working memory). Construct all trees showing the steps followed by forward chaining and show when and how the working memory is updated during the process. 
      
FORWARD CHAINING:

R1:  hobbes gives milk                      ?x gives milk 
         
             succeeds due to A4
  

     WM := WM + {A6: hobbes is a mammal}    ?x is a mammal 


R2:  tweety has feathers                    ?x has feathers 
          |
          |  succeeds due to A3
          |
     tweety flies                           ?x flies 
          |
          |  succeeds due to A5
          |
     tweety lays eggs                       ?x lays eggs 

             fails


      hence rule R2 is not triggered.


R3:   hobbes eats meat                      ?x eats meat 
          |
          |  succeeds due to A2
          |
      hobbes is a mammal                    ?x is a mammal 
           
             succeeds due to A6
           

      WM:= WM + {A7: hobbes is a carnivore} ?x is a carnivore


R4:   hobbes has black stripes              ?x has black stripes 
          |
          |  succeeds due to A1
          |
      hobbes is a carnivore                 ?x is a carnivore 
          
             succeeds due to A7
          

      WM:= WM + {A8: hobbes is a tiger}     ?x is a tiger  
     

Applying again R1, R2, R3, R4 does not yield any new assertions
and so the forward chaining process stops.

    Problem V. Logic-Based Systems (20 points)

    Consider the following set of axioms: