; Zero-page registers

r0 = $fb ; a pointer

c4Player     = $07
c4GameState  = $08 ; and $09
c4Depth      = $0a
c4Level      = $0b
c4BestIndex  = $0c
c4BestWorst  = $0d
c4Goodness   = $0e
c4Alpha      = $0f
c4Beta       = $10
c4MaxAB      = $11
c4Best       = $12
c4Temp1      = $13
c4Temp2      = $14
c4Temp3      = $15
c4Temp4      = $16
c4Temp5      = $17
c4Temp6      = $18

; Game state offsets

c4BoardOffset      = 0 ; assumed
c4ScoreArrayOffset = 48
c4ScoresOffset     = 186
c4WinnerOffset     = 188
c4TopPiecesOffset  = 189

c4StateSize        = 189

; Other constants

c4None            = $ff
c4HighestGoodness = $7f
c4LowestGoodness  = $81

; Kernal routines

chrOut = $ffd2
getIn  = $ffe4

; Start of program

* = 2049
.obj "0:connect4"

    .byte 74, 8  ; end of BASIC program
    .byte 0, 0   ; line number
    .byte $9e    ; SYS
    .asc "2124:"
    .byte $8f    ; REM
    .byte $22    ; quote
  c4IntroText = *
    .byte 147    ; clear screen
    .byte 13+128
    .byte 9, 14  ; switch to lower case
    .asc "Connect 4"
    .byte 13+128, 13+128
    .asc "by Keith Pomakis"
    .byte 13+128
    .asc "pomakis@pobox.com"
    .byte 13+128
    .asc "May, 1997"
    .byte 13+128
    .byte 0, 0, 0

    ldx #19
  - lda $06,x
    sta c4ZeroPageSave-1,x
    dex
    bne -

    lda #<c4IntroText
    sta r0
    lda #>c4IntroText
    sta r0+1
    jsr printStr

    jsr c4PlayGame

    ldx #19
  - lda c4ZeroPageSave-1,x
    sta $06,x
    dex
    bne -
    rts


getNum = *
    ; Gets a single digit between 0 and
    ; 7 from the keyboard.  'q' returns
    ; 0 as well.

    ; Input: r0     - pointer to prompt
    ; Retrn: .Y     - the number
    ; Ruins: .A

    jsr printStr

  - jsr getIn
    cmp #0
    beq -

    cmp #"q"
    bne +
    jsr chrOut
    ldy #0
    beq ++ ; always true

  + cmp #"0"
    bmi ++
    cmp #"8"
    bpl ++
    pha
    jsr chrOut
    pla
    sec
    sbc #"0"
    tay

  + jsr printCR
    jmp printCR ; jsr/rts

  + ldy 53280
    lda #2
    sta 53280
    lda $a2 ; low byte of jiffy clock
    clc
    adc #4
  - cmp $a2
    bne -
    sty 53280
    beq -- ; always true


printStr = *
    ; Prints a null-terminated string.

    ; Input: r0   - pointer to string
    ; Retrn: .Y   - length of string

    pha

    ldy #0
  - lda (r0),y
    beq +
    jsr chrOut
    iny
    bne - ; always true

  + pla
    rts


printCR = *
    ; Prints a carraige return.
    ; Ruins: .A

    lda #13
    jmp chrOut ; jsr/rts

;----------------------------------------------------------------------------

c4PlayGame = *

    jsr c4NewGame

    lda #<c4PlayGameLevelStr
    sta r0
    lda #>c4PlayGameLevelStr
    sta r0+1
    jsr getNum
    cpy #0
    bne +
    rts

  + sty c4Level
    lda #0
    sta c4Player

  - jsr c4PrintBoard
    
    ldy #c4WinnerOffset
    lda (c4GameState),y
    cmp #c4None
    beq +
    lda #<c4PlayGame1WinStr
    sta r0
    lda #>c4PlayGame1WinStr
    sta r0+1
    jsr printStr
    jmp c4PlayGame

  + ldy #c4TopPiecesOffset
    lda (c4GameState),y
    cmp #7
    bne +
    rts

  / ldy c4Player
    lda c4PlayGameTable,y
    sta c4PlayGameMovePieceChar
    lda #<c4PlayGameMoveStr
    sta r0
    lda #>c4PlayGameMoveStr
    sta r0+1
    jsr getNum
    cpy #0
    beq c4PlayGame ; always true

    dey
    jsr c4DropPiece
    bcs -

    jsr c4PrintBoard
    jsr printCR

    ldy #c4WinnerOffset
    lda (c4GameState),y
    cmp #c4None
    beq +
    lda #<c4PlayGame0WinStr
    sta r0
    lda #>c4PlayGame0WinStr
    sta r0+1
    jsr printStr
    jmp c4PlayGame

  + ldy #c4TopPiecesOffset
    lda (c4GameState),y
    cmp #7
    bne +
    lda #<c4PlayGameTieStr
    sta r0
    lda #>c4PlayGameTieStr
    sta r0+1
    jsr printStr
    jmp c4PlayGame

  + lda c4Player
    eor #$01
    sta c4Player

    lda #<c4PlayGameThinkingStr
    sta r0
    lda #>c4PlayGameThinkingStr
    sta r0+1
    jsr printStr

    jsr c4AutoMove

    jsr printCR
    jsr printCR

    lda c4Player
    eor #$01
    sta c4Player

    jmp --

  c4PlayGameTable = *
    .asc "XO"

  c4PlayGameLevelStr = *
    .byte 13
    .asc "Level? "
    .byte 0

  c4PlayGameMoveStr = *
    .byte 13
    .asc "Move "
  c4PlayGameMovePieceChar = *
    .asc " ? "
    .byte 0

  c4PlayGameThinkingStr = *
    .asc "Thinking"
    .byte 0

  c4PlayGameTieStr = *
    .byte 13
    .asc "Tie!"
    .byte 13, 0

  c4PlayGame0WinStr = *
    .byte 13
    .asc "You win!"
    .byte 13, 0

  c4PlayGame1WinStr = *
    .byte 13
    .asc "I win!"
    .byte 13, 0


c4PrintBoard = *
    ; Ruins: .A, .Y, R0

    ldy #40
  - lda (c4GameState),y
    bne +
    lda #"X"
    bne +++ ; always true
  + cmp #1
    bne +
    lda #"O"
    bne ++  ; always true
  + lda #"."

  + jsr chrOut
    iny
    tya
    and #$07
    cmp #$07
    bne -
    jsr printCR
    cpy #$07
    beq +
    tya
    sec
    sbc #15
    tay
    jmp -

  + lda #<c4PrintBoardStr
    sta r0
    lda #>c4PrintBoardStr
    sta r0+1
    jmp printStr ; jsr/rts

  c4PrintBoardStr = *
    .asc "1234567"
    .byte 13, 0


c4NewGame = *
    ; Retrn: .A   - 0
    ; Ruins: .Y

    ; Set up the "real" game state.
    ; Make sure it starts at a page
    ; boundary.
    ldx #0
    stx c4GameState
    ldx #>c4EndOfProgram
    inx
    stx c4GameState+1

    lda #c4None
    ldy #47
  - sta (c4GameState),y
    dey
    bpl -

    lda #1
    ldy #c4ScoreArrayOffset
  - sta (c4GameState),y
    iny
    cpy #c4ScoreArrayOffset+138
    bne -

    lda #69
    ldy #c4ScoresOffset
    sta (c4GameState),y
    iny
    sta (c4GameState),y

    lda #c4None
    ldy #c4WinnerOffset
    sta (c4GameState),y

    lda #0
    ldy #c4TopPiecesOffset
    sta (c4GameState),y
    sta c4Depth

    rts


c4DropPieceSpecial = *
    ; Input: .Y   - c4DropOrder index of column to drop into
    ; Retrn: .C   - 0 success, 1 failure
    ; Ruins: .A, .X, .Y, R0, c4Temp1
    ;        c4Temp2, c4Temp3, c4Temp4

    tya
    tax
    ldy c4DropOrder,x
    ; Fall through to c4DropPiece.


c4DropPiece = *
    ; Input: .Y   - column to drop into
    ; Retrn: .C   - 0 success, 1 failure
    ; Ruins: .A, .X, .Y, R0, c4Temp1
    ;        c4Temp2, c4Temp3, c4Temp4

  - lda (c4GameState),y
    cmp #c4None
    beq +

    tya
    clc
    adc #8
    tay
    cpy #48
    bmi -

    sec
    rts

  + lda c4Player
    sta (c4GameState),y

    ; Keep track of the number of
    ; pieces on the top row of the
    ; board so a tie can be spotted.
    cpy #40
    bmi +
    sty c4Temp1
    ldy #c4TopPiecesOffset
    lda (c4GameState),y
    clc
    adc #1
    sta (c4GameState),y
    ldy c4Temp1

  + tya
    jsr c4UpdateScore
    clc
    rts


