Introduction to Artificial Inteligence

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 t-c-tac-toe geme, the current position is:

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

1.1: The game tree up to 2-ply: we will use the notation (who's move: poistion)
     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).

     Thus, we have the following tree (omitting the initial position). Tree
     also includes values for terminal nodes.

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

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

     X:(3,2)  O:(1,1)   X:(3,3)      Value: 1 (win for X)
                        X:(2,3)
                        X:(2,1)
              O:(2,1)   X:(3,3)      Value: 1 (win for X)
                        X:(2,3)
                        X:(1,1)
              O:(3,3)   X:(1,1)      (leads to value 0: draw)
              O:(2,3)   X:(3,3)      Value: 1 (win for X)
                        X:(1,1)
                        X:(2,1)

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

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

Note that the 2nd move for X is not required for full credit here.

1.2  Optimal ordering for alpha-beta will examine first the best move for
     X, i.e. X:(3,2), and within it O:(3,3). Later on, in each other move
     but X:(3,2) examine first O:(3,2) which gets -1, and all the other
     branches can be pruned, as X will never choose these moves anyway
     (since X can never do worse than lose -1 anyway). In short, all lines
     with no evaluation above denote branches that are pruned - never
     evaluated.

1.3 Clearly, optimal move is X:(3,2).

1.4 If we have a RANDOM player, we need to look at the tree as an EXPECTI-MAX
    tree rather than MINIMAX. We can save a lot of work by computing BOUNDS,
    as follows.

    Move X:(3,3) will result in move O:(3,2) and a loss for X with probability
    1/4. All other moves by O will result in a win for X, probability 3/4.
    Expected utility is 3/4 - 1/4 = 1/2

    Move X:(3,2) will result in move O:(3,3) in 1/4 of the cases, and
    in some other move in 3/4 of the cases. In these LAST cases X will win
    by playing X:(3,3) and win. In the FORMER case, O:(3,3) X may or may
    not win, but will NOT BE CERTAIN TO LOSE, and thus in that case it is
    clear that X will NOT have utility -1. Thus, we have expected utility
    GREATER then 1/2

    Any other move by X: will result in an immediate loss 1/4 of the time,
    and is NOT a sure win in all the remaining cases, and thus the expected
    utility is LESS than 1/2

    Thus, the optimal move is still X:(3,2). Of course, one can get this
    answer by expanding the complete tree...

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 To define a formal search problem, need to define STATES (including initial
    as well as goal-state or goal test), OPERATORS, PATH COST. For finding
    shortest proof, we have:

       States are the modified KB - each state is a CNF formula.

       INITIAL STATE:  A KB in CNF consisting of the given KB
                       + the NEGATION of the theorem to be proved.

       GOAL TEST:      Check if the state (the modified KB) has an empty
                       clause, if it does - return true, else false.

       OPERATORS:      If any 2 disjunctions a,b, can be resolved on some
                       literal c, generate a new state
                       by copying the KB and adding the clause resulting
                       from applying the resolution operator.
                       The operators are thus any application of resolution and
                       adding the result to the KB.

       PATH COST:      Add 1 for each application of the resolution operator.

2.2    Since the heuristic returns 0 on any KB with the empty clause, it is
       exact for goal states. Since applying resolution to pure disjunctions
       can only at most decrease the size of a disjunction by 1, (and
       even that only if one of the disjunctions is of UNIT size), and since
       the heuristic measures the size of the SMALLEST disjunction, this
       heuristic is clearly OPTIMISTIC. Thus, the heuristic is ADMISSIBLE.

2.3    Initial state is:      (AvC) ^ (~C) ^ (AvDvE) ^ (BvC) ^ (~Av~B)

       where the last clause results from the negation of the theorem to
       be proved, and with a heuristic value of 1 (since the size of the
       smalles clause, ~C, is 1.
       Now, using A* we expand by all possible applications of resolution.
       Note that the states contain the ENTIRE KB and with the result ADDED,
       and NOTHING DELETED. However, for conciseness, I will only denote
       the ADDED clause.

       Children of the initial state add:
       1) A
       2) Cv~B
       3) B
       4) Cv~A
       all with a heuristic value of 1 and f-cost of 2. Now, any of these
       can be elected for expansion, as A* is indifferent to which. Suppose
       we choose 1 - to get (note we can STILL get everything we got above,
       except for A, which is already in the KB):
       1.1) ~B
       1.2) Cv~B
       1.3) B
       1.4) Cv~A
       all with a heursitic cost of 2 and f-cost of 3. So now A* must expand
       2, with all children having f-cost of 3:
       2.1) A
       2.2) ~B
       2.3) B
       2.4) Cv~A
       2.5) CvC  (=C - and assume we allow this optimization to get C)
       Expanding 3, we get (with f-cost 3):
       3.1) A
       3.2) Cv~B
       3.3) ~A
       3.4) Cv~A
       Expanding 4, we get (with f-cost 3):
       4.1) A
       4.2) Cv~B
       4.3) B
       4.4) CvC    (=C)
       4.5) ~A
       4.6) CvDvE
       Now we need to expand all the above, getting numerous states. Among
       them will be some children of 2.5 and 4.4, which will generate the
       empty clause from C and ~C, and a proof length of 3. If we are not
       allowed to reduce CvC to C, a few more steps will be needed...

2.4    Note that A* is a HORRIBLE algorithm, since it BACKTRACkS to some
       other state which may contain (setwise) fewer clauses. However, in
       a monotonic logic, the state is also monotonic and there is NO NEED
       to ever backtrack (as long as ANY proof will do)!
       It is enough to always add all clauses generated, and their parents,
       and not worry about backtracking. There are other optimizations related
       to search efficiency, but the above is clearly paramaount.


3      True-false questions.

3.1    FALSE - the greedy algorithm sorts only according to h(n), which here
               is negative g(n) - resulting in a "farthest first" search
               (equal to DEPTH first search if arcs all cost 1).

3.2    FALSE - random elements in genetic algorithm help it escape from local
               optima.

3.3    TRUE - to represent change need a HUGE number of propositions and
              axioms, possibly even UNBOUNDED. This problem does not occur
              in FOL.

3.4    FALSE - calculate the number of possible board positions, which is HUGE.
               However, noting that checkers is NOT a solved game, it is clear
               that if we can fir all board positions on a home computer a 
               simple run of MINIMAX would take linear time in that number
               and checkers would have been a solved game.

3.5    FALSE - there is exactly ONE model, vid.  A=T, B=T.