Programming Exercise II: Playing a 2×2 dot-and-box game

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:

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.

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:

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

(Starting the game: 10%) Randomly pick the system (X) or the user (O) to start the game.

(Taking turns: 10%) The two players take turns making moves.

(System’s moves: 25%) Randomly pick the next move for the system. The move [0-9ab] has to be SHOWN. Use the sleep function of syscall 32 of MARS to slow down the moves (like 3 seconds).

(Marking the moves: 10%) Mark the move by using the index board. For example, if the first move is 8, the board is displayed as follows:

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

    (board)     (index)              (board)     (index)

(Declaring and marking a winner: 25%) A player who firstly completes the 4th side of a 1×1 box wins the game. Mark the boxes right after completing their 4th sides. The system is X and the user is O. For example, if the next move is 8, the board is displayed as follows:

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

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

     (board)     (index)              (board)     (index)

     The System (X) won!

(New game: 10%) Start a new game after asking once a winner is found.

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 2×2 grid:

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

     (board)           (index)

and use the numbers, 0, 1, 2, and 3, to represent the four boxes in the 2×2 grid as follows:

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

The instructor uses the following strings to represent the game board and index:

   board:  .ascii   "\n\n   . . .          . 0 . 1 ."
           .ascii     "\n                  2   3   4"
           .ascii     "\n   . . .          . 5 . 6 ."
           .ascii     "\n                  7   8   9"
           .asciiz    "\n   . . .          . a . b .\n"

The assembly code annotated with the corresponding offsets is given as follows:

   board:  .ascii   "\n\n   . . .          . 0 . 1 ."
         offset =     0 1234567890123456789012345678
           .ascii     "\n                  2   3   4"
         offset =  28 + 1234567890123456789012345678
           .ascii     "\n   . . .          . 5 . 6 ."
         offset =  56 + 1234567890123456789012345678
           .ascii     "\n                  7   8   9"
         offset =  84 + 1234567890123456789012345678
           .asciiz    "\n   . . .          . a . b .\n"
         offset = 112 + 1234567890123456789012345678 9

where the numbers are offsets (not assembly code) and the new line, ‘\n’, is one byte long. The following data structures are used to represent the game board, marker offsets, markers, and box offsets, respectively:

   offset: .byte     6,   8,  33,  35,  37,  62,  64,  89,  91,  93,  118, 120
   marker: .byte    '-', '-', '|', '|', '|', '-', '-', '|', '|', '|', '-', '-'
   box:    .byte    34,  36,  90,  92

Convert the indexes a and b to 10 and 11, respectively. Assuming the integer move, 0-11 (or 0-9 a-b), is stored in $t0, the following code then puts the marker at that location:

   lb  $t1, offset($t0)   # Load $t1 with the offset of the index $t0.
   lb  $t2, marker($t0)   # Find the corresponding marker.
   sb  $t2, board($t1)    # Put the marker at the location, board+offset.

For example, if the first move is 8 stored in $t0 and the above code is executed, the board is displayed as follows:

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

    (board)     (index)              (board)     (index)

Since the grading is mainly based on the testing results without considering much about performance and algorithms, the instructor uses the following data structure to find the scoring combinations of a move. All possible combinations are listed as follows:

   side:   .ascii   "02350     "         # Move 0
           .ascii   "13461     "         # Move 1
           .ascii   "20350     "         # Move 2
           .ascii   "3025031461"         # Move 3
           .ascii   "41361     "         # Move 4
           .ascii   "50230578a2"         # Move 5
           .ascii   "61341689b3"         # Move 6
           .ascii   "758a2     "         # Move 7
           .ascii   "857a2869b3"         # Move 8
           .ascii   "968b3     "         # Move 9
           .ascii   "a5782     "         # Move a or 10
           .ascii   "b6893     "         # Move b or 11

where the first character of each line is the most recent move, the next three characters are the other three sides of the corresponding box, and the last digit is the box scored if the move completes the box. Since one side may complete two boxes, it has ten characters, so the beginning address of each move’s scoring combinations could be found easily. For example, the beginning address of the scoring combinations "857a2869b3" of the move 8 is 80=8×10:

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

     (board)     (board)            (board)       (index)

Sample code of checking box is given below for your reference:

CheckBox.asm (for input [0-9] but no a or b)

#
# Checking Boxes of a 2x2 Dot-and-Box Game
#
        .data
p1:     .ascii  "\n\nStart Checking Boxes."

