commit 3fceb94389d2d61507b1aeadb13b5a7763772f3f
parent c2522876d58e4fda99b87644fca9f362dad13db4
Author: Gerd Beuster <gerd@frombelow.net>
Date: Sun, 25 Oct 2020 12:49:24 +0100
Tic-Tac-Toe
Diffstat:
13 files changed, 2491 insertions(+), 23 deletions(-)
diff --git a/doc/Documentation.txt b/doc/Documentation.txt
@@ -56,6 +56,9 @@ transmission is the number of $100 byte blocks to be transmitted. Run
rom/boot/boot.py on the host PC to upload a program. This python
script triggers a reset by setting DTR to high; see section Reset Logic.
+If no initial byte is recevied, the boot ROM starts to execute a
+standard application from ROM.
+
** Tools
Directory misc/ contains some tools and unfinished parts:
diff --git a/roms/boot/Makefile b/roms/boot/Makefile
@@ -1,6 +1,7 @@
TARGET=boot.bin
TARGET_BASENAME=$(basename $(TARGET))
SYMON=java -jar ../../emulator/symon-1.3.1.jar -cpu 65c02
+INC=-I../../sw/ttt/
all: $(TARGET) $(TARGET_BASENAME)_symon.bin liba.h
@@ -8,7 +9,7 @@ liba.h: $(TARGET_BASENAME).l $(TARGET_BASENAME)_symon.l $(TARGET_BASENAME).s
./export_symbols.py
%.bin: %.s
- xa -l "$(basename $@).l" -r -o "$@" "$<"
+ xa $(INC) -l "$(basename $@).l" -r -o "$@" "$<"
%_symon.bin: %.s
xa -DSYMON -l "$(basename $@).l" -r -o "$@" "$<"
diff --git a/roms/boot/boot.h b/roms/boot/boot.h
@@ -16,7 +16,7 @@ gets_str = $11 ; 16 bit address
;;; Output:
;;; -
;;; Changes:
-;;; a, acai-registers
+;;; a, acai registers
#ifdef SYMON
acia_base = $8800 ; Symon
@@ -28,6 +28,29 @@ gets_str = $11 ; 16 bit address
acia_cmd_reg = acia_base + 2
acia_ctrl_reg = acia_base + 3
+;;; getc
+;;; Read character from acia. Blocks until character is read
+;;; Input:
+;;; -
+;;; Output:
+;;; a:
+;;; Character read
+;;; Changes:
+;;; a, acai registers
+
+;;; getc_seed_rng
+;;; Like getc, but also updates lsfr
+;;; This is our only source of randomness right now:
+;;; While we are busy waiting for a character, lsfr is
+;;; updated.
+;;; Input:
+;;; -
+;;; Output:
+;;; a:
+;;; Character read
+;;; Changes:
+;;; a, acai registers, lsfr_state
+
;;; puts
;;; Send up to 256 characters terminated by null via acia
;;; Input:
@@ -47,7 +70,7 @@ gets_str = $11 ; 16 bit address
;;; Output:
;;; -
;;; Changes:
-;;; x, acai-registers
+;;; x, acai registers
;;; puth
;;; Convert byte to hex and send via acia
@@ -57,7 +80,7 @@ gets_str = $11 ; 16 bit address
;;; Output:
;;; -
;;; Changes:
-;;; a, x, acai-registers, c-flag
+;;; a, x, acai registers, c-flag
;;; puth_nibble
;;; Convert lower half of byte to hex and send via acia
@@ -67,7 +90,7 @@ gets_str = $11 ; 16 bit address
;;; Output:
;;; -
;;; Changes:
-;;; a, x, acai-registers, c-flag
+;;; a, x, acai registers, c-flag
;;; putnl
;;; Send newline via acia
@@ -97,7 +120,25 @@ gets_str = $11 ; 16 bit address
;;; Changes:
;;; a, y, ACAI registers
+;;; lfsr_init
+;;; Initialize lfsr
+;;; Input:
+;;; -
+;;; Output:
+;;; -
+;;; Changes:
+;;; lfsr
+
+;;; lfsr_step
+;;; update lfsr
+;;; Input:
+;;; -
+;;; Output:
+;;; -
+;;; Changes:
+;;; lfsr
+
;;; Macros
;;; PRINT(addr)
@@ -156,7 +197,16 @@ gets_str = $11 ; 16 bit address
;;; Output:
;;; -
;;; Changes:
-;;; a, x, acai-registers
+;;; a, x, acai registers
+
+;;; STORE_WORD(word,dst)
+;;; Store word at dst
+;;; Input:
+;;; word
+;;; Output:
+;;; -
+;;; Changes:
+;;; a, dst
#define PRINT(addr) \
.(: \
@@ -200,5 +250,13 @@ cont: \
lda #$0a: \
jsr putc
+#define STORE_WORD(word,dst) \
+ .(: \
+ lda #<word: \
+ sta dst: \
+ lda #>word: \
+ sta dst+1: \
+ .)
+
;;; The lines below are automatically generated by export_symbols.py
diff --git a/roms/boot/boot.s b/roms/boot/boot.s
@@ -8,6 +8,11 @@
* = $e000
#endif
+
+;;; We have enough space left to
+;;; fit in a Tic-Tac-Toe engine!
+ start_ttt = * + $0c00
+
;;; ----------------------------------------------------------
;;; RESET
;;;
@@ -18,16 +23,39 @@
init:
cld
jsr init_acia
+ jsr check_for_program_download
+ bcs no_program_download
jmp download_program
+no_program_download:
+ ;; No program download?
+ ;; Then let's play some
+ ;; Tic-Tac-Toe!
+ jmp start_ttt
-;;; Downalod program to RAM and start executing it.
-;;; The first byte transmitted is the number of $100 byte
-;;; blocks to receive. Then the program is received.
-;;; Finally, a two byte checksum is send back. The first
-;;; byte of the checksum is the addition of all bytes received.
-;;; The second byte of the checksum is the xor of all bytes
-;;; received.
-
+;;; If we receive a byte right after a reset, this
+;;; triggers a program download via serial line.
+;;; The value of the byte is the number of $100 byte
+;;; blocks to receive.
+check_for_program_download:
+ .(
+ PRINTSNL("READY!")
+ ldy #$20 ; Outer loop counter
+ ldx #$00 ; Inner counter
+loop:
+ ;; Try to get number of 0x100 byte blocks to be read
+ jsr getc_nonblocking
+ bcc got_byte
+ dex
+ bne loop
+ dey
+ bne loop
+ PRINTSNL("Nothing to download.")
+ sec
+got_byte:
+ rts
+ .)
+
+
;; Program is loaded to this memory address
start_addr = $0300
;; Location of temporary variables
@@ -36,11 +64,10 @@ init:
add_checksum = $15
xor_checksum = $16
download_program:
- PRINTSNL("READY!")
- ;; Get number of 0x100 byte blocks to be read
- jsr getc
+ ;; We expect the number of $100 blocks to be
+ ;; downloaded in A.
;; The msb of the last block to be written is the msb
- ;; of the start address plus the number of blocks
+ ;; of the start address plus the number of blocks.
clc
adc #>start_addr
sta msb_last_addr
@@ -168,6 +195,34 @@ getc: ; EXPORT
lda acia_data_reg
rts
+getc_seed_rng: ; EXPORT
+ ;; Read character from acia
+ ;; We also use the time between keystrokes
+ ;; as entropy source for the RNG
+ jsr lfsr_step
+ lda acia_status_reg
+ and #%00001000
+ beq getc_seed_rng
+ lda acia_data_reg
+ rts
+
+getc_nonblocking: ; EXPORT
+ .(
+ ;; Non-blocking read: If
+ ;; character has been read,
+ ;; it is returned in A and
+ ;; C is cleared. If not,
+ ;; C is set
+ sec
+ lda acia_status_reg
+ and #%00001000
+ beq nothing_read
+ clc
+ lda acia_data_reg
+nothing_read:
+ rts
+ .)
+
gets: ; EXPORT
.(
;; Read string terminated by CR
@@ -193,14 +248,14 @@ terminate_string:
;;; bit from the state yields random numbers with reasonable
;;; statistical properties.
lfsr_seed = $beef
-init_lfsr: ; EXPORT
+lfsr_init: ; EXPORT
.(
lda #<lfsr_seed
sta lfsr_state
lda #>lfsr_seed
sta lfsr_state+1
.)
-lfsr: ; EXPORT
+lfsr_step: ; EXPORT
.(
asl lfsr_state
lda lfsr_state+1
@@ -231,7 +286,18 @@ loop:
.)
#endif // TESTS
-
+;;; Include Tic-Tac-Toe binary
+;;; This creates some circular dependencies,
+;;; because ttt.s includes liba.h, which
+;;; is generated from boot.h upon successful
+;;; compiliation of boot.s.
+ .dsb start_ttt-*, $ff
+#ifdef SYMON
+ .bin 0,0,"../../sw/ttt/ttt_boot_symon.bin"
+#else
+ .bin 0,0,"../../sw/ttt/ttt_boot.bin"
+#endif
+
;;; Vectors
.dsb $fffa-*, $ff
.word $0000 ; nmi
diff --git a/sw/10print/10print.s b/sw/10print/10print.s
@@ -4,7 +4,7 @@
init:
cld
jsr init_acia
- jsr init_lfsr
+ jsr lfsr_init
jmp ten_print
ten_print:
@@ -17,7 +17,7 @@ l0:
bne l0
dex
bne l1
- jsr lfsr
+ jsr lfsr_step
and #$01
bne slash
PRINTS('╲')
diff --git a/sw/ttt/Makefile b/sw/ttt/Makefile
@@ -0,0 +1,33 @@
+TARGET=ttt.bin
+TARGET_BASENAME=$(basename $(TARGET))
+
+all: $(TARGET) $(TARGET_BASENAME)_boot.bin \
+ $(TARGET_BASENAME)_symon.bin $(TARGET_BASENAME)_boot_symon.bin \
+ $(TARGET_BASENAME)_test.bin $(TARGET_BASENAME)_symon_test.bin
+
+%.bin: %.s
+ xa -l "$(basename $@).l" -r -o "$@" "$<"
+
+%_boot.bin: %.s
+ xa -DBOOT -l "$(basename $@).l" -r -o "$@" "$<"
+
+%_test.bin: %.s
+ xa -DRUN_TESTS -l "$(basename $@).l" -r -o "$@" "$<"
+
+%_symon.bin: %.s
+ xa -DSYMON -l "$(basename $@).l" -r -o "$@" "$<"
+
+%_boot_symon.bin: %.s
+ xa -DBOOT -DSYMON -l "$(basename $@).l" -r -o "$@" "$<"
+
+%_symon_test.bin: %.s
+ xa -DRUN_TESTS -DSYMON -l "$(basename $@).l" -r -o "$@" "$<"
+
+upload: $(TARGET)
+ ../../roms/boot/boot.py $(TARGET)
+
+upload_test: $(TARGET_BASENAME)_test.bin
+ ../../roms/boot/boot.py $(TARGET_BASENAME)_test.bin
+
+clean:
+ rm -f *.bin *.l
diff --git a/sw/ttt/README.txt b/sw/ttt/README.txt
@@ -0,0 +1,26 @@
+* Targets
+
+ttt.bin
+ is the binary to be uploaded to address $300 on the GATE 2010
+ttt_symon.bin
+ is the binary for Symon (ROM & ACIA at different memory addresses)
+*_boot.bin
+ are binaries to be included into the boot ROM of GATE 2010 and Symon
+*_test.bin
+ are binaries running self-tests on GATE 2010 and Symon
+
+* Source Code
+
+ttt.s
+ Contains the main routine
+board.s
+ Subroutines for managing the board
+board_test.s
+ Tests for board.s
+computer_player.s
+ Implementations of random and perfect computer players
+computer_player_test.s
+ Tests for computer_player.s
+human_player.s
+ CLI for human players
+
diff --git a/sw/ttt/board.s b/sw/ttt/board.s
@@ -0,0 +1,589 @@
+;;; This file contains the definitions and subroutines
+;;; related to the game boards, like printing the
+;;; game board and placing pieces. It also contains
+;;; the subroutines to check for a win constallation
+;;; on the board, and for playing the game.
+
+;;; Orchester a game between two players
+;;; Each player has an init subroutine, called
+;;; once at the beginning, and a ply subroutine,
+;;; called on every turn of the player.
+;;; player_x_init_ptr - Init function of player X
+;;; player_x_ply_ptr - Ply function of player X
+;;; player_o_init_ptr - Init function of player O
+;;; player_o_ply_ptr - Ply function of player O
+play_game:
+ .(
+ jsr init_board
+ ;; jsr does not allow indirect addressing,
+ ;; threfore we have to wrap the indirect
+ ;; calls this way.
+ jsr player_x_init
+ jsr player_o_init
+play_game_loop:
+ lda #piece_x
+ jsr next_ply
+ bne game_finished
+ lda #piece_o
+ jsr next_ply
+ bne game_finished
+ jmp play_game_loop
+game_finished:
+ pha
+ jsr print_board
+ pla
+ jsr print_game_state
+ PRINTNL
+ rts
+next_ply:
+ cmp #piece_x
+ bne ply_player_o
+ ;; Player X's ply
+ ;; jsr does not allow indirect addressing,
+ ;; threfore we have to wrap the indirect
+ ;; calls this way.
+ jsr player_x_ply
+ jmp cont
+ply_player_o:
+ jsr player_o_ply
+cont:
+ jsr get_game_state
+ cmp #$ff
+ rts
+player_x_init:
+ jmp (player_x_init_ptr)
+player_o_init:
+ jmp (player_o_init_ptr)
+player_x_ply:
+ jmp (player_x_ply_ptr)
+player_o_ply:
+before_o:
+ jmp (player_o_ply_ptr)
+after_o:
+ .)
+
+;;; We store the Tic-Tac-Toe board in three
+;;; bytes, one for each row. When passing
+;;; a board on the stack, the first row is
+;;; pushed first, followed by the second,
+;;; and third.
+;;;
+;;; Each field in a row is represented by
+;;; two bits:
+;;; %00 - Field unoccupied
+;;; %01 - Field occupied by player "X"
+;;; %10 - Field occupied by player "O"
+
+piece_none = %00
+piece_x = %01
+piece_o = %10
+;;;
+;;; In the byte for a row, the first
+;;; two bits represent the leftmost field.
+;;; The last two bits are not used.
+;;;
+;;; A contains the piece
+;;; X contains the position (0-8)
+;;; The location of the board is read
+;;; as a 16 bit address from address
+;;; board.
+
+
+;;; Initialize and clear the board.
+;;; When init_board is called, the
+;;; "standard" board location as given
+;;; in variable board is transferred
+;;; to board_ptr before clearing the
+;;; board.
+;;; If clear_board is called, the
+;;; board at board_ptr is cleared
+;;; without changing board_ptr.
+init_board:
+ lda #<main_board
+ sta board_ptr
+ lda #>main_board
+ sta board_ptr+1
+clear_board:
+ // Clear board
+ lda #$00
+ ldy #$00
+ sta (board_ptr),y
+ iny
+ sta (board_ptr),y
+ iny
+ sta (board_ptr),y
+ rts
+
+mirror_board:
+ .(
+ ;; Mirror board on the diagonal axis
+ ;; such that we can
+ ;; use the win_row subroutine.
+ ;; First row to column
+ ldy #$00
+ lda (board_ptr),y
+ and #%00000011
+ sta (other_board_ptr),y
+ lda (board_ptr),y
+ and #%00001100
+ lsr
+ lsr
+ ldy #$01
+ sta (other_board_ptr),y
+ ldy #$00
+ lda (board_ptr),y
+ and #%00110000
+ lsr
+ lsr
+ lsr
+ lsr
+ ldy #$02
+ sta (other_board_ptr),y
+ ;; Second row to column
+ ldy #$01
+ lda (board_ptr),y
+ and #%00000011
+ asl
+ asl
+ ldy #$00
+ ora (other_board_ptr),y
+ sta (other_board_ptr),y
+ ldy #$01
+ lda (board_ptr),y
+ and #%00001100
+ ora (other_board_ptr),y
+ sta (other_board_ptr),y
+ ldy #$01
+ lda (board_ptr),y
+ and #%00110000
+ lsr
+ lsr
+ ldy #$02
+ ora (other_board_ptr),y
+ sta (other_board_ptr),y
+ ;; Third column to row
+ lda (board_ptr),y
+ and #%00000011
+ asl
+ asl
+ asl
+ asl
+ ldy #$00
+ ora (other_board_ptr),y
+ sta (other_board_ptr),y
+ ldy #$02
+ lda (board_ptr),y
+ and #%00001100
+ asl
+ asl
+ ldy #$01
+ ora (other_board_ptr),y
+ sta (other_board_ptr),y
+ ldy #$02
+ lda (board_ptr),y
+ and #%00110000
+ ora (other_board_ptr),y
+ sta (other_board_ptr),y
+ rts
+ .)
+
+;;; Set a field on the board.
+;;; A is the field, X the position.
+;;; This subroutine changes A, X, and Y.
+set_field:
+ ;; Convert position on X
+ ;; to column/row in X/Y.
+ jsr pos_to_column_row
+ ;; Set field based on X/Y coordinates
+set_field_x_y:
+ .(
+ cpx #$00
+ beq change_board
+ asl
+ asl
+ dex
+ jmp set_field_x_y
+change_board:
+ ora (board_ptr),y
+ sta (board_ptr),y
+ rts
+ .)
+
+;;; Get value of field on the board.
+;;; X is the position. Field value is
+;;; returned in A.
+get_field:
+ .(
+ ;; Convert position on X
+ ;; to column/row in X/Y.
+ jsr pos_to_column_row
+ lda (board_ptr),y
+field_loop:
+ cpx #$00
+ beq got_field
+ lsr
+ lsr
+ dex
+ jmp field_loop
+got_field:
+ and #%11
+ rts
+ .)
+
+;;; Convert position in X
+;;; register to row/column
+;;; coordinates.
+;;; X becomes the column,
+;;; Y the row
+pos_to_column_row:
+ .(
+ ldy #$00
+pos_loop:
+ cpx #$03
+ bcc pos_found
+ iny
+ dex
+ dex
+ dex
+ jmp pos_loop
+pos_found:
+ rts
+ .)
+
+
+copy_field:
+ ;; Copy field X from board_ptr
+ ;; to field Y of other_board_ptr
+ ;; Save variables
+ lda board_ptr
+ pha
+ lda board_ptr+1
+ pha
+ phy
+ ;; Get value & save ot
+ jsr get_field
+ pha
+ ;; Write value
+ lda other_board_ptr
+ sta board_ptr
+ lda other_board_ptr+1
+ sta board_ptr+1
+ pla
+ plx
+ jsr set_field
+ ;; Restore variables
+ pla
+ sta board_ptr+1
+ pla
+ sta board_ptr
+ rts
+
+#define COPY_FIELD(from,to) \
+ ldx #from: \
+ ldy #to: \
+ jsr copy_field
+
+#define SET_FIELD(piece,pos) \
+ lda #piece: \
+ ldx #pos: \
+ jsr set_field
+
+#define GET_FIELD(ptr,pos) \
+ STORE_WORD(ptr,board_ptr): \
+ ldx #pos: \
+ jsr get_field
+
+;;; Print Tic-Tac-Toe board.
+;;; Note that the printed
+;;; numbers start with 1, while
+;;; the internal counting of
+;;; fields starts with 0.
+print_board:
+ .(
+ ldx #$ff
+ phx
+ PRINTSNL('+---+---+---+')
+print_field:
+ lda #$03
+ sta tmp ; Print each line 3 times
+print_line:
+ lda #'|'
+ jsr putc
+ plx
+ inx
+ phx
+ jsr get_field
+ jsr piece_to_ascii
+ jsr putc
+ plx
+ phx
+ jsr put_field_number_if_empty_and_middle
+ jsr putc
+ plx
+ phx
+ cpx #$02
+ beq print_row_seperator
+ cpx #$05
+ beq print_row_seperator
+ cpx #$08
+ beq print_row_seperator
+check_if_all_rows_printed:
+ plx
+ phx
+ cpx #$08
+ bne print_line
+ plx ; Clean-up stack
+ rts
+print_row_seperator:
+ PRINTSNL('|')
+ dec tmp ; Check if each line has been printed 3 times
+ lda tmp
+ beq print_seperator
+ pla ; If not,
+ sec ; print
+ sbc #$03 ; line
+ pha
+ jmp print_line ;again.
+print_seperator:
+ PRINTSNL('+---+---+---+')
+ lda #$03
+ sta tmp
+ jmp check_if_all_rows_printed
+put_field_number_if_empty_and_middle:
+ pha
+ cmp #' '
+ bne print_verbatim
+ ;; Check if we are in the
+ ;; middle line
+ lda tmp
+ cmp #$02
+ bne print_verbatim
+ ;; Middle of empty field;
+ ;; print field number
+ txa
+ clc
+ adc #'1'
+ jsr putc
+ pla
+ rts
+print_verbatim:
+ pla
+ jmp putc
+ .)
+
+
+
+piece_to_ascii:
+ .(
+ cmp #piece_x
+ bne not_x
+ lda #'#'
+ rts
+not_x:
+ cmp #piece_o
+ bne not_o
+ lda #':'
+ rts
+not_o:
+ lda #' '
+ rts
+ .)
+
+;;; Check if a player won.
+;;; Returns piece_x or piece_y
+;;; if one of the player won,
+;;; piece_none in case of a draw,
+;;; and #$ff in case the game
+;;; is not finished yet.
+ piece_x_row = (piece_x << 4) + (piece_x << 2) + piece_x
+ piece_o_row = (piece_o << 4) + (piece_o << 2) + piece_o
+get_game_state:
+ .(
+ lda #piece_x_row
+ jsr check_player_won
+ bne done
+ lda #piece_o_row
+ jsr check_player_won
+ bne done
+ jsr check_draw
+done:
+ rts
+ .)
+
+;;; Check if a certain player one.
+;;; This subroutine expects a complete
+;;; row of pieces of the player to be
+;;; checked for winning in A as input.
+check_player_won:
+ .(
+ sta tmp ; Store pattern for following checks
+ jsr check_win_row
+ bne done
+ lda tmp
+ jsr check_win_column
+ bne done
+ lda tmp
+ jsr check_win_first_diagonal
+ bne done
+ lda tmp
+ jsr check_win_second_diagonal
+done:
+ rts
+ .)
+
+;;; Check for three in a row.
+;;; Expects the row pattern of
+;;; three identical pieces in A.
+check_win_row:
+ .(
+ ldy #$00
+loop:
+ cmp (board_ptr),y
+ beq player_won
+ iny
+ cpy #$03
+ bne loop
+ ;; No winning rows
+ lda #$00
+ rts
+player_won:
+ lda tmp
+ and #%00000011
+ rts
+ .)
+
+;;; Check for three in a column.
+;;; Expects the row(!) pattern of
+;;; three identical pieces in A.
+check_win_column:
+ .(
+ and #%00110000 ; Field (column) pattern
+ tax ; We use X as temporary memory
+ ldy #$00
+loop:
+ and (board_ptr),y ; Piece in column?
+ beq check_next_column ; If not, check next column
+ iny ; If yes, advance to next row
+ cpy #$03 ; Until all three rows
+ bne loop ; have been checked
+player_won:
+ lda tmp
+ and #%00000011
+ rts
+check_next_column:
+ ldy #$00 ; Restore row counter
+ txa ; Old field (column) pattern
+ lsr ; Change to
+ lsr ; next column
+ tax ; and save it in temporary memory
+ bne loop
+ ;; No winning columns
+ lda #$00
+ rts
+ .)
+
+check_win_first_diagonal:
+ .(
+ and #%00110000 ; Start with last field (column)
+ tax ; Store pattern in x
+ ldy #$00 ; Row number stored in y
+loop:
+ and (board_ptr),y
+ beq no_win_first_diagonal
+ txa ; Move
+ lsr ; field
+ lsr ; (column)
+ tax ; pattern
+ iny ; and row by one
+ cpy #$03
+ bne loop
+ ;; Player won
+ ;; Return player piece
+ lda tmp
+ and #%00000011
+ rts
+no_win_first_diagonal:
+ lda #$00
+ rts
+ .)
+
+check_win_second_diagonal:
+ .(
+ and #%00000011 ; Start with first field (column)
+ tax ; Store pattern in x
+ ldy #$00 ; Row number stored in y
+loop:
+ and (board_ptr),y
+ beq no_win_second_diagonal
+ txa ; Move
+ asl ; field
+ asl ; (column)
+ tax ; pattern
+ iny ; and row by one
+ cpy #$03
+ bne loop
+ ;; Player won
+ ;; Return player piece
+ lda tmp
+ and #%00000011
+ rts
+no_win_second_diagonal:
+ lda #$00
+ rts
+ .)
+
+check_draw:
+ .(
+ ldy #$00 ; Row
+row_loop:
+ ldx #%00110000 ; Field (column) pattern
+ txa ; Store pattern in x
+col_loop:
+ and (board_ptr),y ; Check
+ beq no_draw ; all
+ txa ; fields
+ lsr ; for
+ lsr ; emptiness
+ tax
+ bne col_loop
+ iny
+ cpy #$03
+ bne row_loop
+ ;; Draw
+ lda #piece_none
+ rts
+no_draw:
+ lda #$ff
+ rts
+ .)
+
+
+
+;;; This subroutine can be called
+;;; called after get_game_state
+;;; in order to print the state
+;;; of the game in human-friendly
+;;; format to the acai.
+print_game_state:
+ .(
+ cmp #piece_x
+ beq win
+ cmp #piece_o
+ beq win
+ cmp #piece_none
+ bne no_draw
+ PRINTSNL("Draw!")
+ rts
+no_draw:
+ PRINTSNL("Let the game continue!")
+ rts
+win:
+ pha
+ PRINTS("Player ")
+ pla
+ clc
+ adc #'0'
+ jsr putc
+ PRINTSNL(" wins!")
+ rts
+ .)
diff --git a/sw/ttt/board_test.s b/sw/ttt/board_test.s
@@ -0,0 +1,143 @@
+;;; Expected value is given in res.
+;;; A is compared to this value.
+#define CHECK_ERROR(res) \
+ .(: \
+ cmp #res: \
+ beq no_error: \
+ PRINTSNL("Error"): \
+stop_loop: \
+ jmp stop_loop: \
+no_error: \
+ .)
+
+#define PLAYER_WIN_ROW(player,row_start) \
+ .(: \
+ jsr init_board: \
+ ldx #row_start: \
+ lda #player: \
+ jsr set_field: \
+ ldx #(row_start+1): \
+ lda #player: \
+ jsr set_field: \
+ ldx #(row_start+2): \
+ lda #player: \
+ jsr set_field: \
+ jsr print_board: \
+ jsr get_game_state: \
+ CHECK_ERROR(player): \
+ jsr print_game_state: \
+ .)
+
+#define PLAYER_WIN_COLUMN(player,col) \
+ .(: \
+ jsr init_board: \
+ lda #player: \
+ ldx #col: \
+ jsr set_field: \
+ lda #player: \
+ ldx #(col+3): \
+ jsr set_field: \
+ lda #player: \
+ ldx #(col+6): \
+ jsr set_field: \
+ jsr print_board: \
+ jsr get_game_state: \
+ CHECK_ERROR(player): \
+ jsr print_game_state: \
+ .)
+
+#define PLAYER_WIN_SECOND_DIAGONAL(player) \
+ jsr init_board: \
+ lda #player: \
+ ldx #$00: \
+ jsr set_field: \
+ lda #player: \
+ ldx #$04: \
+ jsr set_field: \
+ lda #player: \
+ ldx #$08: \
+ jsr set_field: \
+ jsr print_board: \
+ jsr get_game_state: \
+ CHECK_ERROR(player): \
+ jsr print_game_state
+
+#define PLAYER_WIN_FIRST_DIAGONAL(player) \
+ jsr init_board: \
+ lda #player: \
+ ldx #$02: \
+ jsr set_field: \
+ lda #player: \
+ ldx #$04: \
+ jsr set_field: \
+ lda #player: \
+ ldx #$06: \
+ jsr set_field: \
+ jsr print_board: \
+ jsr get_game_state: \
+ CHECK_ERROR(player): \
+ jsr print_game_state
+
+;;; Place some pieces
+;;; and print the field.
+game_board_test:
+ .(
+ ;;
+ ;; Unfinished game.
+ ;;
+ jsr init_board
+ // Place "X" pieces
+ SET_FIELD(piece_x,$00)
+ SET_FIELD(piece_x,$01)
+ SET_FIELD(piece_x,$08)
+ // Place "O" pieces
+ SET_FIELD(piece_o,$04)
+ SET_FIELD(piece_o,$05)
+ SET_FIELD(piece_o,$06)
+ ;; Print board
+ jsr print_board
+ jsr get_game_state
+ CHECK_ERROR($ff)
+ jsr print_game_state
+ ;;
+ ;; Finished game.
+ ;;
+ jsr init_board
+ SET_FIELD(piece_x,$00)
+ SET_FIELD(piece_x,$01)
+ SET_FIELD(piece_o,$02)
+ SET_FIELD(piece_o,$03)
+ SET_FIELD(piece_o,$04)
+ SET_FIELD(piece_x,$05)
+ SET_FIELD(piece_x,$06)
+ SET_FIELD(piece_x,$07)
+ SET_FIELD(piece_o,$08)
+ jsr print_board
+ jsr get_game_state
+ CHECK_ERROR(piece_none)
+ jsr print_game_state
+ ;; Let each player win in
+ ;; each row
+ PLAYER_WIN_ROW(piece_x,$00)
+ PLAYER_WIN_ROW(piece_x,$03)
+ PLAYER_WIN_ROW(piece_x,$06)
+ PLAYER_WIN_ROW(piece_o,$00)
+ PLAYER_WIN_ROW(piece_o,$03)
+ PLAYER_WIN_ROW(piece_o,$06)
+ ;; Let each player win in
+ ;; each column
+ PLAYER_WIN_COLUMN(piece_x,$00)
+ PLAYER_WIN_COLUMN(piece_x,$01)
+ PLAYER_WIN_COLUMN(piece_x,$02)
+ PLAYER_WIN_COLUMN(piece_o,$00)
+ PLAYER_WIN_COLUMN(piece_o,$01)
+ PLAYER_WIN_COLUMN(piece_o,$02)
+ ;; Let each player win in
+ ;; each diagonal
+ PLAYER_WIN_SECOND_DIAGONAL(piece_x)
+ PLAYER_WIN_FIRST_DIAGONAL(piece_x)
+ PLAYER_WIN_SECOND_DIAGONAL(piece_o)
+ PLAYER_WIN_FIRST_DIAGONAL(piece_o)
+ PRINTSNL("Board tests completed. No errors found!")
+ rts
+ .)
diff --git a/sw/ttt/computer_player.s b/sw/ttt/computer_player.s
@@ -0,0 +1,755 @@
+;;; ************************************************
+;;;
+;;; Random Computer Player
+;;;
+;;; ************************************************
+computer_random_init:
+ rts
+computer_random_ply:
+ .(
+ pha ; Remember who we are
+ ;; We need a random number
+ ;; in the range 0..8. For
+ ;; this, we update the lfsr
+ ;; and take the lowest
+ ;; nibble until it is <= 8.
+get_random:
+ jsr lfsr_step
+ lda lfsr_state
+ and #$0f
+ cmp #$09
+ bcs get_random
+ ;; Check if field is occupied
+ sta tmp
+ tax
+ jsr get_field
+ cmp #piece_none
+ bne get_random
+ ;; Occupy field
+ ldx tmp
+ pla
+#ifdef RUN_TESTS
+ jsr print_random_ply
+#endif
+ jsr set_field
+ clc
+ rts
+ .)
+
+;;; ************************************************
+;;;
+;;; Perfect Computer Player
+;;;
+;;; ************************************************
+
+;;; See http://csjarchive.cogsci.rpi.edu/1993v17/i04/p0531p0561/MAIN.PDF
+computer_perfect_init:
+ rts
+computer_perfect_ply:
+ .(
+ ;; Random First
+ ;; Added by gb: Start with a random move on an empty field in
+ ;; order to create different games
+ pha
+ jsr random_first
+ pla
+ bcc done
+ ;; Win
+ ;; If there is a row, column, or diagonal with two of my pieces
+ ;; and a blank space,
+ ;; Then play the blank space (thus winning the game).
+ pha
+ jsr win
+ pla
+ bcc execute_ply
+ ;; Block
+ ;; If there Is a row, column, or diagonal with two of my
+ ;; opponent's pieces and a blank space,
+ ;; Then play the blank space (thus blocking a potential win for
+ ;; my opponent).
+ pha
+ jsr block
+ pla
+ bcc execute_ply
+ ;; Fork
+ ;; If there are two intersecting rows, columns, or diagonals
+ ;; with one of my pieces and two blanks, and
+ ;; If the intersecting space Is empty,
+ ;; Then move to the intersecting space (thus creating two
+ ;; ways to win on my next turn).
+ pha
+ jsr fork
+ pla
+ bcc execute_ply
+ ;; Block Fork
+ ;; If there are two intersecting rows, columns, or diagonals
+ ;; with one of my opponent’s pieces ond two blanks, and
+ ;; If the intersecting space is empty,
+ ;; Then
+ ;; If there is an empty location that creates a
+ ;; two-in-a-row for me (thus forcing my opponent to
+ ;; block rather than fork),
+ ;; Then move to the location.
+ ;; Else move to the Intersection space (thus occupying
+ ;; the location that my opponent could use to fork).
+ pha
+ jsr block_fork
+ pla
+ bcc execute_ply
+ ;; Play Center
+ ;; If the center is blank,
+ ;; Then play the center.
+ pha
+ jsr play_center
+ pla
+ bcc execute_ply
+ ;; Play Opposite Corner
+ ;; If my opponent is in a corner, and
+ ;; If the opposite corner is empty,
+ ;; Then play the opposite corner.
+ pha
+ jsr play_opposite_corner
+ pla
+ bcc execute_ply
+ ;; Play Empty Corner
+ ;; If there is an empty corner,
+ ;; Then move to an empty corner.
+ pha
+ jsr play_empty_corner
+ pla
+ bcc execute_ply
+ ;; Play Empty Side
+ ;; If there is an empty side,
+ ;; Then move to an empty side.
+ pha
+ jsr play_empty_side
+ pla
+ bcc execute_ply
+ ;; No rule left; this should not happen.
+ PRINTSNL('Error')
+error:
+ jmp error
+execute_ply:
+#ifdef RUN_TESTS
+ jsr print_ply
+#endif
+ jsr set_field_x_y
+done:
+ rts
+ .)
+
+random_first:
+ .(
+ sta tmp ; Remember who I am
+ cmp #piece_x ; If we are x
+ bne not_first ;
+ ldy #$00
+row_loop:
+ lda main_board,y ; Check if
+ bne not_first ; all
+ iny ; rows
+ cpy #$03 ; are
+ bne row_loop ; empty
+ lda tmp
+ jmp computer_random_ply
+not_first:
+ sec
+ rts
+ .)
+
+win:
+ .(
+ pha
+ jsr win_row
+ pla
+ bcc done
+ pha
+ jsr win_column
+ pla
+ bcc done
+ pha
+ jsr win_first_diagonal
+ pla
+ bcc done
+ pha
+ jsr win_second_diagonal
+ pla
+done:
+ rts
+ .)
+
+win_row:
+ .(
+ ;; Load complete winning row
+ cmp #piece_x
+ bne this_is_o
+ lda #piece_x_row
+ jmp win_row_set
+this_is_o:
+ lda #piece_o_row
+win_row_set:
+ sta tmp ; Store win row
+ ldy #$00 ; Row counter
+row_loop:
+ ldx #$00 ; Column counter
+ lda tmp
+ and #%00111100
+ cmp (board_ptr),y
+ beq win_ply
+ inx
+ lda tmp
+ and #%00110011
+ cmp (board_ptr),y
+ beq win_ply
+ inx
+ lda tmp
+ and #%00001111
+ cmp (board_ptr),y
+ beq win_ply
+ ;; No win here. Try next row
+ iny
+ cpy #$03
+ bne row_loop
+ ;; No win row
+ ;; Carry set indicates failure
+ sec
+ rts
+win_ply:
+ ;; Found a winning move
+ ;; return piece in A,
+ ;; and position in X/Y.
+ ;; Clear carry to indicate success.
+ lda tmp
+ and #%00000011
+ clc
+ rts
+ .)
+
+win_column:
+ .(
+ sta tmp ; Remember who I am
+ ;; We mirror the board in order to use
+ ;; win_column to check for a winning
+ ;; position.
+ STORE_WORD(board_mirrored,other_board_ptr)
+ jsr mirror_board
+ STORE_WORD(board_mirrored,board_ptr)
+ lda tmp ; Who am I?
+ jsr win_row
+ STORE_WORD(main_board,board_ptr)
+ bcs no_win
+ ;; We found a winning position
+ ;; since we found the winning
+ ;; position on the mirrored board,
+ ;; we have to mirror it back.
+ phx
+ tya
+ tax
+ ply
+ clc
+no_win:
+ rts
+ .)
+
+win_first_diagonal:
+ .(
+ sta tmp ; Remember who I am
+ lda #$ff ; No empty field
+ sta empty_field ; found so far
+ lda #$00 ; Upper left field
+ jsr check_if_occupied_and_update_empty_field
+ bcs no_win
+ lda #$04 ; Middle field
+ jsr check_if_occupied_and_update_empty_field
+ bcs no_win
+ lda #$08 ; Lower right field
+ jsr check_if_occupied_and_update_empty_field
+ bcs no_win
+ ;; We can win!
+ clc
+ lda tmp
+ ldx empty_field
+ jsr pos_to_column_row
+ rts
+no_win:
+ sec
+ rts
+ .)
+win_second_diagonal:
+ .(
+ sta tmp ; Remember who I am
+ lda #$ff ; No empty field
+ sta empty_field ; found so far
+ lda #$02 ; Upper right field
+ jsr check_if_occupied_and_update_empty_field
+ bcs no_win
+ lda #$04 ; Middle field
+ jsr check_if_occupied_and_update_empty_field
+ bcs no_win
+ lda #$06 ; Lower left field
+ jsr check_if_occupied_and_update_empty_field
+ bcs no_win
+ ;; We can win!
+ clc
+ lda tmp
+ ldx empty_field
+ jsr pos_to_column_row
+ rts
+no_win:
+ sec
+ rts
+ .)
+
+ ;; We can complete the first diagonal if
+ ;; we occupy two of the field already,
+ ;; and the third field is empty.
+ ;; This subroutine checks if a field
+ ;; is occupied by us or if it is empty.
+ ;; In the latter case, empty_field is
+ ;; updated unless it was set already
+ ;; (i.e. this is the second empty field,
+ ;; thus no win ply available (yet)).
+check_if_occupied_and_update_empty_field:
+ .(
+ pha ; Field number
+ tax ; stored in X,
+ jsr get_field ; field piece
+ plx ; stored in A.
+ cmp tmp ; Field occupied
+ beq cont ; by me?
+ cmp #$00 ; Field not occupied?
+ bne no_win ; Occupied by opponent. No win.
+ lda empty_field ; Have we seen an empty
+ cmp #$ff ; field before?
+ bne no_win ; Then we have too many empty fields.
+ stx empty_field ; Otherwise this is the empty field.
+cont:
+ clc
+ rts
+no_win:
+ sec
+ rts
+ .)
+
+ ;; We use subroutine win to check
+ ;; if the other player could win
+block:
+ .(
+ cmp #piece_o
+ beq we_are_o
+ lda #piece_o
+ jmp win
+we_are_o:
+ lda #piece_x
+ jmp win
+ .)
+
+fork:
+ .(
+ ;; Forks require two intersecting rows, columns, or diagonals
+ ;; which both contain only one piece of the player and no
+ ;; other pieces. If the intersection is empty, then this
+ ;; is the fork field.
+ ;; To find these points, we create three additional boards:
+ ;; On the first board, all rows satisfying the critera
+ ;; are maintained, while all other rows are filled with $ff.
+ ;; On the second board, we do the same for columns,
+ ;; on the third board for the diagonals.
+ ;; Then we OR the boards pairwise. If there is
+ ;; an empty field after pairing, then this is the
+ ;; fork field.
+ pha ; Remember who I am
+ STORE_WORD(fork_board_rows,other_board_ptr)
+ pla ; Store my piece
+ pha ; in A
+ jsr find_rows_for_fork
+ ;; Generate second board (potential fork columns)
+ ;; For this, we mirror the board and use
+ ;; find_rows_for_fork again.
+ ;; We use board_mirrored as an auxillary variable
+ ;; here.
+ STORE_WORD(main_board,board_ptr)
+ STORE_WORD(fork_board_columns,other_board_ptr)
+ jsr mirror_board
+ ;; Check for fork points on mirrored
+ ;; board and store the result in
+ ;; fork_board_columns
+ STORE_WORD(fork_board_columns,board_ptr)
+ STORE_WORD(board_mirrored,other_board_ptr)
+ pla ; Store my piece
+ pha ; in A
+ jsr find_rows_for_fork
+ ;; Reverse mirroring
+ STORE_WORD(board_mirrored,board_ptr)
+ STORE_WORD(fork_board_columns,other_board_ptr)
+ jsr mirror_board
+ pla
+ pha
+ STORE_WORD(fork_board_rows,board_ptr)
+ STORE_WORD(fork_board_columns,other_board_ptr)
+ jsr check_fork
+ bcs cont
+ jmp done
+cont:
+ ;; We have generated the fork_boards
+ ;; for row and column, but there was
+ ;; no fork on rows and columns.
+ ;; Now we create the fork board for
+ ;; diagonals.
+ ;; In order to use our subroutine
+ ;; find_rows_for_fork
+ ;; again, we map the first diagonal
+ ;; to the first row of a new board,
+ ;; and the second diagonal to the
+ ;; second row.
+ ;; We use board_mirrored as
+ ;; temporary storage.
+ ;; First diagonal to first row
+ lda #$00
+ sta fork_board_diagonals
+ sta fork_board_diagonals+1
+ sta fork_board_diagonals+2
+ STORE_WORD(main_board,board_ptr)
+ STORE_WORD(fork_board_diagonals,other_board_ptr)
+ COPY_FIELD(0,0)
+ COPY_FIELD(4,1)
+ COPY_FIELD(8,2)
+ ;; Second diagonal to second row
+ COPY_FIELD(2,3)
+ COPY_FIELD(4,4)
+ COPY_FIELD(6,5)
+ STORE_WORD(fork_board_diagonals,board_ptr)
+ STORE_WORD(board_mirrored,other_board_ptr)
+ pla ; Store my piece
+ pha ; in A
+ jsr find_rows_for_fork
+ ;; Store result in fork_board_diagonals
+ ;; Invalidate all non-diagonal fields
+ lda #%00001100
+ sta fork_board_diagonals
+ sta fork_board_diagonals+2
+ lda #%00110011
+ sta fork_board_diagonals+1
+ ;; First diagonal
+ STORE_WORD(board_mirrored,board_ptr)
+ STORE_WORD(fork_board_diagonals,other_board_ptr)
+ COPY_FIELD(0,0)
+ COPY_FIELD(1,4)
+ COPY_FIELD(2,8)
+ ;; Second diagonal
+ COPY_FIELD(3,2)
+ COPY_FIELD(5,6)
+ ;; Middle field can be used in either diagonal
+ ;; therefore we have to treat it seperately
+ GET_FIELD(board_mirrored,4)
+ cmp #$00
+ bne middle_field_not_part_of_potential_fork
+ STORE_WORD(fork_board_diagonals,board_ptr)
+ SET_FIELD($00,4)
+middle_field_not_part_of_potential_fork:
+ ;; No check if there is a fork between
+ ;; rows and diagonals ...
+ STORE_WORD(fork_board_diagonals,board_ptr)
+ STORE_WORD(fork_board_rows,other_board_ptr)
+ jsr check_fork
+ bcc done
+ ;; ... and columns and diagonals.
+ STORE_WORD(fork_board_columns,other_board_ptr)
+ jsr check_fork
+done:
+ ;; Some restore operatons
+ STORE_WORD(main_board,board_ptr)
+ pla
+ rts
+ .)
+
+;;; Check if we can create a fork with a
+;;; suitable row and column. If this is
+;;; the case, we set the carry flag
+;;; and return the fork position.
+check_fork:
+ .(
+ ;; Since empty fields in
+ ;; fork_boards_rows and
+ ;; fork roads_columns indicate potential
+ ;; fork fields, we OR these two
+ ;; boards and check if there are
+ ;; empty fields.
+ ;; We store the ORed boards in
+ ;; board_mirrored, because this
+ ;; board is not used here.
+ clc
+ ldy #$00
+copy_and_or_boards_loop:
+ lda (board_ptr),y
+ ora (other_board_ptr),y
+ sta board_mirrored,y
+ iny
+ cpy #$03
+ bne copy_and_or_boards_loop
+ ;; No check for empty fields
+ ldy #$00 ; Row counter
+row_loop:
+ lda #%00000011 ; Field pattern
+ sta tmp
+ ldx #$00 ; Column counter
+pattern_loop:
+ lda board_mirrored,y
+ and tmp
+ beq found_empty_field
+ lda tmp ; Move
+ asl ; to
+ asl ; next
+ sta tmp ; pattern
+ inx
+ cpx #$03
+ bne pattern_loop
+ iny
+ cpy #$03
+ bne row_loop
+ sec
+found_empty_field:
+ rts
+ .)
+
+
+;;; Check for all rows if they may be part
+;;; of a fork. This is the case when the
+;;; row contains one of our pieces and
+;;; no other piece. In this case, the row
+;;; stays intact. In all other cases,
+;;; we overwrite the row with $ff.
+;;; board_ptr points to the input board,
+;;; other_board_ptr_to_the output board
+find_rows_for_fork:
+ .(
+ pha
+ ldy #$00 ; Row counter
+row_loop:
+ pla ; Get pattern we are looking for
+ pha
+ sta tmp
+ ldx #$00 ; Pattern counter
+pattern_loop:
+ lda (board_ptr),y ; Load row
+ cmp tmp ; Compare row to pattern
+ beq potential_fork_row
+ inx ; Is there
+ cpx #$03 ; a next pattern?
+ beq no_potential_fork_row
+ lda tmp ; Generate next pattern
+ asl
+ asl
+ sta tmp
+ jmp pattern_loop ; Test for this pattern
+no_potential_fork_row:
+ lda #$ff
+potential_fork_row:
+ sta (other_board_ptr),y
+ iny
+ cpy #$03
+ bne row_loop
+ pla ; Clean stack
+ rts
+ .)
+
+block_fork:
+ .(
+ pha ; Remember who I am
+ cmp #piece_o
+ beq we_are_o
+ lda #piece_o
+ jmp check_for_fork
+we_are_o:
+ lda #piece_x
+check_for_fork:
+ jsr fork
+ bcs done
+ ;; We found a potential fork for the opponent.
+ ;; Before occupying it, we check if we could
+ ;; create a two-in-a-row
+ ;; situation for me.
+ pla
+ pha
+ jsr two_in_a_row
+done:
+ pla ;Clean up stack
+ rts
+ .)
+two_in_a_row:
+ .(
+ pha ; Remember who I am
+ ldy #$00 ; Row counter
+row_loop:
+ pla ; Set
+ pha ; start
+ sta tmp ; pattern.
+ ldx #$00 ; Pattern counter
+pattern_loop:
+ lda (board_ptr),y
+ cmp tmp
+ beq found_row
+ lda tmp ; Next pattern
+ asl
+ asl
+ sta tmp
+ inx
+ cpx #$03 ; All patterns
+ bne pattern_loop ; checked for row
+ iny
+ cpy #$03
+ bne row_loop
+done:
+ pla ; Clean-up stack
+ sec
+ rts
+found_row:
+ ;; Found empty spot in row
+ ;; It is important to place the next piece
+ ;; on the empty corner field, not the middle field.
+ pla ; Clean-up stack
+ clc
+ lda (board_ptr),y
+ and #%00000011
+ beq first_spot_empty
+ ;; Since first spot is occupied,
+ ;; third spot must be empty
+ ldx #$02
+ rts
+first_spot_empty:
+ ldx #$00
+ rts
+ .)
+
+
+
+play_center:
+ .(
+ GET_FIELD(main_board,4)
+ sec
+ cmp #piece_none
+ bne done
+ ldx #$01
+ ldy #$01
+ clc
+done:
+ rts
+ .)
+
+play_opposite_corner:
+ .(
+ pha ; Remember who I am
+ ldx #$00
+ ldy #$08
+ pla
+ pha
+ jsr check_if_occupied_and_empty
+ bcc done
+ ldx #$02
+ ldy #$06
+ pla
+ pha
+ jsr check_if_occupied_and_empty
+ bcc done
+ ldx #$06
+ ldy #$02
+ pla
+ pha
+ jsr check_if_occupied_and_empty
+ bcc done
+ ldx #$08
+ ldy #$00
+ pla
+ pha
+ jsr check_if_occupied_and_empty
+ sec
+done:
+ pla
+ rts
+ .)
+ ;; Check if field in X is
+ ;; occupied by opponent and
+ ;; field in Y is empty.
+ ;; In this case, return
+ ;; coordinates of empty
+ ;; field in X/Y
+check_if_occupied_and_empty:
+ .(
+ phy
+ sta tmp ; This me
+ jsr get_field
+ cmp tmp ; Occupied
+ beq not_applicable ; by me
+ cmp #$00
+ beq not_applicable ; Field emtpy
+ ;; Check field (originally) in Y
+ plx
+ phx
+ jsr get_field
+ cmp #$00
+ bne not_applicable ; Not empty
+ ;; Field is empty. Occupy it
+ plx
+ jsr pos_to_column_row
+ clc
+ rts
+not_applicable:
+ pla ; Clear stack
+ sec
+ rts
+ .)
+
+play_empty_corner:
+ .(
+ sta tmp
+ ldx #$00
+ jsr occupy_if_empty
+ bcc done
+ ldx #$02
+ jsr occupy_if_empty
+ bcc done
+ ldx #$06
+ jsr occupy_if_empty
+ bcc done
+ ldx #$08
+ jsr occupy_if_empty
+ bcc done
+done:
+ rts
+ .)
+
+occupy_if_empty:
+ .(
+ phx
+ jsr get_field
+ cmp #$00
+ bne already_occupied
+ plx
+ jsr pos_to_column_row
+ clc
+ rts
+already_occupied:
+ plx ; Clear stack
+ sec
+ rts
+ .)
+
+play_empty_side:
+ .(
+ sta tmp
+ ldx #$01
+ jsr occupy_if_empty
+ bcc done
+ ldx #$03
+ jsr occupy_if_empty
+ bcc done
+ ldx #$05
+ jsr occupy_if_empty
+ bcc done
+ ldx #$07
+ jsr occupy_if_empty
+ bcc done
+done:
+ rts
+ .)
+
diff --git a/sw/ttt/computer_player_test.s b/sw/ttt/computer_player_test.s
@@ -0,0 +1,582 @@
+computer_player_test:
+ // jsr mirror_board_test
+ // jsr win_by_column
+ // jsr win_by_diagonal
+ // jsr block_by_column
+ // jsr fork_row_column
+ // jsr test_block_fork
+ // jsr test_play_opposite_corner
+ // jsr test_play_empty_corner
+ // jsr test_perfect_vs_random_computer_player
+ // jsr test_random_vs_perfect_computer_player
+ jsr test_perfect_vs_perfect_computer_player
+loop:
+ jmp loop
+
+#define SET_BOARD(first_row,second_row,third_row) \
+ lda #first_row: \
+ sta main_board: \
+ lda #second_row: \
+ sta main_board+1: \
+ lda #third_row: \
+ sta main_board+2
+
+#define CHECK_BOARD(first_row,second_row,third_row) \
+ .(: \
+ lda board_mirrored: \
+ cmp #first_row: \
+ bne check_board_err: \
+ lda board_mirrored+1: \
+ cmp #second_row: \
+ bne check_board_err: \
+ lda board_mirrored+2: \
+ cmp #third_row: \
+ beq check_board_cont: \
+check_board_err: \
+ jmp error: \
+check_board_cont: \
+ .)
+
+mirror_board_test:
+ .(
+ jsr init_board
+ STORE_WORD(board_mirrored,other_board_ptr)
+ ;; Test rotation of board
+ ;; One piece on field 0.
+ ;; Rotation should change nothing
+ SET_BOARD(%00000011,%00000000,%00000000)
+ jsr mirror_board
+ CHECK_BOARD(%00000011,%00000000,%00000000)
+ ;; First row to first column
+ SET_BOARD(%00111001,%00000000,%00000000)
+ jsr mirror_board
+ CHECK_BOARD(%00000001,%00000010,%00000011)
+ ;; Second row to Second column
+ SET_BOARD(%00000000,%00111001,%00000000)
+ jsr mirror_board
+ CHECK_BOARD(%00000100,%00001000,%00001100)
+ ;; Third row to third column
+ SET_BOARD(%00000000,%00000000,%00111001)
+ jsr mirror_board
+ CHECK_BOARD(%00010000,%00100000,%00110000)
+ ;; Complex board pattern
+ SET_BOARD(%00100100,%00110011,%00011001)
+ jsr mirror_board
+ CHECK_BOARD(%011100,%100001,%011110)
+no_error:
+ PRINTSNL("OK")
+ rts
+error:
+ PRINTSNL("ERROR")
+ rts
+ .)
+
+ ;; Computer finishes game
+ ;; by completing column
+win_by_column:
+ ;; First column
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 0)
+ SET_FIELD(piece_x, 3)
+ jsr play_win_by_column
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 0)
+ SET_FIELD(piece_x, 6)
+ jsr play_win_by_column
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 3)
+ SET_FIELD(piece_x, 6)
+ jsr play_win_by_column
+ ;; Second column
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 1)
+ SET_FIELD(piece_x, 4)
+ jsr play_win_by_column
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 1)
+ SET_FIELD(piece_x, 7)
+ jsr play_win_by_column
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 4)
+ SET_FIELD(piece_x, 7)
+ jsr play_win_by_column
+ ;; Third column
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 2)
+ SET_FIELD(piece_x, 5)
+ jsr play_win_by_column
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 2)
+ SET_FIELD(piece_x, 8)
+ jsr play_win_by_column
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 5)
+ SET_FIELD(piece_x, 8)
+ jsr play_win_by_column
+ rts
+play_win_by_column:
+ jsr print_board
+ PRINTNL
+ lda #piece_x
+ jsr computer_perfect_ply
+ pha
+ jsr print_board
+ pla
+ jsr get_game_state
+ cmp #piece_x
+ bne win_by_column_error
+ PRINTSNL("OK")
+ rts
+win_by_column_error:
+ PRINTSNL("ERROR")
+ rts
+
+win_by_diagonal:
+ ;;
+ ;; First diagonal
+ ;;
+ ;; Lower right field empty
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 0)
+ SET_FIELD(piece_x, 4)
+ jsr play_win_by_diagonal
+ ;; Middle field empty
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 0)
+ SET_FIELD(piece_x, 8)
+ jsr play_win_by_diagonal
+ ;; Upper left field empty
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 4)
+ SET_FIELD(piece_x, 8)
+ jsr play_win_by_diagonal
+ ;;
+ ;; Second diagonal
+ ;;
+ ;; Lower left field empty
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 2)
+ SET_FIELD(piece_x, 4)
+ jsr play_win_by_diagonal
+ ;; Middle field empty
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 2)
+ SET_FIELD(piece_x, 6)
+ jsr play_win_by_diagonal
+ ;; Upper right field empty
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 4)
+ SET_FIELD(piece_x, 6)
+ jsr play_win_by_diagonal
+ rts
+play_win_by_diagonal:
+ jsr print_board
+ PRINTNL
+ lda #piece_x
+ jsr computer_perfect_ply
+ pha
+ jsr print_board
+ pla
+ jsr get_game_state
+ cmp #piece_x
+ bne win_by_diagonal_error
+ PRINTSNL("OK")
+ rts
+win_by_diagonal_error:
+ PRINTSNL("ERROR")
+ rts
+
+block_by_column:
+ ;; First column
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 0)
+ SET_FIELD(piece_x, 3)
+ jsr play_block_by_column
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 0)
+ SET_FIELD(piece_x, 6)
+ jsr play_block_by_column
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 3)
+ SET_FIELD(piece_x, 6)
+ jsr play_block_by_column
+ ;; Second column
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 1)
+ SET_FIELD(piece_x, 4)
+ jsr play_block_by_column
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 1)
+ SET_FIELD(piece_x, 7)
+ jsr play_block_by_column
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 4)
+ SET_FIELD(piece_x, 7)
+ jsr play_block_by_column
+ ;; Third column
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 2)
+ SET_FIELD(piece_x, 5)
+ jsr play_block_by_column
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 2)
+ SET_FIELD(piece_x, 8)
+ jsr play_block_by_column
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 5)
+ SET_FIELD(piece_x, 8)
+ jsr play_block_by_column
+ rts
+play_block_by_column:
+ jsr print_board
+ PRINTNL
+ lda #piece_o
+ jsr computer_perfect_ply
+ pha
+ jsr print_board
+ pla
+ jsr getc
+ rts
+
+fork_row_column:
+ .(
+ ;; Row/column fork
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 0)
+ SET_FIELD(piece_x, 1)
+ SET_FIELD(piece_o, 2)
+ SET_FIELD(piece_o, 3)
+ SET_FIELD(piece_x, 6)
+ pha
+ jsr print_board
+ pla
+ PRINTNL
+ lda #piece_o
+ jsr computer_perfect_ply
+ pha
+ jsr print_board
+ pla
+ ;; Check for correct ply
+ GET_FIELD(main_board,5)
+ CHECK_ERROR(piece_o)
+ jsr getc
+ ;; Row/diagonal fork
+ jsr init_board
+ // lda #$ac ; Test runs perfectly with this initialization of the lfsr
+ // sta lfsr_state
+ // sta lfsr_state+1
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 0)
+ SET_FIELD(piece_o, 3)
+ SET_FIELD(piece_x, 6)
+ PRINTNL
+ pha
+ jsr print_board
+ pla
+ lda #piece_x
+ jsr computer_perfect_ply
+ pha
+ PRINTNL
+ jsr print_board
+ pla
+ ;; Check for correct ply
+ GET_FIELD(main_board,2)
+ CHECK_ERROR(piece_x)
+ jsr getc
+ ;; Another Row/diagonal fork
+ jsr init_board
+ jsr computer_perfect_init
+ SET_FIELD(piece_x, 0)
+ SET_FIELD(piece_x, 3)
+ SET_FIELD(piece_o, 6)
+ SET_FIELD(piece_o, 7)
+ SET_FIELD(piece_x, 8)
+ pha
+ jsr print_board
+ pla
+ PRINTNL
+ lda #piece_o
+ jsr computer_perfect_ply
+ pha
+ jsr print_board
+ pla
+ ;; Check for correct ply
+ GET_FIELD(main_board,4)
+ CHECK_ERROR(piece_o)
+ jsr getc
+ rts
+ .)
+
+test_block_fork:
+ .(
+ jsr computer_perfect_init
+ STORE_WORD(main_board,board_ptr)
+ SET_FIELD(piece_x, 0)
+ SET_FIELD(piece_o, 3)
+ SET_FIELD(piece_x, 4)
+ SET_FIELD(piece_o, 8)
+ PRINTNL
+ pha
+ jsr print_board
+ pla
+ lda #piece_o
+ jsr computer_perfect_ply
+ pha
+ PRINTNL
+ jsr print_board
+ pla
+ ;; Check for correct ply
+ GET_FIELD(main_board,1)
+ CHECK_ERROR(piece_o)
+ jsr getc
+ ;; Check if computer creates
+ ;; two-in-a-row/column/diagonal
+ ;; when when a fork by the opponet is
+ ;; possible.
+ ;; The following scenario
+ ;; can be created by the plys
+ ;; X -> 5
+ ;; O -> 1
+ ;; X -> 9
+ jsr computer_perfect_init
+ STORE_WORD(main_board,board_ptr)
+ SET_FIELD(piece_o, 0)
+ SET_FIELD(piece_x, 4)
+ SET_FIELD(piece_x, 8)
+ PRINTNL
+ pha
+ jsr print_board
+ pla
+ lda #piece_o
+ jsr computer_perfect_ply
+ pha
+ PRINTNL
+ jsr print_board
+ pla
+ ;; Check for correct ply
+ GET_FIELD(main_board,1)
+ CHECK_ERROR(piece_o)
+ jsr getc
+ ;; The following scenario
+ ;; can be created by the plys
+ ;; X -> 1
+ ;; O -> 5
+ ;; X -> 9
+ jsr computer_perfect_init
+ STORE_WORD(main_board,board_ptr)
+ SET_FIELD(piece_x, 0)
+ SET_FIELD(piece_o, 4)
+ SET_FIELD(piece_x, 8)
+ PRINTNL
+ pha
+ jsr print_board
+ pla
+ lda #piece_o
+ jsr computer_perfect_ply
+ pha
+ PRINTNL
+ jsr print_board
+ pla
+ ;; Check for correct ply
+ GET_FIELD(main_board,3)
+ CHECK_ERROR(piece_o)
+ jsr getc
+ rts
+ ;; The following scenario
+ ;; can be created by the plys
+ ;; X -> 5
+ ;; O -> 1
+ ;; X -> 9
+ jsr computer_perfect_init
+ STORE_WORD(main_board,board_ptr)
+ SET_FIELD(piece_x, 4)
+ SET_FIELD(piece_o, 0)
+ SET_FIELD(piece_x, 8)
+ PRINTNL
+ pha
+ jsr print_board
+ pla
+ lda #piece_o
+ jsr computer_perfect_ply
+ pha
+ PRINTNL
+ jsr print_board
+ pla
+ ;; Check for correct ply
+ GET_FIELD(main_board,2)
+ CHECK_ERROR(piece_o)
+ jsr getc
+ rts
+ .)
+
+test_play_opposite_corner:
+ .(
+ jsr computer_perfect_init
+ STORE_WORD(main_board,board_ptr)
+ SET_FIELD(piece_x, 0)
+ SET_FIELD(piece_o, 4)
+ PRINTNL
+ pha
+ jsr print_board
+ pla
+ lda #piece_o
+ jsr computer_perfect_ply
+ pha
+ PRINTNL
+ jsr print_board
+ pla
+ ;; Check for correct ply
+ GET_FIELD(main_board,8)
+ CHECK_ERROR(piece_o)
+ jsr getc
+ rts
+ .)
+
+test_play_empty_corner:
+ .(
+ jsr computer_perfect_init
+ STORE_WORD(main_board,board_ptr)
+ SET_FIELD(piece_x, 4)
+ SET_FIELD(piece_o, 0)
+ PRINTNL
+ pha
+ jsr print_board
+ pla
+ lda #piece_o
+ jsr computer_perfect_ply
+ pha
+ PRINTNL
+ jsr print_board
+ pla
+ ;; Check for correct ply
+ GET_FIELD(main_board,2)
+ CHECK_ERROR(piece_o)
+ jsr getc
+ rts
+ .)
+
+test_perfect_vs_random_computer_player:
+ .(
+game_loop:
+ ;; Set player X
+ STORE_WORD(computer_perfect_init, player_x_init_ptr)
+ STORE_WORD(computer_perfect_ply, player_x_ply_ptr)
+ ;; Set player O
+ STORE_WORD(computer_random_init, player_o_init_ptr)
+ STORE_WORD(computer_random_ply, player_o_ply_ptr)
+ jsr play_game
+ jsr get_game_state
+ cmp #piece_o ; Random player
+ bne game_loop ; Should never win
+ PRINTSNL('Error')
+error:
+ jmp error
+ .)
+test_random_vs_perfect_computer_player:
+ .(
+game_loop:
+ ;; Set player X
+ STORE_WORD(computer_random_init, player_x_init_ptr)
+ STORE_WORD(computer_random_ply, player_x_ply_ptr)
+ ;; Set player O
+ STORE_WORD(computer_perfect_init, player_o_init_ptr)
+ STORE_WORD(computer_perfect_ply, player_o_ply_ptr)
+ jsr play_game
+ jsr get_game_state
+ cmp #piece_x ; Random player
+ bne game_loop ; Should never win
+ PRINTSNL('Error')
+error:
+ jmp error
+ .)
+test_perfect_vs_perfect_computer_player:
+ .(
+game_loop:
+ ;; Set player X
+ STORE_WORD(computer_perfect_init, player_x_init_ptr)
+ STORE_WORD(computer_perfect_ply, player_x_ply_ptr)
+ ;; Set player O
+ STORE_WORD(computer_perfect_init, player_o_init_ptr)
+ STORE_WORD(computer_perfect_ply, player_o_ply_ptr)
+ jsr play_game
+ jsr get_game_state
+ cmp #piece_none ; All games should end in
+ beq game_loop ; a draw.
+ PRINTSNL('Error')
+error:
+ jmp error
+ .)
+
+print_random_ply:
+ .(
+ ;; Debug output - Computer ply
+ pha
+ phx
+ clc
+ adc #'0'
+ jsr putc
+ PRINTS(' plays ')
+ pla
+ pha
+ adc #'0'
+ jsr putc
+ PRINTNL
+ plx
+ pla
+ rts
+ .)
+
+print_ply:
+ .(
+ ;; Debug output - Computer ply
+ pha
+ phy
+ phx
+ clc
+ adc #'0'
+ jsr putc
+ PRINTS(' plays ')
+ pla
+ pha
+ adc #'0'
+ jsr putc
+ lda #'/'
+ jsr putc
+ plx
+ pla
+ pha
+ phx
+ adc #'0'
+ jsr putc
+ PRINTNL
+ plx
+ ply
+ pla
+ rts
+ .)
+
diff --git a/sw/ttt/human_player.s b/sw/ttt/human_player.s
@@ -0,0 +1,53 @@
+;;; No initialization necessary
+human_player_init:
+ rts
+
+;;; Ask human player for his/her next
+;;; move. A contains the piece_x or
+;;; piece_o, depending which
+;;; piece the human plays
+human_player_ply:
+ .(
+ ;; Print board
+ pha
+ jsr print_board
+ ;; Print question for move
+ PRINTS("Player ")
+ pla
+ pha
+ clc
+ adc #'0'
+ jsr putc
+ PRINTS(": ")
+ ;; Get move and check
+ ;; if move is valid.
+ jsr getc
+ jsr putc
+ ;; Check if user input
+ ;; is in range [1..9]
+ cmp #"1"
+ bcc invalid
+ cmp #":" ; Follows 9 in ASCII table
+ bcs invalid
+ ;; Check if field is already
+ ;; occuped
+ sec
+ sbc #"1"
+ sta tmp ; Field number
+ tax
+ jsr get_field
+ cmp #piece_none
+ bne invalid
+ PRINTNL
+ PRINTNL
+ ;; Set the piece
+ ldx tmp ; Field number
+ pla ; Piece
+ jsr set_field
+ rts
+invalid:
+ PRINTNL
+ PRINTSNL("Not a valid move.")
+ pla
+ jmp human_player_ply
+ .)
diff --git a/sw/ttt/ttt.s b/sw/ttt/ttt.s
@@ -0,0 +1,159 @@
+#include "../../roms/boot/liba.h"
+
+;;; Variables
+ ;; This temporary variable is used all over the place
+ tmp = $30
+ ;; Used by win_first_diagonal and win_first_diagonal
+ empty_field = $3e
+ ;; Used to check for forking opportunities
+ fork_board_rows = $4006
+ fork_board_columns = $4009
+ fork_board_diagonals = $400c
+ ;; Used to pass location of board
+ ;; to subroutines.
+ board_ptr = $32
+ ;; Sometimes we copy stuff from one board
+ ;; to the other. For this we have to
+ ;; point to the other board.
+ other_board_ptr = $34
+ ;; Default board location in memory
+ main_board = $4000
+ ;; Mirrored board location in memory
+ board_mirrored = $4003
+ ;; Pointer to init subroutine of
+ ;; first player (2 bytes)
+ player_x_init_ptr = $36
+ ;; Pointer to ply subroutine of
+ ;; first player (2 bytes)
+ player_x_ply_ptr = $38
+ ;; Pointer to init subroutine of
+ ;; second player (2 bytes)
+ player_o_init_ptr = $3a
+ ;; Pointer to ply subroutine of
+ ;; first player (2 bytes)
+ player_o_ply_ptr = $3c
+ ;; Bord rendered as ASCII art
+ board_ascii = $5000
+
+
+#ifdef SYMON
+ rom_start = $c000
+#else
+ rom_start = $e000
+#endif
+
+#ifdef BOOT
+ ;; Program to be backed into
+ ;; boot ROM
+ * = rom_start + $0c00
+#else
+ ;; Program to be uploaded to
+ ;; RAM
+ * = $0300
+#endif
+
+start_ttt:
+ .(
+ cld
+ jsr init_acia
+ jsr lfsr_init
+#ifdef RUN_TESTS
+ jsr run_tests
+#endif
+game_loop:
+ PRINTSNL('** Tic-Tac-Toe **')
+ PRINTNL
+ lda #piece_x
+ jsr choose_player
+ lda #piece_o
+ jsr choose_player
+ jsr play_game
+ jmp game_loop
+ .)
+
+
+choose_player:
+ .(
+ pha
+ PRINTS("Choose player ")
+ pla
+ pha
+ clc
+ adc #'0'
+ jsr putc
+ PRINTSNL(':')
+ PRINTSNL('1 - Human')
+ PRINTSNL('2 - Computer (perfect)')
+ PRINTSNL('3 - Computer (random)')
+ jsr getc_seed_rng
+ cmp #'1'
+ beq set_human_player
+ cmp #'2'
+ beq set_computer_perfect_player
+ cmp #'3'
+ beq set_computer_random_player
+ pla
+ jmp choose_player
+ ;; Board is not initialized at
+ ;; this point. Therefore we can use
+ ;; board_ptr to store a temporary
+ ;; variable.
+set_human_player:
+ STORE_WORD(human_player_init, tmp)
+ STORE_WORD(human_player_ply, board_ptr)
+ jmp set_player
+set_computer_perfect_player:
+ STORE_WORD(computer_perfect_init, tmp)
+ STORE_WORD(computer_perfect_ply, board_ptr)
+ jmp set_player
+set_computer_random_player:
+ STORE_WORD(computer_random_init, tmp)
+ STORE_WORD(computer_random_ply, board_ptr)
+set_player:
+ pla
+ cmp #piece_x
+ bne set_second_player
+ lda tmp
+ sta player_x_init_ptr
+ lda tmp+1
+ sta player_x_init_ptr+1
+ lda board_ptr
+ sta player_x_ply_ptr
+ lda board_ptr+1
+ sta player_x_ply_ptr+1
+ rts
+set_second_player:
+ lda tmp
+ sta player_o_init_ptr
+ lda tmp+1
+ sta player_o_init_ptr+1
+ lda board_ptr
+ sta player_o_ply_ptr
+ lda board_ptr+1
+ sta player_o_ply_ptr+1
+ rts
+ .)
+
+
+
+
+
+#include "board.s"
+#include "human_player.s"
+#include "computer_player.s"
+
+#ifdef RUN_TESTS
+#include "board_test.s"
+#include "computer_player_test.s"
+run_tests:
+ // jsr game_board_test
+ // PRINTNL
+ // jsr getc
+ // jsr mirror_board_test
+ jsr computer_player_test
+ PRINTNL
+ jsr getc
+ jmp run_tests
+#endif
+
+
