Project 1: Gotta connect em'all!

Released: 23:59 Monday, February 5th, 2024.

Due: 17:59 Monday, February 26th 2024.

Can you get 4 in line?

Important: Read this

Please read this document to the end before you start. I give a LOT of useful information that should help you on the project.

It you haven’t, read this how to work with matrices.

You can only submit a maximum of 3 days late! (With a penalty of 45%)

REMEMBER: There are points given for meeting with your TA! I’ll make no exceptions if you don’t do it by the deadline!

The instructor and TAs will NOT be available to answer questions about the project during the weekend. This includes the weekend of the late submission deadline when it’s due. As such, I suggest you start early.

Introduction

In this project, you will be implementing a 2 player game in MIPS assembly: Connect 4 aka Four-in-line.

The game consists a board representing the play area. Two players face each other dropping tokens, one at a time, until one of them manages to place 4 in line! (Ohhh…. so that’s where the name comes from… Extraordinary.)

Check the first result I got on youtube

Start early

The deadline will approach fast! Life happens, sickness happens, so if you start early you can minimize the impact.

Do a little bit every day! 1 hour every day! 30 minutes every day! SOMETHING!

You know you will have questions, and if you decide to ask them in the last week, I may not be able to answer them all!

And of course, if you have any questions, ask!

Game mechanic

The game works like this:

1. Initially, the players have a blank board

   0 1 2 3 4 5 6
   |_|_|_|_|_|_|_|
   |_|_|_|_|_|_|_|
   |_|_|_|_|_|_|_|
   |_|_|_|_|_|_|_|
   |_|_|_|_|_|_|_|
   |_|_|_|_|_|_|_|

2. Player 1 takes the first turn

   0 1 2 3 4 5 6
   |_|_|_|_|_|_|_|
   |_|_|_|_|_|_|_|
   |_|_|_|_|_|_|_|
   |_|_|_|_|_|_|_|
   |_|_|_|_|_|_|_|
   |_|_|_|_|_|_|_|
   Player 1, it's your turn.
   Select a column to play. Must be between 0 and 6
   -1
   That play is invalid. Try again
   Select a column to play. Must be between 0 and 6
   7
   That play is invalid. Try again
   Select a column to play. Must be between 0 and 6
   1

3. When a valid number is input, a token is placed in that column, at the first (lowest) free position.

   0 1 2 3 4 5 6
   |_|_|_|_|_|_|_|
   |_|_|_|_|_|_|_|
   |_|_|_|_|_|_|_|
   |_|_|_|_|_|_|_|
   |_|_|_|_|_|_|_|
   |_|*|_|_|_|_|_|

4. Next it’s player 2 turn.

   Player 2, it's your turn.
   Select a column to play. Must be between 0 and 6

5. The game ends when one of the players manages to place 4 tokens in a horizontal, vertical, or diagonal line!.

   0 1 2 3 4 5 6
   |_|_|_|_|_|_|_|
   |_|_|_|_|_|_|_|
   |*|_|_|_|_|_|_|
   |_|*|_|_|_|_|_|
   |_|_|*|_|_|_|_|
   |_|_|_|*|_|_|_|
   Congratulations player 1. You won!

0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|*|_|_|_|
|_|_|*|_|_|_|_|
|_|*|_|_|_|_|_|
|*|_|_|_|_|_|_|
Congratulations player 1. You won!

0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|+|+|+|+|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
Congratulations player 2. You won!

0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|+|_|_|_|_|_|
|_|+|_|_|_|_|_|
|_|+|_|_|_|_|_|
|_|+|_|_|_|_|_|
|_|_|_|_|_|_|_|
Congratulations player 2. You won!

Your assignment

Plan

Plan your implementation, and discuss it with your TA. And yes, this is part of the assignment and will be awarded points. Before Friday, the 5th of March, you have to meet with your TA (office hours, or recitation) and discuss how you plan to approach the project.

Note: Don’t wait until you’ve met with the TA to start working on your implementation!

This includes data structures you are planning to use, user inputs that may be invalid and you need to account for, etc.. Then, write those down and discuss them with the TA (you don’t have to submit anything).

1. Think of which functions you will need to implement, and what they will do.
   1. Start from the main function and split your program into multiple steps.
   2. This plan is not going to be enforced, but it should be thought through.
2. Think of possible invalid user inputs, and how they will impact the program negatively.
   1. Board bounds.
   2. Filling a column to the top.

Implement

Implement the MIPS assembly code that executes the game described above! Your program will manage all interactions with the user and the board:

1. It begins by displaying a welcome message and an explanation of what the user should do. How is the game played?
2. Print the empty board
3. Then, the game begins and your program will:
   1. Ask player 1 to play
      • Ask and validate user input (MARS will crash if user gives no input or a letter, this is fine!)
        • Don’t allow the user to select an non-existing tile!
        • Don’t allow the user to select an full column!
      • “Drop” the token into the board at the requested column
      • Check for a winning condition
   2. Ask player 2 to play
      • Ask and validate user input (MARS will crash if user gives no input or a letter, this is fine!)
        • Don’t allow the user to select an non-existing tile!
        • Don’t allow the user to select an full column!
      • “Drop” the token into the board at the requested column
      • Check for a winning condition
   3. Repeat until one of the players wins. or the board is full
4. In the end, print a message letting the winning player know the game has ended.

The welcome message

I try to restrict your imagination as little as possible in this project. You do your own thing, as long as it fits the project! So use the welcome message to explain to the user exactly how it should play the game. Explain the rules, and how the player can score points.

User input

Your program needs to ask the user in which column it wants to drop a token. If the user inputs an invalid value, then you inform the user of that and ask again. You MUST validate the user input!

The exact way you implement this, I’ll leave to your consideration. You have to ask the user to input something to select the column. Check my game below if you want an example!

If you want your indices to start at 1 instead of 0? Sure, but that will turn into more lines of code. Do you want letters instead of numbers? Sure, but more lines of code.

Want to make a beautiful ascii art message? Sure, but…. you get the idea.

Representing the board

Feel free to implement all data structures that you need! You have (for practical purposes) infinite memory :)

However, I suggest you use matrices!!! Matrices??? MATRICES????

Yes, matrices! they are just an array-of-arrays :D. But be sure to look at the document I prepared for you!

LAB 4.C will be all about matrices and how to use/think about them.

You can implement your board as a matrix of words to keep the status of the game

Here is what I did:

board: .word
      0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0

Can you use something other than words? Sure, but I don’t recommend it… Cause endianess, and harder to debug.

Note: The board refers only to the contents of the board, not the frame around the tiles! The frame is always the same, it doesn’t need to be stored anywhere! If you include the frame, it’ll make your life harder!

For the status of each tile, I suggest creating a matrix of 0s (empty) 1s (player 1 tokens), and 2s (player 2 tokens).

When you want to print each tile, you simply need to check the status matrix to know if the tile was revealed.

if(board[i][j] == 0) { print('_') }
  else if(board[i][j] == 1) { print('*') }
  else { print('+') }

Check the example below:

The board - this is what you draw:

0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|*|_|_|_|_|_|_|
|*|*|_|_|_|_|_|
|+|*|*|_|_|_|_|
|+|+|+|*|+|_|_|

The matrix representing the board - contains 1s for player 1, and 2 player 2:

0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0, 0,
1, 1, 0, 0, 0, 0, 0,
2, 1, 1, 0, 0, 0, 0,
2, 2, 2, 1, 2, 0, 0

Board size

You can do one of two things:

Easy route

The board should be a 7x6 matrix.

Configurable route

You can make it configurable if you so wish, and then adjust for difficulty. AT THE TOP OF THE FILE! The simplest way, is to name a number, it’s like a #define in C.

In MARS you can do that like this:

.eqv BOARD_SIZE 42 # 7*6 .eqv BOARD_WIDTH 7 .eqv BOARD_HEIGHT 6 

Then you can use the name instead of a number, i.e. in instructions that would normally use a number (the code is nonsense, don’t use it):

lw t0, 3(t1) -> lw t0, N_PLAYS(t1) li t0, 3 -> li t0, N_PLAYS beq t0, 3, _label -> beq t0, N_PLAYS, _label x: .word 3 -> x: .word N_PLAYS arr: .word 0:100 -> arr: .word 0:BOARD_ELEMENTS 

OR… Ask the user?

Create variables, and ask what is the size of the board they want:

board_size: .word 42 # 7*6 board_width: .word 7 board_height: .word 6 

Printing the board

The board must be shown to the user. How exactly? That’s up to you! Check my example below if you are not sure how to proceed!

The only requirement here is that Empty tiles must be clearly empty, and players should have different tokens to represent the tokens. I used an _ to represent empty tiles, * to represent “Player 1” tokens, and + to represent “Player 2” tokens.

If you have any other ideas, go for it! But beware of the difficulty if you do! Drawing the board with ascii art sounds great. But it’ll be a heck of a lot of work! (Want to do it for extra credit? Let me know.)

Ending the game

The game should end when one of the players successfully drops 4 tokens in line. At that point, let the user know that the game has ended, and who won.

Example run

This is only an example!!! Feel free to ignore everything except functionality!

