Toledo Atomchess Game

The world's smallest chess program in x86 machine code, only 392 bytes!
By January 28, 2015 came to my knowledge a new chess program written in 487 bytes of x86 assembly code. I don't ever ran it and moved to another things as I was kind of busy.
Nevertheless my friends from JS1K and Twitter encouraged me to do something, and I've some notions of x86 machine code.
So I started coding my own chess program in x86 assembler, I finished it in 24 hours and went for another 24 hours debugging it.
After this I gave a look to the documentation of the other chess program and I was surprised it made illegal movements and doesn't even has a search tree, for me that is like not playing any chess.
My first version of Toledo Atomchess was 481 bytes of x86 assembly code and it plays very reasonably under the limitations, recently I've saw chances for optimization and made it in 456 bytes (Oct/07/2015), later in 446 bytes (Oct/10/2015) and finally 392 bytes (Mar/04/2016).

Further development

Recently I had some time to research the implementation of full chess moves, including player movement validation, castling, en passant and promotion (only to queen)
I called it Toledo Atomchess Reloaded, it requires 831 bytes of x86 machine code. Also includes a loader for the second sector of disk so is able to boot from a floppy disk.
While developing it, I've discovered a small bug that prevented Toledo Atomchess from moving its bishops in upwards diagonals and other smaller one and not so important about stack comparisons.
Later I changed syntax to nasm assembler per hellmood suggestion and uploaded it to Github for easier change tracking (also given I don't update very fast my website), here I optimized it further and got help from qkumba (Peter Ferrie) and theshich.
And now there is also Toledo Atomchess 6502 crunched in 1K ROM with graphical chessboard for Atari VCS/2600

How to run them

To run it you need a 1.44 MB floppy disk and put the 512 bytes into the boot sector using an utility like Rawrite.
The package also contains a COM file able to run in MS-DOS or Wind*ws command-line.
Also it can be run with DosBox or qemu (from Reddit coding)
qemu-system-x86_64 -hda toledo_atomchess_disk.bin

Toledo Atomchess source code

Here is the full source code for the 446 bytes Toledo Atomchess, for the most recent version check the Toledo Atomchess git.

        ;
        ; Toledo Atomchess
        ;
        ; by Óscar Toledo Gutiérrez
        ;
        ; © Copyright 2015 Óscar Toledo Gutiérrez
        ;
        ; Creation: Jan/28/2015 21:00 local time.
        ; Revision: Jan/29/2015 18:17 local time. Finished.
        ; Revision: Jan/30/2015 13:34 local time. Debugging finished.
        ; Revision. Jun/01/2015 10:08 local time. Solved bug where computer bishops never moved over upper diagonals.
        ; Revision: Oct/06/2015 06:38 local time. Optimized board setup/display, plus tiny bits.
        ; Revision: Oct/07/2015 14:47 local time. More optimization and debugged.
        ; Revision: Oct/10/2015 08:21 local time. More optimization.

        ; Features:
        ; * Computer plays legal basic chess movements ;)
        ; * Enter moves as algebraic form (D2D4) (note your moves aren't validated)
        ; * Search depth of 3-ply
        ; * No promotion of pawns.
        ; * No castling
        ; * No en passant.
        ; * 446 bytes size (fits in a boot sector)

        ; Note: I'm lazy enough to write my own assembler instead of
        ;       searching for one, so you will have to excuse my syntax ;)

        code16

        ; Change to org &0100 for COM file
        org &7c00

        ; Housekeeping
        mov sp,stack
        cld
        push cs
        push cs
        push cs
        pop ds
        pop es
        pop ss
        ; Create board
        mov di,board-8
        mov cx,&0108
sr1:    push di
        pop ax
        and al,&88      ; 0x88 board
        jz sr2
        mov al,&07      ; Frontier
sr2:    stosb
        loop sr1
        ; Setup board
        mov si,initial
        mov di,board
        mov cl,&08
