Artificial Intelligence: Problem Set 2

Assigned: Jan. 30
Due: Feb. 13

Problem 1

Consider the game of 4x4 Tic-Tac-Toe. Suppose that the current board is as follows:

It is O's turn to play.

Suppose that player P uses the following evaluation function:

Thus the value of the current board for O is -1: 1 for row A minus 1 for row B minus 1 for column 1.

A. If O does a one-ply search (i.e. to just after he plays), where will he play?

B. If O does a two-ply search (to just after X responds), where will he play?

C. Give an example of where alpha-beta pruning could be applied to the two-ply search of the game tree from this point.

Problem 2

As in problem 1 of problem set 1, consider the problem of PRECEDENCE CONSTRAINED MULTIPROCESSOR SCHEDULING, where every task has unit length l(T)=1. Consider the very simple case where there are two processors; four tasks A,B,C,D; the three constraints A < B, A < C, and A < D; and a deadline of 3.

This problem can be expressed in propositional form using atoms of the form, "KT", meaning that task K is assigned to start at time T. Thus, in this example, there would be 12 atoms: A0, A1, A2, B0 etc.

A constraint of the form "X < Y" can be expressed in this propositional language as the sentences

~[X0^Y0].
~[X1^Y0]
~[X1^Y1]
~[X2^Y0]
~[X2^Y1]
~[X2^Y2]

A. Using the propositional language, express the statements (a) that three tasks cannot start at the same time; (b) that every task must start some time.

B. Using the propositional language, express the statement that A must start at time 0 and that either B, C, or D must start at time 2.

PLEASE DO NOT ANSWER PART 2.C

C. Using propositional resolution, prove (B) from the given constraints. (Note: you MUST use propositional resolution. NO credit will be given to other kinds of proof.)