Introduction to Artificial Inteligence

Quiz 1 - answers


0. An intelligent agent has to answer 3 questions in a quiz on AI, what is
   the optimal time allocation and pruning on the search space for solutions?
   (most people have flunked this part of the quiz), solution to this
   question embedded in the rest of the answers.

1. In the anti tic-tac-toe game, the current position is:

          |   | X  
       ---+---+---
        O | O |   
       ---+---+---
        X |   | X  

1.1: The game tree up to the terminal nodes: we will use the notation
        (who's move: position)
     to denote the new move in each case. Board position to be read by the
     path from the state up to the current move. Position is denoted by (x,y),
     where x is from the right and y from the top.
     Thus, we have the following tree (omitting the initial position). Tree
     also includes values for terminal nodes.

     MAX       MIN         MAX

     O:(1,1)  X:(2,1)    O:(2,3)     X:(3,2)      Value: 1 (win for O)  
                         O:(3,2)                  Value: -1 (win for X)
              X:(3,2)                             Value: 1 (win for O)
              X:(2,3)                             Value: 1 (win for O)

     O:(2,1)  X:(1,1)    O:(2,3))                 Value: -1 (win for X)
                         O:(3,2))                 Value: -1 (win for X)
              X:(3,2)                             Value: 1 (win for O)  *
              X:(2,3)                             Value: 1 (win for O)  *

     O:(2,3)  X:(1,1)     O:(2,1)                 Value: -1 (win for X)
                          O:(3,2)                 Value: -1 (win for X)
              X:(2,1)     O:(1,1)     X:(3,2)     Value: 1 (win for O)  *
                          O:(3,2)                 Value: -1 (win for X) *
              X:(3,2)                             Value: 1 (win for O)  *

     O:(3,2)              Value: -1 (win for X)


1.2  Optimal ordering for alpha-beta is exactly as above. Now, if the program
     does NOT know the maximal value of the game, it will compute the whole
     subtree rooted at O:(1,1) to get an alpha value of 1. Then, all branches
     marked * can be pruned, as in each case X is guaranteed a win and
     thus it is sure that O will not make that move.

     If, in addition, the program knows the bounds of 1 on game score,
     it need only evaluate the subtree rooted at O:(1,1), but without
     the sub-branch O(3,2),  because it can never get a score higher than
     1 elsewhere!

1.3 Clearly, optimal move is O:(1,1).

1.4 If we have a RANDOM player, we need to look at the tree as an EXPECTI-MAX
    tree rather than MINIMAX. But we can save a lot of work by computing
    BOUNDS. Since move O:(1,1) forces a win against ANY moves by the
    oppenent, this move also has an EXPECTED VALUE of 1 (anything higher is
    impossible). Thus, no need to check anything else, the best move against
    a random opponent is STILL O:(1,1) !

1.5 If we cannot see the response by the opponent, we MIGHT wish to model
    this as a random move - and thus use an "expecti-mini-max" tree. However,
    that will unfortunately be incorrect. The problem here is that the state
    is not currently observable, NOT that it is stochastic. And since there
    is an intelligent agent as an opponent, not a random process, we cannot
    use the expecti-mini-max to obtain optimum. This is a HARD problem, but
    then you were NOT required to find the solution here!



2   Resolution theorem proving in CNF propositional logic.

2.1 The given KB as a CNF (listed as separate clauses, with
    conjunction between clauses written as commas, for convenience):

       A ,  ~A v B ,  ~B v C ,  ~C v D ,  ~E ,  ~A v D v E

2.2 First, resolve the last two clauses to get  ~A v D
    Then, resolve the clause A with the above to get D

2.3 This is optimal because there is no 0-step proof (obvious).
    We can prove that there is no one-step proof by trying all possible
    resolution steps from the initial KB:
       1st and 2nd clauses: result B
       2nd and 3rd clasues: result ~A v C
       3rd and 4th clauses: result ~B v D
       1st and last clauses: result D v E

    The above list (including the one in 2.2) are all possible applications
    of resolution in the original KB, and none of the produce a one-step
    proof. Thus, the proof in 2.2 is the shortest (though there may be,
    and in fact there IS, another 2-step proof).
    The "direct" proof: A -> B -> C -> D requires THREE steps.

2.4 First, we show that h(n) is an admissible heuristic. It is exact
    for a goal state - since if the KB contains the result, h(n)=0.
    The resolution operator on CNF can only at most decrease the size of a
    conjunct by 1, (and even that only if one of the conjuncts is of UNIT
    size). Since the heuristic measures the size of the SMALLEST disjunction,
    containing the goal literal minus 1, this heuristic is clearly OPTIMISTIC.
    Thus, the heuristic is ADMISSIBLE. Therefore, A* is guaranteed to find
    the optimal solution, i.e. a shortest proof IF it exists using only
    resolution steps.

    Admissability of h(n) allows for a shorter proof in 2.3 - for the original
    KB we have h(n) = 1. The only clause with distance 1 is ~C v D, but
    no single resolution step on this clause can produce D, and thus the
    children of the original KB under A* must all have h(n) = 1. Since
    h is optimistic, the solution length is at least 2!
    
3.  Situation calculus question. This is a VERY simple domain. The axioms
    required are:

    If the robot grabs an object, it will be holding it as a result:

    (forall x, s)  holding(x, result(grab(x), s)

    If the robot is holding an object, it will still hold it after it
    grabs an object (whether the same object or not is immaterial):

    (forall x, y, s) holding(x, s) => holding(x, result(grab(y), s))

    If the robot executes exit in a situation where it is holding exactly
    2 object, it will be in a situation wher wins is true:

    (forall s) ((exists x, y) holding(x, s) ^ holding(y, s) ^ ~(x=y) ^
                   (forall z) ~holding(z, s) v z=x v z=y) =>
               wins(result(exit, s))

    Since the above contains complicated nesting of quantifiers, there
    are several equivalent variants...