Assignment 1: minesweeper, MIPS
minesweeper
version: 1.6 last updated: 2021-10-18 20�00�00
Aims
to give you experience writing MIPS assembly code
to give you experience with data and control structures in MIPS
Getting Started
Create a new directory for this assignment called minesweeper, change to this directory, and fetch the provided code
by running these commands:
$ mkdir minesweeper
$ cd minesweeper
$ 1521 fetch minesweeper
If you’re not working at CSE, you can download the provided files as a zip file or a tar file.
This will add the following files into the directory:
grid.h: some grid related constants in C, such as its size.
grid.s: the MIPS version of grid.h.
beginner.[hs]: more constants in C and MIPS.
intermediate.[hs]: more constants in C and MIPS.
expert.[hs]: more constants in C and MIPS.
minesweeper.c: a reference implementation of Minesweeper in C.
minesweeper.s: a stub assembly file to complete.
Minesweeper
How to play Minesweeper
minesweeper.c is an implementation of the classic game Minesweeper. The objective of the game is to clear a board
that contains hidden “mines” or bombs without detonating any of them. To do this, you will need to use the clues on
the board, which indicate how many bombs are in the adjacent cells.
At any point, you can perform 2 actions:
Marking a cell – marking or flagging a cell that you think might be a bomb,
Revealing a cell – revealing the cell. If it is an empty cell, then all of the surrounding empty cells will also be
revealed. Revealing a cell containing a bomb is game over.
Once you have revealed all cells that do not contain a bomb, you win the game.
Before starting the assignment, it is recommended that you understand how to play Minesweeper. A good place to
start is Google’s built-in minesweeper game that can be found here.
minesweeper.c
https://cgi.cse.unsw.edu.au/~cs1521/21T3/assignments/ass1/provided.zip
https://cgi.cse.unsw.edu.au/~cs1521/21T3/assignments/ass1/provided.tar
https://www.google.com/search?q=minesweeper
The assignment version of Minesweeper is played on a grid represented by a 2D array of 8-bit ints (int8_t **grid).
Each element in the 2D array represents a cell on the grid. For each element in the 2D array, 7 of the 8 bits are used
to represent information regarding that cell, as shown in the diagram below.
is_marked – 1 if cell is marked, 0 if not.
is_revealed – 1 if cell is revealed, 0 if not.
is_bomb – 1 if cell is a bomb, 0 if not.
value – number of bombs in adjacent cells, including diagonally adjacent cells. This will hold the value of 0 – 8
as there are a total of 8 adjacent cells. The value 0 represents an empty cell.
You can use bitwise operations to extract or set relevant bits. The relevant masks are #defined at the top of the
minesweeper.c file.
By default, the game is played on a 10×10 grid. However, you can change these settings to play on a different sized
grid by changing the #include provided. As a brief guidline, the standard levels of Minesweeper are:
Beginner: 9 x 9 grid, with max 10 bombs.
Intermediate: 16 x 16 grid, with max 40 bombs.
Expert: 16 x 30 grid, with max 90 bombs.
The assignment Minesweeper runs on an infinite loop, which means that you can play multiple rounds of
Minesweeper. For each round, your score will be calculated based on how many cells are left to be revealed. Once
you have won or lost a game, you will be prompted for input on whether you would like to play again, or if you would
like to print out the user scores so far. The assignment implementation keeps track of the last 10 rounds of
Minesweeper.
Running minesweeper.c
First compile and run minesweeper.c by running these commands:
$ dcc -o minesweeper minesweeper.c
$ ./minesweeper
Once you run the program, you will be prompted for some user input.
Number of bombs – number of bombs on the grid. Input should be an integer from 1 to 91 inclusive.
Seed – number used to generate bombs on the grid. Different seeds will generate different grids.
Debug mode – allows the entire grid to be immediately revealed. Input should be 0 or 1.
Username – any string you would like to use to identify yourself. This will be used to keep track of your score,
and the running high score.
NOTE:
You cannot win a game in debug mode as all the cells are immediately revealed! Debug mode is only useful
to make sure that your board contains the correct values when given a particular seed.
As an example:
How many bombs on the grid? 10
Seed: 2
Debug Mode: 0
Enter your user name: selina
Reveal Any Cell to Begin…:
Total Bomb Count: 10
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
What’s your first move? (action row col)
If debug mode is 1, then the output will look like this:
How many bombs on the grid? 20
Seed: 2
Debug Mode: 1
Enter your user name: selina
Reveal Any Cell to Begin…:
Total Bomb Count: 20
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
What’s your first move? (action row col)
IMPORTANT: Note that the grid is initially always completely empty (all zeroes). This is done as the bombs on the
grid are only generated after you reveal the first cell. This is so that your first input will never cause you to
immediately lose.
Playing minesweeper.c
To play the game you need to provide input in the form of action row col, where
action – either 0 for marking, 1 for revealing or -1 to exit the program.
row – row of cell you want to perform action on. This is zero indexed.
col – column of cell you want to perform action on. This is zero indexed.
As an example, providing the input
1
4
4
will reveal the cell at (4, 4). This input will generate the board, which will look something like this (note that this
example follows on from the above example, i.e. the seed used is 2):
Total Bomb Count: 10
0 0 0 0 1 – – – – –
0 0 0 0 1 – – – – –
0 0 0 0 1 1 2 – – –
0 0 0 0 0 0 2 – – –
0 0 0 0 0 0 2 – – –
0 0 0 1 1 1 2 – – –
0 0 1 2 – – – – – –
0 0 1 – 2 1 1 – – –
0 0 1 1 1 0 1 – – –
0 0 0 0 0 0 1 – – –
What’s your next move? (action row col)
To mark a cell, you would do something like this:
0
7
3
This marks the cell at (7, 3) by placing an X on the cell. Marking a bomb decreases the total bomb count by 1. The
total bomb count can be negative if your number of marked cells is larger than the total number of bombs on the
grid. Note that you can unmark a cell by providing the same input again. This will increase the total bomb count.
What’s your next move? (action row col)
0
7
3
Total Bomb Count: 9
0 0 0 0 1 – – – – –
0 0 0 0 1 – – – – –
0 0 0 0 1 1 2 – – –
0 0 0 0 0 0 2 – – –
0 0 0 0 0 0 2 – – –
0 0 0 1 1 1 2 – – –
0 0 1 2 – – – – – –
0 0 1 X 2 1 1 – – –
0 0 1 1 1 0 1 – – –
0 0 0 0 0 0 1 – – –
If you reveal a bomb, you will lose. If you reveal all cells that are not bombs, you win the game. Either way, your score
will be calculated for you, the high score printed out, and you will be asked whether you want to start a new game.
Boom! you lost 🙁
Your score was: 72 (28 cells remaining)
The highscore is now: 72 by you (selina)
New Game? (no: 0, yes: 1, scores: 2)
To keep playing, enter 1. To stop, enter 0. To print out the last 10 scores, enter 2. Printing out the scores will look
something like this:
New Game? (no: 0, yes: 1, scores: 2)
2
————-SCORES———–
——————————
* USERNAME: selina
* SCORE: 63
——————————
* USERNAME: natalie
* SCORE: 54
——————————
To get a feel of how the assignment should work, try minesweeper.c on a terminal. You should also read through
minesweeper.c before starting the assignment to help you understand what the program is doing.
minesweeper.s: The Assignment
Your task in this assignment is to complete minesweeper.s in MIPS.
You have been provided with some assembly and some helpful information in minesweeper.s and some grid related
constants in grid.s. In order to change the grid size, you can change the constants N_ROWS, N_COLS and MAX_BOMBS
that are defined in grid.s. You can also change the file you’re running the assignment with to the provided files
beginner.s, intermediate.s or expert.s, which simulate different levels of minesweeper.
Read through the provided code carefully, then add MIPS assembly so it executes exactly the same as
minesweeper.c. To run your assignment, run this command:
$ 1521 mipsy grid.s minesweeper.s
or to use the beginner.s file,
$ 1521 mipsy beginner.s minesweeper.s
If you’re running your assignment with spim instead, then run:
$ cat grid.s minesweeper.s > game.s
$ 1521 spim -f game.s
or to use the beginner.s file,
$ cat beginner.s minesweeper.s > game.s
$ 1521 spim -f game.s
A handful of utility functions have already been completed in MIPS assembly for you. You only have to implement the
following unfinished functions in MIPS assembly.
NOTE:
If used mistakenly, cat may overwrite your file. Make sure to submit intermediate versions of your
assignment so that your files can be easily recovered if this happens. You can do this by copying your work
to your CSE account and submitting it using the give command (check the Submission section). Only your
final submission will be marked.
Subset 0 – Revealing the grid
For this subset, you will need to add code to complete the reveal_grid function in minesweeper.s. This function
allows you to immediately reveal all cells on the grid if debug mode is 1.
Remember that the grid is always initially empty and only gets filled up after you input your first reveal action. This is
done so that the first input never kills the player This means that the gridwill be filledwith zeroes for this subset
done so that the first input never kills the player. This means that the grid will be filled with zeroes for this subset.
On completion of this subset, your program should match these behaviours:
How many bombs on the grid? 10
Seed: 2
Debug Mode: 1
Enter your user name: selina
Reveal Any Cell to Begin…:
Total Bomb Count: 10
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
What’s your first move? (action row col)
Subset 1 – Placing bombs
For this subset, you will need to complete the place_bombs function in minesweeper.s. This function will place the
bombs on the grid. Different seed inputs will place bombs in different cells.
On completion of this subset, bombs (denoted by *) should be placed on the grid. Bombs are only placed on the grid
after the user’s first reveal input. To check whether your bombs have been placed in the correct cells, set debug
mode to be 1 so that all the cells of the grid are revealed. On completion of this subset, your program should behave
as such:
How many bombs on the grid? 20
Seed: 2
Debug Mode: 1
Enter your user name: natalie
Reveal Any Cell to Begin…:
Total Bomb Count: 20
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
What’s your first move? (action row col)
1
2
3
Total Bomb Count: 20
0 0 1 * 2 1 1 1 1 1
0 0 1 1 2 * 2 3 * 2
0 0 0 0 1 1 2 * * 2
0 0 0 0 0 0 2 3 4 2
0 0 1 1 2 1 3 * 3 *
0 0 1 * 4 * 4 * 3 1
0 1 3 4 * * 3 1 1 0
0 1 * * 5 3 3 2 2 1
0 1 3 * 3 * 3 * * 2
0 0 1 1 2 1 3 * 4 *
What’s your next move? (action row col)
HINT:
Make sure to follow correct MIPS calling conventions, which will most likely include using $s registers.
Subset 2 – Marking a cell
For this subset, you will need to complete the mark_cell function in minesweeper.s. This will allow you to mark and
unmark cells on the grid. mark_cell takes in two arguments: row and col, which are the row and column of the cell
to mark.
Once you have completed this subset, inputting
0
row
col
should mark or unmark the cell at row, col. For example, to mark the cell at (9, 9), you would do:
What’s your next move? (action row col)
0
9
9
Total Bomb Count: 9
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – X
To unmark the cell at (9,9), provide the same input again.
What’s your next move? (action row col)
0
9
9
Total Bomb Count: 10
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
– – – – – – – – – –
Subset 3 – Revealing cell(s)
For this subset, you need to complete two functions – reveal_cell and clear_surroundings. This will allow you to
reveal cells on the grid. On revealing a cell there are multiple things that can happen:
Revealing a numbered cell (i.e. value 1-8) will reveal only that cell.
Revealing an empty cell (i.e. value 0) will recursively reveal all surrounding cells until it reaches non-empty cells
or cells that have already been revealed on the grid.
Revealing a bomb will cause you to lose the game.
You cannot reveal a marked cell on its own. However, revealing an empty cell that triggers a recursive reveal of
its surroundings can reveal a marked cell as this will never cause you to lose the game.
On completion of this subset, you should be able to reveal cells.
NOTE:
You must implement the recursive method of clear_surroundings as written in the C code.
Example 1: revealing an empty cell, causing surrounding cells to be revealed.
In this case, the cell (4, 4) is an empty cell, and it therefore triggers a recursive reveal of its surrounding cells. Your
first move will always trigger a recursive reveal as the first cell clicked will always be empty (have the value of 0).
What’s your first move? (action row col)
1
4
4
Total Bomb Count: 10
0 0 0 0 1 – – – – –
0 0 0 0 1 – – – – –
0 0 0 0 1 1 2 – – –
0 0 0 0 0 0 2 – – –
0 0 0 0 0 0 2 – – –
0 0 0 1 1 1 2 – – –
0 0 1 2 – – – – – –
0 0 1 – 2 1 1 – – –
0 0 1 1 1 0 1 – – –
0 0 0 0 0 0 1 – – –
Example 2: revealing a single cell.
You can also reveal single cells after the first move. Here, the cell (0, 8) is revealed.
What’s your next move? (action row col)
1
0
8
Total Bomb Count: 10
0 0 0 0 1 – – – 1 –
0 0 0 0 1 – – – – –
0 0 0 0 1 1 2 – – –
0 0 0 0 0 0 2 – – –
0 0 0 0 0 0 2 – – –
0 0 0 1 1 1 2 – – –
0 0 1 2 – – – – – –
0 0 1 – 2 1 1 – – –
0 0 1 1 1 0 1 – – –
0 0 0 0 0 0 1 – – –
Subset 4 – Keeping score
For this subset, you will need to complete both the update_highscore and print_scores function in MIPS
assembly.
update_highscore – updates the running high score if a player managed to get a high score.
print_scores – prints the scores from the last 10 rounds.
The player’s score will be stored in a struct UserScore, which is defined at the top of minesweeper.c:
struct UserScore {
int score;
char name[MAX_NAME_LEN];
}
NOTE:
You must store the user scores and the high score as a struct as written in the C code or you will receive
a correctness penalty.
The score is calculated based on the number of non-bomb cells on the grid.
score = N_CELLS – n_cells_left;
This calculation has been done for you.
On completion of update_highscore, you should be able to see the running high score updated every time a player
earns a high score when a game ends.
What’s your next move? (action row col)
1
0
3
Total Bomb Count: 10
0 0 1 * 1 0 0 0 0 0
0 0 1 1 1 0 1 1 1 0
0 0 0 0 0 0 1 – 1 0
0 0 0 0 0 0 1 1 2 1
0 0 1 1 1 0 0 0 1 –
0 0 1 – 2 1 1 0 1 1
0 1 2 – – – 1 0 0 0
0 1 – – – – 2 0 0 0
0 1 3 – – – 2 1 1 0
0 0 2 – – – – – 1 0
Boom! you lost 🙁
Your score was: 91 (9 cells remaining)
The highscore is now: 91 by you (selina)
On completion of print_scores, you should be able to print the last 10 scores from the last 10 rounds of
Minesweeper.
New Game? (no: 0, yes: 1, scores: 2)
2
————-SCORES———–
——————————
* USERNAME: selina
* SCORE: 63
——————————
* USERNAME: natalie
* SCORE: 54
——————————
Testing
Some simple autotests are available to help you test your code:
1521 autotest minesweeper minesweeper.s
To run autotest for a specific subset, add the subset to the end of the command, like such:
1521 autotest minesweeper minesweeper.s subset_0
You will need to do some further testing on your own to ensure that your code is fully correct. You can do this by
comparing the output of your implementation of minesweeper.s with the observed output of the provided C code
minesweeper.c.
$ dcc -o minesweeper minesweeper.c
$ echo -e “20\n2\n0\nname\n-1” > input
$ cat input | ./minesweeper | tee c.out
$ cat input | 1521 mipsy grid.s minesweeper.s | tee mips.out
$ diff c.out mips.out
You can also use spim to test your assignment. To do this, run these set of commands instead:
$ dcc -o minesweeper minesweeper.c
$ echo -e “20\n2\n0\nname\n-1” > input
$ cat input | ./minesweeper | tee c.out
$ cat grid.s minesweeper.s > game.s
$ cat input | 1521 spim -f game.s | tee mips.out
$ diff c.out mips.out
If there is no output, that means that there is no difference between the two files and your implementation is working
as expected. Note that although you can test your code with both mipsy and spim, your code will be tested with
spim.
NOTE:
IMPORTANT: Your testing input must always end with exiting the program (i.e. providing -1 as the user
input for action) or it will loop infinitely.
Hints
SPIM supports defining constants somewhat like #define in C. The syntax is a bit different:
N_COLS = 10
N_ROWS = 10
N_CELLS = N_COLS * N_ROWS
Take careful note of the types of each global variable. For int8_t types, you will need to use the LB and SB
instructions. For int types, you will need to use the LW and SW instructions.
Assumptions and Clarifications
Like all good programmers, you should make as few assumptions as possible.
Your submitted code must be hand-written MIPS assembly, which you yourself have written. You may not submit
code in other languages. You may not submit compiled output.
You may not copy a solution from an online source (e.g., Github).
There will be a correctness penalty for assignments that do not use the stack to save and restore $ra.
There will be a correctness penalty for assignments that do not follow these important MIPS calling conventions:
that function arguments shall be passed in registers $a0…$a3;
that values in registers $s0…$s7 shall be preserved across function calls: if a function changes these registers,
it must restore the original value before returning.
that different functions should not coordinate registers between them.
There will be a correctness penalty for assignments that do not implement the functions as they are implemented in
the provided C code.
If you need clarification on what you can and cannot use or do for this assignment, ask in the class forum.
You are required to submit intermediate versions of your assignment. See below for details.
Assessment
Testing
When you think your program is working, you can use autotest to run some simple automated tests:
$ 1521 autotest minesweeper minesweeper.s
1521 autotest will not test everything.
Always do your own testing.
Automarking will be run by the lecturer after the submission deadline, using a superset of tests to those autotest
runs for you.
Submission
When you are finished working on the assignment, you must submit your work by running give:
$ give cs1521 ass1_minesweeper minesweeper.s
You must run give before Week 8 Monday 09�00�00 to obtain the marks for this assignment. Note that this is an
individual exercise, the work you submit with give must be entirely your own.
You can run give multiple times.
Only your last submission will be marked.
If you are working at home, you may find it more convenient to upload your work via give’s web interface.
You cannot obtain marks by emailing your code to tutors or lecturers.
You can check your latest submission on CSE servers with:
$ 1521 classrun check ass1_minesweeper
You can check the files you have submitted here.
Manual marking will be done by your tutor, who will mark for style and readability, as described in the Assessment
section below. After your tutor has assessed your work, you can view your results here; The resulting mark will also
be available via give’s web interface.
Due Date
This assignment is due Week 8 Monday 09�00�00.
If your assignment is submitted after this date, each hour it is late reduces the maximum mark it can achieve by 2%.
For example, if an assignment worth 74% was submitted 10 hours late, the late submission would have no effect. If
the same assignment was submitted 15 hours late, it would be awarded 70%, the maximum mark it can achieve at
that time.
Assessment Scheme
This assignment will contribute 15 marks to your final COMP1521 mark.
80% of the marks for assignment 1 will come from the performance of your code on a large series of tests.
20% of the marks for assignment 1 will come from hand marking. These marks will be awarded on the basis of clarity,
commenting, elegance and style. In other words, you will be assessed on how easy it is for a human to read and
understand your program.
An indicative assessment scheme follows. The lecturer may vary the assessment scheme after inspecting the
assignment submissions, but it is likely to be broadly similar to the following:
HD (85+) beautiful, clearly-documented code; implements all behaviour perfectly
DN (75+) very readable code; implements most behaviour perfectly
CR (65+) readable code; some correctly-implemented behaviours
https://cgi.cse.unsw.edu.au/~give/Student/give.php
https://cgi.cse.unsw.edu.au/~cs1521/21T3/student/
https://cgi.cse.unsw.edu.au/~cs1521/21T3/student/
https://cgi.cse.unsw.edu.au/~give/Student/sturec.php
PS (50-60) good progress, but not passing autotests
0% knowingly providing your work to anyone
and it is subsequently submitted (by anyone).
0 FL for
COMP1521
submitting any other person’s work; this includes joint work.
academic
misconduct
submitting another person’s work without their consent;
paying another person to do work for you.
Intermediate Versions of Work
You are required to submit intermediate versions of your assignment.
Every time you work on the assignment and make some progress you should copy your work to your CSE account
and submit it using the give command below. It is fine if intermediate versions do not compile or otherwise fail
submission tests. Only the final submitted version of your assignment will be marked.
Attribution of Work
This is an individual assignment.
The work you submit must be entirely your own work, apart from any exceptions explicitly included in the assignment
specification above. Submission of work partially or completely derived from any other person or jointly written with
any other person is not permitted.
You are only permitted to request help with the assignment in the course forum, help sessions, or from the teaching
staff (the lecturer(s) and tutors) of COMP1521.
Do not provide or show your assignment work to any other person (including by posting it on the forum), apart from
the teaching staff of COMP1521. If you knowingly provide or show your assignment work to another person for any
reason, and work derived from it is submitted, you may be penalized, even if that work was submitted without your
knowledge or consent; this may apply even if your work is submitted by a third party unknown to you. You will not be
penalized if your work is taken without your consent or knowledge.
Do not place your assignment work in online repositories such as github or anywhere else that is publicly accessible.
You may use a private repository.
Submissions that violate these conditions will be penalised. Penalties may include negative marks, automatic failure
of the course, and possibly other academic discipline. We are also required to report acts of plagiarism or other
student misconduct: if students involved hold scholarships, this may result in a loss of the scholarship. This may also
result in the loss of a student visa.
Assignment submissions will be examined, both automatically and manually, for such submissions.
Change Log
Version 1.0
(2021-10-11 12�00�00)
Initial release onto unsuspecting students
Version 1.1
(2021-10-12 19�00�00)
Modified reveal_cell in minesweeper.c slightly
minesweeper.c is now modifiable, not read-only
Version 1.2
(2021-10-14 17�00�00)
Corrected “Arguments” in comment above update_highscore function in
minesweeper.s
COMP1521 21T3: Computer Systems Fundamentals is brought to you by
the School of Computer Science and Engineering
at the University of New South Wales, Sydney.
For all enquiries, please email the class account at .edu.au
CRICOS Provider 00098G
Version 1.3
(2021-10-15 01�00�00)
Corrected subset 2 examples in spec
Version 1.4
(2021-10-18 11�40�00)
Corrected reveal_cell function comment in provided minesweeper.s
Version 1.5
(2021-10-18 16�30�00)
Corrected bombs_error message in provided minesweeper.s
Version 1.6
(2021-10-18 20�00�00)
Add new subset 0 autotests with different sized grids
https://www.cse.unsw.edu.au/
https://www.unsw.edu.au/
mailto:@cse.unsw.edu.au