Problem Set 2

Assigned: Feb. 1.
Due: Feb. 15.

Problem 1

Show the results of applying alpha-beta pruning to the following game tree. What is the best move for MAX at the top level?

Answer: The best move for MAX is the right-hand branch, for a value of 10. The pruned tree is shown below.

Problem 2

Convert the following sentences in the propositional logic to clausal form.
P <=> (Q ^ ~R).
W => P.
R <=> S.
S => P.
P => (~(Q V W) V S).

Answer: 1. ~P V Q.
2. ~P V ~R.
3. P V ~Q V R.
4. ~W V P.
5. ~R V S.
6. R V ~S.
7. P V ~S.
8. ~P V ~Q V S.
9. ~P V ~W V S.

Problem 3

Trace the action of the Davis-Putnam algorithm applied to the clauses in problem 2.

Answer

~W is a pure literal, so set W=FALSE and delete 4 and 9.

Set S1:
1. ~P V Q. 
2. ~P V ~R. 
3. P V ~Q V R. 
5. ~R V S. 
6. R V ~S. 
7. P V ~S. 
8. ~P V ~Q V S. 

No pure literals, no singleton clauses.  Try P=TRUE.  Delete 3,7, delete P from
1, 2, and 8.

Set S2:
1. Q. 
2. ~R. 
5. ~R V S. 
6. R V ~S. 
8. ~Q V S. 

1 is a singleton clause.  Set Q=TRUE. Delete 1, delete ~Q from 8.

Set S3:
2. ~R. 
5. ~R V S. 
6. R V ~S. 
7. ~S V P. 
8.  S. 

2 is a singleton clause. Set R=FALSE. Delete 2,5, delete R from 6.

Set S4:
6.  ~S. 
7.  ~S V P.
8.  S. 

6 is a singleton clause. Set S=FALSE. Delete 6,7.  Delete S from 8.

8 is now the empty clause. Back track to S1. 

Try P=FALSE. Delete 1, 2, 8, delete P from 3, 7.

Set S5:
3. ~Q V R. 
5. ~R V S. 
6. R V ~S. 
7. ~S. 


~Q is a pure literal.  Set Q=FALSE. Delete 3.
7 is a singleton clause. Set S=FALSE. Delete 7, 6, delete S from 5.

Set S6:
5. ~R.

~R is a pure literal. Set R=FALSE. Success.

Valuation: P=FALSE, Q=FALSE, R=FALSE, S=FALSE, W=FALSE.