Programming Exercise I: Showing a one-player Gomoku game

Programming Exercise I: Showing a One-Player Gomoku Game

Absolutely no copying others’ works
(Unlike other languages, using others’ assembly code is obvious.)
Development Requirements
When start developing the exercise, follow the two requirements below:

Have to use the MIPS (Microprocessor without Interlocked Pipeline Stages) assembly language to develop the exercise.
Use the MARS (MIPS Assembler and Runtime Simulator) to test your exercise. The MARS will also be used by the instructor to grade exercises.

Soft Due Date^† and Submission Method
On or before Thursday, February 13, 2025 and upload the source code (no documentation needed) to the section of “COVID-19 Exams, Homeworks, & Programming Exercises” of Blackboard.

^†Since related topics may not be covered completely by the due date, no penalty will be applied if submitted after the due date. However, you may lag behind if you are not able to submit it by then. In addition, the Exam I will cover the materials from the Programming Exercise I.

Objective
Design and implement a MIPS assembly program, which displays a 6×6 Gomoku game of one player. The final program is about 125 lines, many of which are for I/O. The purpose of this exercise is to get students ready for assembly programming and the second exercise, playing a Gomoku game against computer.

An example of an 8×8 Gomoku game, whose winning combination is five pieces in a row

Rules of a Free-Style Gomoku Game
It is a board game for two players who take turns in putting the pieces X and O on empty intersections of a board. Each player’ goal is to create an unbroken row of certain pieces horizontally, vertically, or diagonally. The game ends when either the goal is achieved or winning by either player is not possible such as the board being full. The winner of the game is the player achieving the goal first. Note that the online game on the right side is for demonstration only, and is not exact the game we want to implement.

Requirements
The 6×6, for-display-only Gomoku game includes the following requirements:

(Printing user prompts: 10%) Print appropriate user prompts to guide users to interact with your system.

(Displaying board: 10%) The board includes two parts: the game board (left) and the index board (right) as follows:

      . . . . . .     ⇒     0 1 2 3 4 5
      . . . . . .     ⇒     6 7 8 9 a b
      . . . . . .     ⇒     c d e f g h
      . . . . . .     ⇒     i j k l m n
      . . . . . .     ⇒     o p q r s t
      . . . . . .     ⇒     u v w x y z

(Checking the input move: 15%) Check whether the move (0..9, a..z) is correct. You may need to use the ASCII code for this function.
(Checking a duplicate move: 15%) Check whether the move was taken before.

(Marking the moves: 15%) Mark the move by using the index board. Start with the piece ‘X’ and alternate between the pieces ‘X’ and ‘O’. For example, if the first move is ‘k’, the board is displayed as follows:

      . . . . . .     ⇒     0 1 2 3 4 5
      . . . . . .     ⇒     6 7 8 9 a b
      . . . . . .     ⇒     c d e f g h
      . . X . . .     ⇒     i j k l m n
      . . . . . .     ⇒     o p q r s t
      . . . . . .     ⇒     u v w x y z

(Next move: 15%) Continue with the next move after asking.
(New game: 20%) Start a new game after asking.
Ignore the result (win/loss). The game ends when the user requests for no new game.

Programming Hints
The four essential components of software are (i) algorithms, (ii) data structures, (iii) programming languages, and (iv) code, where algorithms are the most critical one. In addition, using appropriate data structures could save a great deal of coding work, especially for assembly coding. The following hints are from the instructor and you do not necessarily have to use them:

To represent the game board, a 6×6 grid:

      . . . . . .     ⇒     0 1 2 3 4 5
      . . . . . .     ⇒     6 7 8 9 a b
      . . . . . .     ⇒     c d e f g h
      . . . . . .     ⇒     i j k l m n
      . . . . . .     ⇒     o p q r s t
      . . . . . .     ⇒     u v w x y z

the instructor uses the following string:

     board:  .ascii   "\n\n    . . . . . .      0 1 2 3 4 5"
             .ascii     "\n    . . . . . .      6 7 8 9 a b"
             .ascii     "\n    . . . . . .      c d e f g h"
             .ascii     "\n    . . . . . .      i j k l m n"
             .ascii     "\n    . . . . . .      o p q r s t"
             .asciiz    "\n    . . . . . .      u v w x y z\n"

Also, the instructor uses the following command to represent the offsets:

     offset: .half     6,   8,  10,  12,  14,  16  
             .half    39,  41,  43,  45,  47,  49
             .half    72,  74,  76,  78,  80,  82
             .half   105, 107, 109, 111, 113, 115
             .half   138, 140, 142, 144, 146, 148
             .half   171, 173, 175, 177, 179, 181

where the numbers are offsets (not assembly code) and the new line, ‘\n’, is one byte long. Convert the indexes a–z to 10–35, respectively. Assuming the converted index is in $t0, the following code then puts the piece ‘X’ at that location:

     mul  $t0, $t0, 2        # Each offset is two-byte long.
     lh   $t1, offset($t0)   # Load $t1 with the offset of the index $t0.
     li   $t2, 'X'           # Put the piece ‘X’ in $t2.
     sb   $t2, board($t1)    # Put the piece at the location, board+offset.

Using subroutines can reduce repeated code. An example of how to call the subroutine routine1 is given as follows:
```
          jal   routine1      # Jump and link to routine1
   next:  
          ...
```
where the label next is not required. The following command in the subroutine routine1 will return the control back to the next, the next command after the “jal routine1”:
```
   routine1:
          ...
          jr    $ra           # Jump to the contents of $ra
```
where the return address is saved in the register $31 or $ra

When a subroutine calls another subroutine, the return address, $31 or $ra, has to be saved before making the call. The return address is restored after the called subroutine returns. The instructor uses the runtime stack to save the return addresses, so deep subroutine calls are supported. Use the following two commands to push the $ra to the runtime stack:
```
       subu  $sp, $sp, 4      # Decrement the $sp to make space for $ra.
       sw    $ra, ($sp)       # Push the return address, $ra.
```
and use the following two commands to pop up the $ra from the runtime stack:
```
       lw    $ra, ($sp)       # Pop the return address, $ra.
       addu  $sp, $sp, 4      # Increment the $sp.
```
You may also use the runtime stack to save the register and variable values.

Sample code of marking a game board is given below for your reference:

MarkBoard.asm

# 
######################### Mark the Game Board #########################
#
        .data
prompt: .asciiz  "\nEnter the next move: (0..z) "
board:  .ascii   "\n\n    . . . . . .      0 1 2 3 4 5"
        .ascii     "\n    . . . . . .      6 7 8 9 a b"
        .ascii     "\n    . . . . . .      c d e f g h"
        .ascii     "\n    . . . . . .      i j k l m n"
        .ascii     "\n    . . . . . .      o p q r s t"
        .asciiz    "\n    . . . . . .      u v w x y z\n"

offset: .half     6,   8,  10,  12,  14,  16
        .half    39,  41,  43,  45,  47,  49
        .half    72,  74,  76,  78,  80,  82
        .half   105, 107, 109, 111, 113, 115
        .half   138, 140, 142, 144, 146, 148
        .half   171, 173, 175, 177, 179, 181

#
########################## Main Program #######################
#
      .text
      .globl main
main:
      li    $t0, 6             # Mark 6 moves only.

      # Beginning of a loop
L1:   la    $a0, board
      li    $v0, 4             # Print the game board.
      syscall

      la    $a0, prompt
      li    $v0, 4
      syscall                  # Print the prompt.

      # Read the next move.
      li    $v0, 12            # Read a move (0..z).
      syscall                  # The syscall 12 is read char.

      move  $a0, $v0           # a0: the move in character
      jal   MarkMove           # Call the subroutine MarkMove.
      sub   $t0, $t0, 1        # Decrease the counter $t0 by 1.
      bnez  $t0, L1            # If not end of loop, go to L1.
           
      # Closing up
      li    $v0, 10            # Exit.
      syscall

# 
######################### Mark a Move #########################
#
# Input:  $a0 (the move in character)   
# Output: 
           
MarkMove:
      # Save data in the runtime stack.
      subu  $sp, $sp, 4        # Decrement the $sp to make space for $ra.
      sw    $ra, ($sp)         # Push/save the return address, $ra.
      subu  $sp, $sp, 4        # Decrement the $sp to make space for $t0.
      sw    $t0, ($sp)         # Push/save the $t0.
     
      # Convert the move to an integer.
      bgt   $a0, '9', L11
      sub   $t0, $a0, '0'
      j     L12
L11:  sub   $t0, $a0, 'a'
      add   $t0, $t0, 10

      # Find the offset.
L12:  mul   $t0, $t0, 2       # Each offset is two-byte long.
      lh    $t1, offset($t0)  # Load $t1 with the offset of the index $t0.

      # Mark the board.
      li    $t2, 'X'          # Put the piece ‘X’ in $t2.
      sb    $t2, board($t1)   # Put the piece at the location, board+offset.

      # Restore the data from the runtime stack.
      lw    $t0, ($sp)         # Pop/restore $t0.
      addu  $sp, $sp, 4        # Increment the $sp.
      lw    $ra, ($sp)         # Pop/restore the return address, $ra.
      addu  $sp, $sp, 4        # Increment the $sp.
      jr    $ra                # Return.

