Last Modified: April 9, 2017
CS 175: Project in AI (in Minecraft): Spring 2017
Assignment 1: Finding the Shortest Path
Sameer Singh (with help from Moshe Lichman)
http://sameersingh.org/courses/aiproj/sp17/
1 Task Description
In this assignment, you have to guide the player agent in Minecraft through a maze to reach the goal block. For
this exercise, we will assume that the agent can see the whole maze, i.e. it is completely observable. Given this
information, the agent has to reach the goal in the minimum number of moves.
This assignment is based heavily on
tutorial
_
7.py
in the Malmo Python tutorials, so please follow the
tutorials 1 through 5 to familiarize yourself with the API and the Malmo platform (tutorial 6 is not relevant yet).
1.1 Provided Source Code
We have provided two Python files. The most important one is
assignment1.py
which contains the complete
code to setup the Malmo environment with different mazes, and have the agent run through it. The provided
implementation is incomplete, and the agent needs your help to solve the maze most efficiently. We have also
provided
priorit
_
dict.py
, a simple implementation of a heap-based priority queue. See the implementation
for details, and discuss on Piazza if you have any doubts. You can ignore this implementation if you prefer.
1.2 Setup and Running the Code
Assuming you have installed Malmo and started working your way through the tutorials, all you need to do to
run this assignment is to copy the two files above to the
Python
_
Examples
folder, and after launching Minecraft,
run
python assignment1.py
. If everything run successfully, the agent should do nothing while the timer counts
down for each of the ten missions. The output in the terminal should look like the following:
Size of maze: 6
Waiting for the mission 1 to start
Mission 1 running.
Output (start,end) 1 : (None, None)
Output (path length) 1 : 0
Output (actions) 1 : []
Error: out of actions, but mission has not ended!
Error: out of actions, but mission has not ended!
Mission 1 ended
Size of maze: 6
Waiting for the mission 2 to start
Mission 2 running.
Output (start,end) 2 : (None, None)
Output (path length) 2 : 0
Output (actions) 2 : []
Error: out of actions, but mission has not ended!
Error: out of actions, but mission has not ended!
1.3 Overview of the Code
As mentioned before, much of this assignment is based on
tutorial
_
7.py
, so please refer to the Malmo Tutorials
in the
Python
_
Examples
directory. The source code creates a series of increasing difficult mazes made of
diamond_block blocks as the floor, each with a start (emerald_block) and an end (redstone_block) block. The
mission starts with the player at the start block, and ends when the player reaches the end block. Make sure you
are at least somewhat familiar with the whole source code, however the main control code that is relevant for
your implementation are in the following lines:
Assignment 1 UC Irvine 1/ 3
CS 175: Project in AI (in Minecraft) Spring 2017
420
399
378
357
336
315
294
273
252
231
210
189
168
147
126
105
84
63
42
21
0
421
400
379
358
337
316
295
274
253
232
211
190
169
148
127
106
85
64
43
22
1
422
401
380
359
338
317
296
275
254
233
212
191
170
149
128
107
86
65
44
23
2
423
402
381
360
339
318
297
276
255
234
213
192
171
150
129
108
87
66
45
24
3
424
403
382
361
340
319
298
277
256
235
214
193
172
151
130
109
88
67
46
25
4
425
404
383
362
341
320
299
278
257
236
215
194
173
152
131
110
89
68
47
26
5
426
405
384
363
342
321
300
279
258
237
216
195
174
153
132
111
90
69
48
27
6
427
406
385
364
343
322
301
280
259
238
217
196
175
154
133
112
91
70
49
28
7
428
407
386
365
344
323
302
281
260
239
218
197
176
155
134
113
92
71
50
29
8
429
408
387
366
345
324
303
282
261
240
219
198
177
156
135
114
93
72
51
30
9
430
409
388
367
346
325
304
283
262
241
220
199
178
157
136
115
94
73
52
31
10
431
410
389
368
347
326
305
284
263
242
221
200
179
158
137
116
95
74
53
32
11
432
411
390
369
348
327
306
285
264
243
222
201
180
159
138
117
96
75
54
33
12
433
412
391
370
349
328
307
286
265
244
223
202
181
160
139
118
97
76
55
34
13
434
413
392
371
350
329
308
287
266
245
224
203
182
161
140
119
98
77
56
35
14
435
414
393
372
351
330
309
288
267
246
225
204
183
162
141
120
99
78
57
36
15
436
415
394
373
352
331
310
289
268
247
226
205
184
163
142
121
100
79
58
37
16
437
416
395
374
353
332
311
290
269
248
227
206
185
164
143
122
101
80
59
38
17
438
417
396
375
354
333
312
291
270
249
228
207
186
165
144
123
102
81
60
39
18
439
418
397
376
355
334
313
292
271
250
229
208
187
166
145
124
103
82
61
40
19
440
419
398
377
356
335
314
293
272
251
230
209
188
167
146
125
104
83
62
41
20
North
South
EastWest
emerald_block (start)
redstone_block (end)
diamond_block
air
Figure 1:
Grid Layout:
Layout of the two-dimensional grid laid out as a one-dimensional array. The location of
the maze, especially the start and end blocks, may be different in the assignment. The array contain string-values
representing the four types of possible blocks.
223 grid = load
_
grid(world
_
state)
224 start, end = find
_
start
_
end(grid) # implement this
225 path = dijkstra
_
shortest
_
path(grid, start, end) # implement this
226 action
_
list = extract
_
action
_
list
_
from
_
path(path)
We first get the array of blocks that consists of the 2-dimensional maze from Malmo in
load
_
grid
. Then, we want
to identify the start and the end blocks (each represented by an integer index into the
grid
array). Given the
start and the end blocks, and the whole maze, we want to compute the shortest path of blocks from the start to
the end, computed using Djikstra’s algorithm. Finally, we convert these list of blocks into Malmo actions that are
carried out by the agent. We provide the correct implementation of the first and the last functions, but leave the
correct implementation of the second and the third functions to you (more on this later).
1.4 Grid Layout
It is important for you to understand how the grid is laid out. We have requested the 21
×
21 grid of blocks
from the world that lie at the floor of the player, with the player at the center of it ((10
,
10), if zero-indexed).
This two-dimensional is laid out as a single-dimensional array of strings (representing the type of the block) in
a row-major way (where row is the east-west direction), i.e. the (
i, j
) coordinate is represented by the index
j ×
21 +
i
, where
j
is the east-west coordinate, and
i
is the north-south coordinate. For the precise indexing, see
the illustration in Figure 1.
Since the grid is represented by a single-dimensional array, you need to get the neighboring blocks of the
current block, represented by an integer index
i
. Looking at
extract
_
action
_
list
_
from
_
path
should give you
a hint; the blocks to the immediate left (west) and right (east) are of course represented by
i −
1 and
i
+ 1, while
the blocks in the north and south require jumping one whole row, thus
i −
21 and
i
+ 21, respectively. The function
extract
_
action
_
list
_
from
_
path
uses this to go the other way: if block
i
and
j
are next to each other on the
grid, the action to get from
i
to
j
is represented by
j − i
, i.e. if
j − i
is +1, the move is
moveeast
, if
−
1, the move
is movewest , if −21, the move is movenorth , and if +21, the move is movesouth .
Note: The player is facing south, so do not get confused if movesouth is forward.
Assignment 1 UC Irvine 2/ 3
CS 175: Project in AI (in Minecraft) Spring 2017
2 What Do I Submit?
Here we’ll describe what exactly you need to submit to the assignment on Canvas.
1. Code: Finding Start and End Blocks (5 points):
As a simple exercise, implement the
find
_
start
_
end
function, that takes the grid as an array of string describing the block types, and returns the indices of the
start and the end block. This should only require, at maximum, a few lines of code. Submit this snippet as
your submission.
2. Output: Start and End Block Indices (5 points):
Run the code with the above implemented, and look at
the output lines that start with
Output (start,end)
and paste them as your submission. There should be
10 lines, one for each mission.
3. Code: Shortest Path Implementation (50 points):
Implement Dijkstra’s algorithm in order to find the
shortest path from the source to the destination. The set of possible actions from each block is one step in
north, south, east, or west directions, i.e. taking multiple or diagnol steps is not allowed. The path you
compute should be shortest in terms of number of moves (all of them cost the same), should be a list of
block indices (integers), should include both the start and the end blocks, and of course, should not contain
any air blocks. Submit the complete implementation of your function.
4. Output: Length of the Shortest Paths (30 points):
Run the code with the above implemented, and look
at the output lines that start with
Output (path length)
and with
Output (actions)
and paste them
as your submission. There should be 20 lines, two for each mission.
5. Comments:
Any comments about your submission that you want to bring to our attention as we are grading
it. This is completely optional, I expect most of you to leave this empty.
6. Statement of Collaboration (10 points):
It is
mandatory
to include a Statement of Collaboration with
respect to the guidelines below. Include the names of everyone involved in the discussions (especially
in-person ones), and what was discussed. You should also include the links to all online resources you used
for the assignment in this section.
All students are required to follow the academic honesty guidelines posted on the course website. For
programming assignments, in particular, I encourage the students to organize (perhaps using Piazza) to discuss the
task description, assignment requirements, bugs in our/Malmo code, and the relevant technical content before they
start working on it. However, you should not discuss the specific solutions, and, as a guiding principle, you are not
allowed to take anything written or drawn away from these discussions (i.e. no photographs of the blackboard,
written notes, etc.). The same holds for online resources: you are allowed to read the description of algorithms,
but your code should be your own. Especially after you have started working on the assignment, try to restrict the
discussion to Piazza as much as possible, so that there is no doubt as to the extent of your collaboration.
Assignment 1 UC Irvine 3/ 3