sr3:    lodsb           ; Load piece
        stosb           ; Black pieces
        or al,8
        mov [di+&6f],al ; White pieces
        mov byte [di+&0f],&01 ; Black pawn
        mov byte [di+&5f],&09 ; White pawn
        loop sr3

        ;
        ; Main loop
        ;
sr21:   call display_board
        call key2
        push di
        call key2
        pop si
        call sr28
        call display_board
        mov ch,&08      ; Current turn (0=White, 8=Black)
        call play
        jmp short sr21

        ;
        ; Computer plays :)
        ;
play:   mov bp,-32768   ; Current score
        push cx         ; Current side
        push bp         ; Origin square
        push bp         ; Target square

        xor ch,8        ; Change side

        mov si,board
sr7:    lodsb           ; Read square
        xor al,ch       ; XOR with current playing side
        dec ax
        cmp al,6        ; Ignore if frontier or empty
        jnc sr6
        or al,al        ; Is it pawn?
        jnz sr8
        or ch,ch        ; Is it playing black?
        jnz sr25        ; No, jump
sr8:    inc ax
sr25:   dec si
        add al,&04
        mov dl,al       ; Total movements of piece in dl
        and dl,&0c
        mov bx,offsets-4
        xlat
        add al,displacement&255
        mov dh,al       ; Movements offset in dh
sr12:   mov di,si       ; Restart target square
        mov bl,dh
        mov cl,[bx]
sr9:    add di,cx
        and di,&ff
        or di,board
        mov al,[si]     ; Content of: origin in al, target in ah
        mov ah,[di]
        or ah,ah        ; Empty square?
        jz sr10
        xor ah,ch
        sub ah,&09      ; Valid capture?
        cmp ah,&06
        mov ah,[di]
        jnc sr18        ; No, avoid
        cmp dh,16+displacement&255       ; Pawn?
        jc sr19
        test cl,1       ; Straight?
        je sr17         ; Yes, avoid and cancels any double square movement
        jmp short sr19

sr10:   cmp dh,16+displacement&255       ; Pawn?
        jc sr19
        test cl,1       ; Diagonal?
        jne sr18        ; Yes, avoid

sr19:   push ax         ; Save for restoring in near future
        mov bl,scores&255
        mov al,ah
        and al,7
        cmp al,6        ; King eaten?
        jne sr20
        cmp sp,stack-(5+8+5)*2  ; If in first response...
        mov bp,20000    ; ...maximum score (probably checkmate/slatemate)
        je sr26
        mov bp,7811     ; Maximum score
sr26:   add sp,6        ; Ignore values
        pop cx          ; Restore side
        ret

sr20:   xlat
        cbw
;        cmp sp,stack-(5+8+5+8+5+8+5+8+5)*2  ; 4-ply depth
        cmp sp,stack-(5+8+5+8+5+8+5)*2  ; 3-ply depth
;        cmp sp,stack-(5+8+5+8+5)*2  ; 2-ply depth
;        cmp sp,stack-(5+8+5)*2  ; 1-ply depth
        jbe sr22
        pusha
        call sr28       ; Do move
        call play
        mov bx,sp
        sub [bx+14],bp  ; Substract BP from AX
        popa
sr22:   cmp bp,ax       ; Better score?
        jg sr23         ; No, jump
        xchg ax,bp      ; New best score
        jne sr23        ; Same score?
        in al,(&40)
        cmp al,&aa      ; Randomize it
sr23:   pop ax          ; Restore board
        mov [si],al
        mov [di],ah
        jg sr18
        add sp,4
        push si         ; Save movement
        push di

sr18:   dec ax
        and al,&07      ; Was it pawn?
        jz sr11         ; Yes, check special
        cmp al,&04      ; Knight or king?
        jnc sr14        ; End sequence, choose next movement
        or ah,ah        ; To empty square?
        jz sr9          ; Yes, follow line of squares
sr16:   jmp short sr14

sr11:   and cl,&1f      ; Advanced it first square?
        cmp cl,&10
        jnz sr14
        mov ax,si       ; Already checked for move to empty square
        sub al,&20
        cmp al,&40      ; At top or bottom firstmost row?
        jb sr17         ; No, cancel double-square movement
sr14:   inc dh
        dec dl
        jnz sr12
sr17:   inc si
sr6:    cmp si,board+120
        jne sr7
        pop di
        pop si
        pop cx
        cmp sp,stack-2
        jne sr24
        cmp bp,-16384   ; Illegal move? (always in check)
        jl sr24         ; Yes, doesn't move
sr28:   movsb           ; Do move
        mov byte [si-1],0       ; Clear origin square
sr24:   ret

        ; Display board
display_board:
        mov si,board-8
        mov cx,73       ; 1 frontier + 8 rows * (8 cols + 1 frontier)
sr4:    lodsb
        mov bx,chars
        xlat
        cmp al,&0d      ; Is it RC?
        jnz sr5         ; No, jump
        add si,7        ; Jump 7 frontier bytes
        call display    ; Display RC
        mov al,&0a      ; Now display LF
sr5:    call display
        loop sr4
        ret

        ; Read algebraic coordinate
key2:   call key        ; Read letter
        add ax,board+127 ; Calculate board column
        push ax
        call key        ; Read digit
        pop di
        shl al,4        ; Substract digit row multiplied by 16
        sub di,ax
        ret
key:
        mov ah,0        ; Read keyboard
        int &16         ; Call BIOS
display:
        pusha
        mov ah,&0e      ; Console output
        mov bh,&00
        int &10         ; Call BIOS
        popa
        and ax,&0f
        ret

initial:
        db 2,5,3,4,6,3,5,2
scores:
        db 0,10,50,30,90,30

chars:
        db ".prbqnk",&0d,".PRBQNK"

offsets:
        db 16,20,8,12,8,0,8
displacement:
        db -33,-31,-18,-14,14,18,31,33
        db -16,16,-1,1
        db 15,17,-15,-17
        db -15,-17,-16,-32
        db 15,17,16,32

        ; 64 bytes to say something
        db "Toledo Atomchess 10oct2015"
        db " (c)2015 Oscar Toledo G. "
        db "nanochess.org"

        ;
        ; This marker is required for BIOS to boot floppy disk
        ;
        ds &7dfe-*      ; Change to &02fe for COM file
        db &55,&aa

board:  ds 256

        ds 256
stack:
        end

Toledo Atomchess Reloaded source code

Here is the full source code for Toledo Atomchess Reloaded, including support for player movement validation, castling, en passant and promotion to queen:

        ;
        ; Toledo Atomchess reloaded
        ;
        ; by Óscar Toledo Gutiérrez
        ;
        ; © Copyright 2015 Óscar Toledo Gutiérrez
        ;
        ; Creation: 28-ene-2015 21:00 local time.
        ; Revision: 29-ene-2015 18:17 local time. Finished.
        ; Revision: 30-ene-2015 13:34 local time. Debugging finished.
        ; Revision: 26-may-2015. Checks for illegal moves. Handles promotion
        ;                        to queen, en passant and castling.
        ; Revision: 04-jun-2015. At last fully debugged.

        ; Features:
        ; * Full chess movements (except promotion only to queen)
        ; * Enter moves as algebraic form (D2D4) (your moves are validated)
        ; * Search depth of 3-ply
        ; * 831 bytes size (fits in two boot sectors)

        ; Note: I'm lazy enough to write my own assembler instead of
        ;       searching for one, so you will have to excuse my syntax ;)

        code16

        ; Search for "REPLACE" to find changes for COM file
        org &7c00       ; REPLACE with ORG &0100

        ; Housekeeping
        mov sp,stack
        cld
        push cs
        push cs
        push cs
        pop ds
        pop es
        pop ss
        ; Load second sector
