El ratón y los gatos

Juegos de tablero hay muchos: go, ajedrez, damas, Othello / Reversi, etc. Y, lógicamente, cuanto más complejo sea el juego, más compleja será su programación.

Como se trata de ejemplificar las técnicas de programación ya citadas, optaremos por un juego sencillo: el ratón y los gatos. Se trata de un juego que se juega sobre un tablero de 8 x 8, igual que el ajedrez. Un bando dispone de un ratón y el otro de cuatro gatos. El ratón se representa como un peón blanco y los gatos como cuatro peones negros.

El ratón puede moverse hacia delante o hacia atrás. Se mueve en diagonal y puede avanzar o retroceder sólo una casilla en cada movimiento:

Los gatos pueden moverse sólo hacia delante. También se mueven en diagonal y pueden avanzar sólo una casilla en cada movimiento:

El objetivo del juego es, para el ratón, llegar a la última fila, y para los gatos, acorralar al ratón. No hay capturas, es decir, no se puede comer.

La posición inicial es ésta, con las cinco piezas sobre casillas negras. Empieza moviendo el ratón:

Una vez descrito el juego, lo primero es ver cómo representar el tablero en memoria del C64.

A la segunda va la vencida: un juego de tablero

Como sabréis los seguidores del blog “Programación Retro del Commodore 64” (https://programacion-retro-c64.blog) y de los libros asociados, desde abril de 2020 hasta febrero de 2021, aproximadamente, he desarrollado un proyecto para programar un juego de tablero para el C64.

El proyecto estaba bastante avanzado, a mi entender, siendo la principal cuestión pendiente el desarrollo de un procedimiento de poda que permitiera analizar menos tableros y conseguir mejor rendimiento.

Desde entonces, y ha pasado casi un año (ahora es enero de 2022), apenas he tenido tiempo que dedicarle. Lo que sí he podido hacer, en cambio, ha sido leer bastante sobre programación de juegos de ajedrez. En particular, me han interesado mucho estos libros de Bill Jordan, informático y maestro de ajedrez:

  • “The joy of chess programming”.
  • “How to write a chess program”.
  • “How to write a JavaScript chess engine”.

El segundo es el que me parece el más práctico de los tres (programación en C++). Todos ellos están disponibles en Amazon junto con muchos otros libros de Bill Jordan sobre ajedrez y/o programación.

La cuestión es que he aprendido técnicas de programación interesantes que son aplicables al ajedrez, a las damas, al Othello, al ratón y los gatos, y a casi cualquier juego de tablero que nos podamos plantear.

Por tanto, me dispongo a revisar el proyecto de implementar un juego de tablero en ensamblador del C64 aplicando estas técnicas. Para aquellos que todavía tengan interés en el proyecto antiguo, he recogido sus entradas en este PDF.

El nuevo proyecto está terminado y funciona bien, así que ya sólo es cuestión de describirlo. Las técnicas principales que vamos a revisar son:

  • 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.

Vamos a por ello…

Y más libros todavía…

La programación retro está de moda. No paran de publicarse libros y más libros.

Uno de los primeros libros que os recomendé hace tiempo es «Retro Game Dev», de Derek Morris:

DerekMorris1

Lógicamente, el libro me gusta. Si no fuera así no lo recomendaría. No obstante, se le pueden buscar algunas pegas:

  • Está en inglés, aunque esto no es mayor problema para los que conozcan el idioma de Shakespeare.
  • Es muy sucinto (120 páginas). Va al grano, quizás demasiado al grano.
  • Apenas le dedica tiempo o espacio a la programación del 6502/6510, a las capacidades del C64, o al CBM prg Studio.
  • Básicamente es la descripción de cómo programar dos juegos, uno de naves y otro de plataformas. Pero se apoya en unas librerías de macros desarrolladas ad-hoc para esos juegos, y el libro no las describe, lo que significa que el lector tiene que hacer un esfuerzo importante en revisar código ensamblador para entender de verdad los juegos.
  • Todo esto hace que no sea un libro para empezar desde nivel cero o bajo.

En todo caso, ya digo, es un libro recomendable.

Pues bien, hoy me he enterado de que Derek ha sacado el volumen II, que estaba en proyecto desde hace bastante tiempo:

DerekMorris2

El proyecto inicial tenía prevista una primera parte dedicada a la programación del 6502/6510, que muchos de los lectores echamos en falta en el volumen I. No obstante, por lo que veo en la tabla de contenidos y en el tamaño (150 páginas), parece que finalmente tampoco será así.

En todo caso, el contenido anunciado es muy interesante, porque parece que se centra en técnicas avanzadas de programación del C64:

  • VS Code y Kick Assembler
  • Depuración y perfilado
  • Interrupciones Raster
  • Multiplexación de sprites
  • Diseño de sprites y caracteres
  • Música con el SID
  • Codificación de juegos
  • Multipantallas

El precio podía estar más ajustado (17 euros en blanco y negro, 25 en color), pero yo ya he encargado el mío…

Nuevo libro de RetroProgramming Italia

Nuestros colegas de RetroProgramming Italia están publicando una serie de libros muy interesantes sobre programación retro de 8 bits.

El primer volumen, dedicado a la programación de los micros 65xx, ya está publicado, y se puede comprar tanto en formato papel como ebook en Lulu.com:

Libro RPI

Se trata de una edición de alta calidad y fruto de los muchos años de experiencia de este conocido foro.

Otro libro interesante

Hace un par de meses me compré el libro «Commodore 64 Exposed». Por lo visto, es un libro de 1983 que se ha reeditado ahora con la fiebre de la programación retro.

C64 Exposed

El libro está bien. Son algo menos de 200 páginas en las que se tratan:

  • La programación en BASIC.
  • Los comandos de BASIC.
  • Técnicas avanzadas en BASIC.
  • Sonido.
  • Gráficos.
  • Código máquina.
  • Dispositivos externos.
  • Apéndices.

Como os imagináis, con esa extensión y variedad de temas, los asuntos tampoco los puede tratar en mucha profundidad. Casi todo lo ahí mencionado (código máquina, sonido, gráficos, etc.), quitando la parte inicial de BASIC, lo encontraréis tratado con mucho más detalle en este blog y sus libros asociados (volumen I y volumen II).

Lo que sí me ha llamado la atención, porque no lo conocía, es el formato en que se almacenan en memoria los programas en BASIC. Aparece descrito en la página 45. El formato es así (para cada línea del programa):

  • Dos bytes para la dirección en memoria de la siguiente línea. Si valen $0000 es el final del programa.
  • Dos bytes para el número de línea BASIC.
  • El texto de la línea BASIC. Los comandos están tokenizados, es decir, se convierten a unos códigos (ej. $9e para SYS). Lo demás, se almacena tal cual en codificación PETSCII.
  • Un byte $00 para marcar el fin de línea.

Todo esto es fácil de comprobar arrancando VICE, introduciendo un programa BASIC, arrancando el monitor con ALT + M, y revisando las posiciones de memoria $0801 y siguientes.

BASIC

Que lo disfrutéis si os animáis a leerlo.

RetroProgramming Italia – RP Italia

Recientemente he descubierto un grupo que me parece muy interesante. Se trata de RetroProgramming Italia – RP Italia. Es el primer grupo italiano que se ocupa de la programación retro de todos los ordenadores de 8 y 16 bits y, en particular, de nuestro querido Commodore 64.

Os dejo su dirección de Facebook:

https://www.facebook.com/groups/retroprogramming/?ref=share

Se trata de un grupo privado, por lo que deberéis solicitar uniros al grupo.

Aunque las entradas lógicamente están escritas en italiano se entienden bastante bien. Y además el BASIC y el ensamblador del 6510 son lenguajes universales 😉 .

¡¡Que lo disfrutéis!!

Programación del C64… ¿online? ¿Y en C?

Hoy voy a hacer un pequeño paréntesis en lo que nos ocupa últimamente (juegos de tablero). He descubierto un sitio que seguramente lleva unos años en línea, pero que yo he encontrado recientemente y que me ha parecido interesante: 8bitworkshop.

8bitworkshop es un sitio web que permite programar en ensamblador y en C para varias máquinas de 8 bits y, entre ellas, nuestro querido Commodore 64.

Una primera cosa curiosa es que la programación es online, es decir, directamente en el sitio web y con en el navegador. Esto no me parece especialmente interesante. De hecho, me parece que incluso puede ser poco práctico a la hora de abordar proyectos medianos y grandes.

Lo que sí me parece muy interesante es que, según programas en ensamblador, se va generando automáticamente el código máquina, es decir, se va ensamblando. Todavía más, el efecto que tu programa pudiera tener sobre la pantalla del C64 ($0400 – $07e7) también se actualiza instantáneamente:

8bitworkshop

Esto hace que sea una herramienta muy interesante para prototipos rápidos.

Otra cuestión que me ha parecido muy interesante es que no sólo permite programar en ensamblador. También permite programar en C para el C64:

8bitworkshop - C

Esto tampoco es nuevo, ya que hace tiempo que existe https://www.cc65.org/, que es un compilador cruzado de C para el 6502. Se puede ejecutar sobre sistemas Windows, Linux y otros.

Pero, pensándolo bien, no me parece ninguna tontería. El ensamblador es rápido y potente, pero es complejo. Por su parte, el BASIC es mucho más sencillo, pero se queda escaso y es muy lento.

Sin embargo, el C podría conjugar las virtudes de ambos mundos. Es un lenguaje de alto nivel, pero es compilado (no interpretado como el BASIC). Por tanto, es mucho más rápido. Es más estructurado que el BASIC, que apenas admite estructura, tiene más tipos de datos, etc.

Pero es que además C permite acceder fácilmente a la memoria, ya que tiene punteros y operadores para obtener las direcciones de posiciones de memoria. Esto es esencial para máquinas como el C64, en las que el manejo de gráficos, sonido y entrada/salida requiere un conocimiento profundo del mapa de memoria y el acceso a los chips especiales que se encuentran ahí «mapeados».

Hará unos 25 años que no programo en C, pero en cuanto pueda le daré un tiento sobre el C64…

Ensambladores, desensambladores, simuladores y monitores

Releyendo el libro “The machine language book of the Commodore 64” de Lothar Englisch he recordado algunas cosas de interés:

Hoy en día solemos trabajar con ensambladores cruzados (cross assemblers), es decir, programas que se ejecutan en Windows, Linux o Mac y que generan código máquina para el C64. Hay varios ejemplos: CBM prg Studio, Kick Assembler, ACME Cross-Assembler, etc.

En los 80, lógicamente, también se trabajaba con ensambladores, desensambladores y simuladores, pero, a diferencia de lo que hacemos hoy en día, aquellos programas se ejecutaban en C64 y generaban código máquina también para C64. Algunos estaban programados en BASIC (como los del libro “The machine language book of the Commodore 64”) y otros en código máquina. Algunos eran ensambladores, desensambladores o simuladores puros, y otros tenían mezcla de varias funciones. Y, entre ellos, uno de los que más me gustaba era Machine Lightning, aunque nunca llegué a dominarlo ni de lejos.

Machine Lightning

Y luego había un tipo especial de programas que se llamaban “monitores” o “monitores de código máquina”. Su función es un poco difícil de explicar porque, como digo, estos programas normalmente mezclaban varias funciones:

  • Ensamblador: Un ensamblador es un programa que permite escribir programas en ensamblador y ensamblarlos, es decir, generar el código máquina. Esta es su función principal, pero luego hay otras funciones accesorias: grabar y cargar código ensamblador (fuente), grabar y cargar código máquina (objeto), etc. Sería el equivalente a un compilador en un lenguaje de alto nivel.
  • Desensamblador: Un desensamblador es un programa que recibe un rango de posiciones de memoria, lee el código máquina ahí almacenado, y genera el código ensamblador. Sería el equivalente a un decompilador en un lenguaje de alto nivel.
  • Simulador: Un simulador es un programa que recibe un programa en código máquina y simula su ejecución, viendo el efecto que la ejecución tendría sobre los registros del microprocesador y/o la memoria. La ejecución puede ser simulada o real, instrucción a instrucción o varias instrucciones de golpe, etc. Permite cambiar el contenido de los registros y/o posiciones de memoria, etc. El equivalente en un lenguaje de alto nivel sería un depurador.
  • Monitor: Un monitor es parecido a un simulador / depurador. También recibe un programa en código máquina y permite su ejecución (en este caso real, no simulada), así como ver el estado del microprocesador y la memoria, y cambiarlos. La principal diferencia, además de que la ejecución es real y no simulada, es que utiliza interrupciones por software. Es decir, utiliza la instrucción BRK a modo de punto de ruptura. Cuando esta instrucción se encuentra en el programa a ejecutar (normalmente introducida artificialmente con el objeto de depurar), se produce una interrupción, y pasa a ejecutarse el monitor. Esto permite al usuario / programador revisar el estado del microprocesador y la memoria, cambiar su estado, cargar o grabar programas, desensamblar zonas de memoria, rellenar zonas de memoria con valores, etc.

Uno de los monitores más conocidos en su día era Supermon64 de Jim Butterfield:

Supermon

VICE actualmente también tiene su propio monitor (accesible con ALT + M):

Monitor VICE

Finalmente, el cartucho Final Cartridge y el ensamblador Machine Lightning también tenían su monitor. Machine Lightning, además, incluía programas para diseño de gráficos, así como librerías de rutinas en código máquina para el manejo de los mismos:

Machine Lightning 3¿No es increíble la cantidad de herramientas que había y lo potentes que eran?

Algunos libros clásicos

Os presento mis últimas adquisiciones, dos libros clásicos:

Dos libros

El primero es el libro “Mapping the Commodore 64” de Sheldon Leemon. Se trata un mapa de memoria del C64, es decir, de una descripción de la memoria del C64 posición de memoria a posición de memoria.

Es un libro muy interesante porque, como hemos comentado muchas veces, para programar el C64 no es suficiente con saber ensamblador del 6510. Además, hay que conocer bien el mapa de memoria, es decir, en qué posiciones se ubica qué. Por ejemplo, hay que conocer los registros del VIC, del SID o de los CIAs.

En principio, es un libro de referencia o consulta, pero se lee con facilidad. Las partes que puedan resultar un poco más arduas, o menos interesantes, por ejemplo, el intérprete de BASIC, se leen con menos profundidad y ya está.

El segundo es “The machine language book of the Commodore 64” de Lothar Englisch. Es la versión americana de la edición que en su día publicaron Data Becker y Ferré Moret para España:

Data Becker

Me hubiera encantado encontrar la edición española, que es la que me leí hace treinta años, pero me ha resultado imposible.

En todo caso, el contenido de ambas ediciones es el mismo, y gira en torno al ensamblador del 6510. Incluye algunos temas dedicados a un ensamblador (programa para ensamblar, no el lenguaje), un simulador (hoy lo llamaríamos depurador o debugger), un desensamblador, etc., que seguramente en su día tendrían sentido, pero que hoy en día ya no tienen mucho sentido con las modernas herramientas de que disponemos (ej. CBM prg Studio).

Por supuesto, me lo voy a leer, porque para eso me lo he comprado, y además la nostalgia me puede, pero me da la impresión de que para aprender ensamblador del 6510 seguramente esté mejor “Assembly Language Programming with the Commodore 64” de Marvin L. De Jong:

De Jong

En definitiva, libros clásicos e interesantes que se pueden coleccionar (se venden por Internet, aunque son carillos) o disfrutar en línea (ver Archive.org).