Programming Exercise II: Playing a Tic-Tac-Toe Game

(Industry-Level, Second-to-None Comprehensive Specifications)


Absolutely no copying others’ works

(Unlike other languages, using others’ assembly code is obvious. Assembly-language programming is not easy, but the instructor has made the specifications as simple as possible and provides much code. You should be able to get the exercises done based on the given code.)

Development Requirements
When start developing the exercise, follow the two requirements below:


Due Date and Submission Method
On or before Monday, March 25, 2024 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 tic-tac-toe game. The final program is less than 200 lines. The purpose of this exercise is to make students practice assembly language programming including functions, various control instructions, and the runtime stack.
Requirements
The 3×3 tic-tac-toe game 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 Tic-tac-toe Game.

     | |       1|2|3
    -----      -----
     | |       4|5|6
    -----      -----
     | |       7|8|9

Enter the next move (1-9):   4 

     | |       1|2|3
    -----      -----
    o| |       4|5|6
    -----      -----
     | |       7|8|9

My turn: 3

     | |x      1|2|3
    -----      -----
    o| |       4|5|6
    -----      -----
     | |       7|8|9

Enter the next move (1-9):   6 

     | |x      1|2|3
    -----      -----
    o| |o      4|5|6
    -----      -----
     | |       7|8|9

My turn: 8

     | |x      1|2|3
    -----      -----
    o| |o      4|5|6
    -----      -----
     |x|       7|8|9

Enter the next move (1-9):   5 

     | |x      1|2|3
    -----      -----
    o|o|o      4|5|6
    -----      -----
     |x|       7|8|9

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

Start Playing a Tic-tac-toe Game.

     | |       1|2|3
    -----      -----
     | |       4|5|6
    -----      -----
     | |       7|8|9

My turn: 5

     | |       1|2|3
    -----      -----
     |x|       4|5|6
    -----      -----
     | |       7|8|9

Enter the next move (1-9):   3 

     | |o      1|2|3
    -----      -----
     |x|       4|5|6
    -----      -----
     | |       7|8|9

My turn: 1

    x| |o      1|2|3
    -----      -----
     |x|       4|5|6
    -----      -----
     | |       7|8|9

Enter the next move (1-9):   6 

    x| |o      1|2|3
    -----      -----
     |x|o      4|5|6
    -----      -----
     | |       7|8|9

My turn: 9

    x| |o      1|2|3
    -----      -----
     |x|o      4|5|6
    -----      -----
     | |x      7|8|9


I (the system) won!
New game? (y/n)   y 

Start Playing a Tic-tac-toe Game.

     | |       1|2|3
    -----      -----
     | |       4|5|6
    -----      -----
     | |       7|8|9

My turn: 9

     | |       1|2|3
    -----      -----
     | |       4|5|6
    -----      -----
     | |x      7|8|9

Enter the next move (1-9):   5 

     | |       1|2|3
    -----      -----
     |o|       4|5|6
    -----      -----
     | |x      7|8|9

My turn: 1

    x| |       1|2|3
    -----      -----
     |o|       4|5|6
    -----      -----
     | |x      7|8|9

Enter the next move (1-9):   7 

    x| |       1|2|3
    -----      -----
     |o|       4|5|6
    -----      -----
    o| |x      7|8|9

My turn: 3

    x| |x      1|2|3
    -----      -----
     |o|       4|5|6
    -----      -----
    o| |x      7|8|9

Enter the next move (1-9):   6 

    x| |x      1|2|3
    -----      -----
     |o|o      4|5|6
    -----      -----
    o| |x      7|8|9

My turn: 4

    x| |x      1|2|3
    -----      -----
    x|o|o      4|5|6
    -----      -----
    o| |x      7|8|9

Enter the next move (1-9):   2 

    x|o|x      1|2|3
    -----      -----
    x|o|o      4|5|6
    -----      -----
    o| |x      7|8|9

My turn: 8

    x|o|x      1|2|3
    -----      -----
    x|o|o      4|5|6
    -----      -----
    o|x|x      7|8|9

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