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.