Welcome to connect-4 the MIPS version
 This is a 2 player game, each player will take turns placing a token.
 The objective is to create a line of 4 consecutive tokens.
 Good luck!
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
Select a column to play. Must be between 0 and 6
3
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|*|_|_|_|
Select a column to play. Must be between 0 and 6
3
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|+|_|_|_|
|_|_|_|*|_|_|_|
Select a column to play. Must be between 0 and 6
4
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|+|_|_|_|
|_|_|_|*|*|_|_|
Select a column to play. Must be between 0 and 6
5
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|+|_|_|_|
|_|_|_|*|*|+|_|
Select a column to play. Must be between 0 and 6
2
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|+|_|_|_|
|_|_|*|*|*|+|_|
Select a column to play. Must be between 0 and 6
1
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|+|_|_|_|
|_|+|*|*|*|+|_|
Select a column to play. Must be between 0 and 6
4
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|+|*|_|_|
|_|+|*|*|*|+|_|
Select a column to play. Must be between 0 and 6
3
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|+|_|_|_|
|_|_|_|+|*|_|_|
|_|+|*|*|*|+|_|
Select a column to play. Must be between 0 and 6
5
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|+|_|_|_|
|_|_|_|+|*|*|_|
|_|+|*|*|*|+|_|
Select a column to play. Must be between 0 and 6
2
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|+|_|_|_|
|_|_|+|+|*|*|_|
|_|+|*|*|*|+|_|
Select a column to play. Must be between 0 and 6
5
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|+|_|*|_|
|_|_|+|+|*|*|_|
|_|+|*|*|*|+|_|
Select a column to play. Must be between 0 and 6
4
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|+|+|*|_|
|_|_|+|+|*|*|_|
|_|+|*|*|*|+|_|
Select a column to play. Must be between 0 and 6
4
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|*|_|_|
|_|_|_|+|+|*|_|
|_|_|+|+|*|*|_|
|_|+|*|*|*|+|_|
Select a column to play. Must be between 0 and 6
2
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|*|_|_|
|_|_|+|+|+|*|_|
|_|_|+|+|*|*|_|
|_|+|*|*|*|+|_|
Select a column to play. Must be between 0 and 6
0
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|*|_|_|
|_|_|+|+|+|*|_|
|_|_|+|+|*|*|_|
|*|+|*|*|*|+|_|
Select a column to play. Must be between 0 and 6
0
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|*|_|_|
|_|_|+|+|+|*|_|
|+|_|+|+|*|*|_|
|*|+|*|*|*|+|_|
Select a column to play. Must be between 0 and 6
1
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|*|_|_|
|_|_|+|+|+|*|_|
|+|*|+|+|*|*|_|
|*|+|*|*|*|+|_|
Select a column to play. Must be between 0 and 6
1
 0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|*|_|_|
|_|+|+|+|+|*|_|
|+|*|+|+|*|*|_|
|*|+|*|*|*|+|_|
Congratulations player 2. You won.
Thanks for playing!

-- program is finished running --

Project Stages

In order to help you be aware of your progress, I will recommend a series of mile markers to help you divide up the work. You can, of course, ignore these if you wish. However, if you find you need some direction, by all means follow along.

You have three weeks to complete this project, and I’ve divided this into three stages. You could consider accomplishing each stage for each week. (Or do everything in the last three days at your own peril! :)

Stage 1 - Create the main loop logic and user interaction

The tedious part of this program will be to create all the strings, display them to the user, and get user input. It is also the simpler bit.

During the first week, I suggest you focus on creating an application that prints the strings to the user, implements the main loop, and asks the user for input (don’t forget to make sure the input column is valid!).

At this stage you don’t have to worry about saving the input, etc.

If you finish early, move on to stage 2 and try to display the board. You can edit the matrix manually to “simulate” some plays have occurred.

Stage 2 - The board

This is were matrices become important, make sure you read the materials I prepared for you!

Now that you displayed all strings to the user, and get all information from the user, you can move on to implement the next step: displaying the board and dropping tokens as requested by the user.

In this stage, create the data structure that represent the board - wink wink matrix. Implement functions that help you access the matrix (get address? get element? set element?).

You can (and should) start by implementing the code that prints the board to the user, as it will help you debugging.

Then, use the user input to drop a token. How? When the user chooses a column, maybe you can spiral (loop?) down the column to find the first empty cell?

If you finish early, move on to stage 3 and try to find winning game conditions for horizontal and vertical 4-in-line.

Stage 3 - Winning the game and extra credit

In the third and final stage, you can play the game, but no one is winning here :(

Since you know where the token was dropped, the easiest way, probably not the smartest :), it to check the matrix entries around the dropped token. E.g., the this was the last dropped token:

0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|*|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|

You can check the following 4 regions of interest:

1

0 1 2 3 4 5 6
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|?|?|?|*|?|?|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|

2

0 1 2 3 4 5 6
|_|_|_|_|?|_|_|
|_|_|_|_|?|_|_|
|_|_|_|_|*|_|_|
|_|_|_|_|?|_|_|
|_|_|_|_|?|_|_|
|_|_|_|_|?|_|_|

