-
Notifications
You must be signed in to change notification settings - Fork 0
/
multiagentProject.html
218 lines (146 loc) · 12.3 KB
/
multiagentProject.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
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<title>Project 2: 2048</title>
<link href="projects.css" rel="stylesheet" type="text/css">
</head>
<body>
<h2>Project 2: 2048</h2>
<!--announcements-->
<blockquote>
<center>
<img src="2048.jpg" width="400px">
</center>
</blockquote>
<h4>Due on May 3rd, 23:00</h4>
<h3>Introduction</h3>
<p>In this project, you will design agents for the <a href="https://en.wikipedia.org/wiki/2048_(video_game)">2048 game</a>. Along the way, you will implement both minimax and expectimax search and try your hand at evaluation function design.</p>
<p>The code for this project contains the following files, available as a <a href="2048.zip">zip archive</a></p>.
<h5>Key files to read</h5>
<table border="0" cellpadding="10">
<tr>
<td><code><a href="docs/multi_agents.html">multi_agents.py</a></code></td>
<td>Where all of your multi-agent search agents will reside.</td>
</tr>
<tr>
<td><code><a href="docs/2048.html">2048.py</a></code>
<td>The main file that runs the 2048 games.</td>
</tr>
<tr>
<td><code><a href="docs/game_state.html">game_state.py</a></code>
<td>This file describes a 2048 <code>GameState</code> type, which you will use extensively in this project.</td>
</tr>
<tr>
<td><code><a href="docs/game.html">game.py</a></code></td>
<td>The logic behind how the 2048 game works. This file describes several supporting types like Agent, OpponentAction, and Action.</td>
</tr>
<tr>
<td><code><a href="docs/util.html">util.py</a></code></td>
<td>Useful data structures for implementing search algorithms.</td>
</tr>
</table>
<h5>Files you can ignore</h5>
<table border="0" cellpadding="10">
<tr>
<td><code><a href="docs/graphics_display.html">graphics_display.py</a></code></td>
<td>Graphics for 2048.</td>
</tr>
<tr>
<td><code><a href="docs/game_grid.html">game_grid.py</a></code></td>
<td>Support for games graphics.</td>
</tr>
<tr>
<td><code><a href="docs/game2048_grid.html">game2048_grid.py</a></code></td>
<td>Support for 2048 graphics.</td>
</tr>
<tr>
<td><code><a href="docs/displays.html">displays.py</a></code></td>
<td>Summary graphics for 2048.</td>
</tr>
<tr>
<td><code><a href="docs/keyboard_agents.html">keyboard_agents.py</a></code></td>
<td>Keyboard interfaces to control 2048.</td>
</tr>
</table>
<p><strong>What to submit:</strong> You will fill in portions of <code><a href="docs/multi_agents.html">multi_agents.py</a></code> during the assignment. You should submit this file (only) and a README.txt <b>(case sensitive)</b> as a zip file named
id1_id2.zip (or id1.zip) in the moodle website. <b>Each team should submit exactly one file!</b></p>
<p><strong>Evaluation:</strong> Your code will be autograded for technical correctness. Please <em>do not</em> change the names of any provided functions or classes within the code, or you will wreak havoc on the autograder. Please make sure you follow
the readme format <b>exactly</b>.</p>
<p><strong>Academic Dishonesty:</strong> We will be checking your code against other submissions in the class for logical redundancy. If you copy someone else's code and submit it with minor changes, we will know. These cheat detectors are quite hard
to fool, so please don't try. We trust you all to submit your own work only; <em>please</em> don't let us down. If you do, we will pursue the strongest consequences available to us.</p>
<p><strong>Getting Help:</strong> You are probably not alone. Please post your questions via the <a href="https://moodle2.cs.huji.ac.il/nu17/mod/forum/view.php?id=4508">Project 2 Forum</a> on the <a href="http://www.cs.huji.ac.il/~ai"> course website</a>.
<strong>Please do not write to our personal e-mail addresses!</strong></p>
<p><strong>Readme format: </strong>Please submit a README.txt file. The README should include the following lines (exactly):<br> </p>
<ol>
<li>id1 --- student 1 id<br>
<li>id2 --- student 2 id</li>
<li>***** --- 5 stars denote end of i.d info. </li>
<li>comments</li>
</ol>
For an example check out the <a href="README.txt"> README.txt</a> provided with your project. This README will be read by a script, calling an autograder. Note that if you decide to submit alone, please remove lines 2, i.e.<br>
<ol>
<li>id1 --- student 1 id<br>
<li>***** --- 5 stars denote end of i.d info. </li>
<li>comments</li>
</ol>
</ol>
<p></p>
<p> </p>
<h2>2048</h2>
<p>First, sit back relax and play a nice game of 2048:</p>
<pre>python3 2048.py</pre>
<p>Now, run the provided <code>ReflexAgent</code> in <code><a href="docs/multi_agents.html">multi_agents.py</a></code>:</p>
<pre>python3 2048.py --agent=ReflexAgent</pre>
<p>Note that it does not play that well. Inspect its code (in <code><a href="docs/multi_agents.html">multi_agents.py</a></code>) and make sure you understand what it's doing.</p>
<p><em><strong>Question 1 (3 points) </strong></em> Improve the <code>evaluation_function</code> in <code>ReflexAgent</code>. The provided reflex agent code provides some helpful examples of methods that query the
<code>GameState</code> for information.</p>
<pre>python3 2048.py --agent=ReflexAgent --num_of_games=10 --display=SummaryDisplay</pre> How does your agent fare? It will likely to achieve 512 sometime, and 256 most of the times.
<p>The autograder will check the performances of your agent performances on 20 games.</p>
<p>Don't spend too much time on this question, though, as the meat of the project lies ahead.</p>
<p><em><strong>Question 2 (5 points) </strong></em>Now you will write an adversarial search agent in the provided <code>MinimaxAgent</code> class stub in <code><a href="docs/multi_agents.html">multi_agents.py</a></code>.</p>
<p> Your code should also expand the game tree to an arbitrary depth. Score the leaves of your minimax tree with the supplied <code>self.evaluation_function</code>, which defaults to <code>score_evaluation_function</code>.
<code>MinimaxAgent</code> extends <code>MultiAgentAgent</code>, which gives access to <code>self.depth</code> and <code>self.evaluation_function</code>. Make sure your minimax code makes reference to these two variables where appropriate as these
variables are populated in response to command line options.</p>
<p><em>Important:</em> A single search ply is considered to be one agent move and the board response (addition of random tile), so depth 2 search will involve agent move two times.</p>
<p><em><strong>Hints and Observations</strong></em></p>
<ul>
<li>The evaluation function in this part is already written (<code>self.evaluation_function</code>). You shouldn't change this function, recognize that now we're evaluating *states* rather than actions, as we were for reflex agent. Look-ahead agents
evaluate future states whereas reflex agents evaluate actions from the current state.</li>
<li>The minimax values of the initial state in the <code>test_layout</code> layout are 4, 12, 16 for depths 1, 2, and 3 respectively.
<li>We are using random seed for reproducible results, however we may change the seeds in our tests so don't relay on this specific <i>Random</i> board.
<pre>python3 2048.py --agent=MinmaxAgent --depth=1 --random_seed=1 --initial_board=test_layout.txt</pre>
<li>Depth 1 should be pretty quick, but depth 2 will be slower and depth 3 very slow. Don't worry, the next question will speed up the search somewhat.
<li>All states in minimax should be <code>GameStates</code>, either passed in to <code>get_action</code> or generated via <code>GameState.generate_successor</code>. In this project, you will not be abstracting to simplified states.
<pre>python3 2048.py --agent=MinmaxAgent --depth=2</pre>
</ul>
<p><em><strong>Question 3 (3 points) </strong></em> Make a new agent that uses alpha-beta pruning to more efficiently explore the minimax tree, in <code>AlphaBetaAgent</code>.</p>
<p> You should see a small speed-up. (but still depth=3 is too much for online playing in this game).</p>
<pre>python3 2048.py --agent=AlphaBetaAgent --depth=2</pre>
<p> The <code>AlphaBetaAgent</code> minimax values should be identical to the <code>MinimaxAgent</code> minimax values, although the actions it selects can vary because of different tie-breaking behavior. the minimax values of the initial state in the
<code>test_layout</code> layout are 4, 12, 16 for depths 1, 2, and 3 respectively.</p>
<p><em><strong>Question 4 (3 points) </strong></em> Random board responses is, of course, not optimal minimax agents, and so modeling them with minimax search may not be appropriate. Fill in <code>ExpectimaxAgent</code>, where your agent will no
longer take the min over all board possible responses, but the expectation according to your agent's model of how the board acts. To simplify your code, assume the board response uniformly at random. (although that in the original rules their is
a higher probability for the 2 tile.)</p>
<p>You should now observe a more optimistic approach that ignore possible blocking. Investigate the results of these scenario:</p>
<pre>python3 2048.py --agent=AlphaBetaAgent --depth=2 --initial_board=risk_layout.txt --num_of_initial_tiles=0</pre>
<pre>python3 2048.py --agent=ExpectimaxAgent --depth=2 --initial_board=risk_layout.txt --num_of_initial_tiles=0</pre> You should find that your <code>ExpectimaxAgent</code> achieve 1024 about half the time, while your <code>AlphaBetaAgent</code> usually achieve just 512. Make sure you understand why the behavior here differs from the minimax case.
<pre>python3 2048.py --agent=AlphaBetaAgent --depth=2 --num_of_games=10 --display=SummaryDisplay</pre>
<pre>python3 2048.py --agent=ExpectimaxAgent --depth=2 --num_of_games=10 --display=SummaryDisplay</pre>
<p><em><strong>Question 5 (6 points) </strong></em> Write a better evaluation function for 2048 in the provided function
<code>betterevaluation_function</code>. The evaluation function should evaluate states. You may use any tools at your disposal for evaluation, including your search code from the last project. Grading: 3 point for any evaluation function that
when running with AlphaBetaAgent depth=2 most of times achieve score greater than 7000. The other 3 point will be awarded based on best score.
The top 40% submissions will receive full credit; the next 35% will get 2 points and the other submissions
will be awarded with one point.</p>
<pre>python3 2048.py --agent=AlphaBetaAgent --depth=2 --evaluation_function=better --num_of_games=5</pre>
<p><strong>Document your evaluation function!</strong> Please describe your evaluation function at the README file. We're very curious about what great ideas you have, so don't be shy. We reserve the right to reward bonus points for clever solutions
and show demonstrations in class.</p>
<p><em><strong>Hints and Observations</strong></em></p>
<ul>
<li>One way you might want to write your evaluation function is to use a linear combination of features. That is, compute values for features about the state that you think are important, and then combine those features by multiplying them by different
values and adding the results together. You might decide what to multiply each feature by based on how important you think it is.</li>
</ul>
<p><em>Project 2 is done.</em></p>
</body>
</html>