You are here: Home / ECPE 170 / Labs / Lab 11: MIPS Assembly Programming (Advanced)

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 Connect Four , specially the 5-In-A-Row variant. You may have already played this game 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 9 column, 6 row board. At the beginning, the first and last columns are populated with alternating player tokens. The computer will randomly pick which player (the human or the computer) moves first.  That player drops their token into one of the middle 7 columns of the board. (The leftmost and rightmost columns are already full). The next player then does the same thing.  At any point, if a player drops a token which completes a set of 5 tokens in a row (horizontally, vertically, or diagonally), that player 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 drop a token if a column is already full, or drop a token into column 'a'.

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

  1. Randomly select a column, and attempt to drop a token.
  2. Check if that column is already full. It it is full, go back to Step 1.

At the end of a game, you should print out a message indicating who won. An example of the game output is shown here. Your output does not have to match this exactly.

Welcome to Connect Four, Five-in-a-Row variant!
Version 1.0
Implemented by Jeff Shafer

Enter two positive numbers to initialize the random number generator. 
Number 1: 123
Number 2: 456
Human player (H)
Computer player (C)
Coin toss... HUMAN goes first.

   1 2 3 4 5 6 7
 -----------------
 C . . . . . . . C
 H . . . . . . . H
 C . . . . . . . C
 H . . . . . . . H
 C . . . . . . . C
 H . . . . . . . H
 -----------------
What column would you like to drop token into? Enter 1-7: 3
Computer player selected column 5

   1 2 3 4 5 6 7
 -----------------
 C . . . . . . . C
 H . . . . . . . H
 C . . . . . . . C
 H . . . . . . . H
 C . . . . . . . C
 H . . H . C . . H
 -----------------
What column would you like to drop token into? Enter 1-7: 2
Computer player selected column 2

   1 2 3 4 5 6 7
 -----------------
 C . . . . . . . C
 H . . . . . . . H
 C . . . . . . . C
 H . . . . . . . H
 C . C . . . . . C
 H . H H . C . . H
 -----------------
What column would you like to drop token into? Enter 1-7: 3
Computer player selected column 7

   1 2 3 4 5 6 7
 -----------------
 C . . . . . . . C
 H . . . . . . . H
 C . . . . . . . C
 H . . . . . . . H
 C . C H . . . . C
 H . H H . C . C H
 -----------------
What column would you like to drop token into? Enter 1-7: 3
Computer player selected column 5

   1 2 3 4 5 6 7
 -----------------
 C . . . . . . . C
 H . . . . . . . H
 C . . . . . . . C
 H . . H . . . . H
 C . C H . C . . C
 H . H H . C . C H
 -----------------
What column would you like to drop token into? Enter 1-7: 3
Computer player selected column 2

   1 2 3 4 5 6 7
 -----------------
 C . . . . . . . C
 H . . . . . . . H
 C . . H . . . . C
 H . C H . . . . H
 C . C H . C . . C
 H . H H . C . C H
 -----------------
What column would you like to drop token into? Enter 1-7: 3

   1 2 3 4 5 6 7
 -----------------
 C . . . . . . . C
 H . . H . . . . H
 C . . H . . . . C
 H . C H . . . . H
 C . C H . C . . C
 H . H H . C . C H
 -----------------
Congratulations, Human Winner!

Part 1: Implement the Connect Four game in C
(1) You cannot use library functions other than printf(), scanf(), putc() and getc().  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:
bool check_board(player_id)print_board()int user_input().
(4) You must fully check for valid inputs. 

 

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 Connect 4 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.
(4) You can assume that all user inputs have the proper format, but you still must check that the column entered is legal and is not already full. 

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)