-
Notifications
You must be signed in to change notification settings - Fork 1
/
assignment9_part2.html
417 lines (355 loc) · 13.7 KB
/
assignment9_part2.html
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<meta http-equiv="Content-Style-Type" content="text/css" />
<style>
body {
font-family: sans-serif;
max-width: 800px;
margin-top: -21px;
margin-left: 66px;
border-left: 1px solid gray;
padding-left: 24px;
margin-bottom: -15px;
}
div.content {
padding-top: 21px;
padding-bottom: 15px;
}
h1 {
}
hr {
color: gray;
background-color: gray;
height: 1px;
margin-left: -24px;
margin-right: -24px;
border: 0px solid gray;
}
.draft {
color: #008080;
}
div.attention {
background: #ffcccc;
border: 2px dashed red;
padding: 11px 21px 11px 21px;
}
div.hint {
background: lightgreen;
border: 2px dashed green;
padding: 0 21px 0 21px;
}
table {
padding: 0;
border-bottom: 1px solid grey;
border-right: 1px solid grey;
}
tr {
margin: 0;
padding: 2px;
}
td {
border-left: 1px solid grey;
border-top: 1px solid grey;
margin: 0;
padding: 2px;
}
th {
border-left: 1px solid grey;
border-top: 1px solid grey;
margin: 0;
padding: 2px;
}
span.keyword {
font-weight: bold;
}
span.emph {
font-style: italic;
}
span.hilite {
text-decoration: underline;
}
a {
text-decoration: none;
}
div.author {
float: right;
margin-top: 27px;
color: grey;
}
.code {
font-family: monospace;
}
div.code {
border: 1px dashed grey;
padding-top: 11px;
padding-bottom: 11px;
padding-right: 21px;
padding-left: 21px;
white-space: pre;
overflow-x: auto;
background: #fff;
}
div.points {
float: left;
text-align: right;
margin-left: -88px;
min-width: 50px;
}
li div.points {
margin-left: -128px;
}
div.points.easy {
color: #008000;
}
div.points.hard {
color: #800000;
font-weight: bold;
}
table.board {
border: 1px solid #000;
border-right: 0;
border-top: 0;
border-spacing: 0;
}
table.board.highlight {
border: 5px solid #f00;
}
table.board tr {
border: 0;
}
table.board td {
border: 1px solid #000;
border-bottom: 0;
border-left: 0;
padding: 0;
width: 25px;
height: 25px;
background: #0a0;
vertical-align: middle;
}
table.small td {
width: 15px;
height: 15px;
}
table.board div {
-webkit-border-radius: 999px;
-moz-border-radius: 999px;
border-radius: 999px;
behavior: url(PIE.htc);
border: 0;
width: 20px;
height: 20px;
margin-left: auto;
margin-right: auto;
}
table.board div.W {
background: #fff;
}
table.board div.B {
background: #000;
}
table.board div.S {
border: 2px solid #f00;
}
table.small div {
width: 10px;
height: 10px;
}
#minimaxTable {
border: 0;
font-weight: bold;
}
#minimaxTable > tbody > tr > td {
border: 0;
text-align: center;
}
#minimaxTable td > table {
margin: auto;
}
#minimaxTable .bracket {
margin: 10px auto 10px auto;
border: 3px solid #000;
border-bottom: 0;
width: 50%;
height: 25px;
}
</style>
<title>CS2 Assignment 9: Othello - Part 2</title>
</head>
<body>
<div class="content">
<div class="author">Author: Kevin Chen</div>
<h1>CS2 Assignment 9: Othello - Part 2</h1>
<h2>Due <span style="color: #f00">Tuesday</span>, March 14, 2017, at 17:00 PST</h2>
<hr />
<h2>Introduction</h2>
<p>This is <b>Part 2</b> of a two-part CS2 assignment on Othello.
<a href="assignment9_part1.html">For <b>Part 1</b>, click here.</a></p>
<hr />
<h2>Assignment Background</h2>
<p>Recall that we could simply generate a decision tree down to a practical
depth and choose the branch where the smallest possible end score within that
branch is the highest such score across all branches. However, this is an
inefficient approach, since we spend a lot of time considering branches that
will end up being worse than branches we have already considered or that our
opponent would never let us reach. If we could stop ourselves from tracing too
far into these, we could save time, allowing us to look deeper with the time we
have.</p>
<h3>Alpha-Beta Pruning</h3>
<p>To accomplish this, we could use an idea called <span
class="keyword">alpha-beta pruning</span>. As we construct the decision
tree, we keep track of two statistics: <span class="hilite">alpha is our best
overall score</span>, and <span class="hilite">beta is the opponent's best
overall score</span> (i.e., our worst overall score).
We start alpha at some large negative number and beta at
some large positive number; as we traverse the tree, we increase alpha (since
we try to maximize), and we decrease beta (since the opponent tries to
minimize). If at any point we discover that making a move would set alpha
greater than beta, we need not trace further into that subtree, since that
represents a "mistake" made by some side; either we have made a bad move that
allowed the opponent to drive the minimum score too low, or the opponent has
made a bad move that allowed us to drive the maximum score too high. In any
case, the entire subtree resulting from that decision need not be explored
further.</p>
<p>
Consider the following minimax tree, where the numbers are the scores for the
maximizing player:
<div align="center">
<img src="images/AB_pruning.png" /><br />
(source:
<a href="http://en.wikipedia.org/wiki/File:AB_pruning.svg">Wikipedia</a>)
</div>
<p>
Try keeping track of the alpha and beta values as you traverse the tree in
depth-first fashion (from left to right); you will see how this allows us
to avoid exploring the parts of the tree in gray. For example, consider what
happens when we reach the right subtree (rooted at the 5 in the 2nd layer).
At this point, alpha is 6, since the middle subtree has guaranteed us at least
that score. Thus, when we begin traversing the right subtree and find that
the opponent can at least minimize our score to 5, we know there is no reason
to continue exploring the rest of the subtree, since the middle subtree is
guaranteed to be better.
</p>
<h3>Iterative Deepening</h3>
<p>The danger with conducting our search to a large depth is that, if a
position has a high branching factor, we could run out of time and end up with
a bad result if we haven't explored all of the branches. To avoid this,
we can employ a strategy called <span class="keyword">
iterative deepening</span>. Instead of immediately trying to run minimax down
to a large depth,
we can start from a relatively shallow depth (that we know will run in time).
Then, while we still have time, we can repeatedly run minimax, increasing the
depth limit each time. This way, if we are interrupted due to time constraints,
we can fall back to the result from a shallower depth (although not necessarily
optimal, it's usually better than a result from an incomplete search).
</p>
<p>
Hopefully, these ideas are enough to get you started, but there are
<span class="keyword">many</span> other techniques (opening books,
transposition tables, etc.) that can be used to improve your AI.
Feel free to read up on such techniques.
</p>
<div class="hint"><p>
For this assignment, you are free to read up on any resources that might help
you, and we encourage you to! The only exception to this is looking at actual
source code in any non-pseudocode language.</p>
</div>
<br />
<h3>Compiler Optimizations</h3>
<p>In addition to the above algorithmic techniques to improve your AI's
performance, you can also gain some extra speed by letting
<span class="code">g++</span> optimize your code during compilation. So far
in this course, you've been compiling all your code with the lowest optimization
level -O0 (by default) and debugging symbols (-ggdb); while this is great for
debugging, your programs can potentially run much faster at higher
optimization levels. Here are brief descriptions of the different levels:
<ul>
<li><span class="code">-O0</span><br />
Reduce compilation time and make debugging produce the expected results. This is the default.
</li>
<li><span class="code">-O</span><br />
The compiler tries to reduce code size and execution time, without performing any optimizations that take a great deal of compilation time.
</li>
<li><span class="code">-O1</span><br />
Optimize. Optimizing compilation takes somewhat more time, and a lot more memory for a large function.
</li>
<li><span class="code">-O2</span><br />
Optimize even more. GCC performs nearly all supported optimizations that do not involve a space-speed tradeoff. As compared to -O, this option increases both compilation time and the performance of the generated code.
</li>
<li><span class="code">-O3</span><br />
Optimize yet more. -O3 turns on all optimizations specified by -O2 and also turns on the -finline-functions, -funswitch-loops, -fpredictive-commoning, -fgcse-after-reload, -ftree-vectorize and -fipa-cp-clone options.
</li>
</ul>
</p>
<p>
To choose a optimization level, simply add the appropriate flag to the
<span class="code">CFLAGS</span> variable in your Makefile (and remove
the <span class="code">-ggdb</span> keyword). So for optimization level
<span class="code">-O2</span>, you would have:
</p>
<div class="code">CFLAGS = -Wall -ansi -pedantic -O2</div>
<p>
Remember to re-test your AI when changing optimization levels!
Higher optimization levels do not necessarily guarantee more speed
(especially when going from <span class="code">-O2</span> to
<span class="code">-O3</span>). In addition, while very rare, higher
optimization levels can may make your program execute differently
(although this generally only happens if you've done something non-standard
in your code). Finally, try to test your AI on a cluster machine, since we'll
be running the tournament on those machines.
</p>
<hr />
<h2>Prerequisites</h2>
<p>These are the prerequisites for getting this assignment to compile
(ubuntu package names):
<ul>
<li>g++ 4.6.x+</li>
<li>openjdk-6-jre</li>
<li>openjdk-6-jdk (optional - only if you want to use Java)
</ul>
Ask a TA if you need help retrieving these packages, or if these packages appear
to be missing from the CS cluster.</p>
<hr />
<h2>Assignment (20 points)</h2>
<p>For this week, your goal is to continue improving your AI. You will earn points
by crushing some benchmark AI opponents in the tournament.</p>
<p><div class="points easy">5</div>
Beat <b>ConstantTimePlayer</b> (performs a quick evaluation of moves, then chooses one).</p>
<p><div class="points hard">5</div>
Beat <b>BetterPlayer</b> (recursively evaluates moves to depth 3, then chooses the best move).</p>
<p><div class="points hard">3</div>
Beat <b>OogeePlayer</b> (similar to BetterPlayer, recursing to depth 4 with different parameters). <span class="emph">The OogeePlayer player will not be provided to you.</span></p>
<p><div class="points hard">2</div>
Beat <b>DeepKwok</b> (maintains an opening book, uses alpha-beta pruning, uses a transposition table, searches as far as it thinks it can within time limit). <span class="emph">The DeepKwok player will not be provided to you.</span></p>
<p><div class="points">0.5</div>
Beat a TA's AI (0.5 points <span class="emph">each</span>)</p>
<p>You may earn points for each objective by either defeating each opponent at least once during the tournament, or outranking each opponent in the final tournament standings. Draws are judged in your favor, except where caused by an error (in which case judgment is passed by the TAs).</p>
<div class="attention" style="padding-top: 0">
<p><span class="keyword">IMPORTANT:</span> Your grade this week will be determined by your AI's performance in the tournament. Make sure your code compiles on the computers in the Annenburg lab! If your program does not compile or crashes on the lab computers, you may not get credit for any of the points above. </p>
</div>
<br />
<p>In addition to your AI bot, fill in the <span class="code">README.txt</span> file
in your repository with the following (make sure to <span class="hilite">git add</span> it when committing):
</p>
<p><div class="points easy">2</div>
Describe how and what each group member contributed for the past two weeks. If you
are solo, these points will be part of the next section.</p>
<p><div class="points easy">3</div>
Document the improvements that your group made to your AI to make it tournament-worthy.
Explain why you think your strategy(s) will work. Feel free to discuss any ideas were
tried but didn't work out.</p>
<p>
Remember, the tournament will take place on
<b>Wednesday, March 15, at 5:00 PM</b> in <b>Annenberg 104 (computer cluster)</b>, and will be publicly viewable. We will be providing refreshments (pizza and drinks) if you want to come by and watch - it should be fun!</p>
<p>On the day of the tournament, you will be able to view realtime standings at: </p>
<a href="http://courses.cms.caltech.edu/cs2/status.html">http://courses.cms.caltech.edu/cs2/status.html</a>
<hr />
<div class="hint">If you have any questions about this week's assignment,
please contact cs2-c-tas@caltech.edu, or show up at any TA's office
hours.</div>
</div>
</body>
</html>