## AI: Problem Set 2

Assigned: Feb. 5

Due: Feb. 19

### 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. 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 + 20 - (N mod 41)

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 + 25 - (N mod 51)

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?

(Note: I haven't yet worked through this problem, so I don't know whether
* any * alpha-beta pruning can be carried out.)

### Problem 2

Consider the following set of sentences in the propositional calculus.
(p < = > q) => r.

~(q ^ r).

q => w.

r => ~w.

p => (w V r).

~(p^q) => x.

A. Convert the above sentences to CNF.

B. Show how the Davis-Putnam procedure finds a satisfying assignment over
these sentences.