Lab 11: MIPS Assembly Programming (Advanced)
Overview
In this lab, you are going to write a program (in both C and MIPS assembly) that allows a human to play against a computer in "Dots and Boxes". You may have already played this game or a variation in COMP 51. If so, just adapt your existing solution to meet the unique ECPE 170 requirements described below.
Lab
In this game, you have a 4 by 4 grid of dots. At the beginning, the computer will randomly pick which player (the human or the computer) moves first. That player draws a line between two adjacent dots (in a row or column). The next player then does the same thing. At any point, if a player adds a line which creates a box then that player "wins" the box and the box is filled in with their identifier (in this case, either a "H" or "C"). The first player to fill in 5 or more boxes wins the game.
You should not allow the player to make an illegal move, or to enter invalid input. For example, a player can't redraw an existing line or attempt to draw two lines at once.
The computer’s "strategy" for taking a turn should be very simple.
- Randomly select two adjacent coordinates.
- Check that no line already exists between those coordinates; if one does, go back to Step 1.
- Draw the line and check to see if any new squares are filled in, and if so has it won.
At the end of a game, you should print out a message indicating who won. A example of the game output is shown here. Your output does not have to match this exactly.
Welcome to Dots and Boxes!
Version 1.0
Implemented by Ken Hughes
Enter two positive numbers to initialize the random number generator.
Number 1: 123
Number 2: 456
I will make the first move.
My turn: I draw between b1 and c1
1 2 3 4
a . . . .
b . . . .
c | . . .
d . . . .
Your turn:
Enter coordinate of the first dot: b1
Enter coordinate of the second dot: c1
There is already a line there.
Enter coordinate of the first dot: b1
Enter coordinate of the second dot: c2
Coordinates must be adjacent
Enter coordinate of the first dot: a1
Enter coordinate of the second dot: a2
My turn: I draw between a3 and a4
1 2 3 4
a ._. ._.
b . . . .
c | . . .
d . . . .
Your turn:
Enter coordinate of the first dot: a2
Enter coordinate of the second dot: a3
My turn: I draw between c1 and d1
1 2 3 4
a ._._._.
b . . . .
c | . . .
d | . . .
Your turn:
Enter coordinate of the first dot: a1
Enter coordinate of the second dot: b1
My turn: I draw between c2 and c3
1 2 3 4
a ._._._.
b | . . .
c | ._. .
d | . . .
Your turn:
Enter coordinate of the first dot: c1
Enter coordinate of the second dot: c2
My turn: I draw between b3 and b4
1 2 3 4
a ._._._.
b | . ._.
c |_._. .
d | . . .
Your turn:
Enter coordinate of the first dot: c3
Enter coordinate of the second dot: c3
Coordinates must be adjacent
Enter coordinate of the first dot: b3
Enter coordinate of the second dot: c3
My turn: I draw between d1 and d2
1 2 3 4
a ._._._.
b | . ._.
c |_._| .
d |_. . .
Your turn:
Enter coordinate of the first dot: c4
Enter coordinate of the second dot: d4
My turn: I draw between a4 and b4
1 2 3 4
a ._._._.
b | . ._|
c |_._| .
d |_. . |
Your turn:
Enter coordinate of the first dot: b1
Enter coordinate of the second dot: b2
My turn: I draw between d2 and d3
1 2 3 4
a ._._._.
b |_. ._|
c |_._| .
d |_._. |
Your turn:
Enter coordinate of the first dot: a2
Enter coordinate of the second dot: b2
My turn: I draw between c2 and d2
1 2 3 4
a ._._._.
b |H| ._|
c |_._| .
d |C|_. |
Your turn:
Enter coordinate of the first dot: d3
Enter coordinate of the second dot: d4
My turn: I draw between c3 and d3
1 2 3 4
a ._._._.
b |H| ._|
c |_._| .
d |C|C|_|
Your turn:
Enter coordinate of the first dot: c3
Enter coordinate of the second dot: c4
My turn: I draw between b4 and c4
1 2 3 4
a ._._._.
b |H| ._|
c |_._|C|
d |C|C|H|
Your turn:
Enter coordinate of the first dot: a3
Enter coordinate of the second dot: b3
My turn: I draw between b2 and c2
1 2 3 4
a ._._._.
b |H| |H|
c |C|_|C|
d |C|C|H|
Your turn:
Enter coordinate of the first dot: b2
Enter coordinate of the second dot: b3
You win!
1 2 3 4
a ._._._.
b |H|H|H|
c |C|H|C|
d |C|C|H|
Part 1: Implement the Dots and Boxes game in C
(1) You cannot use library functions other than printf() and scanf(). Specifically, you *cannot* use rand(), because there is no analogous function in the MIPS simulator or assembly language.
(2) You must provide a Makefile.
(3) Your game must use at least 3 subroutines -- feel free to use more. At least one of the subroutines must have parameters and at least one must return a value. For example, you could use: check_board(player_id), print_board(), user_input().
(4) You must fully check for valid inputs. Coordinates must always be a letter followed by a number, and the values must be in range.
There is no "C Standard Library" in MIPS. The simulator provides analogous functions for printf() and scanf(), but nothing to generate random numbers. This snippet code of C code from Wikipedia provides an acceptable random number generator for the project. Note that it produces a random 32-bit number, so if you want a random number in a smaller range, use modular division afterwards. Prompt the user for two random numbers to use as seeds (for m_w and m_z), so your program doesn't produce the same random number sequence each time. The m_w and m_z variables should be global, or at least persist after the function finishes. (Otherwise, your random number generator will always produce the same output).
m_w = <choose-initializer>; /* must not be zero */
m_z = <choose-initializer>; /* must not be zero */
uint32_t get_random()
{
m_z = 36969 * (m_z & 65535) + (m_z >> 16);
m_w = 18000 * (m_w & 65535) + (m_w >> 16);
return (m_z << 16) + m_w; /* 32-bit result */
}
You should completely test and debug your C implementation before moving on to Part 2. Assembly programming is slow and tedious. You DO NOT want to have to fix bugs later that were caused by a sloppy C implementation!
Part 2: Implement the Dots and Boxes game in MIPS assembly
(1) **Each line** of assembly code must be documented with a comment!
(2) Each region of assembly code must clearly have a **comment block** documenting the overall purpose of that region, along with what values each register holds. You can use your own judgement for a reasonable region size.
(3) Implement the same subroutines as in your C program. They must take the same parameters and return the same values, although it is up to you to determine the exact implementation. For example, if you have a C subroutine which returns an array of two values for a coordinate, you may decide to return those values in $v0 and $v1.
(4) You can assume that all user inputs have the proper format (a valid letter followed by a valid number); you still must check that coordinates are adjacent and have not already been played.
To reduce the work involved in the MIPS implementation (part 2), you are permitted to replace the computer player with a second human player. This simplification is only for the MIPS part of the assignment. The C implementation must provide all of the features of the full game. However, you can earn 10 points of extra credit for a full MIPS implementation.
Tip: In-class discussion during the time period allotted to Lab 11 will discuss generating a random number in assembly. Sample code will be generated on the whiteboard.
Lab Submission:
(1) There is no lab report for this lab.
(2) All source code must be submitted via Mercurial. Place the source files inside the lab11 folder that was previously created.
Optional Feedback:
(Feel free to include a text file with comments/feedback on the lab)
(1) What was the best aspect of this lab?
(2) What was the worst aspect of this lab?
(3) How would you suggest improving this lab in future semesters?
Resources
The MIPS Instruction Set and MIPS Example Programs will be very useful in this project. Don't forget about the H&P Appendix A PDF in Sakai! (It shows the full list of branch instructions)
