Programming Exercise II: Playing a snakes game

Programming Exercise II: Playing a Snakes 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.

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

Objective
Design and implement a MIPS assembly program, which has the user play a 6×6 snakes game against the computer. The final program is less than 400 lines without counting the declarations of data structures. The purpose of this exercise is to make students practice assembly language programming including various control instructions, functions, and the runtime stack.

The first player, Blue (or top), can not move, and so Red (or bottom) wins.

Rules of a Snakes Game
It is a board game for two players who take turns in drawing segments of a snake. The last player able to move wins. The game is played on a grid; 6×6 is a good size. The above game is played on a matrix of 5×5 dots. The first player, Blue (top), starts in the second row and column, and the other player, Red (bottom), starts in the last but one row and column, as shown by the blue and red squares. The players take turns in growing a snake, extending it a segment at a time by drawing a horizontal or vertical line from the previous dot to an adjacent dot. Each player must avoid touching either his/her opponent’s snake or his/her own snake. The first player unable to move loses.

Requirements
The 6×6 snakes game includes the following requirements:

(Starting the game: 10%) Use the syscall of MARS to randomly pick either one of the two players, System or user, to start the game. If the user starts the game, ask the user to pick a piece (X or O), whereas if the System starts the game, use the syscall to randomly pick the piece.

(Taking turns: 05%) The players (X and O) take turns making moves.

(Marking the user’s moves: 15%) Mark a move after the user enters an index. For example, if the first move consists of the piece X and an index 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

(Marking the System’s shortest-distance moves: 30%) The move will result in a shortest distance in segment between the two snake heads regardless of any pieces in the path. For example, the next move for the following game board:

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

is the piece X (the System) at the index e since it will result in a 1-segment distance between X and O as follows:

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

Each of the other moves would result in a greater distance. If there are more than one move resulting in the same shortest distance, pick any one of them. Another example is 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
      . . . . O .     ⇒     u v w x y z

The piece X (the System) at the index g will result in a 3-segment distance between X and O as follows:

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

The other two moves l and n each will also result in a 3-segment distance.

(Changing the markers: 15%) For example, if the next move of the player X is e, the boards are displayed as follows:

      . . . . . .     ⇒     0 1 2 3 4 5
      $ . . . . .     ⇒     6 7 8 9 a b
      $ X . . . .     ⇒     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

                    ⇓ X at e

      . . . . . .     ⇒     0 1 2 3 4 5
      $ . . . . .     ⇒     6 7 8 9 a b
      $ $ X . . .     ⇒     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

(Next move: 05%) Continue with the next move after asking the user to pick y or n.

(Result: 15%) Declare the winner (including the player, System or User, and the piece, X or O) once it is decided.

(New game: 05%) Start a new game after asking the user to pick y or n.

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),
the new line, ‘\n’, is one byte long, and
each offset uses 2 bytes because the range of 1 byte, [-128 – 127], is not enough for a number ≥ 128.

Convert the character indexes 0–9a–z to integer indexes 0–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.

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 horizontal and vertical neighbors of a cell. All possible neighbors are listed as follows:

     nbrs: .ascii   "16  "      # 0
           .ascii   "027 "      # 1
           .ascii   "138 "      # 2
           .ascii   "249 "      # 3
           .ascii   "35a "      # 4
           .ascii   "4b  "      # 5
           .ascii   "07c "      # 6
           .ascii   "168d"      # 7
           .ascii   "279e"      # 8
           .ascii   "38af"      # 9
           .ascii   "49bg"      # a (10)
           .ascii   "5ah "      # b (11)
           .ascii   "6di "      # c (12)
           .ascii   "7cej"      # d (13)
           .ascii   "8dfk"      # e (14)
           .ascii   "9egl"      # f (15)
           .ascii   "afhm"      # g (16)
           .ascii   "bgn "      # h (17)
           .ascii   "cjo "      # i (18)
           .ascii   "dikp"      # j (19)
           .ascii   "ejlq"      # k (20)
           .ascii   "fkmr"      # l (21)
           .ascii   "glns"      # m (22)
           .ascii   "hmt "      # n (23)
           .ascii   "ipu "      # o (24)
           .ascii   "joqv"      # p (25)
           .ascii   "kprw"      # q (26)
           .ascii   "lqsx"      # r (27)
           .ascii   "mrty"      # s (28)
           .ascii   "nsz "      # t (29)
           .ascii   "ov  "      # u (30)
           .ascii   "puw "      # v (31)
           .ascii   "qvx "      # w (32)
           .ascii   "rwy "      # x (33)
           .ascii   "sxz "      # y (34)
           .ascii   "ty  "      # z (35)

