Introduction to Artificial Inteligence
Mid-term Exam 1 - Solutions
Question 1)
1) TRUE. Defined as an algorithm for energy function minimization.
Ransom moves (esp. at higher temperatures) escape from
local minima).
(If you wrote: "FALSE, because simulated annealing escapes
from local MAXIMA" then your answer is still essentialy correct).
2) FALSE. The fact that the environment is dynamic (adversary) does not
allow you to do A* search over the state space.
(Note that A* over STRATEGY SPACE is still possible, but this
was ruled out in the question).
3) TRUE. Once you know the response of the adversary for each board
state, you can model the problem by using "extended operators"
that map from state to next state after both your move and
the oposing move, making this a standard search problem over
a static domain.
4) FALSE. The expression ( A => (B => C)) is equal to (~A or ~B or C)
which clearly has 7 satisfying models.
Question 2)
a) FOL representation:
1. Forall(x) Pres(x,Iran) => (~RF(x) => Psycho(x))
2. Forall(x,a,s) (RF(x) and Does(x,a)) => Ruin(Result(a,s))
Note: if you used the 3-position does predicate, simply use
Does(x, a, s) above instead.
3. Forall(x) Psycho(x) => Exists(s,a) (Does(x,a) and Ruin(Result(a,s)))
Note: again, if you used the 3-position does predicate, simply use
Does(x, a, s) above instead.
b) Conversion to CNF:
1. ~Pres(x, Iran) or RF(x) or Psycho(x)
2. ~RF(x) or ~Does(x,a) or Ruin(Result(a,s)
Due to the "and" this decomposes into two clauses at the end:
3a. ~Psycho(x) or Does(x,Ruinous_action_of(x))
3b. ~Psycho(x) or Ruin(Result(Ruinous_action_of(x),State_of(x)))
where Ruinous_action_of(.) and State_of(.) are Skolem functions,
appropriately named for better human intuitive understanding.
c) We need to add the fact "for some situation, an action done
by a president of Iran results in ruin", i.e. in FOL:
Exists (x, a, s) Pres(x,Iran) and Does(x,a) and Ruin(Result(a,s))
(Again, those who use the 3-argument Does predicate, simply use it
above instead of the 2-argument predicate).
Negating the above gives us:
~Exists (x, a, s) Pres(x,Iran) and Does(x,a) and Ruin(Result(a,s))
Converting to CNF gives us (using DeMorgan and removing universals):
Q'. ~Pres(x,Iran) or ~Does(x,a) or ~Ruin(Result(a,s))
Now we can continue with the refutation proof.
Resolving Q' with 3a, unifier {a|Ruinous_action_of(x)}
(we cheated a little, we should have stanardized the x's apart and
then added a substitution, but we are safe being lazy here), we get:
4. ~Psycho(x) or ~Pres(x, Iran) or ~Ruin(Result(Ruinous_action_of(x),s))
Resolving 4 and 3b, unifier {s|State_of(x)} we get:
~Psycho(x) or ~Psycho(x) or ~Pres(x, Iran)
which simplifies to:
5. ~Psycho(x) or ~Pres(x, Iran)
Resolving 5 with 1, empty unifier, results in:
~Pres(x, Iran) or ~Pres(x, Iran) or RF(x)
which simplifies to:
6. ~Pres(x, Iran) or RF(x)
Resolving 6 with 2, empty unifier, results in:
7. ~Pres(x, Iran) or ~Does(x,a) or Ruin(Result(a,s)
Resolving 7 with Q', unifier: {a|Ruinous_action_of(x)}
we get, after simplification:
8. ~Pres(x, Iran) or ~Does(x,a)
We can continue doing resolutions, but in this case we will never
be able to get rid of the term "~Pres(x,Iran)", because there
is no term in the KB and Q' which has its contrapart "Pres(x,y)".
Also, getting rid of this term is necessary - this can be shown by
running "relaxed resolution" on sentences made up of just propositional
symbols instead of predicates.
Therefore, one cannot reach a contradiction, and Q does not
follow from the KB.
d) Since the entire KB and negated query do not contain any unit clauses,
we cannot use unit resolution at all, and cannot proceed. Since
we do not have the empty clause ab-initio, the proof fails.
e) Clause 1 is necessary for the proof. Since it is not a Horn clause,
it is not available as input to backward chaining, and the proof
fails.
Question 3)
a) Tree values for minimax will be as follows:
A , val B , val A, val
----------------------------------
L 4 L 4 L -5
R 4
R 5 L 0
R 5
M 4 L 4 L 2
R 4
R 10 L 8
R 10
R 6 L 6 L -10
R 6
R 6 L 6
R 2
Best move for A from starting position is the right most branch (R),
for a min-max score of 6.
b) Pruning (alpha-beta):
A , val B , val A, val
----------------------------------
L 4 L 4 L -5
R 4
R 5 L 0
R 5
M 4>= L 4 L 2
R 4
R pruned L pruned (A knows it does not need M now)
R pruned
R 6 L 6 L -10
R 6
R >=6 L 6
R pruned (A knows B it will not pick R now)
c) With B a random agent with uniform prob:
A , val B , val A, val
----------------------------------
L 4.5 L 4 L -5
R 4
R 5 L 0
R 5
M 7 L 4 L 2
R 4
R 10 L 8
R 10
R 6 L 6 L -10
R 6
R 6 L 6
R 2
Best move for A from starting position is the center branch (M), for
an expected score of 7.
d) In general, pruning is possible in such cases, but here the conditions
for pruning will not apply.
e) In this case, in 50% of the cases it will choose the optimal
outright. In the remaining 50% it will choose randomly, and since
in this example it always has 2 possibilities, it will have 50%
to pick the optimal (out of the 50% random case). So, in toto,
B will pick the optimal move with probability 0.75, and the other
move with probability 0.25 (in cases of equality, it actually
does not matter what B picks). The resulting scored tree is, thus:
A , val B , val A, val
----------------------------------
L 4.25 L 4 L -5
R 4
R 5 L 0
R 5
M 5.5 L 4 L 2
R 4
R 10 L 8
R 10
R 6 L 6 L -10
R 6
R 6 L 6
R 2
Best move for A from starting position is the right branch (R), for
a score of 6.