## AI: Problem Set 2

Assigned: Feb. 2
Due: Feb. 16

### Problem 1

Consider the following very dreary game: There are two players, X and Y. At each stage, the state of the game is an integer N. When it is X's turn he has his choice of two possible moves:

Move A: N := N + (N mod 23) - 11.
Move B: N := N + (N mod 7) - 4.

When it is Y's turn to play, he has his choice of two possible moves:

Move C: N := N + 2*(N mod 17) - 16.
Move D: N := N + ((N mod 11)-5) * (N mod 17)

At the start N=100, and it is X's turn to play. The game will be played for 4 ply; that is, X will play, then Y, then X, then Y and then the game is over.

Assume that the game tree is evaluated using a depth-first search from left to right (that is, we always explore A before B and C before D) and that alpha-beta pruning is carried out. Show the part of the game tree that is evaluated. What is the best starting move for X? What is the value of the start state?

### Problem 2

Consider the following set of sentences in the propositional calculus.
p => (q < = > r).
p => (x V w).
w => (q ^ ~r).
x => (p < = > w).

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 attempting FALSE.