Introduction to Artificial Inteligence

Assignment 3 - SOLUTIONS


1) Consider the following search problem (also known as the WEIGHTED ABDUCTION
   problem, which is NP-hard). You have a list KB of weighted
 of propositional Horn clauses, i.e. clauses of the form:
          X1 and X2 and ... and Xn  implies Y
 where each clause C has a weight w(C). For some rules, n=0, i.e.
 nothing is required to imply Y. A proof is defined as a set of clauses P
(from KB), such that if C is in P, then all propositions in the body of C
 must also be in the head of some clause C' in P. In addition, proof P
 is a proof of X if X is also in the head of some clause C' in P.
 The weight (or cost) of a proof P is
 the sum of costs of all the clauses in P. The problem is: given clauses KB and
 proposition Y, find the proof P (subset of KB) for Y that has the least cost.

 a) Write the above problem as a formal search problem. Note that the
    path cost has to reflect the proof cost.

Answer:
   Initial state: Empty set of clauses P, proposition Y to prove.
   Final state:   Set of clauses P obeying above conditions.
   Path cost:     Sum of weights of clauses in P.
   Operators:     Add a clause from KB to P.
     (Improved version of operators - limit operators to select:
         a.  only clauses NOT already in P, and
         b.  only clauses which have in their head a proposition Y
               which appears in the body of a clause in P, but not
               in the head of any clause in P)

 b) If we represent the state in a node as a set of clauses P (that is
    not necessarily a proof), we consider the following heuristic:
          h(P) = sum of the costs of all clauses in P
    Now, we run the A* algorithm on this problem, using the above h as
    a heuristic. Is the algorithm guaranteed to find the least-cost proof?
    PROVE you answer.

Answer:  The path cost is exactly the sum of costs in P, which is NOY
         optimistic, and we cannot claim the heuristic is addmissible.
         However, we have: f(n) = g(n) + h(n) = 2g(n).
         Since this is a constant factor of g(n), the node ordering in
         search is EXACTLY the same as if we had f(n) = g(n) = g(n) + 0.
         Thus, the search with A* behaves AS IF we had h(n) = 0 for all
         n. Now, h(n) = 0 is admissible (exact for goal, optimistic
         for everything else), thus A* is guaranteed to find the optimal
         answer.

    (As discussed in class: clue - what would happen if we used as a heuristic
     h(P) = 0 for all P? How would the search be different, if at all?)

 c) This sub-question also serves as an example for the above. Suppose that
    the give clauses in the knowledge base (KB) are:

         C1:  A and B implies X         (with cost 5)
         C2:  B and C implies X         (with cost 7)
         C3:  D implies B               (with cost 1)
         C4:  D implies C               (with cost 1)
         C5:  E implies A               (with cost 10)
         C6:  E implies D               (with cost 1)
         C7:  E                         (with cost 2)
         C8:  Y implies X               (with cost 1)
         C9:  Y                         (with cost 20)

    Note that here, the set of clauses P = {C8, C9} is a proof of X,
    because X is at the head of rule C8, and Y is at the head of rule C9,
    and there are no other propositions mentioned in P. The cost of P is 21.

      Show all the steps of the search using A* on the above problem, where
   we need to find the least-cost proof for X.

