Connect 4
# init
true = 1
false = 0
CONNECT = 4
MIN_BOARD_DIMENSION = 4
MAX_BOARD_WIDTH = 9
MAX_BOARD_HEIGHT = 16
CELL_EMPTY = '.'
CELL_RED = 'R'
CELL_YELLOW = 'Y'
WINNER_NONE = 0
WINNER_RED = 1
WINNER_YELLOW = 2
TURN_RED = 0
TURN_YELLOW = 1
.data
# char board[MAX_BOARD_HEIGHT][MAX_BOARD_WIDTH];
board: .space MAX_BOARD_HEIGHT * MAX_BOARD_WIDTH
board_width: .word 0
board_height: .word 0
enter_board_width_str: .asciiz "Enter board width: "
enter_board_height_str: .asciiz "Enter board height: "
game_over_draw_str: .asciiz "The game is a draw!\n"
game_over_red_str: .asciiz "Game over, Red wins!\n"
game_over_yellow_str: .asciiz "Game over, Yellow wins!\n"
board_too_small_str_1: .asciiz "Board dimension too small (min "
board_too_small_str_2: .asciiz ")\n"
board_too_large_str_1: .asciiz "Board dimension too large (max "
board_too_large_str_2: .asciiz ")\n"
red_str: .asciiz "[RED] "
yellow_str: .asciiz "[YELLOW] "
choose_column_str: .asciiz "Choose a column: "
invalid_column_str: .asciiz "Invalid column\n"
no_space_column_str: .asciiz "No space in that column!\n"
debug: .asciiz "Debug:\n"
.text
main:
# Args: void
# Returns:
# - $v0: int
#
# Frame: [$ra, ...]
# Uses: [...]
# Clobbers: [...]
#
# Locals:
# - [...]
#
# Structure:
# main
# -> [prologue]
# -> body
# -> [epilogue]
main__prologue:
begin # begin a new stack frame
push $ra # | $ra
main__body:
# check valid board dimensions
# print width string
la $a0, enter_board_width_str
li $v0, 4
syscall
# read and store width integer into board_width
li $v0, 5 # read integer
syscall
la $t0, board_width
sw $v0, ($t0)
move $a0, $v0
li $a1, MIN_BOARD_DIMENSION
li $a2, MAX_BOARD_WIDTH
jal assert_board_dimension
# print height string
la $a0, enter_board_height_str
li $v0, 4
syscall
# read and store height integer into board_height
li $v0, 5
syscall
la $t1, board_height
sw $v0, ($t1)
move $a0, $v0
li $a1, MIN_BOARD_DIMENSION
li $a2, MAX_BOARD_HEIGHT
jal assert_board_dimension
# initialise board
jal initialise_board
# print board
jal print_board
# play game
jal play_game
main__epilogue:
pop $ra # | $ra
end # ends the current stack frame
li $v0, 0
jr $ra # return 0;
########################################################################
# .TEXT <assert_board_dimension>
.text
assert_board_dimension:
# Args:
# - $a0: int dimension
# - $a1: int min
# - $a2: int max
# Returns: void
#
# Frame: [...]
# Uses: [...]
# Clobbers: [...]
#
# Locals:
# - [...]
#
# Structure:
# assert_board_dimension
# -> [prologue]
# -> body
# -> [epilogue]
assert_board_dimension__prologue:
begin
push $ra
assert_board_dimension__body:
blt $a0, $a1, assert_board_dimension__small
bgt $a0, $a2, assert_board_dimension__large
assert_board_dimension__epilogue:
pop $ra
end
jr $ra # return;
assert_board_dimension__small:
la $a0, board_too_small_str_1
li $v0, 4
syscall
li $a0, 4
li $v0, 1
syscall
la $a0, board_too_small_str_2
li $v0, 4
syscall
# returns with error code 1
li $a0, 1
li $v0, 17
syscall
assert_board_dimension__large:
la $a0, board_too_large_str_1
li $v0, 4
syscall
li $a0, 16
li $v0, 1
syscall
la $a0, board_too_large_str_2
li $v0, 4
syscall
# returns with error code 1
li $a0, 1
li $v0, 17
syscall
#j assert_board_dimension__epilogue
########################################################################
# .TEXT <initialise_board>
.text
initialise_board:
# Args: void
# Returns: void
#
# Frame: [...]
# Uses: [...]
# Clobbers: [...]
#
# Locals:
# - [...]
#
# Structure:
# initialise_board
# -> [prologue]
# -> body
# -> [epilogue]
initialise_board__prologue:
begin
push $ra
initialise_board__body:
li $s0, 0 # row
la $t0, board
lw $t6, board_width
lw $t7, board_height
initialise_board__row_loop:
bge $s0, $t7, initialise_board__row_end
li $s1, 0 # col
initialise_board__col_loop:
bge $s1, $t6, initialise_board__col_end
# adding row offset
mul $t1, $s0, MAX_BOARD_WIDTH
# adding col offset
add $t3, $t1, $s1
li $t4, CELL_EMPTY
sb $t4, board($t3)
addi $s1, $s1, 1
b initialise_board__col_loop
initialise_board__col_end:
addi $s0, $s0, 1
b initialise_board__row_loop
initialise_board__row_end:
# clearing variables
li $s0, 0
li $s1, 0
initialise_board__epilogue:
pop $ra
end
jr $ra # return;
########################################################################
# .TEXT <play_game>
.text
play_game:
# Args: void
# Returns: void
#
# Frame: [...]
# Uses: [...]
# Clobbers: [...]
#
# Locals:
# - [...]
#
# Structure:
# play_game
# -> [prologue]
# -> body
# -> [epilogue]
play_game__prologue:
begin
push $ra
play_game__body:
li $s4, TURN_RED
li $s3, WINNER_NONE
play_game__loop:
bne $s3, WINNER_NONE, play_game__check
jal is_board_full
beq $v0, true, play_game__check
move $a0, $s4
jal play_turn
move $s4, $v0
jal print_board
jal check_winner
move $s3, $v0
b play_game__loop
play_game__check:
li $t0, WINNER_NONE
li $t1, WINNER_RED
li $t2, WINNER_YELLOW
beq $s3, $t0, play_game__draw
beq $s3, $t1, play_game__red
beq $s3, $t2, play_game__yellow
play_game__draw:
la $a0, game_over_draw_str
li $v0, 4
syscall
j play_game__epilogue
play_game__red:
la $a0, game_over_red_str
li $v0, 4
syscall
j play_game__epilogue
play_game__yellow:
la $a0, game_over_yellow_str
li $v0, 4
syscall
j play_game__epilogue
play_game__epilogue:
pop $ra
end
jr $ra # return;
########################################################################
# .TEXT <play_turn>
.text
play_turn:
# Args:
# - $a0: int whose_turn
# Returns: void
#
# Frame: [...]
# Uses: [...]
# Clobbers: [...]
#
# Locals:
# - [...]
#
# Structure:
# play_turn
# -> [prologue]
# -> body
# -> [epilogue]
play_turn__prologue:
begin
push $ra
lb $t0, board_width
play_turn__prints:
move $s0, $a0
beq $s0, TURN_RED, play_turn__print_red
beq $s0, TURN_YELLOW, play_turn__print_yellow
play_turn__print_red:
la $a0, red_str
li $v0, 4
syscall
j play_turn__body
play_turn__print_yellow:
la $a0, yellow_str
li $v0, 4
syscall
j play_turn__body
play_turn__body:
la $a0, choose_column_str
li $v0, 4
syscall
li $v0, 5
syscall
move $s1, $v0
sub $s1, $s1, 1 # user input 1-indexed (column)
blt $s1, $zero, play_turn__invalid
bge $s1, $t0, play_turn__invalid
lb $s2, board_height
sub $s2, $s2, 1 # row
play_turn__loop:
blt $s2, 0, play_turn__body_cont
li $t7, MAX_BOARD_WIDTH
mul $t0, $s2, $t7
add $t0, $t0, $s1
lb $t2, board($t0)
beq $t2, 46, play_turn__body_cont
sub $s2, $s2, 1
blt $s2, 0, play_turn__full
b play_turn__loop
play_turn__body_cont:
beq $s0, TURN_RED, play_turn__set_red
beq $s0, TURN_YELLOW, play_turn__set_yellow
play_turn__set_red:
mul $t0, $s2, MAX_BOARD_WIDTH
add $t0, $s1
li $t1, CELL_RED
sb $t1, board($t0)
li $s0, TURN_YELLOW
j play_turn__epilogue
play_turn__set_yellow:
mul $t0, $s2, MAX_BOARD_WIDTH
add $t0, $s1
li $t1, CELL_YELLOW
sb $t1, board($t0)
li $s0, TURN_RED
j play_turn__epilogue
play_turn__invalid:
la $a0, invalid_column_str
li $v0, 4
syscall
j play_turn__epilogue
play_turn__full:
la $a0, no_space_column_str
li $v0, 4
syscall
j play_turn__epilogue
play_turn__epilogue:
la $v0, ($s0)
pop $ra
end
jr $ra # return;
########################################################################
# .TEXT <check_winner>
.text
check_winner:
# Args: void
# Returns:
# - $v0: int
#
# Frame: [...]
# Uses: [...]
# Clobbers: [...]
#
# Locals:
# - [...]
#
# Structure:
# check_winner
# -> [prologue]
# -> body
# -> [epilogue]
check_winner__prologue:
begin
push $ra
check_winner__body:
li $s0, 0 # row
lw $t6, board_width
lw $t7, board_height
check_winner__row_loop:
bge $s0, $t7, check_winner__row_end
li $s1, 0 # col
check_winner__col_loop:
bge $s1, $t6, check_winner__col_end
# computing row offset
mul $t2, $s0, MAX_BOARD_WIDTH
# computing col offset
add $t2, $s1
## check vertical line
move $a0, $s0
move $a1, $s1
li $a2, 1
li $a3, 0
jal check_line
bne $v0, WINNER_NONE, check_winner__epilogue
# check horizontal line
move $a0, $s0
move $a1, $s1
li $a2, 0
li $a3, 1
jal check_line
bne $v0, WINNER_NONE, check_winner__epilogue
# check gradient = -1 line
move $a0, $s0
move $a1, $s1
li $a2, 1
li $a3, 1
jal check_line
bne $v0, WINNER_NONE, check_winner__epilogue
# check gradient = 1 line
move $a0, $s0
move $a1, $s1
li $a2, 1
li $a3, -1
jal check_line
bne $v0, WINNER_NONE, check_winner__epilogue
addiu $s1, 1
j check_winner__col_loop
check_winner__col_end:
addiu $s0, 1
j check_winner__row_loop
check_winner__row_end:
check_winner__epilogue:
pop $ra
end
jr $ra # return;
########################################################################
# .TEXT <check_line>
.text
check_line:
# Args:
# - $a0: int start_row
# - $a1: int start_col
# - $a2: int offset_row
# - $a3: int offset_col
# Returns:
# - $v0: int
#
# Frame: [...]
# Uses: [...]
# Clobbers: [...]
#
# Locals:
# - [...]
#
# Structure:
# check_line
# -> [prologue]
# -> body
# -> [epilogue]
check_line__prologue:
begin
push $ra
lw $s2, board_height
lw $s5, board_width
# calculating offset
mul $t0, $a0, MAX_BOARD_WIDTH
add $t0, $t0, $a1 # first_cell
lb $t1, board($t0)
beq $t1, CELL_EMPTY, check_line__winner_none
add $t2, $a0, $a2 # row
add $t3, $a1, $a3 # col
# how many connects required
li $t5, CONNECT
sub $t5, $t5, 1
# i for loop
li $t4, 0
# clearing t7 register
li $t8, 0
check_line__body:
bge $t4, $t5, check_line__body_cont
blt $t2, $zero, check_line__winner_none
blt $t3, $zero, check_line__winner_none
bge $t2, $s2, check_line__winner_none
bge $t3, $s5, check_line__winner_none
mul $t8, $t2, MAX_BOARD_WIDTH
add $t8, $t8, $t3 # board[row][col]
lb $t9, board($t8)
bne $t1, $t9, check_line__winner_none
add $t2, $t2, $a2
add $t3, $t3, $a3
addiu $t4, 1
b check_line__body
check_line__winner_none:
li $v0, WINNER_NONE
j check_line__epilogue
check_line__winner_red:
li $v0, WINNER_RED
j check_line__epilogue
check_line__winner_yellow:
li $v0, WINNER_YELLOW
j check_line__epilogue
check_line__body_cont:
beq $t1, CELL_RED, check_line__winner_red
beq $t1, CELL_YELLOW, check_line__winner_yellow
check_line__epilogue:
pop $ra
end
jr $ra # return;
########################################################################
# .TEXT <is_board_full>
# YOU DO NOT NEED TO CHANGE THE IS_BOARD_FULL FUNCTION
.text
is_board_full:
# Args: void
# Returns:
# - $v0: bool
#
# Frame: []
# Uses: [$v0, $t0, $t1, $t2, $t3]
# Clobbers: [$v0, $t0, $t1, $t2, $t3]
#
# Locals:
# - $t0: int row
# - $t1: int col
#
# Structure:
# is_board_full
# -> [prologue]
# -> body
# -> loop_row_init
# -> loop_row_cond
# -> loop_row_body
# -> loop_col_init
# -> loop_col_cond
# -> loop_col_body
# -> loop_col_step
# -> loop_col_end
# -> loop_row_step
# -> loop_row_end
# -> [epilogue]
is_board_full__prologue:
is_board_full__body:
li $v0, true
is_board_full__loop_row_init:
li $t0, 0 # int row = 0;
is_board_full__loop_row_cond:
lw $t2, board_height
bge $t0, $t2, is_board_full__epilogue # if (row >= board_height) goto is_board_full__loop_row_end;
is_board_full__loop_row_body:
is_board_full__loop_col_init:
li $t1, 0 # int col = 0;
is_board_full__loop_col_cond:
lw $t2, board_width
bge $t1, $t2, is_board_full__loop_col_end # if (col >= board_width) goto is_board_full__loop_col_end;
is_board_full__loop_col_body:
mul $t2, $t0, MAX_BOARD_WIDTH # row * MAX_BOARD_WIDTH
add $t2, $t2, $t1 # row * MAX_BOARD_WIDTH + col
lb $t3, board($t2) # board[row][col];
bne $t3, CELL_EMPTY, is_board_full__loop_col_step # if (cell != CELL_EMPTY) goto is_board_full__loop_col_step;
li $v0, false
b is_board_full__epilogue # return false;
is_board_full__loop_col_step:
addi $t1, $t1, 1 # col++;
b is_board_full__loop_col_cond # goto is_board_full__loop_col_cond;
is_board_full__loop_col_end:
is_board_full__loop_row_step:
addi $t0, $t0, 1 # row++;
b is_board_full__loop_row_cond # goto is_board_full__loop_row_cond;
is_board_full__loop_row_end:
is_board_full__epilogue:
jr $ra # return;
########################################################################
# .TEXT <print_board>
# YOU DO NOT NEED TO CHANGE THE PRINT_BOARD FUNCTION
.text
print_board:
# Args: void
# Returns: void
#
# Frame: []
# Uses: [$v0, $a0, $t0, $t1, $t2]
# Clobbers: [$v0, $a0, $t0, $t1, $t2]
#
# Locals:
# - `int col` in $t0
# - `int row` in $t0
# - `int col` in $t1
#
# Structure:
# print_board
# -> [prologue]
# -> body
# -> for_header_init
# -> for_header_cond
# -> for_header_body
# -> for_header_step
# -> for_header_post
# -> for_row_init
# -> for_row_cond
# -> for_row_body
# -> for_col_init
# -> for_col_cond
# -> for_col_body
# -> for_col_step
# -> for_col_post
# -> for_row_step
# -> for_row_post
# -> [epilogue]
print_board__prologue:
print_board__body:
li $v0, 11 # syscall 11: print_int
la $a0, '\n'
syscall # printf("\n");
print_board__for_header_init:
li $t0, 0 # int col = 0;
print_board__for_header_cond:
lw $t1, board_width
blt $t0, $t1, print_board__for_header_body # col < board_width;
b print_board__for_header_post
print_board__for_header_body:
li $v0, 1 # syscall 1: print_int
addiu $a0, $t0, 1 # col + 1
syscall # printf("%d", col + 1);
li $v0, 11 # syscall 11: print_character
li $a0, ' '
syscall # printf(" ");
print_board__for_header_step:
addiu $t0, 1 # col++
b print_board__for_header_cond
print_board__for_header_post:
li $v0, 11
la $a0, '\n'
syscall # printf("\n");
print_board__for_row_init:
li $t0, 0 # int row = 0;
print_board__for_row_cond:
lw $t1, board_height
blt $t0, $t1, print_board__for_row_body # row < board_height
b print_board__for_row_post
print_board__for_row_body:
print_board__for_col_init:
li $t1, 0 # int col = 0;
print_board__for_col_cond:
lw $t2, board_width
blt $t1, $t2, print_board__for_col_body # col < board_width
b print_board__for_col_post
print_board__for_col_body:
mul $t2, $t0, MAX_BOARD_WIDTH
add $t2, $t1
## debug
#la $a0, ($t2)
#li $v0, 1
#syscall
## debug
lb $a0, board($t2) # board[row][col]
li $v0, 11 # syscall 11: print_character
syscall # printf("%c", board[row][col]);
li $v0, 11 # syscall 11: print_character
li $a0, ' '
syscall # printf(" ");
print_board__for_col_step:
addiu $t1, 1 # col++;
b print_board__for_col_cond
print_board__for_col_post:
li $v0, 11 # syscall 11: print_character
li $a0, '\n'
syscall # printf("\n");
print_board__for_row_step:
addiu $t0, 1
b print_board__for_row_cond
print_board__for_row_post:
print_board__epilogue:
jr $ra # return;
Backlinks (4)
1. Chess Bot /wiki/ai/adv-search/chess-bot/
two chess projects live in this codebase, and honesty requires separating them up front. the first is a from-scratch javascript engine (in arcade/references/chess/js/, built following the classic bluefever software series): 120-square mailbox board, hand-rolled move generator validated by perft, material + piece-square evaluation, alpha-beta with quiescence, a principal-variation hash table, and iterative deepening. the second is voice chess (code/private/chess-bot/, published as github.com/abaj8494/ollama-voice-chess): there i did not write the engine — stockfish plays the moves over uci — and the engineering is in the wrapper: skill throttling, an ollama llm that provides spoken commentary without being allowed to hallucinate moves, neural tts, and spaced-repetition opening training. one project teaches you how engines work; the other teaches you what to build around an engine.
𐃏
2. Ultimate Tic Tac Toe /wiki/ai/adv-search/ultimate-ttt/
ordinary tic-tac-toe is a solved bore — both players draw with a lookup table. glue nine boards together and add one rule about where you are allowed to move, and suddenly the game tree is deep enough that you need actual search theory: minimax, the negamax reformulation, alpha-beta pruning, and a heuristic to stand in for the leaves you cannot reach. this page documents the agent my partner and i wrote for unsw comp3411 (assignment 3, “nine-board tic-tac-toe”), warts and all — and the warts are instructive. 𐃏
3. Wiki /wiki/
Knowledge is a paradox. The more one understand, the more one realises the vastness of his ignorance.