Assigned: Jan. 30
Due: Feb. 13
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.
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.
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.)