## 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:

- 100 points if P has won.
- -100 points if P has lost.
- Add 1 point for each row where P has two pieces and Q has none.
- Add 5 point for each row where P has three pieces and Q has none.
- Subtract 1 point for each row where Q has two pieces and P has none.
- Subtract 5 point for each row where Q has three pieces and P has none.

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.)