sr0:    push ds
        push es
        mov ax,&0201
        mov bx,&7e00
        mov cx,&0002
        xor dx,dx
        int &13         ; REPLACE with NOP NOP
        pop es
        pop ds
        jb sr0
        ; Create board
        mov bx,board
sr1:    mov al,bl
        and al,&88      ; 0x88 board
        jz sr2
        mov al,&07      ; Frontier
sr2:    mov [bx],al
        inc bl
        jnz sr1
        ; Setup board
        mov si,initial
        mov [enp],si    ; Reset en passant state
sr3:    lodsb           ; Load piece
        mov [bx],al     ; Black pieces
        or al,8
        mov [bx+&70],al ; White pieces
        mov al,&11
        mov [bx+&10],al ; Black pawn
        mov al,&19
        mov [bx+&60],al ; White pawn
        inc bx
        cmp bl,&08
        jnz sr3

        ;
        ; Main loop
        ;
sr21:   call display_board
        call key2
        push di
        call key2
        pop si
        mov ch,&00      ; Current turn (0=White, 8=Black)
        call play_validate
        test ch,ch      ; Changed turn?
        je sr21         ; No, wasn't valid
        call display_board
        mov ch,&08      ; Current turn (0=White, 8=Black)
        dec byte [legal]
        mov word [depth],stack-(4+8+4+8+4+8+4)*2
        call play
        call play_validate
        jmp short sr21

        ;
        ; Computer plays :)
        ;
play_validate:
        mov byte [legal],1
        mov word [depth],stack-(4+8+4)*2
play:   mov bp,-32768   ; Current score
        push si         ; Origin square
        push di         ; Target square

        xor ch,8        ; Change side

        mov si,board
sr7:    lodsb           ; Read square
        xor al,ch       ; XOR with current playing side
        and al,&0f      ; Remove moved bit
        dec ax          ; Translate to 0-5
        cmp al,6        ; Is it frontier or empty square?
        jnc sr6         ; Yes, jump
        or al,al        ; Is it pawn?
        jnz sr8         ; No, jump
        or ch,ch        ; Is it playing black?
        jnz sr25        ; No, jump
sr8:    inc ax          ; Inverse direction for pawn
sr25:   dec si
        mov bx,offsets
        push ax
        xlat
        mov dh,al       ; Movements offset in dh
        pop ax
        add al,total-offsets
        xlat
        mov dl,al       ; Total movements of piece in dl
sr12:   mov di,si       ; Restart target square
        mov bx,displacement
        mov al,dh
        xlat
        mov cl,al       ; Current displacement offset in cl
sr9:    add di,cx
        and di,&ff
        or di,board
        mov al,[si]     ; Content of origin square in al
        mov ah,[di]     ; Content of target square in ah
        and ah,&0f      ; Empty square?
        jz sr10         ; Yes, jump
        xor ah,ch
        sub ah,&09      ; Is it a valid capture?
        cmp ah,&06
        mov ah,[di]
        jnc sr18        ; No, jump to avoid
        cmp dh,16       ; Moving pawn?
        jc sr19
        test cl,1       ; Straight advance?
        je sr18         ; Yes, avoid
        jmp short sr19

sr10:   cmp dh,16       ; Moving pawn?
        jc sr19         ; No, jump
        test cl,1       ; Diagonal?
        je sr19         ; No, jump
        mov bx,si
        dec bx
        test cl,2       ; Going left?
        jne sr29
        inc bx
        inc bx
sr29:   cmp bx,[enp]    ; Is it a valid en passant?
        jne sr18        ; No, avoid

sr19:   push ax         ; Save origin and target square in stack
        mov al,ah
        and al,7
        cmp al,6        ; King eaten?
        jne sr20
        cmp sp,stack-(4+8+4)*2  ; If in first response...
        mov bp,20000    ; ...maximum score (probably checkmate/slatemate)
        je sr26
        mov bp,7811     ; Maximum score
sr26:   add sp,6        ; Ignore values
        jmp sr24

