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
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. |
syscall
32 of MARS to slow down the moves (like 3 seconds).
. . . . 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)
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!
. . . . 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 9where 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, 92Convert 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)
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 11where 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"
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 |
|
|
|
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 -- |
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 syscallThe instructor also uses the system call 32, sleep, to slow down the system’s move.
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 $rawhere the return address is saved in the register
$31
or $ra
$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.
|
|
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 -- |
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 |
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. |