Answer: we will specify in the state only the DELTA, i.e. the clause added
    from the parent, in order to save space (and time!). Also, we will assume
    that our set of operators is the IMPROVED version above (the simple
    version is also correct, but will require a lot more search!)

    Initial state S0 = empty set of clasues, cost 0 (pushed before loop).

    In first loop - get S0 from agenda (unsupported: X),
     put (in following order):
        S1: added C8, cost 1
        S2: added C1, cost 5
        S3: added C2, cost 7

      agenda now (state:cost): S1:1, S2:5, S3:7

    In 2nd loop, get S1 (= C8) - (unsupported: Y) put:
        S4: added C9, total cost 21

      agenda now: S2:5, S3:7, S4:21

    In 3rd loop, get S2 (= C1) - (unsupported: A, B), put:
        S5: added C3, total cost 6
        S6: added C5, total cost 15

      agenda now: S5:7, S3:7, S6:15, S4:21

    In 4th loop, get S5 (= C1, C3) - (unspported: A, D), put:
         S7: added C6, total cost 7
         S8: added C5, total cost 16

      agenda now: S3:7, S7:7, S6:15, S8:16, S4:21

    In 5th loop, get S3 (= C2) - (unsupported: B, C), put:
         S9: added C3, total cost 8
         S10: added C4, total cost 8

      agenda now:  S7:7, S9:8, S10:8, S6:15, S8:16, S4:21

    In 6th loop, get S7 (= C1, C3, C6) - (unsupported: A, E), put:
         S11: added C7, total cost 9
         S12: added C5, total cost 17

       agenda now: S9:8, S10:8, S11:9, S6:15, S8:16, S12:17, S4:21

     In 7th loop, get S9 (= C2, C3) - (unsupported: C, D), put:
         S13: added C4, total cost 9
         S14: added C6, total cost 9

       agenda now: S10:8, S11:9, S13:9, S14:9, S6:15, S8:16, S12:17, S4:21

     In 8th loop, get S10 (= C2, C4) - (unsupported: B, D), put:
          adding C3: (prune, identical with S13, so do not add)
          S15: adding C6, total cost 9
  
       agenda now: S15:9, S11:9, S13:9, S14:9, S6:15, S8:16, S12:17, S4:21

     In 9th loop, get S15 (= C2, C4, C6) - (unsupported: B, E), put:
           S16: adding C3, total cost 10
           S17: adding C7, total cost 11

       agenda now: S11:9, S13:9, S14:9, S16:10, S17:11,
                   S6:15, S8:16, S12:17, S4:21
        From now on not showing anything with cost more than 12...

     In 10th loop, get S11 (= C1, C3, C6, C7) - (unsupported: A), put:
            S18: adding C5, total cost 19

        agenda now (truncated):  S13:9, S14:9, S16:10, S17:11, ...

     In 11th loop, get S13 (= C2, C3, C4) - (unsupported: D), put:
            adding C6 - identical with S16, so don't add

        agenda now (truncated):  S14:9, S16:10, S17:11, ...

     In 12th loop, get S14 (= C2, C3, C6) - (unsupported: B, E), put:
           adding C4 - identical with S16, so don't add
           S19: adding C7, total cost 11

        agenda now (truncated):  S16:10, S17:11, ...

     In 13th loop, get S16 (= C2, C3, C4, C6) - (unsupported: E), put:
           S20: adding C7, total cost 12

        agenda now (truncated):  S17:11, S20:12, ...

     In 14th loop, get S17 (= C2, C4, C6, C7) - (unsupported: B), put:
           adding C3 - identical with S20, so don't add

        agenda now (truncated):  S20:12, ...

     In 15th loop, get S20 (= C2, C3, C4, C6, C7) - (unsupported: none).

        This is a goal state, so return S20, which is the cheapest proof for X.

 d) Consider the following heuristic h'(P):
         h'(P) = h(greedy_extension(P)-P)
    where greedy_extension(P, KB) is computed as follows:
      greedy_extension(P, KB) {
         P' = P;
         while(P' is not a proof and P' not = KB) {
             Find an arbitrary C in P', and Z in the body of C, such that
               Z does not appear as the head of any rule in P'. (Intuitively:
               some Z that is not "justified" in P'.)
             From all the given rules in KB, find the lowest-cost
               rule C' that has Z as its head, and add C' to P'.
             If there is no such rule, return KB.
         }
         return P'
       }

    (note change from original - as discussed in class. Now h'(P) is
     just the cost of the ADDED rules in the extension).

     Is the above heuristic computable in polynomial time? Is it addmissible?
     Prove your answers!

Answer: the heuristic is computable in polynomial time, since finding Z at
    each step takes time polynomial in size of P', and so does searching KB
    for the clause C'. Number of passes through loop is at most equal
    to number of propositions, so total runtime of heuristic is polynomial
    in size of KB and P'. Size of P' is also at most quadratic in number
    of propositions.

    This heuristic is NOT addmissible. For example, consider the following KB,
    when looking for least-cost proof of X:
       C1: Y for a cost of 10
       C2: A implies Y for a cost of 1
       C3: A for a cost of 100
       C4: X for a cost of 20
       C5: Y imples X - cost 1

    For the state S1 = (C5), the heuristic will return P' = C2, C3
    and a heuristic cost of 101, which is pessimistic, resulting in
    preference of the state S2 = (C4), costing 20. However, in fact S1
    has a child S2 = (C1, C5), which is a goal state, and only costs 11.
         