Execution Examples
The following list shows some execution examples, where the italic, white text with a navy background color is entered by users:

Examples of Exercise I Execution

Start Showing a One-Player Gomoku Game.
 
     . . . . . .      0 1 2 3 4 5
     . . . . . .      6 7 8 9 a b
     . . . . . .      c d e f g h
     . . . . . .      i j k l m n
     . . . . . .      o p q r s t
     . . . . . .      u v w x y z

Enter the next move: (0..z)  5 

     . . . . . X      0 1 2 3 4 5
     . . . . . .      6 7 8 9 a b
     . . . . . .      c d e f g h
     . . . . . .      i j k l m n
     . . . . . .      o p q r s t
     . . . . . .      u v w x y z

Continue? (y/n)  y 

     . . . . . X      0 1 2 3 4 5
     . . . . . .      6 7 8 9 a b
     . . . . . .      c d e f g h
     . . . . . .      i j k l m n
     . . . . . .      o p q r s t
     . . . . . .      u v w x y z

Enter the next move: (0..z)  p 

     . . . . . X      0 1 2 3 4 5
     . . . . . .      6 7 8 9 a b
     . . . . . .      c d e f g h
     . . . . . .      i j k l m n
     . O . . . .      o p q r s t
     . . . . . .      u v w x y z

Continue? (y/n)  y 

     . . . . . X      0 1 2 3 4 5
     . . . . . .      6 7 8 9 a b
     . . . . . .      c d e f g h
     . . . . . .      i j k l m n
     . O . . . .      o p q r s t
     . . . . . .      u v w x y z

Enter the next move: (0..z)  r 

     . . . . . X      0 1 2 3 4 5
     . . . . . .      6 7 8 9 a b
     . . . . . .      c d e f g h
     . . . . . .      i j k l m n
     . O . X . .      o p q r s t
     . . . . . .      u v w x y z

Continue? (y/n)  y 

     . . . . . X      0 1 2 3 4 5
     . . . . . .      6 7 8 9 a b
     . . . . . .      c d e f g h
     . . . . . .      i j k l m n
     . O . X . .      o p q r s t
     . . . . . .      u v w x y z

Enter the next move: (0..z)  5 
***** Duplicate move! *****

     . . . . . X      0 1 2 3 4 5
     . . . . . .      6 7 8 9 a b
     . . . . . .      c d e f g h
     . . . . . .      i j k l m n
     . O . X . .      o p q r s t
     . . . . . .      u v w x y z

Enter the next move: (0..z)  / 
***** Wrong move! *****

     . . . . . X      0 1 2 3 4 5
     . . . . . .      6 7 8 9 a b
     . . . . . .      c d e f g h
     . . . . . .      i j k l m n
     . O . X . .      o p q r s t
     . . . . . .      u v w x y z

Enter the next move: (0..z)  k 

     . . . . . X      0 1 2 3 4 5
     . . . . . .      6 7 8 9 a b
     . . . . . .      c d e f g h
     . . O . . .      i j k l m n
     . O . X . .      o p q r s t
     . . . . . .      u v w x y z

Continue? (y/n)  n 
New game? (y/n)  y 

Start Showing a One-Player Gomoku Game.

     . . . . . .      0 1 2 3 4 5
     . . . . . .      6 7 8 9 a b
     . . . . . .      c d e f g h
     . . . . . .      i j k l m n
     . . . . . .      o p q r s t
     . . . . . .      u v w x y z

Enter the next move: (0..z)  g 

     . . . . . .      0 1 2 3 4 5
     . . . . . .      6 7 8 9 a b
     . . . . X .      c d e f g h
     . . . . . .      i j k l m n
     . . . . . .      o p q r s t
     . . . . . .      u v w x y z

Continue? (y/n)  y 

     . . . . . .      0 1 2 3 4 5
     . . . . . .      6 7 8 9 a b
     . . . . X .      c d e f g h
     . . . . . .      i j k l m n
     . . . . . .      o p q r s t
     . . . . . .      u v w x y z

Enter the next move: (0..z)  0 

     O . . . . .      0 1 2 3 4 5
     . . . . . .      6 7 8 9 a b
     . . . . X .      c d e f g h
     . . . . . .      i j k l m n
     . . . . . .      o p q r s t
     . . . . . .      u v w x y z

