Programming Exercise II: Playing a Gomoku Game
(Industry-Level, Second-to-None Comprehensive Specifications)

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:

Due Date and Submission Method
On or before Monday, March 27, 2023 and upload the source code (no documentation needed) to the section of “COVID-19 Exams, Homeworks, & Programming Exercises” of Blackboard.

†Though Exercise II covers parts of Exercise I, you still have to submit both exercises separately. One exercise will not be counted twice.




Objective
Design and implement a MIPS assembly program, which plays a Gomoku game. The final program is about 250 lines. The purpose of this exercise is to make students practice assembly language programming including various control instructions, functions, and the runtime stack.

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. The 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, e.g., 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, free-style Gomoku game with a winning combination of an unbroken row of four pieces horizontally, vertically, or diagonally includes the following requirements:

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: 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 2 Execution 
Start Playing a 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

You are the player O.  Enter the next move: (0..z)  l 

     . . . . . .      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 p q r s t
     . . . . . .      u v w x y z

I (the System) am the player X and my move is w

     . . . . . .      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 p q r s t
     . . X . . .      u v w x y z

You are the player O.  Enter the next move: (0..z)  q 

     . . . . . .      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 . . .      o p q r s t
     . . X . . .      u v w x y z

I (the System) am the player X and my move is 8

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

You are the player O.  Enter the next move: (0..z)  v 

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

I (the System) am the player X and my move is 5

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

You are the player O.  Enter the next move: (0..z)  g 

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

You (O) won!
New game? (y/n)  y 

Start Playing a Gomoku Game.
I (the System) am the player X and my move is 4

     . . . . 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

You are the player O.  Enter the next move: (0..z)  z 

     . . . . 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
     . . . . . O      u v w x y z

I (the System) am the player X and my move is d

     . . . . X .      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
     . . . . . O      u v w x y z

You are the player O.  Enter the next move: (0..z)  u 

     . . . . X .      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
     O . . . . O      u v w x y z

I (the System) am the player X and my move is s

     . . . . X .      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
     . . . . X .      o p q r s t
     O . . . . O      u v w x y z

You are the player O.  Enter the next move: (0..z)  0 

     O . . . X .      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
     . . . . X .      o p q r s t
     O . . . . O      u v w x y z

I (the System) am the player X and my move is b

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

You are the player O.  Enter the next move: (0..z)  t 

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

I (the System) am the player X and my move is e

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

You are the player O.  Enter the next move: (0..z)  v 

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

I (the System) am the player X and my move is o

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

You are the player O.  Enter the next move: (0..z)  1 

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

I (the System) am the player X and my move is a

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

You are the player O.  Enter the next move: (0..z)  6 

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

I (the System) am the player X and my move is f

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

You are the player O.  Enter the next move: (0..z)  c 

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

I (the System) am the player X and my move is g

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

I (X) won!
New game? (y/n)  y 

Start Playing a Gomoku Game.

...

We are tied!
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 ble rs, rt, label if rs≤rt then goto label Branch if less than or equal to
6 blt rs, rt, label if rs<rt then goto label Branch if less than
7 bne rs, rt, label if rs≠rt then goto label Branch if not equal to
8 bnez rs, label if rs≠0 then goto label Branch if not equal to zero
9 j label jump to label Jump
10 jal label jump to label and save the return address in $31 Jump and link
11 jr rs jump to [rs]; [ ]: contents of Jump register
12 la rd, mem rd = address( mem ) Load address
13 lb rd, mem rd = mem Load byte
14 lh rd, mem rd = mem Load half word
15 li rd, imm rd = imm Load immediate
16 lw rd, mem rd = mem Load word
17 move rd, rs rd = rs Move register
18 mul rd, rs, rt rd = rs × rt Multiply
19 sb rs, mem mem = rs Store byte
20 sub rd, rs, rt rd = rs - rt Subtract
21 subu rd, rs, rt rd = rs - rt (no overflow) Subtract unsigned
22 sw rs, mem mem = rs Store word
23 syscall   System call; check System Services.
24 xor rd, rs, rt rd = rs xor rt Bitwise exclusive or

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
sleep 32 $a0 = the length of time to sleep in milliseconds. Causes the MARS Java thread to sleep for (at least) the specified number of milliseconds.
random int range 42 $a0 = i.d. of pseudorandom number generator (any int).
$a1 = upper bound of range of returned values.		 $a0 contains pseudorandom, uniformly distributed int value in the range 0 ≤ [int] < [upper bound], drawn from this random number generator’s sequence.

Evaluations
The following features will be considered when grading: