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?

**Answer: ** Either A1 or A4 (board value = 3)

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

** Answer: ** To B1. If X then makes the optimal response of C2 or D4, the
board value will be -1. If O plays to A1 then X can respond to A4,
giving a value of -2. If O plays to A4 then X can respond to A1, giving
a value of -6.

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

** Answer:**
Suppose that O first consider his move to B1, and determines that it
has value -1. He now considers his move to A4 and X's response to A1,
giving an upper bound of -6 on O's move to A4. He may then prune all other
possible responses by X to A4.

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.

** Answer: **
No three tasks start at the same time:

1. ~[A0^B0^C0]

2. ~[A0^B0^D0]

3. ~[A0^C0^D0]

4. ~[B0^C0^D0]

5. ~[A1^B1^C1]

6. ~[A1^B1^D1]

7. ~[A1^C1^D1]

8. ~[B1^C1^D1]

9. ~[A2^B2^C2]

10. ~[A2^B2^D2]

11. ~[A2^C2^D2]

12. ~[A2^C2^D2]

Every task starts some time:

13. A0 V A1 V A2.

14. B0 V B1 V B2.

15. C0 V C1 V C2.

16. D0 V D1 V D2.

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.

**Answer: **
A0 ^ (B2 V C2 V D2)

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

** Answer: ** We have the following clauses. From the constraint
of only two processors: (Interestingly, the only two of these that are used
are (8) and (12).)

1. ~A0 V ~B0 V ~C0

2. ~A0 V ~B0 V ~D0

3. ~A0 V ~C0 V ~D0

4. ~B0 V ~C0 V ~D0

5. ~A1 V ~B1 V ~C1

6. ~A1 V ~B1 V ~D1

7. ~A1 V ~C1 V ~D1

8. ~B1 V ~C1 V ~D1

9. ~A2 V ~B2 V ~C2

10. ~A2 V ~B2 V ~D2

11. ~A2 V ~C2 V ~D2

12. ~B2 V ~C2 V ~D2

From the constraint that every task starts some time:

13. A0 V A1 V A2.

14. B0 V B1 V B2.

15. C0 V C1 V C2.

16. D0 V D1 V D2.

From the ordering constraints

17. ~A0 V ~B0.

18. ~A1 V ~B0.

19. ~A1 V ~B1.

20. ~A2 V ~B0.

21. ~A2 V ~B1

22. ~A2 V ~B2

23. ~A0 V ~C0.

24. ~A1 V ~C0.

25. ~A1 V ~C1.

26. ~A2 V ~C0.

27. ~A2 V ~C1

28. ~A2 V ~C2

29. ~A0 V ~D0.

30. ~A1 V ~D0.

31. ~A1 V ~D1.

32. ~A2 V ~D0.

33. ~A2 V ~D1

34. ~A2 V ~D2

From the negated goal:

35. ~A0 V ~B2.

36. ~A0 V ~C2.

37. ~A0 V ~D2.

The resolution proof proceeds as follows:

38. ~A2 V B1 V B2 (from 20 and 14)

39. ~A2 V B2 (from 38 and 21, with factoring)

40. ~A2 (from 39 and 22, with factoring)

41. A0 V A1 (from 40 and 13).

42. B0 V B1 V ~C2 V ~D2 (From 12 and 14)

43. B0 V B1 V C0 V C1 V ~D2 (from 42 and 15).

44. B0 V B1 V C0 V C1 V D0 V D1 (from 43 and 16)

45. A1 V ~B0 (from 41 and 17)

46. ~B0 (from 45 and 18, with factoring).

47. A1 V ~C0 (from 41 and 23)

48. ~C0 (from 47 and 24, with factoring).

49. A1 V ~D0 (from 41 and 29)

50. ~D0 (from 49 and 30, with factoring).

51. B1 V C0 V C1 V D0 V D1 (from 44 and 46)

52. B1 V C1 V D0 V D1 (from 51 and 48)

53. B1 V C1 V D1 (from 52 and 40)

54. ~A1 V C1 V D1 (from 53 and 19)

55. ~A1 V D1 (from 54 and 25 with factoring)

56. ~A1 (from 55 and 31 with factoring)

57. A0. (from 41 and 56)

58. ~B2. (from 57 and 35).

59. ~C2. (from 57 and 36).

60. ~D2. (from 57 and 37).

61. B0 V B1 (from 58 and 14).

62. C0 V C1 (from 59 and 15).

63. D0 V D1 (from 60 and 16).

64. B1 (from 61 and 46)

65. C1 (from 62 and 48)

66. D1 (from 63 and 50)

67. ~C1 V ~D1 (from 8 and 64)

68. ~D1 (from 67 and 65)

69. null (from 68 and 66)