1) Game Playing:
a) Assume that you have the following game tree:
4
C
3 4 2
6 3 9 4 2 9 8
(1) Show the backed up values for each node when minimax searching is done. What will be the first move that is made in the game?
The tree has been annotated.
The first move that max will make is to the middle child.
(2) Show which nodes would be pruned when minimax searching is done with alpha beta pruning.
The two rightmost leaf nodes will be
pruned. Once node G is explored, we are
certain that max will not want to go to its rightmost child, because min can
get a score of 2, which is worse for max than the middle choice.
(3) What happens if G is the rightmost child of node C? Show which nodes would be pruned in this case.
No nodes would be pruned.
(4) Define: ply, horizon effect, terminal test,........
Look up these and other bold words
in your book.
2) Propositional Logic:
a) Which of the following sentences are valid, unsatisfiable or neither:
i) ((p => q) => p) => p
|
p |
q |
p => q |
(p =>q)=>p |
((p => q)=>p)=>p |
|
0 |
0 |
T |
F |
T |
|
0 |
1 |
T |
F |
T |
|
1 |
0 |
F |
T |
T |
|
1 |
1 |
T |
T |
T |
It is always true, therefore it is
VALID.
ii) (p V q) ^ (~p V q)
|
p |
q |
p V q |
~p V q |
(p V q) ^ (~p V q) |
|
0 |
0 |
F |
T |
F |
|
0 |
1 |
T |
T |
T |
|
1 |
0 |
T |
F |
F |
|
1 |
1 |
T |
T |
T |
It is sometime true, therefore it is neither valid nor unsatisfiable.
b) Given a vocabulary of 3 propositions – A,B,C , show the models (worlds that the sentence is true) for the following sentences:
i) A V C
|
A |
B |
C |
A V C |
|
0 |
0 |
0 |
F |
|
0 |
0 |
1 |
T |
|
0 |
1 |
0 |
F |
|
0 |
1 |
1 |
T |
|
1 |
0 |
0 |
T |
|
1 |
0 |
1 |
T |
|
1 |
1 |
0 |
T |
|
1 |
1 |
1 |
T |
There are six models for the above
sentence.
Another way to look at it is: A V C is true
for 3 combinations of values of A and C.
Since there is another proposition B, each of these 3 combinations can be
true for any value of B, yielding 3 * 2 = 6 models.
ii) (A ^ C) => B
|
A |
B |
C |
A ^ C |
(A ^ C) => B |
|
0 |
0 |
0 |
F |
T |
|
0 |
0 |
1 |
F |
T |
|
0 |
1 |
0 |
F |
T |
|
0 |
1 |
1 |
F |
T |
|
1 |
0 |
0 |
F |
T |
|
1 |
0 |
1 |
T |
F |
|
1 |
1 |
0 |
F |
T |
|
1 |
1 |
1 |
T |
T |
It is true in 7 models.
c) Use modus ponens and forward chaining to derive Q from the following KB:
A
B
C
A ^ B => C
A ^ C => W
W ^ C => F
F ^ A => Q
Use A with B to derive C.
Use A with C to derive W.
Use W with C to derive F.
Use F with A to derive Q.
d) Which inference procedures are complete and sound for propositional logic? Why might we use one inference mechanism over another?
Truth table inference is both sound
and complete. Many inference rules such
as Modus Ponens and And
Introduction etc. can be shown to be sound.
Resolution is refutation complete.
If the KB contains only Horn clauses then forward chaining or backward chaining (Modus Ponens) are sound and complete.
The truth table entails enumerating
all possibilities; this can be inefficient. Deriving a proof by applying sound
inference rules may ignore many irrelevant propositions, and may be much more
efficient. Resolution can be directed by
the goal sentence, and does not have to explore all propositions, either.
See your book for more details on
this.
3) First Order Logic
a) Assume the following knowledge base:
i) Noone hates Sam. Ax ~hate(x,Sam)
ii) Jack hates all women. Ax female(x) => hates(Jack,x)
iii) If a person is not female, he is male. Ax ~female(x) => male(x)
We wish to find out if Sam is male(Samuel or Samantha?).
The query is therefore: male(Sam)?
Use resolution to prove the query.
First we must put all the sentences
into CNF:
i) ~hate(x1,Sam) We only had to drop the
universal quantifier.
ii) ~female(x) V hates(Jack,x2) Eliminate implication, standardize variables,
and remove universal quantification.
iii)female(x3)
V male(x3)
This was done by elliminating the implication,
standardizing the variables and then dropping the universal quantifier.
Negate the goal and put it into
CNF ~male(Sam)
Resolve:
~hates(x1,Sam) ^
(~female(x2) V hates(Jack,x2) )
^ (female(x3) V male(x3)) ^
~male(Sam)
Resolve female(x3) V male(x3) with ~male(Sam)
with theta = {x3/Sam}
to get: female(Sam)
Resolve ~hatex(x1,Sam) with ~female(x2) V hates(Jack,x2) with theta = {
x1/Jack,x2/Sam} to get: ~female(Sam)
Resolve the two clauses that we just
obtained to get the empty clause. Hence
we proved that our query is entailed by the KB and male(Sam) is true.
b) Put the following sentence into FOL:
All csc731 students are intelligent.
Ax csc731stud(x) => intelligent(x)
or if you wish to use
other predicates:
Ax student(x) ^ takes(x,CSC731) => intelligent(x)