Lab 9: 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 the computer in Wythoff's Game, a variation on the popular game of Nim.

Pre-Lab

There is no pre-lab activity for this lab.

Lab

In Wythoff's Game, you have 2 heaps of marbles. At the beginning, the computer should randomly populate each heap with between 10 and 50 marbles. The player and computer will alternate turns. On each turn, the player removes either an arbitrary number of marbles from one heap, or the same (arbitrary) number of marbles from both heaps. A player must remove at least one marble from one heap and cannot remove more than half of the marbles currently in the heap. (If the player opts to remove from both heaps, than the upper bound on the maximum number of marbles to remove should be based on the smaller of the two heaps.) The game continues until no marbles are left in either heap. The last player to make a move is the winner.

The user will always be given the first turn. You should not allow the user to make an illegal move, or to enter invalid input. For example, no player can take ZERO marbles from a heap. That’s cheating! Similarly, no player can draw ALL the marbles from the heap.

The computer’s "strategy" for taking a turn should be very simple.

1. Randomly decide whether to remove marbles from one heap or both heaps 2.
2. Select a random integer between 1 and the size of the heap / 2 to remove.
   Note: If the computer selected both heaps to remove from, then this upper bound on the maximum number of marbles to remove should be based on the smaller of the two heaps.
   Note: If the heap only has one marble then the computer should be allowed to draw it, even though that is more than half the pile.
3. Remove the selected marbles and print out a message indicating the move performed.

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 Wythoff's Game!
Version 1.0
Implemented by Jeff Shafer
Enter two positive numbers to initialize the random number generator. 
Number 1: 564
Number 2: 3516854
HeapA   HeapB
-------------
 45     18
What heap would you like to draw from? Enter 'a', 'b', or 'c' for both: c
How many marbles do you want to remove from heap c? 9
Computer sected to remove 7 from heap a
HeapA   HeapB
-------------
 29     9
What heap would you like to draw from? Enter 'a', 'b', or 'c' for both: a
How many marbles do you want to remove from heap a? 14
Computer sected to remove 3 from heap a
HeapA   HeapB
-------------
 12     9
What heap would you like to draw from? Enter 'a', 'b', or 'c' for both: c
How many marbles do you want to remove from heap c? 4
Computer sected to remove 2 from heap c
HeapA   HeapB
-------------
 6     3
What heap would you like to draw from? Enter 'a', 'b', or 'c' for both: a
How many marbles do you want to remove from heap a? 3
Computer sected to remove 1 from heap a
HeapA   HeapB
-------------
 2     3
What heap would you like to draw from? Enter 'a', 'b', or 'c' for both: c
How many marbles do you want to remove from heap c? 1
Computer sected to remove 1 from heap a
HeapA   HeapB
-------------
 0     2
What heap would you like to draw from? Enter 'a', 'b', or 'c' for both: b
How many marbles do you want to remove from heap b? 1
Computer sected to remove 1 from heap b
*** Welcome to our new computer overlords! ***

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 */
}

Part 1: Implement Wythoff's 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.
(2) You must provide a Makefile.

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 Wythoff's 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) Your game must use at least 3 subroutines -- feel free to use more. For example, you could use:  random_in_range(low, high), print_game(), user_input()

To reduce the work involved in the MIPS implementation (part 2), you are permitted to make the following optional simplifications to the project:

1. The computer player can be replaced with a second human player.
2. The human player(s) are trustworthy. Thus, their input does not require error checking beyond a trivial (is the number of marbles to remove greater than zero?) verification.

These simplifications are only for the MIPS part of the assignment.  The C implementation must provide all of the features of the full game.

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