It was a dark and stormy night, and I could have been watching a movie, but instead, I decided to program a new game for my Intellivision. I felt like it would be far more productive than being stuck in the chair, lowering my IQ with stereotypical scripts, action scenes, and special effects.
Many years ago, when I was a kid, I always wanted to write chess programs. At these times I was using a Z80-based homebrew computer, and I had no idea of tree search, minimax algorithm, alpha-beta cut, or board scoring.
I used to pass hours drawing chess pieces that I would put on the screen and then making the interface for moving pieces, later (and embarrassingly), I only had a two-player game because I couldn’t figure out how to make the computer play.
My first attempt to make a computer to play the game of chess happened in the year 1989, and it was based simply on reading the board, trying all the moves, then calling itself, and being only a kid I didn’t envision all the possible paths of the game. I was able to play excitedly a few movements against the computer, and then the stack overrun all the memory, and my precious first chess game with AI code was lost in the mists of time. Maybe the most interesting thing is that no one of my family saw what I did, so when I told they what just happened I was meet with unbelief.
The year is 2023!
Let us return to the year 2023, 44 years after the introduction of Intellivision, and 41 years after the introduction of USCF Chess for Intellivision.
USCF Chess running on the jzintv emulator.
The USCF Chess game used 8x8 pixels and the chess graphics suffer because of the small space available to draw (although in fact something pretty recognizable can be done in 6x6 pixels as my JS1K Chess shows). I decided to draw the chess pieces on a matrix of 16x8 pixels, in this area I could draw 10x8 pixels for each piece.
The chess figures for my Intellivision chess program.
With an initial set of pieces, I proceeded to design the routines to draw the board on the screen, and put a cursor on the screen movable with the disc controller.
Now I had a typical two-players chess game with no move validation. How about an engine?
The engine
I took my Toledo Atomchess code originally written for x86 processors and started translating it to the CP1610 processor assembler code.
The main challenge was to keep the memory usage inside the limits of the Intellivision (240 bytes, and 112 16-bit words). In contrast, the Mattel USCF Chess has the advantage of an extra 2K of RAM (at the time a pricey cartridge).
In my chess engine, the board is represented as 120 bytes, a 10x12 arrangement where the 8x8 chessboard is positioned at the center, plus a stack is built into the 8-bit memory to keep search data (10 bytes for each ply).
Furthermore, it was being built on a chessboard interface written in the IntyBASIC language, and IntyBASIC requires some memory on its own (40 bytes for basic support and music player, and 41 words for display support), plus the variables required by the chessboard display and interface.
Although it was a pretty direct translation, it wasn’t so easy to port these routines. The most difficult part was to assign registers to the code and keep these valid along the playing routine. More than once, I missed a register that should be preserved along several steps of the engine and caused a bug.
Using the registers R4 and R5 to read or write to memory, also auto-increments these registers. There’s no similar behavior on the x86, but of course, this made several parts of the code to require redesign. By the night I had a working version of this simple engine.
The first working version of my chess game for Intellivision.
This simple engine didn’t have support for the full chess movements, like en passant, castling, and promotion. However, it is so short this little test engine that as a programmer I need to show you the beauty of it! Only 262 lines of assembler source code.
;
; Chess engine for Intellivision
;
; (c) Copyright 2023 Oscar Toledo G.
; https://nanochess.org/
;
; Creation date: Feb/28/2023.
;
STACK_ENTRY: EQU 10
piece_total:
DECLE 3,3,7,3,3,7,7
piece_offsets:
DECLE displacement+16
DECLE displacement+20
DECLE displacement+0
DECLE displacement+12
DECLE displacement+8
DECLE displacement+8
DECLE displacement+8
displacement:
DECLE -21,-19,-12,-8,8,12,19,21
DECLE -10,10,-1,1
DECLE 9,11,-9,-11
DECLE -11,-9,-10,-20
DECLE 9,11,10,20
piece_scores:
DECLE 0,1,3,3,5,9
PLAY_CHESS: PROC
BEGIN
MVII #-128,R0
MVO R0,var_BEST_SCORE
MVI var_TURN,R0
XORI #8,R0
MVO R0,var_TURN
MVII #array_BOARD+21,R3
SR7: MVI@ R3,R1 ; Read square.
XOR var_TURN,R1 ; XOR with current playing side.
ANDI #$0F,R1 ; Remove moved bit.
DECR R1 ; Translate to 0-5.
CMPI #6,R1 ; Is it frontier or empty square?
BC SR17 ; Yes, jump.
TSTR R1 ; Is it a pawn?
BNE SR8 ; No, jump.
MVI var_TURN,R0
TSTR R0 ; Is it playing black?
BNE SR25 ; No, jump.
SR8: INCR R1 ; Reverse direction for pawn.
SR25:
ADDI #piece_total,R1
MVI@ R1,R0
MVO R0,var_TOTAL_MOVEMENTS
ADDI #7,R1
MVI@ R1,R1 ; Movements offset in R1.
SR12: MOVR R3,R2 ; Restart target square.
SR9: ADD@ R1,R2 ; Displace in direction.
MVI@ R3,R4 ; Origin square.
MVI@ R2,R5 ; Target square.
ANDI #$0F,R5 ; Empty square?
BEQ SR10 ; Yes, jump.
;
; Moving to a square containing something.
;
XOR var_TURN,R5
SUBI #9,R5 ; Is it a valid capture?
CMPI #6,R5
MVI@ R2,R5
BC SR18 ; No, jump to avoid.
CMPI #displacement+16,R1 ; Moving pawn?
BNC SR19 ; No, jump to capture.
MVI var_TOTAL_MOVEMENTS,R0
ANDI #2,R0 ; Straight advance?
BEQ SR18 ; Yes, jump to avoid.
B SR19 ; No, jump to capture.
;
; Moving to an empty square.
;
SR10:
CMPI #displacement+16,R1 ; Moving pawn?
BNC SR19 ; No, jump to move.
MVI var_TOTAL_MOVEMENTS,R0
SARC R0,2 ; Diagonal movement?
BNOV SR19 ; No, jump to move.
MOVR R3,R0
DECR R0
BNC SR29
INCR R0
INCR R0
SR29: CMP var_EN_PASSANT,R0 ; Is it a valid en passant?
BNE SR18 ; No, avoid.
;
; Save the current state into the simulated stack
;
SR19: MVI var_&STACK,R5
MVO@ R3,R5 ; +0 Origin square
MVO@ R2,R5 ; +1 Target square
MVI@ R3,R0 ; Content of origin square.
MVO@ R0,R5 ; +2
MVI@ R2,R0 ; Content of target square.
MVO@ R0,R5 ; +3
ANDI #7,R0
CMPI #6,R0 ; King eaten?
BNE SR20 ; No, jump.
MOVR R5,R1
SUBI #STACK_ENTRY*1+4,R1
CMP var_&STACK_BASE,R1 ; Is it the first answer to computer move?
MVII #63,R0 ; Yes, maximum plus score.
BEQ SR26
MVII #47,R0 ; Yes, maximum score.
SR26: B SR24
SR20:
MOVR R0,R4
ADDI #piece_scores,R4
MVI@ R4,R0 ; Capture score
MOVR R5,R4
SUBI #STACK_ENTRY*2+4,R4 ; Search depth
CMP var_&STACK_BASE,R4
MVI var_BEST_SCORE,R4
BEQ SR22
MVO@ R0,R5 ; +4
MVO@ R1,R5 ; +5 Pointer to movement table.
SWAP R1
MVO@ R1,R5 ; +6
MVI var_EN_PASSANT,R0 ; Current en passant state.
MVO@ R0,R5 ; +7
MVI var_TOTAL_MOVEMENTS,R0 ; Total movements remaining.
MVO@ R0,R5 ; +8
MVI var_BEST_SCORE,R0 ; Best score so far.
MVO@ R0,R5 ; +9
MVO R5,var_&STACK
CLRR R0
MVO R0,var_EN_PASSANT
MVI@ R3,R4 ; R4 = Content of origin square
; MVI@ R2,R5 ; R5 = Content of target square
CLRR R5
MVO@ R5,R3 ; Clear origin square
MVO@ R4,R2 ; Move to target square
CALL PLAY_CHESS
; R0 = Reply score
MVI var_&STACK,R5
SUBI #STACK_ENTRY,R5
MVO R5,var_&STACK
MVI@ R5,R3 ; +0
ADDI #$0100,R3 ; Restore current origin square
MVI@ R5,R2 ; +1
ADDI #$0100,R2 ; Restore current target square
MVI@ R5,R1 ; +2
MVO@ R1,R3 ; Restore content of origin square
COMR R0 ; Negate new score
MVI@ R5,R1 ; +3
MVO@ R1,R2 ; Restore content of target square
INCR R0
ADD@ R5,R0 ; +4 Subtract from previous score
MVI@ R5,R1 ; +5
SWAP R1
ADD@ R5,R1 ; +6
SWAP R1
MVI@ R5,R4 ; +7
MVO R4,var_EN_PASSANT
MVI@ R5,R4 ; +8
MVO R4,var_TOTAL_MOVEMENTS
MVI@ R5,R4 ; +9
SR22:
XORI #$80,R4 ; Extend sign
SUBI #$80,R4
CMPR R4,R0
BLT SR23
BNE SR27
MVI _rand,R0
ANDI #$2A,R0
BNE SR23
MOVR R4,R0
SR27:
MOVR R0,R4 ; New best score
MVI var_&STACK,R0
CMP var_&STACK_BASE,R0
BNE SR23
MOVR R3,R0
SUBI #array_BOARD,R0
MVO R0,var_BEST_ORIGIN
MOVR R2,R0
SUBI #array_BOARD,R0
MVO R0,var_BEST_TARGET
SR23:
MVO R4,var_BEST_SCORE
SR18: MVI@ R3,R0
ANDI #7,R0 ; Was it pawn?
DECR R0
BEQ SR11 ; Yes, check special.
CMPI #1,R0 ; Knight?
BEQ SR14 ; Yes, end movement.
CMPI #5,R0 ; King?
BEQ SR14 ; Yes, end movement.
MVI@ R2,R0
TSTR R0 ; To empty square?
BEQ SR9 ; Yes, follow line of squares.
B SR14
SR11: MVI@ R1,R0
CMPI #-10,R0
BEQ SR15
CMPI #10,R0
BNE SR14
SR15: MVI@ R2,R0
TSTR R0 ; Pawn to empty square?
BNE SR17 ; No, cancel double-square movement.
MOVR R3,R0
SUBI #array_BOARD+41,R0
CMPI #40,R0 ; At first top row or bottom row?
BNC SR17 ; No, cancel double-square movement.
SR14: INCR R1
MVI var_TOTAL_MOVEMENTS,R4
DECR R4
MVO R4,var_TOTAL_MOVEMENTS
BPL SR12
SR17: INCR R3
CMPI #array_BOARD+99,R3
BNE SR7
MVI var_BEST_SCORE,R0
XORI #$80,R0 ; Extend sign
SUBI #$80,R0
SR24: MVI var_TURN,R1
XORI #8,R1
MVO R1,var_TURN
RETURN
ENDP
In case you want to test this early and very basic chess program, you can download the source code for it (you'll need IntyBASIC to compile it):
Later, the optimizations caused a lot of headaches, for example, when removing a calculation, or limiting an expression to a certain register, and that very register was used later in a different way. My favorite one happened when integrating the castling, en passant, and promotions, the new code depended on chess pieces having a bit to indicate if these had moved from their original positiion, but the old code still did comparisons with the whole value, so it couldn’t capture any unmoved piece since the bit pattern didn’t match a valid piece!
Just as I was showing the chess game, Psycho Stormtrooper suggested that there could be a tournament mode. And it turn on the proverbial light on my mind! Of course, Japanese chess games for the Gameboy consoles typically have a tournament mode! It is battling the console in different levels where each level is represented by a different character.
So I created Midori, the challenger, and her foes: Monkey, Sue, and Professor Shifu. I drew first some screens depicting Midori as she enters the tournament, another one when she wins the tournament, and one more for losing the tournament.
Midori.
Also it was the moment when the game got the name Mr. Chess. As I think it had a lot more punch.
The final title screen.
Later I started to think that the foes also should have their own intro screen, and I draw the intro screens and texts for each opponent. It is kind of hard to do nice graphics on Intellivision, but I managed to fit everything in the context of the graphical limitations. William Moeller contributed a better (and more fun) description for Monkey that the one I wrote first.
Monkey.
The game got several nice melodies for each character, and also for the title screen, the winning screen, and the defeat screen. All of these were composed by my brother Adán Toledo.
Midori vs Monkey.
Further development
I made stronger the engine by following the recapture chain. Let us suppose that the engine captures a queen with its queen, but the player retaliates with a pawn capture, then it would be ignored; but let us suppose that the engine does any movement, the player does any other movement, and the engine captures the queen (3rd ply) and the search stops! The Intellivision would "believe" that the queen capture is possible, and integrate it as the best movement possible, but if we add a recapture chain, it would detect immediately that the queen is captured by the pawn, and it would ignore it! This simple technique makes the engine stronger and makes it avoid falling into simple blunders.
This enhancement made the engine too slower, I felt like it should be faster, but not. Something was making it too slow at certain “simple” positions involving captures that should be no-brainers for a chess engine. I revised several times the Alpha-Beta cut algorithm and everything looked just right. In the end, my mind finally “connected,” and I noticed the score used for comparison wasn’t sign-extended, so indeed the movement was losing points, but it wasn’t pruned because it looked like a very high value, and the Intellivision keep exploring because it seemed like a good movement! After this correction, the speed went up three times the previous speed.
A further bug detected into the testing caused the chess program to allow the player to put the king in check, and because this same routine was used for recapture analysis, it didn’t detected certain captures. After the correction, the game played slightly stronger, of course, not at the level of a master, but fair enough for a 895 khz. 16-bit processor.
