Video Chess disassembled and commented

Since I discovered Video Chess for the Atari 2600, I found it pretty impressive. However, I believed the game implemented extra RAM memory, but more recently I discovered it worked using only the 128 bytes of memory available, and with a 4K ROM cartridge. That's an impressive achievement for such a small game console, also the rumor of a bug triggered me to reverse engineer this game to see how it works.

Video Chess was developed by Larry Wagner and Bob Whitehead, and released by Atari in 1979. Although the original game is greater than 4K and a bank-switching PCB was created, the final released game was optimized to use only a 4K ROM cartridge.

Video Chess also has the distinction of displaying eight different objects on a screen row using a technique known as Venetian Blinds, where the odd row of the screen would show four chesspieces, and the even row of the screen would show other four chesspieces. This technique allows the Atari 2600 to exceed its own limit of 3 figures per screen row. I won't discuss this technique as it is a video display trick, and in this article I'll concentrate in the AI (Artificial Intelligence) code.

Disclaimer: Video Chess is property of their respective owners, and the disassembled code and comments authored by myself are purely for historical and educative purposes.

Video Chess running on the Stella emulator.

Reverse engineering (1st day)

I've used the Stella emulator to get a preliminary disassembly of Video Chess. It was a great help to start analyzing it, and I've documented each line of assembler code as I passed over the instructions.

Let us remember the Atari 2600 uses the 6507 processor (a reduced pin equivalent of the 6502 processor). The execution of Video Chess starts at the address $f000.

The first thing I found was the representation of the pieces on the chessboard. It was relatively easy as it is the second thing the game does on booting (the first thing is resetting the internal 128 bytes of RAM).

Atari's Video Chess uses this representation for the pieces on the chessboard:

$06 = Pawn (3 points)
$05 = Rook (15 points)
$04 = Knight (9 points)
$03 = Bishop (9 points)
$02 = Queen (27 points)
$01 = King (66 points)
Bit 3 = Side (0=Black, 1=White)

The chessboard itself is located at the addresses $80 to $bf (one byte for each square). It is common the idiom LDA $80,X to access a square, where X contains a value from 0 to 63 for the 64 squares on the chessboard. The contents of each square is located in the bits 3-0 of the byte, while the upper bits 7-4 are used to save other data in a clever way.

$80	$81	$82	$83	$84	$85	$86	$87
$88	$89	$8a	$8b	$8c	$8d	$8e	$8f
$90	$91	$92	$93	$94	$95	$96	$97
$98	$99	$9a	$9b	$9c	$9d	$9e	$9f
$a0	$a1	$a2	$a3	$a4	$a5	$a6	$a7
$a8	$a9	$aa	$ab	$ac	$ad	$ae	$af
$b0	$b1	$b2	$b3	$b4	$b5	$b6	$b7
$b8	$b9	$ba	$bb	$bc	$bd	$be	$bf

RAM address for each chessboard square.

After this, I found the game reset buttons and level selection (variable $ea contains a value from 0 to 7), followed by the joystick movement handling and button press.

The chessboard setup directed me to a piece of code looking for kings on the chessboard, and a distance calculation between the two kings, and between the center of the chessboard and the Atari's king.

A stack of movements (2nd day)

I had a brief moment of confussion with the game level selection, instead it was the chessboard edit mode, as it incremented by one the content of the square to cycle each piece.

After identifying this code, it was easy to uncover the routine doing a movement over the chessboard. Also I could uncover the way it saved the board state while analyzing each movement.

Before doing each movement, the game saves the current chessboard state using a simulated stack located in the same addresses as the board:

$80-$8c = Upper nibble contains bit 7 of ram_B4, and bits 5-4 contains the bits 5-4 of the source square number.
$8d-$99 = Upper nibble contains the content of the source square.
$9a-$a6 = Upper nibble contains the content of the target square.
$a7-$b3 = Upper nibble contains the lower nibble of the source square number.
$ef-$fb = Copy of the movement counter (ram_D8).
$c0-$cc = Current movement score (without sign, so $7f is -1 and $81 is +1)
$d4 = Source square number for current movement.
$d5 = Target square number for current movement.
$d6 = Current piece in evaluation ($01-$06).
$d7 = Content of target square ($00-$0f).
$d8 = Movement counter.
$da = Current board score (incremental).
$dc = Current score for kings distance.
$e3 = Current side playing ($01 = Black, $ff = White).

The Select button doesn't select directly the analysis depth, instead it refers to a table located at $fff5:

Game 1 - $02
Game 2 - $12
Game 3 - $13
Game 4 - $23
Game 5 - $24
Game 6 - $34
Game 7 - $56
Game 8 - $00

The lower nibble is saved at ram_D2 (maximum depth), and the upper nibble is saved at ram_D9 (full analysis depth). While ram_D0 contains the current analysis depth ($00 at start).

