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))