-
Notifications
You must be signed in to change notification settings - Fork 3
/
hw2
141 lines (115 loc) · 4.43 KB
/
hw2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
[20 points]
<a href=http://en.wikipedia.org/wiki/Tic_tac_toe>Tic-tac-toe</a> (also known as Noughts and Crosses)
is a two-person, zero-sum game, in which player X and player O alternate placing their symbols in
one of the blank spaces in a 3-by-3 grid that looks like this:
<p>
<table>
<tr><td><br></td><td>|</td><td><br></td><td>|</td><td><br></td></tr>
<tr><td>--</td><td>--</td><td>--</td><td>--</td><td>--</td></tr>
<tr><td><br></td><td>|</td><td><br></td><td>|</td><td><br></td></tr>
<tr><td>--</td><td>--</td><td>--</td><td>--</td><td>--</td></tr>
<tr><td><br></td><td>|</td><td><br></td><td>|</td><td><br></td></tr>
</table>
<p>
The first player to place three of his symbols in a row -- horizontally, vertically, or diagonally --
wins.
<ol>
<li>
[10 points]
Beginning from the position
<p>
<table>
<tr><td>X</td><td>|</td><td>X</td><td>|</td><td><br></td></tr>
<tr><td>--</td><td>--</td><td>--</td><td>--</td><td>--</td></tr>
<tr><td>O</td><td>|</td><td><br></td><td>|</td><td>X</td></tr>
<tr><td>--</td><td>--</td><td>--</td><td>--</td><td>--</td></tr>
<tr><td><br></td><td>|</td><td>O</td><td>|</td><td><br></td></tr>
</table>
with O's turn to move, construct by hand
the game-tree for the rest of the game.
Assume the search horizon is the end of the game on all branches.
<p>
Hint: You can save a lot of work by taking advantage of symmetry. For example,
<table>
<tr>
<td>
<table>
<tr><td><br></td><td>|</td><td>X</td><td>|</td><td><br></td></tr>
<tr><td>--</td><td>--</td><td>--</td><td>--</td><td>--</td></tr>
<tr><td><br></td><td>|</td><td><br></td><td>|</td><td><br></td></tr>
<tr><td>--</td><td>--</td><td>--</td><td>--</td><td>--</td></tr>
<tr><td><br></td><td>|</td><td><br></td><td>|</td><td><br></td></tr>
</table>
</td>
<td>,</td>
<td>
<table>
<tr><td><br></td><td>|</td><td><br></td><td>|</td><td><br></td></tr>
<tr><td>--</td><td>--</td><td>--</td><td>--</td><td>--</td></tr>
<tr><td>X</td><td>|</td><td><br></td><td>|</td><td><br></td></tr>
<tr><td>--</td><td>--</td><td>--</td><td>--</td><td>--</td></tr>
<tr><td><br></td><td>|</td><td><br></td><td>|</td><td><br></td></tr>
</table>
</td>
<td>,</td>
<td>
<table>
<tr><td><br></td><td>|</td><td><br></td><td>|</td><td><br></td></tr>
<tr><td>--</td><td>--</td><td>--</td><td>--</td><td>--</td></tr>
<tr><td><br></td><td>|</td><td><br></td><td>|</td><td><br></td></tr>
<tr><td>--</td><td>--</td><td>--</td><td>--</td><td>--</td></tr>
<tr><td><br></td><td>|</td><td>X</td><td>|</td><td><br></td></tr>
</table>
</td>
<td>, and</td>
<td>
<table>
<tr><td><br></td><td>|</td><td><br></td><td>|</td><td><br></td></tr>
<tr><td>--</td><td>--</td><td>--</td><td>--</td><td>--</td></tr>
<tr><td><br></td><td>|</td><td><br></td><td>|</td><td>X</td></tr>
<tr><td>--</td><td>--</td><td>--</td><td>--</td><td>--</td></tr>
<tr><td><br></td><td>|</td><td><br></td><td>|</td><td><br></td></tr>
</table>
</td>
</tr>
</table>
are all the same position because of symmetry.
<li>
[5 points]
Suppose the static evaluation function scores
a win for O as +1, a draw as 0, and a loss for O as -1.
At each level of your sketch of the game tree, indicate the value of each node based on its children.
Indicate the best next move for O.
<li>
[5 points]
Now use α-β pruning.
At each level of your sketch of the game tree,
indicate the value of the nodes and indicate any nodes that would be pruned.
Explicitly indicate the final value of the α-β interval is for each node.
Indicate the best next move for O.
</ol>
<br><br>
<hr>
<li>[30 points]
Consider the following English sentences.<br><br>
<ul>
<li> One or another customs official searches everyone entering the country
who is not a VIP.
<li> Some drug dealers entered the country and they were searched only by drug dealers.
<li> No drug dealer was a VIP.
</ul>
<br><br>
<ol>
<li> [12 points] Convert the sentences into first order predicate logic.
Use the following lexicon:<br>
<pre>
Predicates: vip(X) -- X is a VIP
entered(X) -- X entered the country
customs(X) -- X is customs official
dealer(X) -- X is a drug dealer
searched(X, Y) -- Y searched X (watch the argument order)
</pre>
<li> [9 points] Convert the logic statements into CNF.
<li> [9 points] Using resolution, prove that
"At least one of the customs officials was a drug dealer."
</ol>