c4UpdateScore = *
    ; Input: c4Player - player (0 or 1)
    ;        .A   - index of new piece
    ;               (x*8 + y)
    ; Ruins: .A, .X, .Y, R0, c4Temp1,
    ;        c4Temp2, c4Temp3, c4Temp4

    c4ScoreDiffOfThisPlayer  = c4Temp3
    c4ScoreDiffOfOtherPlayer = c4Temp4

    ; Calculate the index of the proper
    ; array of score array indexes.
    ; i.e., one of c4Map00, c4Map01, ...

    asl
    tay
    lda c4Map,y
    sta c4ProperMap
    lda c4Map+1,y
    sta c4ProperMap+1

    lda #0
    sta c4ScoreDiffOfThisPlayer
    sta c4ScoreDiffOfOtherPlayer

    ; Loop through each of the score
    ; units in the indexed array.
    ldx #0
  c4ProperMap = *+1
  - lda $ffff,x
    cmp #c4None
    bne ++

    ; We're done.  Update the scores.
    lda c4Player
    beq +
    ldy #c4ScoresOffset
    lda (c4GameState),y
    clc
    adc c4ScoreDiffOfOtherPlayer
    sta (c4GameState),y
    iny
    lda (c4GameState),y
    clc
    adc c4ScoreDiffOfThisPlayer
    sta (c4GameState),y
    rts

  + ldy #c4ScoresOffset
    lda (c4GameState),y
    clc
    adc c4ScoreDiffOfThisPlayer
    sta (c4GameState),y
    iny
    lda (c4GameState),y
    clc
    adc c4ScoreDiffOfOtherPlayer
    sta (c4GameState),y

    rts

  + clc
    adc #c4ScoreArrayOffset

    ; .A now contains the index of the
    ; proper score unit of player 0.

    ; Double the score unit of the
    ; current player.
    sta c4Temp1
    ldy #0
    cpy c4Player
    beq +
    clc
    adc #69
  + tay
    lda (c4GameState),y
    sta c4Temp2
    asl
    sta (c4GameState),y

    ; Is this a winning move?
    cmp #16
    bne +
    lda c4Player
    ldy #c4WinnerOffset
    sta (c4GameState),y
    lda #16

  + sec
    sbc c4Temp2
    clc
    adc c4ScoreDiffOfThisPlayer
    sta c4ScoreDiffOfThisPlayer

    ; Zero the score unit of the other
    ; player.
    lda c4Temp1
    ldy #1
    cpy c4Player
    beq +
    clc
    adc #69
  + tay
    lda c4ScoreDiffOfOtherPlayer
    sec
    sbc (c4GameState),y
    sta c4ScoreDiffOfOtherPlayer
    lda #0
    sta (c4GameState),y

    inx
    bne - ; always true


c4GoodnessOfCurrentPlayer = *
    ; Calculates the "goodness" of the
    ; current board relative to the
    ; current player.  This amounts to
    ; score(player)-score(other(player)).

    ; Retrn: .A   - goodness
    ;        .Y   - current player

    ldy #c4ScoresOffset
    lda (c4GameState),y
    iny
    sec
    sbc (c4GameState),y
    ldy c4Player
    beq +
    eor #$ff
    clc
    adc #1
  + rts


c4PushState = *
    ; Ruins: .A, .X

    ldx c4GameState+1
    stx c4OldStateAddr1
    stx c4OldStateAddr2
    inx
    stx c4NewStateAddr1
    stx c4NewStateAddr2
    stx c4GameState+1

    ldx #c4StateSize
  c4OldStateAddr1 = *+2
  - lda $ff00,x
  c4NewStateAddr1 = *+2
    sta $ff00,x
    dex
    bne -

  c4OldStateAddr2 = *+2
    lda $ff00,x
  c4NewStateAddr2 = *+2
    sta $ff00,x

    inc c4Depth
    rts


c4PollFn = *
    ; Protect .Y!

    lda #"."
    jmp chrOut ; jsr/rts