The next step was marking the code that scores movements. Video Chess is able to castle but only on the king side. The search doesn't consider castling on player's side, except to validate movements.

Marking each discovered variable made the code to start looking more legible. I found a piece of code setting the current analysis square as 64 (an invalid origin square), and following the trail I discovered the $fa66 subroutine does the analysis of a chessboard.

ram_D3 = Frame counter (low-byte).
ram_F1 = Frame counter (high-byte).

No trees or nodes (3rd day)

So far there is nothing like trees and nodes, although of course we can consider the stack as a tree with a single branch.

Video Chess starts analyzing the board from the bottom-right corner, and once it finds an own piece, it saves the current state in the simulated stack, does the movement, and starts another board analysis with the opposite side (and very probably starting a recursive deeper analysis), once this is finished, it reverts the movement using the information on the stack, and continues where it was.

Getting to discover how the cursor behaves with the chessboard was another challenge:

ram_F3:
- $00 - Cursor moving (static X on current position)
- $01 - Piece selected (static X on origin, blinking piece on current position)
- $80 - Piece moving (erased on origin, blinking piece on current position)
- $c0 - Does chessboard search (same as $80 but with counter in ram_F4 to blink first and then search)
ram_E5 = En passant state (origin square of en passant pawn) or $80 if invalid.

Once I revealed enough code, I could discover some obscure code that handles castling validation just after calculating material for the chessboard. The bits come out easily:

ram_82 = bit 6 = 1 = Black king moved.
ram_83 = bit 6 = 1 = White king moved.
ram_84 = bit 6 = 1 = Black queen-side rook moved.
ram_85 = bit 6 = 1 = Black king-side rook moved.
ram_86 = bit 6 = 1 = White queen-side rook moved.
ram_87 = bit 6 = 1 = White king-side rook moved.
ram_88 = bit 6 = 1 = Black unable to castle queen-side.
ram_89 = bit 6 = 1 = Black unable to castle king-side.
ram_8A = bit 6 = 1 = White unable to castle queen-side.
ram_8B = bit 6 = 1 = White unable to castle king-side.

And finally I still couldn't understand how it entered the analysis phase until I revised the display code instruction by instruction, and in the same routine where it removed the cursor from the chessboard and read the joystick, it has a small check of ram_F3 bit 6 to jump into the board search code at $f574.

The board search code just keeps running, and it only updates the video background color with no attempt to keep the video synchronization.

The variable ram_F5 signals if the current move is valid or invalid. Video Chess continuously checks for valid movement as the player displaces the cursor over the chessboard.

The one thing that really makes difficult the reverse engineering of this game is the fact that memory bytes are reused as some paths of code are executed for display, but not when doing the "thinking". For example, ram_CC is reused as a graphic byte, black material score, king to find, and temporary variable for square distance.

The movement generator was one of these special pieces of codes that works, but the understanding of how it works was pretty hard to achieve. The movement table contains all the possible offsets for a piece movement. For example, the queen can move in eight directions, and in each direction it can move seven squares, so the table has the following numbers for going to the left: $99, $98, $97, $96, $95, $94, $93, and $92.

However, the queen is defined as having 64 movements, because when it is finished exploring a "ray" it reduces the counter by a multiple of 8 (faster than a multiple of 7).

Also the displacements in the movement table are in BCD (Binary-Coded-Decimal) numbers, and before adding the displacement, it converts the square number (0-63) to a BCD number using this piece of code:

    lda ram_D4  ; 00xxxyyy
    and #$38    ; 00xxx000 extract row.
    adc ram_D4  ; 0xxx0yyy add row itself and combine with column.

The same day I found the colors for the display:

ram_E1 = Color for background.
ram_E0 = Color for chessboard.
ram_DF = Color for white pieces.
ram_DE = Color for black pieces.

Where's the bug?

Level 6 and level 7 of Video Chess are infamous because people says that the Atari sometimes move two pieces at the same time. However, I couldn't find a screenshot or movement list that could prove this asseveration.

My first suspicion was the ram_EF stack as it can contain up to thirteen bytes of data covering $ef to $fb addresses, and this stack in particular contains the movement counter for the current chess piece.

Given the processor stack pointer starts at $ff, we only need a path in code that does three JSR instructions to overwrite the $fa and $fb addresses, or a path that does two JSR instructions and a PHA/PHP instruction to overwrite $fb.

Why this could cause a problem? Because when restoring a move, it depends on the content of the ram_EF stack to restore ram_D8 and in turn recreate the target square number to return the chess piece to its right place. A failure doing this would cause the chess piece to stay where it moved, essentially duplicating it on the chessboard.