where each string consists of the indexes of the horizontal and vertical neighbors of the cell. For example, the indexes of the neighbors of the cell s are mrty .

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

Assuming the integer index like 28 (s) is in $v0, the following code then prints the neighbors of $v0 like mrty for s:

          mul   $a1, $v0, 4      # Each string is four-byte long.
          li    $t0, 4           # $t0: the counter
     L1:  beqz  $t0, L2          # Go to L2 if the end of string is reached.
          lb    $a0, nbrs($a1)   # Load one neighbor.
          beq   $a0, ' ', L2     # Go to L2 if the neighbor == ' '.
          li    $v0, 11 
          syscall                # Print the neighbor.
          add   $a1, $a1, 1      # Advance to the next neighbor.
          sub   $t0, $t0, 1      # Decrement the counter.
          j     L1               # Go to L1.
     L2:  ...

The following data structure is used to find the distance:

     coord: .ascii   "05"      # 0
            .ascii   "15"      # 1
            .ascii   "25"      # 2
            .ascii   "35"      # 3
            .ascii   "45"      # 4
            .ascii   "55"      # 5
            .ascii   "04"      # 6
            .ascii   "14"      # 7
            .ascii   "24"      # 8
            .ascii   "34"      # 9
            .ascii   "44"      # a (10)
            .ascii   "54"      # b (11)
            .ascii   "03"      # c (12)
            .ascii   "13"      # d (13)
            .ascii   "23"      # e (14)
            .ascii   "33"      # f (15)
            .ascii   "43"      # g (16)
            .ascii   "53"      # h (17)
            .ascii   "02"      # i (18)
            .ascii   "12"      # j (19)
            .ascii   "22"      # k (20)
            .ascii   "32"      # l (21)
            .ascii   "42"      # m (22)
            .ascii   "52"      # n (23)
            .ascii   "01"      # o (24)
            .ascii   "11"      # p (25)
            .ascii   "21"      # q (26)
            .ascii   "31"      # r (27)
            .ascii   "41"      # s (28)
            .ascii   "51"      # t (29)
            .ascii   "00"      # u (30)
            .ascii   "10"      # v (31)
            .ascii   "20"      # w (32)
            .ascii   "30"      # x (33)
            .ascii   "40"      # y (34)
            .ascii   "50"      # z (35)

where each string is the coordinates of the point in the Quadrant I of the Cartesian coordinate plane as follows:

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

For example, the distance between p(1,1) and y(4,0) is

        dist(p,y) = |1-4| + |1-0| = 4

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

