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

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 10x10 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.

As an example:

How many bombs on the grid? 10
Seed: 2
Debug Mode: 0
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
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-----------

------------------------------
* SCORE:	63
------------------------------
* 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.

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 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
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
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)


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.

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];
}


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-----------

------------------------------
* SCORE:	63
------------------------------
* SCORE:	54
------------------------------


Testing

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.

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.

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.

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 very readable code; implements most behaviour perfectly readable code; some correctly-implemented behaviours good progress, but not passing autotests knowingly providing your work to anyone and it is subsequently submitted (by anyone). submitting any other person's work; this includes joint work. 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.

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
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