Continue? (y/n)  n 
New game? (y/n)  n 
-- program is finished running --

Possible Instructions to Be Used
The following directives and instructions may be used in this exercise, but you are not limited to them. For instruction syntax, check MIPS Instruction Reference.

No.	Directive	Description
1	`.ascii "string"`	Allocating space for string
2	`.asciiz "string"`	Allocating space for string, NULL terminated
3	`.byte`	Allocating space for a byte
4	`.data`	Beginning of data section
5	`.globl name`	Making the following name be a global symbol
6	`.half`	Allocating space for a half word (two bytes)
7	`.space n`	Allocating `n` bytes of space
8	`.text`	Beginning of text section
No.	Instruction	Operation	Description
1	`add rd, rs, rt`	`rd = rs + rt`	Add; `rd`: destination register, `rs`: first source register, and `rt`: second source register or immediate value. Check MIPS Registers and Usage Convention.
2	`addu rd, rs, rt`	`rd = rs + rt` (no overflow)	Add unsigned
3	`beq rs, rt, label`	`if rs==rt then goto label`	Branch if equal to
4	`bgt rs, rt, label`	`if rs>rt then goto label`	Branch if greater than
5	`blt rs, rt, label`	`if rs<rt then goto label`	Branch if less than
6	`j label`	`jump to label`	Jump
7	`jal label`	`jump to label` and save the return address in `$31` or `$ra`	Jump and link
8	`jr rs`	`jump to [rs]`; [ ]: contents of	Jump and link
9	`la rd, mem`	`rd = address( mem )`	Load address
10	`lb rd, mem`	`rd = mem`	Load byte
11	`lh rd, mem`	`rd = mem`	Load half word
12	`li rd, imm`	`rd = imm`	Load immediate
13	`lw rd, mem`	`rd = mem`	Load word
14	`mul rd, rs, rt`	`rd = rs × rt`	Multiply
15	`sb rs, mem`	`mem = rs`	Store byte
16	`sub rd, rs, rt`	`rd = rs - rt`	Subtract
17	`subu rd, rs, rt`	`rd = rs - rt` (no overflow)	Subtract unsigned
18	`sw rs, mem`	`mem = rs`	Store word
19	`syscall`		System call; check System Services.

The following table lists some System Services provided by the MARS:

Service	Code in `$v0`	Arguments	Result
print_int	1	`$a0` = integer to be printed
print_float	2	`$f12` = float to be printed
print_double	3	`$f12` = double to be printed
print_string	4	`$a0` = address of string in memory
read_int	5		integer returned in `$v0`
read_float	6		float returned in `$v0`
read_double	7		double returned in `$v0`
read_string	8	`$a0` = address of string input buffer `$a1` = length of string buffer (`n`)
malloc	9	`$a0` = amount	address in `$v0`
exit	10
print character	11	`$a0` = character to be printed
read character	12		character returned in `$v0`

Evaluations
The following features will be considered when grading:

Specifications:
- The instructor has given the exercise specifications as detailedly as possible. If you are confused about the specifications, you should ask in advance. Study the specifications very carefully. No excuses for misunderstanding or missing parts of the specifications after grading.
- The specifications may not be possible to cover every detail. You are free to implement the issues not mentioned in the specifications, but the implementations should make sense. Implemented functions lacking common sense may cause the instructor to grade your exercise mistakenly, and thus lower your grade.
- The exercise must meet the specifications. However, exercises with functions exceeding the specifications will not receive extra credits.

Grading:
- This exercise will be graded after the source code is submitted. Students take full responsibility if the code does not work.
- The MARS simulator will be used to grade exercises. Make sure your exercise works on MARS.
- Before submitting the exercise, test it comprehensively. Absolutely no extra points will be granted after grading.
- A set of test data will be used to test the exercises of all students. The grades are primarily based on the results of testing. Other factors such as performance, programming styles, algorithms, and data structures will be only considered minimally.
- Unless specified, no error checking is required.
- The total weight of exercises is 20% (10% each) of the final grade.
- Though Exercise II covers parts of Exercise I, you still have to submit both exercises separately. One exercise will not be counted twice.
- The instructor will inform you the exercise evaluations by emails or Blackboard after grading.

Comments:
- According to a study, students in computer-science courses learn much more by building large-scale exercises instead of many small-scale test programs, which give fragmented knowledge contrary to solid understanding of the language.
- Time management is critical for software development. If you are not able to complete the exercises, show whatever you have accomplished, so the instructor can give partial credit to your exercises.