c4AutoMove = *
    ; Retrn: c4BestIndex
    ;            - c4DropOrder index of column dropped into

    lda #c4LowestGoodness
    sta c4BestWorst
    lda #c4None
    sta c4BestIndex
    ldy c4GameState+1
    iny
    sty c4GameStatePage
    lda #0
    sta c4Goodness

    ldy #0
  - jsr c4PushState
    jsr c4PollFn

  - sty c4Temp5
    jsr c4DropPieceSpecial
    ldy c4Temp5
    bcc +
    iny
    cpy #7
    bne -
    dec c4Depth ; pop state
    dec c4GameState+1
    bne c4AutoMoveFinish ; always true

    ; We have just dropped a piece
    ; into column .Y

  + lda c4Player
    ldx #c4WinnerOffset
  c4GameStatePage = *+2
    cmp $ff00,x
    bne +
    lda #c4HighestGoodness
    sta c4Goodness
    bne ++ ; always true

    ; Call c4Evaluate
  + lda #c4LowestGoodness
    sta c4Alpha
    lda #0
    sec
    sbc c4BestWorst
    sta c4Beta
    sty c4Temp5
    jsr c4Evaluate
    ldy c4Temp5

  + lda c4Goodness
    sec
    sbc c4BestWorst
    bne +

    ; Make a random decision
    lda $a2 ; low byte of jiffy clock
    ror
    bcc c4AutoMoveContinue
    bcs +++

  + bmi +
    bvs c4AutoMoveContinue
    bvc ++
  + bvc c4AutoMoveContinue
  + lda c4Goodness
    sta c4BestWorst
    sty c4BestIndex

  c4AutoMoveContinue = *
    dec c4Depth ; pop state
    dec c4GameState+1
    iny
    cpy #7
    bne --

  c4AutoMoveFinish = *
    ldy c4BestIndex
    cpy #c4None
    beq +
    jmp c4DropPieceSpecial ; jsr/rts
  + rts


c4Evaluate = *

    lda c4Level
    cmp c4Depth
    bne +
    jsr c4GoodnessOfCurrentPlayer
    sta c4Goodness
    rts

  + lda #c4LowestGoodness
    sta c4Best
    lda c4Alpha
    sta c4MaxAB

    ldy #0
    sty c4Temp6
    lda c4Player
    eor #1
    sta c4Player

  - jsr c4PushState
    jsr c4DropPieceSpecial
    bcc +
    dec c4Depth ; pop state
    dec c4GameState+1
    jmp c4EvaluateContinue2

  + ldy #c4WinnerOffset
    lda (c4GameState),y
    cmp #c4None
    beq +

    lda #c4HighestGoodness
    sec
    sbc c4Depth
    sta c4Goodness
    bne ++ ; always true

    ; Recurse
  + lda c4Best
    pha
    lda c4MaxAB
    pha 
    lda c4Temp6
    pha
    lda c4Alpha
    pha
    lda c4Beta
    pha

    lda #0
    sec
    sbc c4Beta
    sta c4Alpha
    lda #0
    sec
    sbc c4MaxAB
    sta c4Beta

    jsr c4Evaluate

    pla
    sta c4Beta
    pla
    sta c4Alpha
    pla
    sta c4Temp6
    pla
    sta c4MaxAB
    pla
    sta c4Best

  + lda c4Goodness
    sec
    sbc c4Best
    bmi +
    bvs c4EvaluateContinue1
    bvc ++
  + bvc c4EvaluateContinue1
  + beq c4EvaluateContinue1

    lda c4Goodness
    sta c4Best

    lda c4Best
    sec
    sbc c4MaxAB
    bmi +
    bvs c4EvaluateContinue1
    bvc ++
  + bvc c4EvaluateContinue1
  + beq c4EvaluateContinue1

    lda c4Best
    sta c4MaxAB

  c4EvaluateContinue1 = *
    dec c4Depth ; pop state
    dec c4GameState+1
    lda c4Beta
    sec
    sbc c4Best
    bmi +
    bvs ++
    bvc c4EvaluateContinue2
  + bvc +

  c4EvaluateContinue2 = *
    inc c4Temp6
    ldy c4Temp6
    cpy #7
    beq +
    jmp -

  + lda c4Player
    eor #1
    sta c4Player
    lda #0
    sec
    sbc c4Best
    sta c4Goodness
    rts