2) Consider a 4-person game with complete information, where the score is
   computed for PAIRS that are defined in advance. That is, the players are
   A, B, C, D, and AC are a pair, BD are the other pair. The score for
   each member a pair are the same, and is NEGATIVE of the scores for the
   other pair. For example, if A scores 100, C also scores 100, B scores -100
   and D scores -100. Assume that players take turns in the order A, B, C, D,
   repeatedly, until the game ends.

 
   a) Write an algorithm for optimal play by player A.

Answer: since C is the partner in a complete information game, and C, D are
opponents, by reasons of symmetry this is exactly like a 2-person game.
Also, since the game is zero-sum, we can just use the minimax algorithm!
However, this also requires that our partner C play optimally!

   b) If A cannot communicate with C, and vice-versa, is your algorithm
      still optimal?

Answer: yes, because the entire prior state can be observed.

   c) Modify your algorithm so that it is optimal for A, but where B
      makes moves randomly with uniform probability.

Answer:
Here we need to implement a variant of the expecti-minimax algorithm. Use
3 functions: maximize, minimize, and expectation.


3) Give an example of a 3-ply game tree (branching factor 3)
   where alpha-beta pruning saves NOTHING, and another where the savings
   is maximal. How many nodes are pruned in each case?


Answer:

   We will denote MAX moves by 1,2,3 and MIN moves by a, b, c.
   For the BEST-CASE pruning (assuming no global bound on scores), the
   tree might be (printed bottom-up left to right, in order of search:

   1, a, 1     value 100
   1, a, 2     value  50
   1, a, 3     value  20

   1, a        value is max of above, 100

   Now, search proceeds to:

   1, b, 1     value 200

   So score of 1,b is at least 200, so MIN will never pick b,
   we can prune 1, b, 2  and 1, b, 3

   Now, search proceeds to:

   1, c, 1     value 300

   So score of 1,c is at least 300, so MIN will never pick c,
   we can prune 1, c, 2  and 1, c, 3

   Now, search proceeds to:

   2, a, 1     value 50
   2, a, 2     value 30
   2, a, 3     value 20

   So, score of parent (MAX move) is:

   2, a        value 50

   So, MIN can always choose a, resulting in a score less than 100,
   which MAX can achieve by chosing move 1. So MAX will never choose 2,
   we can thus prune 2, b and 2, c and all their children.

   Now, search proceeds to:

   3, a, 1     value 0
   3, a, 2     value 20
   3, a, 3     value 30

   So, score of parent (MAX move) is:

   3, a        value 30

   So, MIN can always choose a, resulting in a score less than 100,
   which MAX can achieve by chosing move 1. So MAX will never choose 3,
   we can thus prune 3, b and 3, c and all their children.
   Total pruning achieved: 16 terminal nodes and 4 non-terminal nodes.

  To sum up, the tree is:

  1, a, 1           100
  1, a, 2            50
  1, a, 3             0
  1, b, 1           200
  1, b, 2    don't care
  1, b, 3    don't care
  1, c, 1           300
  1, c, 2    don't care
  1, c, 3    don't care
  2, a, 1            50
  2, a, 2            30
  2, a, 3            20
  2, b  and children - don't care
  2, c  and children - don't care
  3, a, 1             0
  3, a, 2            20
  3, a, 3            30
  3, b  and children - don't care
  3, c  and children - don't care


A 3-ply, branching factor 3 tree where no pruning is achieved is, e.g.:

  1, a, 1           20
  1, a, 2           21
  1, a, 3           22          (1, a value = 22)
  1, b, 1           15
  1, b, 2           16
  1, b, 3           17          (1, b value = 17)
  1, c, 1           10
  1, c, 2            9
  1, c, 3           12          (1, c value = 12,  1 value = 12)
  2, a, 1           5
  2, a, 2           4
  2, a, 3           50          (2, a value = 50)
  2, b, 1           0
  2, b, 2           1
  2, b, 3           32          (2, b value = 32)
  2, c, 1           2
  2, c, 2           1
  2, c, 3           22          (2, c value = 22, 2 value = 22)
  3, a, 1           0
  3, a, 2           1
  3, a, 3           62          (3, a value = 62)
  3, b, 1           0
  3, b, 2           5
  3, b, 3           57          (3, b value = 57)
  3, c, 1           12
  3, c, 2           13
  3, c, 3           41          (3, c value = 41, 3 value = 41 (best))