The tree of calls however disrupted my "smart" thinking. There are no stack overruns:


	Entry point
	Lf574
		; Level 1 call
			; Level 2 call
		jsr Lfa66
			jsr Lfb91
		jsr Lfb91
		jsr Lfbb6	; This call happens outside of analysis.
			php
				jsr Lfe9c
				jsr Lfe9c
			plp
			pha/pla
		jsr Lfd4d
		jsr Lfa95
			jsr Lfb91
			jsr Lfd4d
			jsr Lfb91
		jsr Lfe71
		jsr Lfe6f
		jsr Lfe9c
		jsr Lfd65

Also a research of the paths used to add movements to the stack doesn't reveal any simulated stack overflow. So unless I can come across a position that triggers the bug, it is currently only a legend. It could have been an electrical glitch, or a buggy RAM that created the legend.

Later analysis

Even when most of the code operation has been discovered, some later analysis still revealed the inner workings of other variables:

ram_b4 bit 7 clear means to generate all the moves, set means to generate all the moves to empty squares.
ram_B7 bit 7 set means to only find pieces but don't generate a move, and setting it to zero means to find piece and generate the first move.
ram_E2 bit 7 set means the game has just started, and bit 7 clear means it is in the middlegame. Bit 6 set means the white king is alone.
ram_E4 a count of half-moves made both by computer and player.
ram_81 bit 6 signals white is not able to respond to black (stalemate) because on every move the white king is captured. It is used just before Lf99e, probably to avoid doing stalemate of an alone white king.

Finally, Lf9ab is in charge of doing alpha-beta cut to avoid researching movements that aren't improving the current depth and position.

Conclusion

The board initialization pattern triggered a glitch in my mind because I was sure I saw something before. I went to my personal library to retrieve my copy of "Sargon: A computer chess program", and I could confirm it: In the board initialization pattern, Video Chess has an amazingly similar instruction order in comparison to the Sargon chess program. Probably the author of Video Chess read the book, I only can think it was a kind of homage as there is no other similar code.

The board initialization code of Sargon.

	;
	; Chessboard setup
	;
    ldx     #$07                    ; X = $07 for eight columns.
Lf2b6
    lda     Lfef2,x                 ; Read corresponding piece.        
    sta     ram_80,x                ; Put in top of the board.        
    eor     #$08                    ; Switch side.
    sta     ram_B8,x                ; Put in bottom of the board.
    lda     #$8e                    ; Unmoved white pawn.        
    sta     ram_B0,x                ; Put at 2nd row.
    lda     #$46                    ; Unmoved black pawn.
    sta     ram_88,x                ; Put at 7th row.
    sty     ram_90,x                ; Clear square at 6th row.
    sty     ram_98,x                ; Clear square at 5th row. 
    sty     ram_A0,x                ; Clear square at 4th row.
    sty     ram_A8,x                ; Clear square at 3rd row.
    dex                             ; Count column.
    bpl     Lf2b6                   ; Jump if not negative.

Video Chess code for chessboard initialization.

Video Chess is pretty impressive by the fact it has a full-depth analysis, and a quiescense search if it detects a changing position (see LF71c).

Also it has a king opposition score to try to corner the adversary king, and it is triggered by the detection of the white king alone (see LF7c1).

Furthermore, it detects when there is few material on board, and increases the analysis depth in a kind of interesting endgame enhancement (see just before Lf448).

All these things make Video Chess an impressive tour de force for the year 1979.

Downloads

Disassembled and commented assembler code of Video Chess for Atari VCS/2600 (131.91 kb).

The disassembled and commented source code for Video Chess can be re-assembled to a binary file equivalent to the original game. You need to use dasm with this command line:

dasm video_chess.asm -ovideo_chess.bin -f3

$80	$81	$82	$83	$84	$85	$86	$87
$88	$89	$8a	$8b	$8c	$8d	$8e	$8f
$90	$91	$92	$93	$94	$95	$96	$97
$98	$99	$9a	$9b	$9c	$9d	$9e	$9f
$a0	$a1	$a2	$a3	$a4	$a5	$a6	$a7
$a8	$a9	$aa	$ab	$ac	$ad	$ae	$af
$b0	$b1	$b2	$b3	$b4	$b5	$b6	$b7
$b8	$b9	$ba	$bb	$bc	$bd	$be	$bf

$80	$81	$82	$83	$84	$85	$86	$87
$88	$89	$8a	$8b	$8c	$8d	$8e	$8f
$90	$91	$92	$93	$94	$95	$96	$97
$98	$99	$9a	$9b	$9c	$9d	$9e	$9f
$a0	$a1	$a2	$a3	$a4	$a5	$a6	$a7
$a8	$a9	$aa	$ab	$ac	$ad	$ae	$af
$b0	$b1	$b2	$b3	$b4	$b5	$b6	$b7
$b8	$b9	$ba	$bb	$bc	$bd	$be	$bf