c4Map = *
    .word c4Map00, c4Map01, c4Map02, c4Map03, c4Map04, c4Map05, c4Map06, 0
    .word c4Map10, c4Map11, c4Map12, c4Map13, c4Map14, c4Map15, c4Map16, 0
    .word c4Map20, c4Map21, c4Map22, c4Map23, c4Map24, c4Map25, c4Map26, 0
    .word c4Map30, c4Map31, c4Map32, c4Map33, c4Map34, c4Map35, c4Map36, 0
    .word c4Map40, c4Map41, c4Map42, c4Map43, c4Map44, c4Map45, c4Map46, 0
    .word c4Map50, c4Map51, c4Map52, c4Map53, c4Map54, c4Map55, c4Map56

c4Map00 .byte 03, 24, 45, c4None
c4Map01 .byte 03, 02, 27, 48, c4None
c4Map02 .byte 03, 02, 04, 30, 51, c4None
c4DropOrder = *
; This is an evil thing to do, but it saves 7 bytes!
; I've organized the map so that c4Map03 is overloaded to represent the
; order in which the computer tries dropping pieces.
c4Map03 .byte 03, 02, 04, 01, 05, 00, 06, c4None
c4Map04 .byte 02, 04, 01, 36, 60, c4None
c4Map05 .byte 04, 01, 39, 63, c4None
c4Map06 .byte 01, 42, 66, c4None

c4Map10 .byte 33, 24, 25, 46, c4None
c4Map11 .byte 33, 54, 27, 28, 45, 49, c4None
c4Map12 .byte 33, 54, 57, 30, 31, 48, 52, 06, c4None
c4Map13 .byte 33, 54, 57, 07, 05, 34, 51, 55, 58, 60, c4None
c4Map14 .byte 54, 57, 07, 36, 37, 00, 61, 63, c4None
c4Map15 .byte 57, 07, 39, 40, 64, 66, c4None
c4Map16 .byte 07, 42, 43, 67, c4None

c4Map20 .byte 08, 24, 25, 26, 47, c4None
c4Map21 .byte 08, 09, 27, 28, 29, 46, 50, 06, c4None
c4Map22 .byte 08, 09, 10, 30, 31, 32, 45, 49, 53, 58, 60, c4None
c4Map23 .byte 08, 09, 10, 11, 05, 34, 35, 48, 52, 56, 59, 61, 63, c4None
c4Map24 .byte 09, 10, 11, 36, 37, 38, 51, 55, 62, 64, 66, c4None
c4Map25 .byte 10, 11, 39, 40, 41, 00, 65, 67, c4None
c4Map26 .byte 11, 42, 43, 44, 68, c4None

c4Map30 .byte 12, 24, 25, 26, 06, c4None
c4Map31 .byte 12, 13, 27, 28, 29, 47, 58, 60, c4None
c4Map32 .byte 12, 13, 14, 30, 31, 32, 46, 50, 59, 61, 63, c4None
c4Map33 .byte 12, 13, 14, 15, 05, 34, 35, 45, 49, 53, 62, 64, 66, c4None
c4Map34 .byte 13, 14, 15, 36, 37, 38, 48, 52, 56, 65, 67, c4None
c4Map35 .byte 14, 15, 39, 40, 41, 51, 55, 68, c4None
c4Map36 .byte 15, 42, 43, 44, 00, c4None

c4Map40 .byte 16, 25, 26, 58, c4None
c4Map41 .byte 16, 17, 28, 29, 59, 61, c4None
c4Map42 .byte 16, 17, 18, 31, 32, 47, 62, 64, c4None
c4Map43 .byte 16, 17, 18, 19, 34, 35, 46, 50, 65, 67, c4None
c4Map44 .byte 17, 18, 19, 37, 38, 49, 53, 68, c4None
c4Map45 .byte 18, 19, 40, 41, 52, 56, c4None
c4Map46 .byte 19, 43, 44, 55, c4None

c4Map50 .byte 20, 26, 59, c4None
c4Map51 .byte 20, 21, 29, 62, c4None
c4Map52 .byte 20, 21, 22, 32, 65, c4None
c4Map53 .byte 20, 21, 22, 23, 35, 47, 68, c4None
c4Map54 .byte 21, 22, 23, 38, 50, c4None
c4Map55 .byte 22, 23, 41, 53, c4None
c4Map56 .byte 23, 44, 56, c4None

c4ZeroPageSave = *

c4EndOfProgram = *+18
