Programación Retro del Commodore 64

Tras el éxito de los volúmenes I y II, acaba de publicarse en Amazon el nuevo libro “Programación Retro del Commodore 64 Volumen III”:

Son 193 páginas que describen en detalle cómo programar en ensamblador un juego de tablero, es decir:

• La representación del tablero.
• La generación de jugadas.
• El árbol de juego.
• La función de evaluación.
• La búsqueda minimax.
• La búsqueda alfa-beta (con poda).
• La profundización iterativa.
• La ordenación de movimientos.
• Las tablas de historia.
• Etc.

El libro está disponible en los principales portales de Amazon:

• “Programación Retro del Commodore 64 Volumen III” en Amazon.es.
• “Programación Retro del Commodore 64 Volumen III” en Amazon.com.
• “Programación Retro del Commodore 64 Volumen III” en Amazon.co.uk.
• “Programación Retro del Commodore 64 Volumen III” en Amazon.de.
• “Programación Retro del Commodore 64 Volumen III” en Amazon.fr.
• “Programación Retro del Commodore 64 Volumen III” en Amazon.it.
• “Programación Retro del Commodore 64 Volumen III” en Amazon.jp.

Yo lo he pasado fenomenal escribiéndolo, así que espero que lo paséis igual de bien leyéndolo y, sobre todo, adaptando las ideas a vuestros propios proyectos con el C64.

Casi todos los aficionados al C64 conocemos su sucesor natural, el C128:

El C128 se lanzó en 1985 –el C64 en 1982–, y se caracterizaba por:

• Tener dos procesadores, un MOS 8502 y un Z80.
• Tener 128 KB de RAM.
• Soportar BASIC 2.0, BASIC 7.0 y CP/M.

Y, por encima de todo, el C128 era compatible con el C64, en el sentido de que casi todo el software del C64 se podía ejecutar en el C128, entrando éste en “modo C64”.

Menos conocido que el C128 fue el C65. De hecho, el C65 fue un prototipo de finales de los 80 que no llegó al mercado:

Las características principales del C65 eran:

• Tener un procesador MOS 65CE02.
• Tener 128 KB de RAM.
• Soportar BASIC 2.2 y BASIC 10.0.
• Tener una unidad de disquetes de 3,5 integrada.

El C65 también tenía previsto un “modo 64” para poder ejecutar el software del C64.

Pues bien, aunque ya lleva tiempo por ahí, recientemente he podido conocer un proyecto llamado Mega65 para reproducir el C65 con FPGA, es decir, con circuitos programables. Algo similar a Ultimate 64, pero para el C65.

El proyecto tiene muy buena pinta, y podéis conocer todos sus detalles en su página web https://mega65.org/.

Eso sí, el Mega65 podía tener un precio un poco más ajustado, porque cuesta cerca de los 800 euros. ¡¡Por ese precio te compras varios C64 auténticos de segunda mano!!

El proyecto lo damos por terminado con su versión 11 aunque, por supuesto, admite muchas mejoras. Aquí van algunas sugerencias para el lector que tenga interés:

• Calcular y mostrar unos contadores de podas alfa y beta.
• Mostrar el registro de jugadas (tabla “game_list”).
• Guardar el registro de jugadas a cinta o disco, y permitir su carga.
• Mejorar la función de evaluación con más criterios, por ejemplo, para identificar y evaluar de forma adecuada situaciones de fin de partida.
• Implementar algoritmos de ordenación de movimientos más eficientes.
• Añadir un “libro” con comienzos y/o finales de partida.
• Adaptar las ideas comentadas a otros tipos de juegos de tablero, por ejemplo, Othello, damas, ajedrez o go.
• Mejorar la interfaz de usuario, utilizando caracteres personalizados para pintar ratón, gatos, casillas, mensajes, etc.
• Desarrollar sonidos SID para avisar al usuario de que el C64 ha movido, o que el movimiento que pretende hacer el usuario es ilegal.
• Utilizar los temporizadores y las interrupciones del CIA1 para poner un límite máximo (ej. X minutos/movimiento) al tiempo de juego del C64.
• Que el C64 “piense” mientras el humano piensa, asumiendo que éste hará una jugada determinada.
• Hacer un perfilado del programa mediante herramientas como C64 Debugger, de modo que se identifiquen posibles cuellos de botella y el programa se pueda optimizar.

En fin… las posibilidades son casi infinitas… ¡¡a disfrutarlo!!

HVSW.

“Colossus Chess” fue una serie de juegos de ajedrez ganadores de muchos premios durante los 80. Lo programó Martin Bryant y se portó a casi todos los equipos de 8 bits de la época.

Jugué muchas veces contra “Colossus Chess”. Ya no recuerdo si conseguí ganarle en alguna ocasión, pero sí recuerdo haberlo puesto contra las cuerdas más de una vez. Al final, casi siempre cometía algún fallo garrafal, se me revolvía, y me daba un buen repaso.

Aquí os dejo un par de pantallas de una partida reciente. Este es el tablero de juego (tenía una vista 2D y otra 3D):

Y este es el registro de la partida y lo que está pensando la máquina:

El juego tenía muchísimas funcionalidades, entre las que destacan:

• Tablero de juego con vistas 2D y 3D. Se pueden cambiar los colores. Se puede cambiar la orientación del tablero.
• Registro de jugadas de la partida en notación algebraica, incluyendo los tiempos de juego de cada jugador.
• Información sobre el análisis de jugadas que está haciendo Colossus (“lookahed”: profundidad de análisis, “positions”: número de tableros analizados, “current line”: variante actual, “best line”: variante principal, etc.).
• Evaluación de tableros atendiendo a criterios materiales (número y tipos de piezas), de posición (posición de las piezas en el tablero), y otros.
• El juego no sólo “piensa” durante su turno, sino que también analiza jugadas mientras piensa el contrincante humano. Para ello, hace una hipótesis sobre la jugada que jugará el humano (“assumed”), y analiza jugadas a partir de esa hipótesis.
• Se permite alterar la posición de las piezas, para así llevar el tablero a una situación X desde la que se quiera continuar una partida.
• Se permite deshacer movimientos, por ejemplo, para rectificar errores; también se permite repetir movimientos.
• Guardar partidas a cinta o disco, y cargarlas de nuevo.
• Cambiar de bando. Pedir a Colossus que haga una jugada por ti.
• Que Colossus juegue contra sí mismo.
• Aplicar una base de datos de aperturas y finales de partida.
• Repetir una partida, en el sentido de reproducir todos los movimientos del registro de jugadas, desde el primero hasta el último.
• Modificar los parámetros de configuración del juego: si Colossus usa o no la base de datos de aperturas / finales, si Colossus “piensa” o no durante el turno del contrincante, la profundidad de análisis del árbol de jugadas, etc.
• Etc.

En definitiva, un juego completísimo e imbatido cuando se midió contra programas similares en otros equipos de 8 bits (Apple II, Spectrum, Atari, etc.).

Ahora que hemos intentado acercarnos un poco a la programación de este tipo de juegos, podemos hacernos una idea de la grandísima dificultad que suponen.

Ahora que ya hemos definido las tablas de historia, y sabemos manejarlas con las rutinas “newHistory”, “getHistory” e “incHistory”, vamos a usarlas. Esto se describen en los apartados siguientes:

Novedades en la rutina “thinkIter”:

En la rutina “thinkIter”, que es la que aplica la profundización iterativa, lo que vamos a hacer es inicializar las tablas de historia, para lo cual llamamos a “newHistory”:

Como se puede observar, después de preparar el proceso de búsqueda con “newPosition”, y antes de empezar la profundización iterativa que va desde X=0 hasta X=max_depth-1, aparece una nueva llamada a “newHistory”. Esta llamada es la que borra las tablas de historia.

Novedades en la rutina “search”:

Por otro lado, en la rutina “search”, tanto en la rama dedicada a la búsqueda del ratón “searchMouse”, como en la rama dedicada a la búsqueda de los gatos “searchCats”, aparecen sendas llamadas a “incHistory”:

La llamada a “incHistory” se produce después de llamar a “addHashPosMouse”, es decir, después de insertar el movimiento (admStart, admDest) en la tabla hash. Esta nueva llamada sirve para incrementar el valor de historia asociado al movimiento elegido, y el incremento puede ser de un punto o de tantos puntos como la profundidad “depth”, que es lo que está programado actualmente.

Novedades en la rutina “addMove”:

Esto ya es lo último, y consiste en generar los movimientos no con puntuación cero, como hasta ahora, sino con una puntuación igual a la de las tablas de historia:

De este modo, cuando los movimientos se desarrollan y prueban en “search”, debido a la llamada a “sort”, primero se desarrollan aquellos que tienen mayor puntuación.

Esta reordenación de movimientos debería tener un efecto positivo en la poda, en el sentido de podar más, pero no debería cambiar los movimientos que se deciden o eligen para cada tablero y para una profundidad dada.

En la práctica, sí puede haber pequeños cambios entre los movimientos que elige la versión del proyecto sin tablas de historia (versión 10) y los movimientos que eligen la nueva versión con tablas de historia (versión 11), pero siempre cambiando entre movimientos que dan lugar a tableros con la misma puntuación. Esto es, simplemente, un pequeño efecto secundario de la reordenación de movimientos.

Otras novedades:

Además de las novedades ya comentadas, hay algunas otras pequeñas novedades relacionadas con las tablas de historia, pero son de entidad menor:

• En el fichero “Display.asm” hay una nueva rutina “displayHistory” para mostrar el contenido las tablas de historia.
• En el fichero “Main.asm” hay un nuevo comando especial “.F” para mostrar el contenido de las tablas de historia. Llama a la rutina “displayHistory” anterior, y se usa para depuración.
• La rutina “addHashMove”, que suma #HASH_SCORE a la puntuación de los movimientos que están en las tablas hash, ahora aplica un tope de 255 ya que, al sumarse en ocasiones también los valores de las tablas de historia, podría superarse ese valor (acarreo).

Mejora en la poda:

El objetivo de todo esto de las tablas de historia es mejorar la ordenación de los movimientos y, por tanto, la poda. Por tanto, no deberíamos concluir esta sección sin comprobar si lo hemos logrado.

En la versión 10 del proyecto, con una profundidad de análisis de 8 niveles, ante el movimiento E1F2, el C64 analizaba $29F8 = 10.744 tableros, lo cual ya era un 40% menos que con la versión 9 ($4535 = 17.717 tableros).

Veamos ahora con las tablas de historia, es decir, con la versión 11 del proyecto:

Es decir, ahora se desarrollan $DCF = 3.535 tableros, lo cual es un 67% menos que con la versión 10 ($29F8 = 10.744) y un 80% menos que con la versión 9 ($4535 = 17.717). Como se puede ver, la reducción es muy notable.

---

Código del proyecto: RYG3-11

Las tablas de historia son una forma adicional de mejorar la ordenación de movimientos y, por tanto, la poda alfa – beta.

La idea básica es definir una tabla de doble entrada (origen, destino) o, lo que es lo mismo, 64 tablas (con 64 destinos cada una), una tabla por cada casilla origen. Por eso hablamos de “tablas de historia”.

Cada vez que un movimiento (origen, destino) se inserta en la tabla hash, además, se incrementa el valor (origen, destino) en la tabla de historia correspondiente. Ese incremento puede ser de un punto o, mejor, de tantos puntos como la profundidad de análisis a la que se produzca la inserción (“depth”).

Posteriormente, cuando la rutina “gen” genera los movimientos, en vez de nacer todos con puntuación 0, pueden nacer con una puntuación igual a la que figure en las tablas de historia.

En el fondo es algo como decir, “si este movimiento fue bueno en el pasado, es probable que vuelva a serlo ahora y, por tanto, voy a desarrollarlo antes”. No se trata de dar ese movimiento por bueno, o de seleccionarlo como mejor movimiento; se trata, simplemente, de desarrollarlo antes que otros confiando en que vuelva a ser bueno y que mejore la poda.

Por último, las tablas de historia pueden inicializarse al comienzo de la partida e ir dándoles valor y utilizándolas durante toda la partida o, según el caso, inicializarlas con cada nuevo movimiento o proceso de búsqueda. En un juego como el ratón y el gato no es probable que un movimiento que fue bueno hace N jugadas vuelva a ser bueno ahora, así que mejor inicializar las tablas de historia en cada proceso de búsqueda.

Desde el punto de vista del código ensamblador, las principales novedades se concentran en un nuevo fichero “History.asm”. Este fichero contiene:

• La definición de las 64 tablas de historia (una por cada casilla origen).
• Unos punteros para acceder a las tablas anteriores.
• La rutina “getHistory” que, dado un movimiento, consulta su puntuación en las tablas de historia.
• La rutina “incHistory” que, dado un movimiento, incrementa su puntuación en las tablas de historia.
• La rutina “newHistory” que inicializa las tablas de historia.

Todo esto se revisa a continuación:

Tablas de historia:

Hay 64 tablas de historia, una por cada casilla origen. Y cada tabla de historia tiene 64 posiciones, una por cada casilla destino. Es decir, las tablas de historia ocupan 64 x 64 = 4 KB.

Teniendo en cuenta que no todos los orígenes son posibles, ni tampoco todos los destinos, dado que el ratón y los gatos siempre se mueven por casillas negras (marcadas con “X”), las tablas de historia se podrían compactar. Sin embargo, por facilidad de programación, dado que las posiciones origen y destino se determinan con un índice entre 0 y 63, se van a mantener así.

Podríamos definir las 64 tablas una detrás de otra, en plan:

Sin embargo, esto daría bastante trabajo y ocuparía bastante espacio en el fichero “History.asm”. Por ello, vamos a usar una funcionalidad muy interesante de CBM prg Studio, que consiste en usar directivas:

Esto lo que viene a decir es:

• Empezando en index = 0.
• Y terminando en index = 63.
• Mete una tabla history_index, donde “index” se sustituye por su valor.

De este modo acabamos con 64 tablas de historia, desde history_0 (para la casilla origen 0) hasta history_63 (para la casilla origen 63). Cada tabla de historia tiene 64 destinos posibles.

Esto se puede comprobar fácilmente en el “assembly dump” al ensamblar con Ctrl + F5 desde CBM prg Studio:

Por tanto, hemos definido 64 tablas. Veamos cómo acceder a ellas.

Punteros para acceso a las tablas de historia:

Dado un movimiento (origen, destino), tendremos que acceder a la tabla de historia de ese origen, ya sea para incrementar o para leer el valor del destino en esa tabla.

Esto lo vamos a lograr con una técnica similar:

De este modo conseguimos dos tablas:

• Una llamada “histLo” con las partes low (partes menos significativas) de los punteros de acceso a las tablas de historia.
• Otra llamada “histHi” con las partes high (partes más significativas) de los punteros de acceso a las tablas de historia.

De este modo, accediendo a ese par de tablas usando la casilla origen como índice podemos fácilmente componer un puntero (lo, hi) para acceder a la tabla de historia correspondiente.

Aquí puede verse que al ensamblar con Ctrl + F5, efectivamente, se ha formado una tabla con las partes low (<) de los punteros y otra con las partes high (>):

Rutina “getHistory”:

Con las piezas anteriores resulta fácil leer o escribir en las tablas de historia. Por ejemplo, para leer el valor de historia del movimiento (start, dest) se utilizaría la rutina “getHistory”, que es así:

Esta rutina:

• Carga la posición origen “ghStart” en el índice Y.
• Usando Y / “ghStart” como índice, lee la parte low del puntero de acceso a la tabla de historia. Este valor lo graba en $fb.
• Usando Y / “ghStart” como índice, lee la parte high del puntero de acceso a la tabla de historia. Este valor lo graba en $fc.
• Carga la posición destino “ghDest” en el índice Y.
• Usando el direccionamiento indirecto – indexado (lda ($fb),y), es decir, usando $fb – $fc como puntero base y sumando Y / “ghDest”, accede al valor de historia.

En este caso el valor de historia se devuelve directamente en el acumulador, porque se va a usar desde ahí. En otras rutinas este valor se hubiera guardado en una variable “ghScore” o similar.

Rutina “incHistory”:

Para incrementar el valor de historia la rutina es muy similar a la anterior:

Las ideas son muy parecidas, es decir, se monta un puntero a la tabla de historia correspondiente con ($fb – $fc), siendo las principales diferencias:

• Se lee el valor de la tabla de historia con lda($fb),y, pero además se suma con adc la puntuación pasada en el parámetro “ihAdd”.
• Si el resultado de la suma excede $ff = 255, se topa a 255.
• El nuevo valor resultante se guarda en la tabla de historia con sta($fb),y.

En definitiva, se incrementa el valor de la tabla de historia en “ihAdd”, pero a su vez se pone un tope de $ff = 255.

Rutina “newHistory”:

La rutina “newHistory” sirve para inicializar las tablas de historia. Esto puede hacerse al comienzo de la partida o, como vamos a hacer, al comenzar el proceso de búsqueda alfa – beta.

Como se puede ver, esta rutina es un doble bucle:

• El bucle exterior va desde X=0 hasta X=63.
• Lo primero que hace es preparar un puntero ($fb – $fc) a la base de la tabla de historia X.
• El bucle interior va desde Y=0 hasta Y=63, es decir, recorre las 64 posiciones de la tabla de historia X.
• En cada una de esas 64 posiciones se almacena un 0 (sta($fb),y).

Esta rutina también se puede optimizar puesto que, como ya se ha dicho, hay posiciones (las casillas blancas o marcadas con “.”) que no se usan como origen ni como destino y, por tanto, no hace falta inicializarlas. Esto es especialmente cierto en el caso de las casillas origen, porque de forma directa te ahorras inicializar la mitad de las tablas de historia (porque no se usan).

Con esto acabamos la descripción de las tablas de historia, aunque ahora falta utilizarlas, cosa que ya haremos en la entrada siguiente.

---

Código del proyecto: RYG3-11

Si recordamos, en alguna entrada anterior introdujimos el concepto de “profundización iterativa”, que consiste en no buscar directamente a la profundidad de análisis configurada, sino empezar por profundidad uno, luego dos, luego tres, etc., hasta llegar a la profundidad configurada. Y todo ello con el objeto de mejorar la ordenación de los movimientos y, por tanto, optimizar la poda alfa – beta.

Aunque los movimientos se generen e inserten en “move_list” con un orden arbitrario, que en nuestro caso es y va a seguir siendo suroeste – sureste – noreste – noroeste (ver rutina “gen”), eso no quiere decir que esos movimientos tengan que desarrollarse en ese mismo orden. Pueden reordenarse en función del algún criterio antes de desarrollarlos recursivamente. Y esto es, precisamente, lo que vamos que vamos a hacer en esta entrada, de modo que saquemos provecho de la profundización iterativa.

Movimientos con puntuación:

Lo primero que vamos a hacer es asignar a los movimientos una puntuación, de modo que desarrollemos primero aquellos movimientos de mayor puntuación. Es importante no confundir la puntuación de los movimientos con la puntuación o evaluación de los tableros, que sirve para que elegir qué tableros son mejores.

De este modo, los movimientos de “move_list” pasan de tener un origen y un destino a tener un origen, un destino y una puntuación:

Como se puede ver, ahora los movimientos tienen:

• “move_list_start”: origen.
• “move_list_dest”: destino.
• “move_list_score”: puntuación (nuevo).

Por otro lado, la rutina que genera los movimientos permitidos a partir del tablero actual, es decir, la rutina “gen”, sigue generando los movimientos en el mismo orden (suroeste – sureste – noreste – noroeste), pero ahora los genera con una puntuación inicial de cero. Ver su subrutina “addMove”:

Esta puntuación inicial la modificaremos más adelante, de modo que podamos reordenar los movimientos y desarrollar primero los mejores, de modo que se optimice la poda.

Aprovechar la profundización iterativa:

Ahora es cuando por fin vamos a aprovechar la profundización iterativa. Si un movimiento ha sido bueno en alguna iteración anterior, por ejemplo, porque ha dado lugar a una poda alfa o beta, estará en la tabla hash desde esa iteración.

Por tanto, en las rutinas “searchMouse” y “searchCats”, después de generar los movimientos posibles con “gen”, vamos a llamar a una nueva rutina “hashMove”:

Esta nueva rutina “hashMove” hace esto:

Es decir, “hashMove” busca el tablero actual, aquel para el que “gen” ha generado los movimientos posibles, en la tabla hash de ratón o gatos, según el turno, y, si el tablero está en la tabla hash, llama a la rutina “addHashMove”:

La rutina “addHashMove”, por su parte, recorre los movimientos generados por “gen”, es decir, los movimientos posibles a partir del tablero actual, y, al que coincida con el movimiento almacenado en la tabla hash (hash_start, hash_dest), que se supone que es el mejor movimiento, le suma a su puntuación el valor “#HASH_SCORE”.

Dicho de forma sencilla, de todos los movimientos posibles a partir del tablero actual, si alguno está en la tabla hash proveniente de alguna iteración anterior (profundización iterativa), le sumamos “#HASH_SCORE” a su puntuación, lo que (en breve) va a hacer que se desarrolle antes.

“#HASH_SCORE” es una nueva constante definida en el fichero “Globals.asm” e inicialmente toma el valor de 10.

Ordenación de movimientos antes de desarrollarlos:

Los movimientos ya tienen una puntuación (“move_list_score”) y ya sabemos cuándo incrementamos su valor: cuando ese movimiento está en la tabla hash como consecuencia de una iteración anterior de la profundización iterativa.

Ahora falta, por fin, reordenar los movimientos, es decir, desarrollar primero los movimientos con mejor puntación. Esto lo hacemos también en “searchMouse” y “searchCats” con una llamada a la nueva rutina “sort”:

En cada iteración del bucle que prueba y desarrolla cada jugada, es decir, el bucle que empieza en la etiqueta “schMouseAgain” o “schCatsAgain”, vemos la llamada a “sort”:

“Sort” lo que hace es comparar la puntación de la jugada actual con la puntuación de todas las jugadas que quedan por probar / desarrollar y, si alguna tiene puntuación mayor, las reordena en “move_list”, para lo cual se apoya en la rutina auxiliar “shift” (ordenación por inserción):

De este modo, se prueban y desarrollan primero las jugadas con mayor puntuación que, de momento, son aquellas que la profundización iterativa ha decidido que son buenas. Luego se pueden añadir otros criterios para modificar la puntuación y la ordenación, como las tablas de historia.

Mejora en la poda:

Si todo lo que hemos dicho es cierto, que ordenar los movimientos de forma lógica favorece la poda, debería notarse este efecto al comparar la versión anterior del proyecto (versión 9) con la nueva versión (versión 10).

En la versión 9 del proyecto, con una profundidad de 8, se analizaban estos movimientos en la primera jugada de los gatos tras E1F2:

Es decir, se analizaban $4535 = 17.717 nodos. Recordemos que este es el número de nodos acumulado para los ocho niveles, no el valor específico para el octavo nivel.

Sin embargo, con la versión 10 del proyecto, que es la que ya tiene ordenación de movimientos, se analizan estos nodos (también para nivel 8, claro):

Como se puede observar, se han analizado $29F8 = 10.744, que es un 40% menos.

De hecho, una cosa que puede llamar la atención es que los movimientos elegidos no son el mismo. Con la versión 9 del proyecto era el H8G7, mientras que con la versión 10 es el B8A7. Ni la poda alfa – beta ni la ordenación de movimientos deberían tener este efecto. El origen del mismo radica en que en la versión 10 del proyecto se han hecho algunos ajustes en la rutina “search” cuando la puntuación retornada coincide con alfa o beta (cálculo del máximo o mínimo).

Con la versión 10 del proyecto, con una profundidad de 8 niveles o superior, jugando el humano con el ratón y el C64 con los gatos, yo no he conseguido ganarle, lo cual es muy buena noticia. A esa profundidad el C64 tarda menos de minuto y medio en decidir su siguiente jugada.

Por tanto, el proyecto está prácticamente terminado, aunque, por supuesto, admite muchas mejoras.

---

Código del proyecto: RYG3-10

Ahora que ya sabemos cómo mueve el C64 con la rutina “computerTurn”, lo siguiente es estudiar cómo mueve el humano con la rutina “humanTurn”:

Rutina “humanTurn”:

En primer lugar, la rutina “humanTurn” declara unos textos (“GO”, “HELP”, “NEW GAME”, etc.). Luego veremos en qué situaciones se usan:

A continuación, tenemos el bloque principal de “humanTurn”:

En este bloque principal:

• Se llama a la rutina “command”, que imprime “?“ apoyándose en la rutina del Kernal CHROUT (dirección $ffd2) y lee hasta cuatro caracteres apoyándose en la rutina del Kernal GETIN (dirección $ffe4). Estos cuatro caracteres se almacenan en las variables “command*”.
• Si el primer carácter (“command1”) es un punto (“.”), entonces se trata de un comando especial, y la ejecución continúa en la etiqueta “commands”.
• En caso contrario, se trata de un movimiento, y la ejecución continúa en la etiqueta “parse”.

Comandos especiales:

Los comandos especiales empiezan todos por punto, es decir, command1 = “.”. A partir de ahí, hay que analizar el segundo carácter para identificar de qué comando se trata. Y algunos comandos, incluso, aceptan un tercer carácter, como el comando “.DN” para fijar la profundidad de análisis o el comando “.TN” para fijar el tiempo máximo.

Los comandos soportados son:

• “.B” para mostrar el tablero.
• “.G” para arrancar el motor de juego.
• “.H” para mostrar la ayuda.
• “.M” para mostrar los movimientos posibles.
• “.N” para empezar una nueva partida.
• “.O” para parar el motor de juego.
• “.Q” para terminar y volver a BASIC.
• “.DN” para fijar la profundidad de análisis.
• “.TN” para fijar el máximo tiempo por jugada (no implementado).
• “.S” para que sea el turno del otro bando.
• “.U” para deshacer la última jugada.
• “.E” para mostrar el contenido de las tablas hash (depuración).

Se podrían definir otros comandos como, por ejemplo, mostrar los movimientos jugados desde el comienzo de la partida (tabla “game_list”), grabar esos movimientos a un fichero, cargarlos desde un fichero y continuar la partida, etc.

Casi todos los comandos se implementan igual:

• Se identifica el comando analizando la variable “command2”.
• A veces se muestra un texto de confirmación, por ejemplo, “GO”, para que el usuario sepa que el C64 le ha entendido. Estos son los textos apuntados por las variables “text*” que se mencionaron al comienzo de la rutina “humanTurn”.
• Se ejecuta la rutina que haga falta, por ejemplo, “displayBoard” para el comando “.B”. Si la rutina ya muestra algún texto, el texto de confirmación se suele obviar, puesto que no es necesario.

A modo de ejemplo, se comenta detalladamente la implementación del comando “.U”, que es uno de los más complejos, aunque todos son muy similares:

Como se puede observar, el comando “.U” o “undo”:

• Primero detecta que se trata del comando “undo”.
• Después imprime el texto apuntado por “textUndo”, es decir, imprime “UNDO”.
• Después carga en el acumulador el valor de “hply”, es decir, el número de jugadas de la partida.
• Si el número de jugadas es cero, termina, puesto que no hay ninguna jugada que se pueda deshacer.
• Si el número de jugadas es mayor que cero, carga el valor #PIECE_EMPTY en “computer_side”, es decir, para el motor de juego.
• Además, deshace la última jugada con la rutina “takeBack” y deja preparada la siguiente búsqueda inicializando “ply” y “first_move”.

De este modo, la ejecución de “E1F2” y luego “.U” tiene este resultado:

El resto de comandos tienen implementaciones muy similares, por lo que no los revisaremos todos aquí.

Movimientos:

La alternativa a los comandos son los movimientos. Los comandos empiezan por punto, los movimientos no. Y los movimientos ocupan cuatro caracteres, por ejemplo, “E1D2”.

Los movimientos se analizan y ejecutan a partir de la etiqueta “parse”:

Es decir, en primer lugar, llama a la rutina “parseMove”, que pasa de una cadena de caracteres a una pareja (command_start, command_dest), por ejemplo, de “E1D2” a (4, 11). En caso de que el movimiento no sea sintácticamente correcto, es decir, una letra de la A a la H y un número del 1 al 8 para el origen y otro tanto para el destino, “parseMove” devuelve ($ff, $ff).

Siguiendo con el código de “parse”:

• Verifica si “command_start” vale $ff.
• En caso afirmativo, el movimiento introducido por el usuario es sintácticamente incorrecto, y se ejecuta “parseKo”. Por tanto, se imprime “ILLEGAL” y termina. Se vuelve a pedir un comando o un movimiento al usuario.
• En caso negativo, el movimiento introducido por el usuario es sintácticamente correcto, pero aun así puede ser inválido. Por tanto, hay que verificar el movimiento, es decir, hay que comprobar que se trata de un movimiento válido. Por ello, se generan los movimientos permitidos con “gen” y se ejecuta “verifyMove”.
• La rutina “verifyMove” básicamente recorre los movimientos generados y almacenados en “move_list”, desde first_move(0) hasta first_move(1), y se comparan con (command_start, command_dest). Si alguno de los movimientos permitidos, es decir, almacenados en “move_list”, coincide con (command_start, command_dest), entonces se trata de un movimiento válido y se señaliza con vmOK = 0.

Si el movimiento es sintácticamente correcto, pero no es válido, entonces se ejecuta igualmente “parseKo”, es decir, se imprime “ILLEGAL” y se vuelve a pedir un comando o movimiento al usuario.

Por último, si se han superado todos los controles, es decir, si el movimiento es sintácticamente correcto y válido, se ejecuta “parseMove2”:

A partir de “parseMove2” lo que ocurre es:

• Se ejecuta el movimiento (command_start, command_dest) con la rutina “makeMove”.
• Se imprime el movimiento (command_start, command_dest) con dos llamadas a “algebraic”.
• Se inicializa “ply” y “first_move” para dejar preparado el siguiente proceso de búsqueda.
• Se vuelve a generar las jugadas posibles con “gen”, en previsión de que el humano quiera consultarlas con el comando “.M”.
• Se podría imprimir el tablero con “displayBoard”, igual que cuando mueve el C64, aunque ahora mismo lo tenemos comentado.
• Finalmente, se comprueba si es el final de la partida con “checkResult”, que es una de las rutinas vistas en la entrada anterior (verificaba si el ratón estaba acorralado o si estaba en la última fila).

De este modo, el intento de ejecución de un movimiento sintácticamente incorrecto sería así:

Por otro lado, el intento de ejecución de un movimiento sintácticamente correcto, pero inválido, sería así:

Y, por último, la ejecución de un movimiento sintácticamente correcto y válido sería así (añadimos el comando “.B” para ver el tablero resultante):

---

Código del proyecto: RYG3-09

Como hemos visto en la entrada anterior, el bucle de juego básicamente consiste en alternar los turnos del jugador uno y del jugador dos, ya que la variable “side” va cambiando de valor en cada iteración (ratón => gatos => ratón => gatos => …). Así hasta que el humano salga del juego con el comando “.Q”.

Y, aunque se ha visto que hay otras opciones, lo normal será que el C64 juegue toda la partida por un bando, por ejemplo, los gatos, y el humano juegue toda la partida por el otro bando, por ejemplo, el ratón.

Por tanto, lo que nos interesa ahora es revisar las rutinas “computerTurn” y “humanTurn”:

Rutina “computerTurn”:

La rutina “computerTurn” está en el fichero “Main.asm” y se encarga de que el C64 mueva. Tiene cuatro partes principales:

• Ejecutar la búsqueda alfa – beta con profundización iterativa.
• Localizar el movimiento decidido por la búsqueda.
• Comunicar el movimiento decidido y aplicarlo con “makeMove”.
• Verificar si la partida ha terminado.

La primera parte es así:

Es decir:

• Declara unas cadenas de texto que se usarán más adelante.
• Graba en la posición de “player” correspondiente a “side” (índice Y) que el C64 (#PLAYER_COMPUTER) está jugando por ese bando.
• Llama a “thinkIter”, que es donde está el grueso de la inteligencia.
• Incrementa el número de movimientos de “turns”.

La rutina “thinkIter” es la búsqueda alfa – beta con profundización iterativa. Por tanto, es el proceso que decide qué jugada debe hacer el C64.

Lo que puede que no esté muy claro a estas alturas es dónde queda la jugada decidida o elegida por el C64. Aunque no sea obvio del todo, esa jugada queda en las tablas hash después del proceso de búsqueda. Llega con buscar en las tablas hash a partir del tablero actual, y eso nos dará el mejor movimiento.

Por eso la segunda parte de “computerTurn” es así:

Es decir:

• Recalcula el hash y el lock del tablero actual con “getHash” y “getLock”.
• En función del bando por el que juega el C64, ratón o gatos, busca el tablero actual / hash actual en la tabla hash de ratón con “lookUpMouse” o en la tabla hash de gatos con “lookUpCats”.
• El resultado de esa búsqueda, que es el mejor movimiento a partir del tablero actual, se guarda en (hash_start, hash_dest).

Si “hash_start” (o “hash_dest”) vale $ff, el proceso de búsqueda no consiguió determinar un mejor movimiento. No será lo normal; más que nada es una previsión del programa. En ese caso se ejecutaría la rama “ctNoLegalMove”, que tampoco tiene mucho interés, ya que básicamente avisa al usuario y para el motor.

Si “hash_start” es distinto de $ff, entonces pasamos a la tercera parte de “computerTurn”:

En esta tercera parte, la rutina “computerTurn”:

• Muestra el texto “COMPUTER’S MOVE:” y el movimiento decidido (hash_start, hash_dest) en notación algebraica.
• Y ejecuta el movimiento elegido (hash_start, hash_dest) con “makeMove”.

Por último, la rutina “computerTurn”:

Es decir, por último, la rutina “computerTurn”:

• Inicializa “ply” y “first_move”, puesto que este proceso de búsqueda ha terminado, y hay que dejar preparado el siguiente.
• Vuelve a generar las jugadas posibles con “gen”, en previsión de que el humano quiera consultarlas con el comando “.M”.
• Muestra el tablero actualizado con “displayBoard”.
• Y llama a la nueva rutina “checkResult”.

La rutina “checkResult” también se llama desde el final “humanTurn”, y lo que hace es verificar si la partida ha terminado.

Rutina “checkResult”:

La rutina “checkResult”, que también es parte del fichero “Main.asm”, es así:

Por tanto, “checkResult” verifica a quien le toca mover ahora (recordemos que “makeMove” ya ha modificado “side” con la instrucción “eor #%00000001”) y:

• Si ahora ya le toca mover al ratón, es decir, si acaban de mover los gatos, verifica si el ratón puede mover o si está acorralado, llamando para ello a la rutina “mouseNoMoves”.
• Si ahora ya le toca mover a los gatos, es decir, si acaba de mover el ratón, verifica si el ratón ha llegado a la fila 7 con “mouseInRow7” y si los gatos no pueden mover con “catsNoMoves”.

Rutina “mouseInRow7”:

La rutina “mouseInRow7” es sencilla:

Básicamente lo que hace es revisar las casillas 56 a 63, es decir, la última fila, y verificar si el ratón está ahí. Si está en alguna de esas casillas imprime “*** MOUSE WINS!! ***” y ejecuta “newGame”, que se verá más adelante, pero que lógicamente prepara una nueva partida.

En caso contrario, la rutina “mouseInRow7” termina y “checkResult” continúa con otras verificaciones.

Rutinas “mouseNoMoves” y “catsNoMoves”:

Las rutinas “mouseNoMoves” y “catsNoMoves” son muy parecidas, casi idénticas. La única diferencia es el mensaje que se presenta en caso de que el ratón o los gatos no puedan mover:

Ambas rutinas:

• Leen el valor de la posición first_move(1). Recordemos que “first_move” es una tabla con punteros a “move_list”, concretamente con los puntos de entrada de “move_list” donde empiezan los movimientos a profundidad 1 (first_move(0)), a profundidad 2 (fisrt_move(1)), a profundidad 3 (first_move(2)), etc.
• Si el valor almacenado en first_move(1) es 0 o, lo que es lo mismo, si first_move(0) = first_move(1) = 0, es que no hay movimientos posibles. Por tanto, ambas rutinas terminan con un mensaje (“*** MOUSE WINS!! ***” o “*** CATS WIN!! ***”) y preparando una partida nueva llamando a “newGame”.
• En caso contrario, es decir, si sí hay movimientos posibles, entonces las rutinas terminan y “checkResult” continúa con otras verificaciones, si es el caso.

Gracias a todas estas rutinas que forman parte o son llamadas por “computerTurn” (“thinkIter” para ejecutar la búsqueda alfa – beta con profundización iterativa, “lookUp*” para localizar el mejor movimiento, “makeMove” para mover y “checkResult” para comprobar el final de partida), un movimiento del C64 tendría esta pinta:

---

Código del proyecto: RYG3-09

Hasta ahora hemos usado el programa principal, es decir, el fichero “Main.asm”, para probar las diferentes funcionalidades que íbamos desarrollando: la representación e impresión del tablero, la generación de jugadas, las tablas hash de movimientos, la función de evaluación, etc.

Ahora nos disponemos a desarrollar el programa principal definitivo:

Objetivos del programa principal:

Los objetivos de este programa principal serán:

• Ejecutar la configuración inicial del juego.
• Ejecutar el bucle de juego, que consiste en alternar los turnos del jugador uno y del jugador dos hasta que termine la partida.

Normalmente un jugador será el C64 y el otro será un humano, pero también es posible que el C64 o un humano jueguen por ambos bandos a la vez. Esto es muy interesante, porque significa que el C64 podrá jugar contra sí mismo. El humano también, pero para esto casi es más práctico tomar un tablero y unas fichas de verdad 🙂 .

Tanto el C64 como el humano podrán jugar por el bando del ratón o los gatos o, incluso, por ambos, como ya se ha dicho.

Cuando sea el turno del C64, da igual que juegue por el ratón o los gatos, el objetivo será ejecutar la búsqueda alfa – beta hasta la profundidad de análisis configurada, aplicar la jugada elegida, y verificar si es el final de la partida.

Cuando sea el turno del jugador humano, da igual que juegue por el ratón o los gatos, el objetivo principal será aceptar el movimiento del humano, verificar que es un movimiento válido, aplicar el movimiento del humano, y verificar si es el final de la partida.

En caso de que sea el turno del humano, además, se aceptarán una serie de “comandos especiales” para funciones como:

• Mostrar el tablero.
• Arrancar o parar el motor de juego.
• Mostrar la ayuda.
• Mostrar los movimientos válidos.
• Empezar una partida nueva.
• Salir del juego.
• Configurar la profundidad de análisis.
• Configurar el tiempo máximo por movimiento (mejora).
• Cambiar el turno.
• Deshacer la última jugada.
• Etc.

En particular, esta opción de que el humano meta “comandos especiales” puede resultar muy útil para imprimir información que facilite la depuración del programa, como el contenido de las tablas hash, el contenido de las tablas de historia (se verán más adelante), etc.

Algunas variables importantes:

Antes de revisar el programa principal, veamos algunas variables importantes:

Estas variables se usan para lo siguiente:

• “computer_side”: Permite parar el motor de juego (computer_side = #PIECE_EMPTY), arrancarlo para que el C64 juegue por el ratón (computer_side = #SIDE_MOUSE), y arrancarlo para que el C64 juegue por los gatos (computer_side = #SIDE_CATS).
• “player”: Sirve para llevar control de quién juega por el ratón (valor almacenado en player[#SIDE_MOUSE = 0]) y por los gatos (valor almacenado en player[#SIDE_CATS = 1]). Ambos pueden ser el humano (#PLAYER_HUMAN = 0) o el C64 (#PLAYER_COMPUTER = 1).
• “fixed_time” y “fixed_depth”: Sirven para configurar que el juego juegue a un tiempo fijo por jugada (fixed_time = 1), a una profundidad fija por jugada (fixed_depth = 1), o a ambas cosas, es decir, a la limitación que salte antes (tiempo límite o profundidad límite). De momento sólo está implementada la opción de profundidad fija.
• “max_time” y “max_depth”: Sirven para configurar el tiempo máximo en minutos por jugada y la profundidad máxima en niveles. De momento sólo se utiliza “max_depth” puesto que sólo está implementada esa opción.
• “turns”: Sirve para llevar cuenta del número de jugadas ejecutadas. En realidad, sólo cuenta las jugadas ejecutadas por el C64. Se podrían contar también las jugadas del humano, caso de quererse así.
• “command1” … “command4”: Sirven para almacenar los movimientos y los “comandos especiales” que introduzca el jugador humano. Los movimientos pueden tener hasta 4 caracteres, por ejemplo “E1D2”, que se almacenan respectivamente en command1, 2, 3 y 4.
• “command_start” y “command_dest”: Cuando el comando del jugador humano sea un movimiento del tipo “E1D2”, “E1” se traducirá por la casilla 4, que se almacenará en “command_start”, y “D2” se traducirá por la casilla 11, que se almacenará en “command_dest”. De este modo la información queda lista para ejecutar la rutina “makeMove”.

Todas estas variables controlan el funcionamiento del programa principal.

Programa principal definitivo:

El nuevo programa “main” del fichero “Main.asm” queda así:

Es decir:

• Primero ejecuta la configuración inicial llamando a la rutina “setup”.
• A partir de ahí, entra en el bucle de juego, que sólo termina cuando el jugador humano teclea el comando especial “.Q”. Los comandos especiales empiezan siempre por punto (“.”).
• Es posible jugar varias partidas seguidas sin salir del programa.

Veamos cómo son la configuración inicial y el bucle de juego.

Configuración inicial:

La configuración inicial es la rutina “setup”, que ya está en el programa principal desde hace un par de versiones. La nueva rutina “setup” es así:

Es decir, la nueva rutina “setup”:

• Configura las tablas aleatorias con “fixedHash” (para depuración) o con “randomize” (para valores aleatorios).
• Inicializa la partida con la rutina “initBoard”.
• Con la rutina “gen”, genera los movimientos posibles desde la posición inicial. De este modo, se podrían mostrar con el comando especial “.M”.
• Mete el valor #PIECE_EMPTY en “computer_side”, de modo que el motor de juego no arranca automáticamente, sino que hay que arrancarlo manualmente con el comando especial “.G”.
• Inicializa “player”, porque de momento no se sabe quién va a jugar por cada bando, si el C64 o el humano.
• Fija el tiempo máximo por jugada en 5 minutos, aun cuando está función de jugar a tiempo fijo no está desarrollada del todo. Implicaría utilizar interrupciones del CIA1. Este tiempo se puede cambiar con el comando especial “.TM”, donde M es el número de minutos.
• Fija la profundidad de análisis a 4 niveles. Esta profundidad también se puede cambiar con el comando especial “.DN”, donde N es el nuevo nivel de profundidad.

Veamos ahora el bucle de juego.

Bucle de juego:

El bucle de juego es esta parte específica del programa principal (inicialización con “setup” aparte):

Como se puede ver:

• Compara el bando al que le toca mover, que está en “side”, con el bando por el que juega el C64, que está en “computer_side”.
• Si son iguales, es decir, si le toca mover al ratón y el C64 juega por el ratón, o si le toca mover a los gatos y el C64 juega por los gatos, entonces ejecuta “computerTurn”. Como veremos más adelante, “computerTurn” básicamente ejecuta la profundización iterativa, es decir, “thinkIter”.
• Por el contrario, si son distintos, es decir, si le toca mover al ratón y el C64 juega por los gatos, o al revés, entonces ejecuta “humanTurn”. Esto permite que el jugador humano mueva o ejecute un “comando especial”.
• El punto anterior tiene un caso especial, que es cuando “computer_side” vale #PIECE_EMPTY, que es su valor inicial. Esto significa que el C64 de momento está parado, que no juega ni por el ratón ni los gatos. En este caso, es imposible que “side” y “computer_side” sean iguales, puesto que “side” sólo puede valer ratón o gatos, así que en este caso siempre se ejecuta “humanTurn”. Es decir, cuando el motor está parado sólo puede mover o ejecutar comandos el humano. Todo ello hasta que se arranque el motor con el comando “.G”, que básicamente lo que hace es darle un valor a “computer_side”.

Gracias a este bucle de juego tan flexible es posible arrancar el juego con “RUN”, que ejecuta el cargador BASIC “10 SYS 2080”, y hacer cosas como:

• Mostrar el tablero con “.B”:

• Mover por el ratón con “E1F2”:

• Volver a mostrar el tablero con “.B”:

• Pedirle al C64 que mueva por los gatos con “.G”:

• Volver a pedirle al C64 que mueva, ahora por el ratón, con “.G”:

• Pedir los movimientos posibles con “.M”:

• Mover ahora por los gatos con “F8E7”. Como el motor está arrancado, el C64 vuelve a mover automáticamente por el ratón con “E3D4”:

• Parar el motor con “.O”:

• Volver a pedir los movimientos posibles con “.M”.

• Volver a mover por los gatos con “D8C7”. Como el motor ahora está parado, el C64 no mueve automáticamente por el ratón:

• Volver a mostrar el tablero con “.B”:

• Salir del juego con “.Q”:

Lógicamente, lo normal será que el C64 juegue por un bando y el humano por otro, pero un bucle de juego como éste permite todo tipo de opciones y cambios.

---

C´´odigo del proyecto: RYG3-09