Assuming the coordinates of the cell #1 are ($t1,$t2) like p(1,1) and the coordinates of the cell #2 are ($t3,$t4) like y(4,0), the following code then finds the distance between the two cells like 4=distance(p,y):

          sub   $t1, $t1, $t3     # $t1 = $t1 - $t3
          bgez  $t1, L1           # Go to L1 if $t1 ≥ 0
          neg   $t1, $t1          # $t1 = -$t1 if $t1 < 0 
     L1:  sub   $t2, $t2, $t4     # $t2 = $t2 - $t4
          bgez  $t2, L2           # Go to L2 if $t2 ≥ 0
          neg   $t2, $t2          # $t2 = -$t2 if $t2 < 0
     L2:  add   $a0, $t1, $t2     # $a0 (distance) = $t1+$t2 = |$t1-$t3|+|$t2-$t4|

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

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

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.
```
Winning strategies for the snakes games could be fairly complicated. The System’s next move is one of many possible moves that results in the shortest distance between two snake heads, which may not be a good strategy, but is simple. There are many ways to do this. Instead of using complicated calculations, the instructor lists all possible moves and selects the best one. This is not an efficient way to solve the problem, but the efficiency issue will be considered minimally when grading. To encourage independent thinking, the details are not given.

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

MarkBoard.asm

# 
######################### Marking the Game Board #########################
#

        .data
pr1:    .asciiz  "\nStart Marking a Snakes Game Board."
pr2:    .asciiz  "\nEnter X's next move [/0..z]: "
pr3:    .asciiz  "\nEnter O's next move [/0..z]: "

player: .byte    'X'       # current player
mov:    .byte    ' '       # current move
last_X: .byte    ' '       # last move of X
last_O: .byte    ' '       # last move of O

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, font-size:120
        .half   138, 140, 142, 144, 146, 148
        .half   171, 173, 175, 177, 179, 181

        .text
        .globl main
#
####################### Main Program #######################
#
main:
      la    $a0, pr1          # Greeting
      li    $v0, 4
      syscall
      la    $a0, board        # Game board
      li    $v0, 4 
      syscall

L0:   lb    $v0, player       # $v0 = current player
      beq   $v0, 'O', L1
      la    $a0, pr2          # X's next move
      li    $v0, 4
      syscall
      li    $t0, 'O'          # $t0 = 'O'
      j     L2
      
L1:   la    $a0, pr3          # Y's next move
      li    $v0, 4
      syscall
      li    $t0, 'X'          # $t0 = 'X'
      
L2:   li    $v0, 12
      syscall
      sb    $v0, mov          # mov = $v0, next move
      beq   $v0, '/', L3
      move  $a0, $v0
      jal   MarkBoard         # Mark the move.
      sb    $t0, player
      j     L0
      
L3:   li    $v0, 10           # End of program
      syscall

#
####################### Mark the board. #######################
#
# Input:  $a0 (the char move [0-z])  
# Output: the updated board

MarkBoard:
      subu  $sp, $sp, 4
      sw    $ra, ($sp)         # Push the return address, $ra.
      subu  $sp, $sp, 4        # Decrement the $sp to make space for $t0.
      sw    $t0, ($sp)         # Push the $t0.
      
      # Mark the board.
      jal   FindIndex
      lh    $t1, offset($t0)
      lb    $t2, player        # $t2 = current player
      sb    $t2, board($t1)

      # Change the marker.
      beq   $t2, 'O', L21
      lb    $t0, last_X
      sb    $a0, last_X
      li    $t2, '$'
      j     L22
      
L21:  lb    $t0, last_O
      sb    $a0, last_O
      li    $t2, '+'

L22:  move  $a0, $t0
      jal   FindIndex
      lh    $t1, offset($t0)
      sb    $t2, board($t1)
      la    $a0, board
      li    $v0, 4
      syscall
  
      lw    $t0, ($sp)           # Pop $t0.
      addu  $sp, $sp, 4          # Increment the $sp.
      lw    $ra, ($sp)           # Pop the return address, $ra.
      addu  $sp, $sp, 4
      jr    $ra
          
#
####################### Find the Index of Offset. #######################
#
# Input:  $a0 (the char move [0-z])  
# Output: $t0 (the integer index)

FindIndex:
      subu  $sp, $sp, 4
      sw    $ra, ($sp)           # Push the return address, $ra.
      subu  $sp, $sp, 4          # Decrement the $sp to make space for $a0.
      sw    $a0, ($sp)           # Push the $a0.
      
      bgt   $a0, '9', L31
      sub   $a0, $a0, '0'
      j     L32
L31:  sub   $a0, $a0, 'a'
      add   $a0, $a0, 10
L32:  mul   $t0, $a0, 2
      
      lw    $a0, ($sp)           # Pop $a0.
      addu  $sp, $sp, 4          # Increment the $sp.
      lw    $ra, ($sp)           # Pop the return address, $ra.
      addu  $sp, $sp, 4
      jr    $ra                  # Return.

An Example of MarkBoard.asm Execution

Start Marking a Snakes Game Board.

    . . . . . .      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 X's next move [/0..z]:  8 

    . . . . . .      0 1 2 3 4 5
    . . X . . .      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 O's next move [/0..z]:  r 

    . . . . . .      0 1 2 3 4 5
    . . X . . .      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 X's next move [/0..z]:  9 

    . . . . . .      0 1 2 3 4 5
    . . $ X . .      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 O's next move [/0..z]:  q 

    . . . . . .      0 1 2 3 4 5
    . . $ X . .      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 X's next move [/0..z]:  a 

    . . . . . .      0 1 2 3 4 5
    . . $ $ X .      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 O's next move [/0..z]:  k 

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

Enter X's next move [/0..z]:  / 

-- program is finished running --

^†The italic, white text with a navy background color is entered by users.

^‡Notice the subroutine is not necessary. It is to show how to use subroutines and runtime stack.

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

Examples of Exercise II Execution
Start Playing a Snakes 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 first. Pick a piece: (X\|O) X Enter your move: (0..z) 0 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 Hit the spacebar to start the System’s next move. X O . . . . 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 Enter your move: (0..z) 6 $ O . . . . 0 1 2 3 4 5 X . . . . . 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 Hit the spacebar to start the System’s next move. $ + . . . . 0 1 2 3 4 5 X O . . . . 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 Enter your move: (0..z) c $ + . . . . 0 1 2 3 4 5 $ O . . . . 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 Hit the spacebar to start the System’s next move. $ + . . . . 0 1 2 3 4 5 $ + . . . . 6 7 8 9 a b X O . . . . 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 Enter your move: (0..z) i $ + . . . . 0 1 2 3 4 5 $ + . . . . 6 7 8 9 a b $ O . . . . 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 Continue? (y/n) y Hit the spacebar to start the System’s next move. $ + . . . . 0 1 2 3 4 5 $ + . . . . 6 7 8 9 a b $ + . . . . c d e f g h X O . . . . i j k l m n . . . . . . o p q r s t . . . . . . u v w x y z Continue? (y/n) y Enter your move: (0..z) o $ + . . . . 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 X . . . . . o p q r s t . . . . . . u v w x y z Continue? (y/n) y Hit the spacebar to start the System’s next move. $ + . . . . 0 1 2 3 4 5 $ + . . . . 6 7 8 9 a b $ + . . . . c d e f g h $ + . . . . i j k l m n X O . . . . o p q r s t . . . . . . u v w x y z Continue? (y/n) y Enter your move: (0..z) u $ + . . . . 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 X . . . . . u v w x y z Continue? (y/n) y Hit the spacebar to start the System’s next move. $ + . . . . 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 X O . . . . u v w x y z ***** The System (O) wins! *** New game? (y/n) y Start Playing a Snakes 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 I (the System) am first and I pick X. Hit the spacebar to start the System’s next move. . . . . . . 0 1 2 3 4 5 . . . . X . 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 Enter your move: (0..z) p . . . . . . 0 1 2 3 4 5 . . . O X . 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 Hit the spacebar to start the System’s next move. . . . . X . 0 1 2 3 4 5 . . . O $ . 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 Enter your move: (0..z) 3 . . . O 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 Hit the spacebar to start the System’s next move. . . . O $ 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) n New game? (y/n) y Start Playing a Snakes 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 first. Pick a piece: (X\|O) O Enter your move: (0..z) s . . . . . . 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 Hit the spacebar to start the System’s next move. . . . . . . 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 . o p q r s t . . . . . . u v w x y z Continue? (y/n) y Enter your move: (0..z) 6 . . . . . . 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 . . . . O . u v w x y z Continue? (y/n) y Hit the spacebar to start the System’s next move. . . . . . . 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 Continue? (y/n) y Enter your move: (0..z) z . . . . . . 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 Continue? (y/n) y Hit the spacebar to start the System’s next move. . . . . . . 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 Continue? (y/n) y Enter your move: (0..z) t . . . . . . 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 o p q r s t . . . . + + u v w x y z Continue? (y/n) y Hit the spacebar to start the System’s next move. . . . . . . 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 o p q r s t . . . . + + u v w x y z *** The System (X) wins! ***** New game? (y/n) n -- program is finished running --

Examples of Exercise II Execution


Start Playing a Snakes 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 first. Pick a piece: (X|O)  X 
Enter your move: (0..z)  0 

    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 
Hit the spacebar to start the System’s next move.

    X O . . . .      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 
Enter your move: (0..z)  6 

    $ O . . . .      0 1 2 3 4 5
    X . . . . .      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 
Hit the spacebar to start the System’s next move.

    $ + . . . .      0 1 2 3 4 5
    X O . . . .      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 
Enter your move: (0..z)  c 

    $ + . . . .      0 1 2 3 4 5
    $ O . . . .      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 
Hit the spacebar to start the System’s next move.

    $ + . . . .      0 1 2 3 4 5
    $ + . . . .      6 7 8 9 a b
    X O . . . .      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 
Enter your move: (0..z)  i 

    $ + . . . .      0 1 2 3 4 5
    $ + . . . .      6 7 8 9 a b
    $ O . . . .      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

Continue? (y/n)  y 
Hit the spacebar to start the System’s next move.

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

Continue? (y/n)  y 
Enter your move: (0..z)  o 

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

Continue? (y/n)  y 
Hit the spacebar to start the System’s next move.

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

Continue? (y/n)  y 
Enter your move: (0..z)  u 

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

Continue? (y/n)  y 
Hit the spacebar to start the System’s next move.

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

******* The System (O) wins! *******

New game? (y/n)  y 

Start Playing a Snakes 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

I (the System) am first and I pick X.
Hit the spacebar to start the System’s next move.

    . . . . . .      0 1 2 3 4 5
    . . . . X .      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 
Enter your move: (0..z)  p 

    . . . . . .      0 1 2 3 4 5
    . . . O X .      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 
Hit the spacebar to start the System’s next move.

    . . . . X .      0 1 2 3 4 5
    . . . O $ .      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 
Enter your move: (0..z)  3 

    . . . O 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 
Hit the spacebar to start the System’s next move.

    . . . O $ 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)  n 
New game? (y/n)  y 

Start Playing a Snakes 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 first. Pick a piece: (X|O)  O 
Enter your move: (0..z)  s 

    . . . . . .      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 
Hit the spacebar to start the System’s next move.

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

Continue? (y/n)  y 
Enter your move: (0..z)  6 

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

Continue? (y/n)  y 
Hit the spacebar to start the System’s next move.

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

Continue? (y/n)  y 
Enter your move: (0..z)  z 

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

Continue? (y/n)  y 
Hit the spacebar to start the System’s next move.

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

Continue? (y/n)  y 
Enter your move: (0..z)  t 

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

Continue? (y/n)  y 
Hit the spacebar to start the System’s next move.

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

******* The System (X) wins! *******

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	`beqz` `rs label`	`if rs==0 then goto label`	Branch if equal to zero
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	`bltz` `rs, label`	`if rs<0 then goto label`	Branch if less than zero
9	`bne` `rs, rt, label`	`if rs≠rt then goto label`	Branch if not equal to
10	`j` `label`	`jump to label`	Jump
11	`jal` `label`	`jump to label` and save the return address in `$31` or `$ra`	Jump and link
12	`jr` `rs`	`jump to [rs]`; [ ]: contents of	Jump and link
13	`la` `rd, mem`	`rd = address( mem )`	Load address
14	`lb` `rd, mem`	`rd = mem`	Load byte
15	`lh` `rd, mem`	`rd = mem`	Load half word
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	`neg` `rd, rs`	`rd = -rs`	Negate
21	`sb` `rs, mem`	`mem = rs`	Store byte
22	`sub` `rd, rs, rt`	`rd = rs - rt`	Subtract
23	`subu` `rd, rs, rt`	`rd = rs - rt` (no overflow)	Subtract unsigned
24	`sw` `rs, mem`	`mem = rs`	Store word
25	`syscall`		System call; check System Services.
26	`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`
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 only if both of the printout and source code are 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 15% of the final grade, 05% for the Exercise I and 10% for this exercise.
- The source-code printouts will be kept until all grading is done. They will be used to check against others’ exercises. The instructor will inform you the exercise evaluations by emails after grading.