(Note - minor fixes March 3, as discussed in class March 2)
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.
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.
(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.
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!
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.
b) If A cannot communicate with C, and vice-versa, is your algorithm
still optimal?
c) Modify your algorithm so that it is optimal for A, but where B
makes moves randomly with uniform probability.
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?
Deadline: April 6, 2003, at 11 AM ( strict deadline).