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?

(By all means work out this problem on this sheet, rather than recopy this tree.)

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.

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.