Artificial Intelligence: Problem Set 2

Assigned: Sep. 19
Due: Sep. 26

Problem 1

What is the result of doing alpha-beta pruning on the game tree below? What move should MAX make? What is the value of the game for MAX?

MAX should make the second move. The value of the game is 7.

Problem 2

Consider the following set of sentences in the propositional calculus.
P => (Q < = > R).
W^R => ~Q.
X => Q V R.
P ^ ~W => X
X => W.
~P => R.
A. Convert the above sentences to CNF.
1. ~P V ~Q V R
2. ~P V Q V ~R
3. ~Q V ~R V ~W
4. Q V R V ~X
5. ~P V W V X
6. W V ~X.
7. P V R.

B. Show how the Davis-Putnam procedure finds a satisfying assignment over these sentences. In tracing the algorithm, when you come to a branch point, you should make an assignment to the lowest atom alphabetically, and attempt the assignment of TRUE before the assignment of FALSE.

Set S0.
1. ~P V ~Q V R
2. ~P V Q V ~R
3. ~Q V ~R V ~W
4. Q V R V ~X
5. ~P V W V X
6. W V ~X.
7. P V R.

Try P=T.  Delete ~P from 1,2,5; delete 7.

Set S1
1. ~Q V R
2. Q V ~R
3. ~Q V ~R V ~W
4. Q V R V ~X
5. W V X
6. W V ~X.

Try Q=TRUE. Delete ~Q from 1, 3; delete 2, 4.
Set S2
1. R
3. ~R V ~W
5. W V X
6. W V ~X.

1 is a singleton, set R=TRUE. Delete ~R from 3, delete 1.

3. ~W
5. W V X
6. W V ~X.

3 is a singleton, set W=FALSE. Delete W from 5,6, delete 3.
5. X
6. ~X.

5 is a singleton, set X=TRUE. Delete X from 6, delete 5.

6. empty

6 is the empty clause.  Return to S1 and set Q=FALSE. Delete Q from
2,4, delete 1,3.
 
Set S3
2. ~R
4. R V ~X
5. W V X
6. W V ~X.

2. is a singleton, set R=FALSE. Delete R from 4, delete 2.
4. ~X
5. W V X
6. W V ~X.

4 is a singleton, set X=FALSE. Delete X from 5, delete 4,6.

5. W

5 is a singleton, set W=TRUE.  Delete 5.  There are no more clauses, so
we succeed with the current assignment:

P=TRUE, Q=FALSE, R=FALSE, W=TRUE, X=FALSE.