sr20:   mov bx,scores
        xlat
        cbw             ; ax = score for capture (guarantees ah = 0)
        mov bx,[enp]    ; bx = current pawn available for en passant
        cmp sp,[depth]
        jbe sr22
        pusha
        mov [enp],ax    ; En passant not possible
        mov al,[si]     ; Read origin square
        and al,&0f      ; Clear bit 4 (marks piece moved)
        cmp al,&0e      ; Is it a king?
        je sr36
        cmp al,&06
        jne sr37        ; No, jump
sr36:   mov bx,si
        sub bx,di
        mov bh,ch       ; Create moved rook
        xor bh,&02      ;
        cmp bl,2        ; Is it castling to left?
        jne sr38        ; No, jump
        mov [di+1],bh   ; Put it along king
        mov [di-2],ah
        jmp sr37

sr38:   cmp bl,-2       ; Is it castling to right?
        jne sr37
        mov [di-1],bh   ; Put it along king
        mov [di+1],ah
sr37:
        cmp al,&09      ; We have a pawn?
        je sr31
        cmp al,&01
        jne sr30        ; No, jump
sr31:   mov bp,sp
        mov bx,di
        cmp bl,&10      ; Going to uppermost row?
        jc sr32         ; Yes, jump
        cmp bl,&70      ; Going to lowermost row?
        jc sr33         ; No, jump
sr32:   xor al,&05      ; Promote to queen
        add word [bp+14],90     ; Add points for queen
sr33:   sub bx,si
        call en_passant_test
        jnc sr41
        mov [bx],ah     ; Clean en passant square
        add word [bp+14],10     ; Add points for pawn
        jmp sr30

sr41:   and bx,&001f    ; Moving two squares ahead?
        jne sr30        ; No, jump
        mov [enp],di    ; Take note of en passant
sr30:   mov [di],al
        mov [si],ah     ; Clear origin square
        call play
        mov bx,sp
        sub [bx+14],bp  ; Substract BP from AX
        popa

        ;
        ; If reached maximum depth then the code can
        ; come here >without< moving piece
        ;
sr22:   mov [temp],ax
        cmp sp,stack-4*2        ; First ply?
        jnz sr28        ; No, jump
        test byte [legal],255   ; Checking for legal move?
        jz sr28         ; No, jump
        mov bp,sp
        cmp si,[bp+4]   ; Origin is same?
        jnz sr23
        cmp di,[bp+2]   ; Target is same?
        jnz sr23
        cmp ax,-16384   ; Illegal movement?
        jl sr23
        add sp,6
        ret

        ;
        ; Note: TEST instruction clears carry flag
        ;
en_passant_test:
        test bl,1       ; Diagonal?
        je sr42         ; No, jump
        test byte [di],255 ; Capture?
        jne sr42        ; Yes, jump
        test bl,2       ; Going left?
        stc             ; Set carry
        lea bx,[si-1]
        jne sr42
        lea bx,[si+1]
sr42:   ret

displacement:
        db -33,-31,-18,-14,14,18,31,33
        db -16,16,-1,1
        db 15,17,-15,-17
        db -15,-17,-16,-32
        db 15,17,16,32

scores:
        db 0,10,50,30,90,30

        ;
        ; This marker is required for BIOS to boot floppy disk
        ;
        ds &7dfe-*      ; REPLACE with nothing for COM file
        db &55,&aa  ; REPLACE with nothing for COM file

        ; Start of second sector

sr28:   cmp bp,ax       ; Better score?
        jg sr23         ; No, jump
        mov bp,ax       ; New best score
        jne sr27
        in al,(&40)
        cmp al,&55      ; Randomize it
        jb sr23
sr27:   pop ax
        add sp,4
        push si         ; Save movement
        push di
        push ax

sr23:   mov [enp],bx    ; Restore en passant state
        pop ax          ; Restore board
        mov [si],al
        mov [di],ah
        mov bx,di
        sub bx,si
        and al,&07      ; Separate piece
        cmp al,&01      ; Is it a pawn?
        jne sr43
        call en_passant_test
        jnc sr43
        mov byte [bx],ch ; Clean
        xor byte [bx],9  ; Restore opponent pawn