board:  .ascii   "\n\n   .-.-.          . 0 . 1 ."
        .ascii     "\n   |   |          2   3   4"
        .ascii     "\n   .-.-.          . 5 . 6 ."
        .ascii     "\n                  7   8   9"
        .asciiz    "\n   . . .          . a . b .\n"

p2:     .asciiz  "\nEnter the your move [0..9]: "

offset: .byte     6,   8,  33,  35,  37,  62,  64,  89,  91,  93,  118, 120
marker: .byte    '-', '-', '|', '|', '|', '-', '-', '|', '|', '|', '-', '-' 
box:    .byte    34, 36, 90, 92

side:   .ascii   "02350     "         # Move 0
        .ascii   "13461     "         # Move 1
        .ascii   "20350     "         # Move 2
        .ascii   "3025031461"         # Move 3
        .ascii   "41361     "         # Move 4
        .ascii   "50230578a2"         # Move 5
        .ascii   "61341689b3"         # Move 6
        .ascii   "758a2     "         # Move 7
        .ascii   "857a2869b3"         # Move 8
        .ascii   "968b3     "         # Move 9
        .ascii   "a5782     "         # Move a or 10
        .ascii   "b6893     "         # Move b or 11

        .text
        .globl  main
#
########################## Main Program #######################
#
main:
      # Print the Prompt p1, greeting.
      la    $a0, p1
      li    $v0, 4
      syscall

      # Print the Prompt p2, entering a move.
      la    $a0, p2
      li    $v0, 4
      syscall
  
      li    $v0, 12            # Read the move, [0..9].
      syscall

      move  $a0, $v0           # $v0: the input move
      sub   $a0, $a0, '0'      # Convert char move to int move.
      move  $s0, $a0           # Save the move in $s0.
      
      lb    $t0, offset($a0)   # Load $t0 with the offset of the index $a0.
      lb    $t1, marker($a0)   # Find the corresponding marker.
      sb    $t1, board($t0)    # Put the marker at the location, board+offset.

      mul   $s1, $s0, 10       # $s0: move
      jal   Score              # $s1: address of the 1st box
      add   $s1, $s1, 5        # $s1: address of next box
      jal   Score

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

      # End of program
      li    $v0, 10
      syscall

#
########################  Check scoring or not.  ############################
#
# Input: $s1 (the starting address of the 1st box)
# Output: Filling in the box if scored

Score:
      subu  $sp, $sp, 4
      sw    $ra, ($sp)              # Push the return address, $ra.
      subu  $sp, $sp, 4
      sw    $s1, ($sp)              # Push the value of $s1.

      li    $t3, 1                  # $t3: counter for 4 sides + 1 box
L10:  lb    $t0, side($s1)
      beq   $t0, ' ', L11           # No match
      sub   $t0, $t0, '0'           # $t0: int offset
      lb    $t1, offset($t0)
      lb    $t2, board($t1)
      beq   $t2, ' ', L11           # No match
      add   $s1, $s1, 1
      add   $t3, $t3, 1
      blt   $t3, 5, L10

      # Scored and filling the box
      lb    $t0, side($s1)          # $t0: box address
      sub   $t0, $t0, '0'
      lb    $t0, box($t0)
      li    $t2, 'X'
      sb    $t2, board($t0)

L11:  lw    $s1, ($sp)             # Pop and restore the value of $s1.
      addu  $sp, $sp, 4
      lw    $ra, ($sp)             # Pop the return address, $ra.
      addu  $sp, $sp, 4
      jr    $ra

An Example of CheckBox.asm Execution

Start Checking Boxes.

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

Enter the your move [0..9]:  3 

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

-- program is finished running --

Start Checking Boxes.

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

Enter the your move [0..9]:  8 

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

-- program is finished running --

The random number generator can be found from the syscall 42 of MARS such as:

       xor  $a0, $a0, $a0     # Set a seed number.
       li   $a1, 12           # random number 0 to 11
       li   $v0, 42           # random number generator
       syscall

The instructor also uses the system call 32, sleep, to slow down the system’s move.

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.

Execution Examples
The following list shows some execution examples, where

the italic, white text with a navy background color is entered by users and
the italic, white text with a purple background color is generated by the system.

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:

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% of the final grade, 10% for each.
- 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.
- Time management is critical for software development. If you are not able to complete the exercise, show whatever you have accomplished, so the instructor can give partial credit to your exercise.