Introduction to Artificial Inteligence

Assignment 3


Homework assignment - simulators, agents, search, games, propositional logic

1) Consider the following search problem (also known as
   LEAST-COST PROOF, which is NP-hard).
   You have a list KB of clauses F1,...Fk. Each Fi is of the form:

    l1 or l2 or ... lm

   where the l's are literals, i.e. a propositional variable or its negation.
   You need to apply the operators:  a) resolution b) simplification
   in order to prove a propositional statement (by contradiction).

   Assume that applying resolution costs 2, and
   simplification costs 1 (simplification means: in a clause that contains
   2 or more instances of the same literal - remove one of them. Note that only
   ONE literal is removed at each step (e.g. reducing 3 copies of the same
   litral to 1 copy takes 2 steps).

The problem is: given clauses KB and a sentence Y, find the proof P
that has the least cost. For example, we have the KB consisting of the
clauses:
    C1:  ~P or Q
    C2:  ~R or Q
    C3:  ~Q

and need to prove the sentence Y:   ~P or ~R

(hint - before the search, you need to add a transformed Y into your KB)

 a) Write the above problem as a formal search problem. Note that the
    path cost has to reflect the proof cost.
 b) Consider the heuristic h(n) = number of literals in the shortest
    clause. Is h(n) an admissible heuristic? Prove it.
 c) Find another another admissible heuristic h1 that performs better than h,
    for at least SOME cases (and provide an example or prove that it dominates
    h).
 d) Find a non-admissible heuristic h2 and an example where it performs better
    than h and h1.
 e) Would keeping track of repeated states help in the search algorithm? If so,
    give an example.
 f) Can the algorithm be made more efficient in SPACE requirements, if
    we need to find ANY proof, rather than the shortest proof? How, and
    how much more efficient, asymptotically? 

2) Consider a 3-person complete information game between players A, B, and C,
   playing in turn (first A, then B, then C, and then the game ends).
   The game tree is defined as follows:

   A    B    C      scores
----------------------------
   A1   B1   C1     (100, 5, 20)
             C2     (50, 10, 0)
        B2   C1     (10, 20, 30)
             C2     (20, 0, 50)
   A2   B1   C1     (90, 0, 80)
             C2     (0, 20, 90)
   A3   B1   C1     (90, 0, 20)
             C2     (80, 30, 0)
        B2   C1     (80, 0, 40)
             C2     (0, 0, 0)
        B3   C1     (30, 20, 50)
   A4   B1   C1     (0, 90, 50)
             C2     (20, 70, 70)
        B2   C1     (100, 100, 0)
             C2     (95, 95, 1)
   
   Assume that the scores theoretically achievable by each player are
   all between 0 and  100.
   a) What is the best play for A, assuming that each player is out to improve
      its own score, and there is no communication between players?
   b) If players can reach agreements, will this make any difference
      (answer separately for each different type of agreements).
   c) How will the answer change if A is paranoid (i.e. believe that the other
      players will act to minimize A's score)?
   d) Suppose that B always plays randomly with uniform probability. What
      is the best action by A now?
   e) Will using alpha-beta pruning above (modified alpha-beta in case d)
      save any search in the search algorithm for the best move? What will
      be the savings in each case? Assume
      (and show) the best-case ordering for the search.
   f) How would you treat the problem if C could not observe the move
      made by B?

3) A rational agent has a choice of algorithms to apply for a search problem.
   Suppose the agent need to minimize total operating costs,
   which are given as:  1000 * G + S, where G is the cost of the path taken
   by the agent, and S is the number of search steps used by the search
   algorithm.
   a)  Assuming that the agent knows the above, and reasons to optimize
       the cost, what type of agent is this (reactive? goal-based? etc.).
   b) Assume that the agent has 3 choices:
      1) Use default actions without search, and use an immediately available
         solution with cost 1000.
      2) Use A*, where it has an admissible heuristic that is usually
         wrong by a factor of 2.
      3) Use RTA*, with the same heuristic, and a limit of K search steps.
   We assume that the branching factor is 2, and that the agent knows
   (correctly) that there exists a solution at depth 10. (Assume operator
   cost of 1, and  that the search space is acyclic).

   (Note: there may be insufficient information to answer b, but the point
    is to try to answer, and to figure out what's missing, if anything, and
    what further assumptions may be necessary).


Justify all answers shortly!

Deadline: December 7, 2003, at 11 AM ( strict deadline).