sr43:   cmp al,&06      ; Is it a king?
        jne sr18
        mov bh,ch       ; Create unmoved rook
        xor bh,&12      ;
        cmp bl,-2       ; Castling to left?
        jne sr40
        mov [di-2],bh
        mov [di+1],ah
        jmp sr18

sr40:   cmp bl,2        ; Castling to right?
        jne sr18
        mov [di+1],bh
        mov [di-1],ah

sr18:   dec ax
        and al,&07      ; Was it pawn?
        jz sr11         ; Yes, check special
        cmp al,&05      ; King?
        jne sr34        ; No, jump
        test byte [si],&10      ; King already moved?
        je sr34         ; Yes, jump
        cmp word [temp],-4096   ; In check?
        jl sr34         ; Yes, jump
        or ah,ah        ; Moved to empty square?
        jne sr34        ; No, jump
        cmp bl,-1       ; Going left by one?
        je sr44
        cmp bl,1        ; Going right by one?
        jne sr34
        mov bh,[si+3]   ; Read rook
        mov bl,[si+2]   ; Read destination square
        jmp sr46

sr44:   test byte [si-3],255    ; Is empty square just right of rook?
        jne sr34        ; No, jump
        mov bh,[si-4]   ; Read rook
        mov bl,[si-2]   ; Read destination square
sr46:   test bl,bl      ; Ending in empty square?
        jne sr34        ; No, jump
        and bh,&17
        cmp bh,&12      ; Unmoved rook?
        je sr9          ; Yes, can move two squares for castling

sr34:   cmp al,&04      ; Knight or king?
        jnc sr14        ; End sequence, choose next movement
        or ah,ah        ; To empty square?
        jz sr9          ; Yes, follow line of squares
sr16:   jmp short sr14

sr11:   and cl,&1f      ; Advanced it first square?
        cmp cl,&10
        jnz sr14
sr15:   or ah,ah        ; Pawn to empty square?
        jnz sr17        ; No, cancel double-square movement
        mov ax,si
        sub al,&20      ; At first top row?
        cmp al,&40      ; At first bottom row?
        jb sr17         ; No, cancel double-square movement
sr14:   inc dh
        dec dl
        jnz sr12
sr17:   inc si
sr6:    cmp si,board+120
        jne sr7
        pop di
        pop si
sr24:   xor ch,8
        ret

display_board:
        ; Display board
        call display3
        mov si,board
sr4:    lodsb
        and al,&0f
        mov bx,chars
        xlat
        call display2
sr5:    cmp si,board+128
        jnz sr4
        ret

key2:
        mov di,board+127
        call key
        add di,ax
        call key
        shl al,4
        sub di,ax
        ret
key:
        push di
        mov ah,0
        int &16
        push ax
        call display
        pop ax
        and ax,&0f
        pop di
        ret

display2:
        cmp al,&0d
        jnz display
display3:
        add si,7
        mov al,&0a
        call display
        mov al,&0d
display:
        push si
        mov ah,&0e
        mov bh,&00
        int &10
        pop si
        ret

chars:
        db ".prbqnk",&0d,".PRBQNK"

initial:
        db &12,&15,&13,&14,&16,&13,&15,&12
offsets:
        db 16,20,8,12,8,0,8
total:
        db  4, 4,4, 4,8,8,8

        ; Bytes to say something
        db "Toledo Atomchess reloaded"
        db "nanochess.org"

        ds &8000-*      ; REPLACE with &0500 for COM file

board:  ds 256

depth:  ds 2            ; Depth for search
enp:    ds 2            ; En passant square
temp:   ds 2            ; Working score
legal:  ds 1            ; Flag indicating legal movement validation
        ds 249
stack:
        end

Related links

Last modified: Jan/14/2017