Programming Exercise II: Playing a 2×2 Dot-and-Box Game


Absolutely no copying others’ works
(Unlike other languages, using others’ assembly code is obvious.)
According to a study, students in computer courses learn much more by building large-scale exercises instead of many small-scale test programs like these, which give fragmented knowledge contrary to solid understanding of the system.
Development Requirements
When start developing the exercise, follow the two requirements below:

Due Date and Submission Method
On or before Monday, March 31, 2025 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 2×2 dot-and-box game against a user. The final program is about 200 lines. The purpose of this exercise is to make students practice assembly language programming including various control instructions, functions, and the runtime stack.

Rules of Dot-and-Box Game
Starting with an empty grid of dots, players take turns, adding a single horizontal or vertical line between two unjoined adjacent dots. A player who completes the fourth side of a 1×1 box earns one point and takes another turn. The game ends when no more lines can be placed. The winner of the game is the player with the most points. The board may be of any size.


An example of a 2×2 dot-and-box game


Requirements
The 2×2 dot-and-box 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:

Execution Examples
The following list shows some execution examples, where


Examples of Exercise II Execution
Start Playing a 2x2 Dot-and-Box Game.

   . . .          . 0 . 1 .
                  2   3   4
   . . .          . 5 . 6 .
                  7   8   9
   . . .          . a . b .

You are the player O.  Enter the your move (0..b):  a 

   . . .          . 0 . 1 .
                  2   3   4
   . . .          . 5 . 6 .
                  7   8   9
   .-. .          . a . b .

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

   . . .          . 0 . 1 .
   |              2   3   4
   . . .          . 5 . 6 .
                  7   8   9
   .-. .          . a . b .

You are the player O.  Enter the your move (0..b):  5 

   . . .          . 0 . 1 .
   |              2   3   4
   .-. .          . 5 . 6 .
                  7   8   9
   .-. .          . a . b .

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

   . . .          . 0 . 1 .
   |   |          2   3   4
   .-. .          . 5 . 6 .
                  7   8   9
   .-. .          . a . b .

You are the player O.  Enter the your move (0..b):  8 

   . . .          . 0 . 1 .
   |   |          2   3   4
   .-. .          . 5 . 6 .
     |            7   8   9
   .-. .          . a . b .

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

   . .-.          . 0 . 1 .
   |   |          2   3   4
   .-. .          . 5 . 6 .
     |            7   8   9
   .-. .          . a . b .

You are the player O.  Enter the your move (0..b):  7 

   . .-.          . 0 . 1 .
   |   |          2   3   4
   .-. .          . 5 . 6 .
   |O|            7   8   9
   .-. .          . a . b .

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

Start Playing a 2x2 Dot-and-Box Game.

   . . .          . 0 . 1 .
                  2   3   4
   . . .          . 5 . 6 .
                  7   8   9
   . . .          . a . b .

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

   . . .          . 0 . 1 .
     |            2   3   4
   . . .          . 5 . 6 .
                  7   8   9
   . . .          . a . b .

You are the player O.  Enter the your move (0..b):  1 

   . .-.          . 0 . 1 .
     |            2   3   4
   . . .          . 5 . 6 .
                  7   8   9
   . . .          . a . b .

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

   . .-.          . 0 . 1 .
     | |          2   3   4
   . . .          . 5 . 6 .
                  7   8   9
   . . .          . a . b .

You are the player O.  Enter the your move (0..b):  0 

   .-.-.          . 0 . 1 .
     | |          2   3   4
   . . .          . 5 . 6 .
                  7   8   9
   . . .          . a . b .

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

   .-.-.          . 0 . 1 .
   | | |          2   3   4
   . . .          . 5 . 6 .
                  7   8   9
   . . .          . a . b .

You are the player O.  Enter the your move (0..b):  7 

   .-.-.          . 0 . 1 .
   | | |          2   3   4
   . . .          . 5 . 6 .
   |              7   8   9
   . . .          . a . b .

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

   .-.-.          . 0 . 1 .
   | | |          2   3   4
   . . .          . 5 . 6 .
   |              7   8   9
   .-. .          . a . b .

You are the player O.  Enter the your move (0..b):  8 

   .-.-.          . 0 . 1 .
   | | |          2   3   4
   . . .          . 5 . 6 .
   | |            7   8   9
   .-. .          . a . b .

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

   .-.-.          . 0 . 1 .
   | |X|          2   3   4
   . .-.          . 5 . 6 .
   | |            7   8   9
   .-. .          . a . b .

I (X) won!
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 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 bne rs, rt, label if rs≠rt then goto label Branch if not equal to
7 j label jump to label Jump
8 jal label jump to label and save the return address in $31 Jump and link
9 jr rs jump to [rs]; [ ]: contents of Jump register
10 la rd, mem rd = address( mem ) Load address
11 lb rd, mem rd = mem Load byte
12 li rd, imm rd = imm Load immediate
13 lw rd, mem rd = mem Load word
14 move rd, rs rd = rs Move register
15 mul rd, rs, rt rd = rs × rt Multiply
16 sb rs, mem mem = rs Store byte
17 sub rd, rs, rt rd = rs - rt Subtract
18 subu rd, rs, rt rd = rs - rt (no overflow) Subtract unsigned
19 sw rs, mem mem = rs Store word
20 syscall   System call; check System Services.
21 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: