AI MidTerm 1, solutions ---------------------------- Question 1: ----------- 1) True. IDA* expands each node expanded by A* numerous times, but requires memory only linear in search depth. (Claim of "false" but stating that this is due to thrashing of A* in a memory hierarchy due to not fitting in main memory gets full credit). 2) True. Given a correct neigborhood function and sampler, and slow enough schedule, optimum found with probability 1. (Unfortunately, this is not a very practical result!) 3) False. Trivial example: if there is a complete subtree where the first player gets maximal score, immaterial of opposing play, all siblings of the subtree can be pruned. 4) False. In a dynamic environment, time to action (hence decision) may be very important, and A* may take a LONG time. In many cases a suboptimal action done quickly is better than the optimal done too late! Question 2: ----------- Let us number the clauses in the KB as follows: 1: A, 2: ~AvB, 3: ~BvC, 4: ~AvD but also one to be added later, for convenience: 5: ~AvC 6: B We will denote steps below numbers denoting resolved clauses, and the resulting clause. a) The full tree is below (on its side). Note that we do not write "MAX and MIN" as this is NOT a zero-sum game! Player 1 Player 2 Player 1 Player2 Scores (1-4) D (1-2) B (3-6) C (12, 1) (2-3) ~AvC (1-5) C (3, 12) (3-6) C (3, 12) (2-3) ~AvC (1-5) C (12, 2) (1-2) B (1-5) C (2, 13) (3-6) C (2, 13) (1-2) B (3-6) C (1, 11) (1-4) D (3-6) C (12, 1) (2-3) ~AvC (1-5) C (3, 12) (3-6) C (3, 12) (2-3) ~AvC (1-5) C (12, 2) (3-6) C (12, 2) (1-4) D (1-5) C (3, 12) (3-6) C (3, 12) (2-3) ~AvC (1-5) C (2, 11) (1-4) D (3-6) C (13, 1) (1-2) B (1-5) C (3, 11) (3-6) C (3, 11) (1-2) B (1-4) D (1-5) C (3, 12) (3-6) C (3, 12) (1-5) C (13, 1) (3-6) C (13, 1) b) Internal node scores are as follows (ommiting the clauses used to get a new clause, for brevity). Player 1 Player 2 Player 1 Player2 D (12, 2) B (12, 1) C (12, 1) ~AvC (3, 12) C (3, 12) C (3, 12) ~AvC (12, 2) C (12, 2) B (2, 13) C (2, 13) C (2, 13) B (1, 11) C (1, 11) D (12, 1) C (12, 1) ~AvC (3, 12) C (3, 12) C (3, 12) ~AvC (12, 2) C (12, 2) C (12, 2) D (3, 12) C (3, 12) C (3, 12) ~AvC (2, 11) C (2, 11) D (13,1) C (13, 1) B (3, 11) C (3, 11) C (3, 11) B (13, 1) D (3, 12) C (3, 12) C (3, 12) C (13, 1) C (13, 1) Clearly, player 1 should resolve clauses 1 and 4 to get D, assuring that it gets 12 (any other option will get less than 10). c) Since this is not a zero-sum game, pruning is problematic. However, it is clear that at most 4 clauses can be generated here, and only one involves a shortest clause of 2 literals. Thus, the sum of scores of BOTH players is at most 10+5=15. The maximum for a winning player is 13, and the maximum for a losing player is 3. Also, once the 2-point operator was used, by the opposing player, the maximum for a win is 12 (and 2 for a loss). Therefore, the pruned branches are as follows (marked with *): Player 1 Player 2 Player 1 Player2 D (12, 2) B (12, 1) C (12, 1) ~AvC (3, 12) C (3, 12) C (3, 12) * ~AvC (12, 2) C (12, 2) B (2, 13) C (2, 13) C (2, 13) * B (1, 11) C (1, 11) D (12, 1)* C (12, 1) ~AvC (3, 12) C (3, 12) C (3, 12) ~AvC (12, 2)* C (12, 2) C (12, 2) D (3, 12) C (3, 12) C (3, 12) ~AvC (2, 11) C (2, 11) D (13,1)* C (13, 1) B (3, 12) C (3, 12) C (3, 12) B (13, 1)* D (3, 12) C (3, 12) C (3, 12) C (13, 1) C (13, 1) * The ordering is optimal. Note that player 1, after scanning most of the 1st tree, can see that it gets 12 or more. In the other sub-trees, once it is obvious that player 2 has a "bonus-winning" move, then player 1 is known NOT to be able to force a "bonus-winning" move, and thus the rest can be pruned. In the first sub-tree, the two terminal nodes are pruned because player 1 can see that the "heavier" resolution (gain 2) was already used, so there is no sense to look once there is a loss in that branch. d) Tree repeated below, scores computed as expectimax (in some cases, the branches for player 2 have the same score, so it does not matter whether it is adversarial or random!) Player 1 Player 2 Player 1 Player2 D (12, 1.5) B (12, 1) C (12, 1) ~AvC (3, 12) C (3, 12) C (3, 12) ~AvC (12, 2) C (12, 2) B (2, 13) C (2, 13) C (2, 13) B (8.3, 4.7) C (1, 11) D (12, 1) C (12, 1) ~AvC (3, 12) C (3, 12) C (3, 12) ~AvC (12, 2) C (12, 2) C (12, 2) D (3, 12) C (3, 12) C (3, 12) ~AvC (9.3, 4.3) C (2, 11) D (13,1) C (13, 1) B (3, 11) C (3, 11) C (3, 11) B (13, 1) D (3, 12) C (3, 12) C (3, 12) C (13, 1) C (13, 1) Although the score for player 1 has improved for the last 2 choices, producing D on the first round is still optimal for player 1. Question 3: ----------- a) In this case, Manhattan distance is no longer admissible. Proof by counterexample - consider the following state, which Manhattan distance heuristic returns 2, but is 1 step away from the goal: 1 2 3 4 6 7 8 5 b) If moving on a diagonal costs 2, then Manhattan distance is again admissible. Proof: as in the standard case, each operator moves at most a single tile. Each operator can either: reduce the Manhattan distance by at most 1, or reduce the Manhattan distance by at most 2, but then always at a cost of 2. c) Using sum of infinity norms (as distances of tiles from their final position) is admissible (i.e. maximum(delta x, delta y) ). Again, this is because each operator can change this quantity by 1 at most. We will call this heuristic hi(n), where i stands for "infinity norm". d) Initial state has h(n0) = 3. 1 2 3 7 6 n0, hi(n0) = 3, f(n0) = 3 4 8 5 It is not a goal state, so it is expanded, resulting in 5 children: 1 2 3 4 7 6 n1, hi(n1) = 2, f(n1) = 3 8 5 2 3 1 7 6 n2, hi(n2) = 4, f(n2) = 5 4 8 5 1 3 2 7 6 n3, hi(n3) = 4, f(n3) = 5 4 8 5 1 2 3 7 6 n4, hi(n4) = 3, f(n4) = 4 4 8 5 1 2 3 8 7 6 n5, hi(n5) = 4, f(n5) = 5 4 5 The best is n1, which is not goal, so it is expanded, and has only 3 children: 1 2 3 7 6 n6, hi(n6) = 3, f(n6) = 5 (same state as initial) 4 8 5 1 2 3 4 6 n7, hi(n7) = 1, f(n7) = 3 7 8 5 1 2 3 4 7 6 n8, hi(n8) = 3, f(n8) = 5 8 5 The best now is n7, which has 8 children: 1 2 3 4 5 6 n9, hi(n9) = 0, f(n9) = 3 7 8 1 2 3 4 Y 6 n10-n16, hi(n1X) = 2, f(n1X) = 5 7 8 5 (Shorthand for moving any tile EXCEPT for 5). The best is n9, which is a goal state, so A* returns it and halts, after only 3 expansions.