TEST 1 CS724

Instructor Dr P Juell    NAID______________________ NAME__________________________
100 points, closed book                                  Feb. 6, 2001

1. (20) In large game tree such as chess and Go we can not afford to go all the way to leaf in a search. What is required to allow us to stop after say 5 plies to the search.

   Does the above technique effect the answer quality? Explain.

2. (20) Write a lisp program to produce the logical difference of two lists. For example if the input was
   (setdif '(a b c d e) '(d a)) the output would be (b c e). You can write as many functions as you want/need. Also (equal 'a 'b) will return t if the two are the same. To do this, you will probably want to write a function called member that checks if an item is in a list.

3. (20) For the following tree, Goal states have an -G after the node number. If you need edge costs, they are given. Specify which, if any goal will be found by each search technique. (The node numbers are 1, 2, 3, 4-G, 5, 6-G, 7-G, 8, 9, 10-G).

   Depth first ____________

   Breadth first __________

   Branch and Bound _______

                             1
                         /   |  \
                        /    |    \
                      /3     |3     \5
                     /       |       \
   		 2        3         4-G
                   / \     /  \      /  \
                 / 3 4\   /2  1\   /1   3\
   	     5     6-G 7-G  8  9    10-G
   

4. (20) The following AND/OR represents ways to solve a problem. List (or circle) the names of the leaves that would be visited (used) if you want to visit a minimum number of leaves.

    
                                        o
    
                         ------------------------------ 
    
                    o            o               o               o
    
               ---------                      -------
    
            o       o     o   o      o      o    o     o     o         o
                    
                   ---             ----   ---        ----             -----
        a   b  c   d  e   f   g    h   i  j   k  l   m   n o  p  q   r  s   t
   

5. (20) FOPC has a frame problem. FOPC is used to represent the real world. Why is there not a frame problem in the real world?

6. (20) For the blocks world, you are to change the program so you can not place an object on another object, if they are both the same color. Where in the program would you make this change, and what would your code do?

   Someone suggested that you do this in the move function. What problem would this create, and how can this be solved?