3

0 1 2 3 4 5 6
|_|_|?|_|_|_|_|
|_|_|_|?|_|_|_|
|_|_|_|_|*|_|_|
|_|_|_|_|_|?|_|
|_|_|_|_|_|_|?|
|_|_|_|_|_|_|_|

4

0 1 2 3 4 5 6
|_|_|_|_|_|_|?|
|_|_|_|_|_|?|_|
|_|_|_|_|*|_|_|
|_|_|_|?|_|_|_|
|_|_|?|_|_|_|_|
|_|?|_|_|_|_|_|

Also, don’t forget to stop the game if the board is full! (Just keep track of how many tokens were dropped.

Finally, go through the rubric and make sure you can tick all boxes!

Once this is done, the project should be completed!!

And if you have time left, why not tackle the extra credit points?

Helpful Tidbits

Starting the code

This is a very simple program in a higher level language! But it is much more complex in assembly. As such, here are some advices for developing your program.

Plan ahead. start by writing high level comments on how you plan to approach the problem:

• If you are not sure what to write, start with the items in the “Your assignment” section of the project :)
• Then add detail to those comments.
• If you need, then write the program in a high-level language, draw a diagram, write pseudo-code, and then translate that into MISP assembly.

Testing

DO NOT TRY TO WRITE THE WHOLE PROGRAM BEFORE TESTING IT!!!!

• Really! Do not do it! It’s the easiest way to get overwhelmed and confused without knowing what to do!
• Implement small parts of the code and test them!

Split your code into functions

Use functions! They will help you manage the cognitive load. Here is a starting point!

main: jal print_welcome jal display_board _main_loop: ... _main_player1: <stuff> j _main_loop <moar stuff> 

Extra credit

Want to do something more for a couple of points? (10 pts)

Have an idea? Let me know! I’ll let you know if it’s worth extra credit. It must change the game play significantly.

BUT MAKE A BACKUP COPY OF YOUR SUBMISSION!!!

Submission

Submit a single ZIP file with your project named username_proj1.zip (e.g. lun8_proj1.zip). In the zip file, there should be no folder!, just the following files:

Your connect.asm file. Put your name and username at the top of the file in comments! A readme.txt file. DO NOT SUBMIT A README.DOCX. DO NOT SUBMIT A README.PDF. SUBMIT A PLAIN TEXT FILE. PLEASE. It should contain:

• Your name
• Your Pitt username
• Anything that does not work
• Anything else you think might help the grader grade your project more easily

Submit into the canvas. Let me know immediately if there are any problems submitting your work.

Rubric

• [10] Planning
  • You have until Friday the 16th of February to meet with your TA and discuss your plan to solve the project. IT’S ALL OR NOTHING
• [90] The game
  • [5] Submitted as per instructions
    • No exceptions! includes file with correct name, files, and everything I asked for!!! It’s all or nothing!
  • [15] Coding style
    • [5] Functions include a C/Java pseudo-code implementation as a comment at the top
    • [5] Commented the code, so the grader and I can understand what is going on!!!!!!!!
    • [5] Split code into functions that follow conventions (no functions, no points)
      • Must preserve saved registers
      • ONLY JAL and JR instructions are used to call a function and return
      • Passed arguments in “a” registers and returned in “v” registers
      • etc.
  • [15] Game flow
    • [5] Main loop works and ends somehow
    • [5] No crashes during normal operation (if game crashes when user inputs a letter in read_int syscall it’s ok!)
    • [5] Game ends, prints winner, and syscall 10 is used to terminate
  • [40] Mechanics
    • [6] The first player with 4 tokens in line (horizontal and vertical) wins
    • [10] The first player with 4 tokens in line (both diagonals) wins
    • [6] Game terminates when board is full and a play cannot be made
    • [6] Token is placed in lowest free slot in selected column
    • [6] A token cannot be placed in a full column
    • [6] Placed tokens are not overwritten
  • [15] Input and Output
    • [2] Explains the game to the user in a welcome message that accurately explains how to play the game
    • [4] Prompts the user for input and validates the input
    • [4] Tells the user the input is invalid, and asks the user for input again
    • [5] Prints the board with clearly marked tiles (empty, player 1, player 2)

Note: You may lose points for significantly deviating from the described game, even if the items are not described in the rubric. E.g. not having 2 players take turns! If you are unsure about any missing feature, talk to your TA/Instructor.

Note2: You may lose points for significantly understating the status of your project in the readme file! The purpose of the readme is assisting in the grading, so I don’t want to see any readme files stating everything works when it clearly doesn’t. If you do that, you will lose (more) points! If you are unsure about any missing feature, talk to your TA/Instructor.