Toledo Atomchess Game
The world's smallest chess program in x86 machine code,
only 326 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), 392 bytes
(Mar/04/2016), and finally 326 bytes (Dec/15/2019).
- Plays basic chess movements (no en passant, no castling and no promotion)
- Enter your movements as basic algebraic (D2D4)
- Your movements aren't checked for legality
- Search depth of 3-ply
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 779
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
Also it appears even better documented in my book Programming Boot Sector Games.
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: Apr/23/2021