Introduction to Artificial Inteligence
Mid-term Exam 1 - Solutions
Question 1)
1) FALSE. There are far harder problems in AI than complexity, such as:
knowledge representation...
2) FALSE. To represent states in an unbounded world, need more than
propositional logic alone. Possible solutions: FOL, or
"parametrized" propositional representations.
3) TRUE. By modifying the heuristic, either greedy search or A* can
simulate many other algorithms. To simulate DFS using A*,
we can have f(n) = path_cost(n) + h(n) = -depth(n), i.e.
h(n) = -path_cost(n) - depth(n)
4) FALSE. Typically, hill climbing finds only a local optimum.
Question 2)
1) To solve, simply back up the scores up the tree using max-max-max.
Denoting choices in the (binary) tree by L(eft) and R(ight), top
down, we have:
Value of A:L, B:L = (10,5,0) because 0 is preferred by C over -3
Value of A:L, B:R = (-3,7,10) because 10 is preferred by C over 0
Value of A:L = (-3, 7, 10) because 7 is preferred bu B over 5
Value of A:R, B:L = (-10,0,5) because 5 is preferred by C over 2
Value of A:R, B:R = (0,1,10) because 10 is preferred by C over 5
Value of A:R = (0, 1, 10) because 1 is preferred bu B over 0
Value of root is (0, 1, 10) because A preferes 0 over -3
So A should move R, and will get 0 when B, C play optimally.
The values for B, C playing optimally is also seen at the root:
B will get 1 (by playing R), after A plays R.
C will get 10 (by playing L), after A plays R and B plays R.
2) No pruning possible anywhere here, even theoretically. Since
the games is NOT zero sum, and no prior bounds on values exist,
it is ALWAYS possible for an unexamined terminal to have values
(x, x, x) with x larger than any previously seen values, making
moves in this direction the best move for all playes, and vice versa.
3) If B chooses moves randomly, A should optimize expected utility,
essentially performing an expecti-minimax algorithm.
The values for the one level removed from the bottom remain
the same as in (1). Values for next level are:
Node A:L expected utilities are:
0.5 * (10, 5, 0) + 0.5 * (-3, 7, 10) = (3.5, 6, 5)
Node A:R expected utilities are:
0.5 * (-10, 0, 5) + 0.5 * (0, 1, 10) = (-5, 0.5, 7.5)
Clearly A should choose L to get an expected utility of 3.5,
and C has an expected utility of 7.5 (but clearly should wait to
see what B does before making a choice).
4) Again, no pruning possible, since none of the branches have 0
probability, and the scores are unbounded.
5) With bounds of [-10, 10] pruning may be possible in both the
deterministic and randomized versions. However, since players
may have to make a choice among indifferent outcomes, we will
also need to assume that the OTHER agents search the relevent
subtree in the same order, at least for the deterministic case...
IF this is done, in the deterministic case, looking at the last-but
one terminal node, (0, 1, 10) C can achieve a score of 10 by moving L
here, and will thus not move R. So, B is guaranteed to get 1
by moving R here, independent of the last node. This choice is
better than moving L, which will get 0 for B, because then C will move
L. Thus, A will get 0 by moving R, independent of the values in the
last node, so we can prune the last (rightmost) node - and A should
move R regardless.
Note that the above assumption is necessary here, because if C looked
at the options in a reversed order, and the last node had been
(-10, 2, 10) C would have picked it (possibly), resulting in -10
for A, so A should move L.
In the RANOMIZED case, examining the move L we can see that A gets 3.5.
Now, after examining R,L,L and R,L,R the value of node R,L has -10 for
A. So, independent of the value of the children of R, R, the value
of R for A can be no more than 0.5 * (-10) + 0.5 * 10 = 0,
because value for A at any terminal node cannot be more than the bound
of 10. Therfore, A should move L in any case, pruning node R, R
and its children.
Question 3)
1) Initial state: the given KB (a set of sentences)
Goal state: modified KB including the sentence to be proved
Operators: of 3 types:
a) Apply DeMorgan law to an arbitrary sentence in KB
b) Apply Modus Ponens to an arbitrary sentence and
an implication in KB
c) Apply and introduction between 2
arbitrary sentences in KB
In the first 2 cases, sentences need to match the patterns for
the operators. In all cases, the resulting sentence is added
to KB. (Operators are assumed to be INAPPLICABLE if they add
a sentence already in KB, for reasons of efficiency)
Path cost: sum of costs of applied operators on the path.
(also we assumed and-introduction is only between LITERALS, not
arbitrary sentences).
2) BFS search: in the initial state, only 2 operators are
applicable:
S1: A, B -> A and B (by and introduction, cost 2)
S2: ~(~C or ~D) -> C and D (by DeMorgan, cost 9)
At the next level, nodes are selected arbitrarily, and state S2
is selected - it is a goal state. The result is NOT the cheapest
proof.
3) Using A*, we begin exactly as before, but with different f costs:
S1: A, B -> A and B (by and introduction, cost 1, f(S1)=2)
S2: ~(~C or ~D) -> C and D (by DeMorgan, cost 9, f(S2)=9)
agenda: f(S1)=2, f(S2)=9
A* now picks S1, and expands:
S3: A and B, A and B => C -> C (MP, cost 2, f(S3)=4)
S4: A and B, A and B => D -> D (MP, cost 2, f(S4)=4)
S5: ~(~C or ~D) -> C and D (by DeMorgan, cost 9, f(S5)=10)
agenda: f(S3)=4, f(S4)=4,... (truncated at fcost=9)
A* now picks S3 (S4 also possible...), and expands:
S6: A, C -> A and C (and introduction, cost 1, f(S6)=5)
S7: B, C -> B and C (and introduction, cost 1, f(S7)=5)
S8: A and B, A and B => D -> D (MP, cost 2, f(S4)=6)
S9: ~(~C or ~D) -> C and D (by DeMorgan, cost 9, f(S5)=12)
agenda: f(S4)=4, f(S6)=5, f(S7)=5, f(S8)=6, ...
A* now picks S4, and expands:
S10: A, D -> A and D (and introduction, cost 1, f(S10)=5)
S11: B, D -> B and D (and introduction, cost 1, f(S11)=5)
S12: A and B, A and B => C -> C (MP, cost 2, f(S12)=6)
S13: ~(~C or ~D) -> C and D (by DeMorgan, cost 9, f(S13)=12)
agenda: f(S6)=5, f(S7)=5, f(S10)=5, f(S11)=5, f(S8)=6, f(S12)=6, ...
A* now expands S6, then S7, then S10, then S11, all resulting
in numerous states which we ignore here, generating states with
f-cost at least 6.... Assuming we now get to S8, we have:
S14: C, D -> C and D (and introduction, cost 1, f(S14)=6)
S15: A, C -> A and C (and introduction, cost 1, f(S15)=7)
etc. (all f-costs here greater than 6, as h-value will be 1 for them)
Finally, we get S14 (f-cost 6), which is a goal state. We applied
A, B -> A and B cost 1
A and B, A and B => C -> C cost 2
A and B, A and B => D -> D cost 2
C, D -> C and D cost 1
total cost 6
4) Yes, an optimal solution is assured here, due to the optimality of
A* when applied with an optial heuristic. All we need to prove
is that h(n) is admissible. Now, by definition h(n) = 0 for
goal states, as required. Also, since all operators cost at least 1,
and from a non-goal state n, at least one must be applied to get to
a goal state, h(n) = 1 is optimistic. Thus, h(n) is admissible.