Artificial Intelligence: Solution Set 2

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?

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.

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.

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)