Página principal
Emulador Intel 8080
Programas de ajedrez
Concursos
Tienda
Retrogaming
FAQ
Enlaces
Acerca de mí
English version

Video Chess desensamblado y comentado

Desde que descubrí Video Chess para Atari 2600, lo encontré bastante impresionante. Sin embargo, yo creía que el juego implementaba memoria RAM extra, y más reciente descubrí que trabajaba usando solo los 128 bytes de memoria disponible y con un cartucho ROM de 4K. Ese es un logro impresionante para una consola de juegos tan pequeña, también el rumor de un bug me intrigó lo suficiente para hacer ingeniería en reversa del juego y ver como funciona.
Video Chess fue desarrollado por Larry Wagner y Bob Whitehead, y vendido por Atari en 1979. A pesar de que el juego original era mayor de 4K y se creó una PCB con intercambio de bancos, el juego final fue optimizado para utilizar solo un cartucho con 4K de ROM.
Video Chess también tiene la distinción de ilustar ocho objetos diferentes en una sola línea de la pantalla usando la técnica conocida como Venetian Blinds, donde una línea impar de la pantalla muestra cuatro piezas de ajedrez, y la línea par de la pantalla muestra las otras cuatro piezas. Esta técnica permite que el Atari 2600 exceda su propio límite de 3 gráficos por línea de la pantalla. No discutiré esta técnica aquí, ya que en este artículo me concentro en el código de la IA (Inteligencia Artificial).
Aviso: Video Chess es propiedad de sus respectivos propietarios, y el código desensamblado y comentado por mí es puramente para propósitos históricos y educativos..

Video Chess corriendo en el emulador Stella.

Ingeniería en reversa (1er día)

Utilicé el emulador Stella para obtener un desensamblaje preliminar de Video Chess. Fue una gran ayuda para comenzar a analizarlo, y documenté cada línea de ensamblador según iba pasando por el código.
Recordemos que el Atari 2600 utiliza el procesador 6507 (un equivalente reducido en patas del procesador 6502). La ejecución de Video Chess comienza en la dirección $f000.
La primera cosa que encontré fue la representación de las piezas en el tablero. Fue relativamente sencillo ya que es la segunda cosa que hace el juego al arrancar (la primera es resetear los 128 bytes internos de RAM).
Video Chess de Atari utiliza esta representación para las piezas del tablero:
El tablero mismo esta localizado en las direcciones $80 a $bf (un byte por cada cuadro). Es común ver la jerga LDA $80,X para acceder un cuadro, donde X contiene un valor de 0 a 63 para los 64 cuadros en el tablero. El contenido de cada cuadro se localiza en los bits 3-0 del byte, mientras que los bits 7-4 son usados para guardar otros datos en forma ingeniosa.
$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
Dirección RAM para cada escaque del tablero.
Después de esto, encontré los botones para reiniciar el juego y seleccionar el nivel (la variable $ea contiene un valor de 0 a 7), seguido por el movimiento del joystick y apretar el botón.
La inicialización del tablero me dirigió a una pieza de código que busca los reyes en el tablero, y un cálculo de distancia entre dos reyes, y entre el centro del tablero y el rey del Atari.

Una pila de movimientos (2do día)

Tuve un breve momento de confusión con la selección del nivel de juego, en lugar de eso era el modo de edición del tablero, ya que incrementa por uno el contenido del cuadro para ciclar cada pieza.
Después de identificar este código, fue fácil descubrir la rutina que hacía un movimiento sobre el tablero. También pude revelar la forma en que guardaba el estado del tablero mientras analizaba los movimientos.
Antes de realizar cada movimiento, el juego salva el estado actual del tablero utilizando una pila simulada localizada en las mismas direcciones del tablero:
El botón Select no selecciona directamente el nivel de análisis, en lugar de eso se refiere a una tabla en la dirección $fff5:
Los 4 bits inferiores se guardan en ram_D2 (profundidad máxima), y los 4 bits superiores se guardan en ram_D9 (profundidad máxima para análisis completo). Mientras que ram_D0 contiene la profundidad actual de análisis ($00 al comienzo).
El siguiente paso fue marcar el código que puntua los movimientos. Video Chess es capaz de enrocar pero solo del lado del rey. La búsqueda no considera enroque del lado del jugador, excepto para validar movimientos.
Al marcar cada variable descubierta el código comenzó a ser más legible. Encontré una pieza de código poniendo el cuadro inicial de análisis en 64 (un número inválido de cuadro), y siguiendo la pista descubrí la subrutina $fa66 que analiza el tablero completo.

Sin árboles ni nodos (3er día)

Hasta ahora no hay nada como árboles y nodos, aunque por supuesto podemos considerar la pila como un árbol con una sola rama.
Video Chess comienza analizando el tablero desde el cuadro inferior derecho, y una vez que encuentra una pieza propia, salva el estado actual del tablero en la pila simulada, realiza el movimiento, y comienza otro análisis de tablero para el lado opuesto (posiblemente anidando otra exploración a un nivel más profundo), una vez que termina, revierte el movimiento usando la información de la pila, y continua donde estaba.
Descubrir como se comportaba el cursor en el tablero fue otro desafío:
Una vez revelado suficiente código, pude sacar a la luz el código que maneja la validación de enroque después de calcular el material del tablero. Los bits salieron fácilmente:
Y finalmente no podía comprender todavía como entraba en la fase de análisis, hasta que revisé el código de video instrucción por instrucción, y en la misma rutina donde quitaba el cursor del tablero y leía el joystick, tenía un pequeño test del bit 6 de ram_F3 para saltar en el código de búsqueda de tablero en $f574.
La búsqueda de tablero corre y solo actualiza el color de fondo del video sin ningún intento de mantener la sincronización de video.
La variable ram_F5 señala si el movimiento actual es válido o inválido. Video Chess checa continuamente si un movimiento es válido así como el jugador desplaza el cursor sobre el tablero.
Una cosa que hizo realmente difícil la ingeniería en reversa de este juego es el hecho de que los bytes de memoria son reutilizados ya que algunas partes del código son ejecutadas para visualización, pero no cuando realiza el "pensamiento". Por ejemplo, ram_CC es reutilizado como byte de gráficos, puntos de material de las negras, rey para encontrar, y variable temporal para la distancia a un escaque.
El generador de movimientos fue una de esas piezas de código especiales que funcionan, pero comprender como funcionan fue increíblemente difícil. La tabla de movimientos contiene todos los posibles desplazamientos para mover una pieza. Por ejemplo, la reina se puede mover en ocho direcciones, y en cada dirección se puede mover siete escaques, así que la tabla tiene los siguientes números para ir a la izquierda: $99, $98, $97, $96, $95, $94, $93 y $92.
Sin embargo, la reina esta definida como 64 movimientos, porque cuando termina de explorar un "rayo" reduce el contador por un múltiplo de 8 (más rápido que un múltiplo de 7).
También los desplazamientos de la tabla de movimientos están en números BCD (Binary-Coded-Decimal), y antes de realizar un desplazamiento, convierte el número de escaque (0-63) a un número BCD usando esta pieza de código: 
    lda ram_D4  ; 00xxxyyy
    and #$38    ; 00xxx000 extrae línea.
    adc ram_D4  ; 0xxx0yyy suma línea a si misma y combina con columna.
El mismo día encontré los colores para la visualización:

¿Dónde está el bug?

El nivel 6 y el nivel 7 de Video Chess son infames porque la gente dice que el Atari algunas veces mueve dos piezas al mismo tiempo. Sin embargo, no pude encontrar ninguna captura de pantalla o lista de movimientos que pudiera probar esta aseveración.
Mi primera sospecha fue la pila simulada en ram_EF ya que puede contener trece bytes de datos cubriendo las direcciones $ef a $fb, y esta pila en particular contiene el contador de movimientos para la pieza de ajedrez actual.
Dado que la pila del procesador empieza en $ff, solo se necesita un camino en el código que ejecute tres intrucciones JSR para sobreescribir las direcciones $fa y $fb, o un camino que ejecute dos instrucciones JSR y una instrucción PHA/PHP para sobreescribir $fb.
¿Por qué esto causaría un problema? Porque cuando restaure un movimiento, depende en el contenido de la pila ram_EF para restaurar ram_D8 y en turno recrear el número del cuadro destino para regresar la pieza de ajedrez a su lugar correcto. Una falla haciendo esto puede causar que la pieza de ajedrez se quede donde se movió, esencialmente duplicandola en el tablero.
Sin embargo, el árbol de llamadas destruyó mi "creativa" idea. No hay sobrepasamientos de pila. 

	Punto de entrada
	Lf574
		; Llamada nivel 1
			; Llamada nivel 2
		jsr Lfa66
			jsr Lfb91
		jsr Lfb91
		jsr Lfbb6	; Esta llamada sucede fuera del análisis.
			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
También una investigación de los caminos usados para agregar movimientos a la pila no reveló ningún sobrepasamiento de pila. Así que a menos que me encuentre una posición que muestre el bug, actualmente solo es una leyenda. Pudo ser suficiente un glitch de la luz, o una memoria defectuosa en un Atari para crear esta leyenda.

Análisis posterior

Incluso con la mayor parte de la operación del código descubierta, algún análisis posterior reveló el funcionamiento de otras variables:
Finalmente, Lf9ab esta a cargo de realizar el corte alfa-beta para evitar investigar movimientos que no mejora la profundidad y posición actual.

Conclusión

La forma de inicialización del tablero me produjo un blip mental porque estaba seguro de que lo había visto antes. Fui a un biblioteca personal para buscar mi copia de "Sargon: A computer chess program", y pude confirmarlo: El patrón de inicialización del tablero, Video Chess tiene una similitud interesante del orden de instrucciones al comparar con el programa de ajedrez Sargon. Tal vez el autor de Video Chess leyó el libro. Solo se me ocurre que es un homenaje, ya que no hay otro código similar.

El código de inicialización de tablero de 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.
El código de Video Chess para inicializar el tablero.
Video Chess es muy impresionante por el hecho de que tiene un análisis de profundidad completa, y una búsqueda de tranquilidad si detecta una posición cambiante (vea LF71c).
También tiene una puntuación de oposición de reyes para tratar de acorralar al rey adversario, y se activa por la detección de un rey blanco solitario (vea LF7c1).
Además, detecta cuando hay poco material en el tablero, e incrementa la profundidad de análisis en una forma interesante de mejora del fin de juego (vea justo antes de Lf448).
Todas estas cosas hacen que Video Chess sea un impresionante tour de force para el año 1979.

Descargas

El código desensamblado y comentado de Video Chess puede ser reensamblado a un binario equivalente del juego original. Necesitas usar dasm con esta línea de comandos:
dasm video_chess.asm -ovideo_chess.bin -f3

Ligas relacionadas

Última modificación: 21-jun-2023