Inicialización e impresión del tablero

Ahora que ya sabemos cómo representar el tablero en la memoria del C64 los siguientes pasos van a ser inicializar el tablero y “pintarlo”.

Inicializar el tablero es colocar sobre él el ratón y los gatos en su posición inicial. Esto es necesario para empezar el juego.

E imprimir el tablero es hacer una representación del mismo en la pantalla del C64, de momento en modo texto. Esto será necesario casi para cualquier cosa, por ejemplo, para depurar los programas.

Todo esto lo vamos a hacer en una versión inicial del programa que iremos sofisticando de manera incremental. De momento, nos llega con cuatro ficheros *.asm:

  • “Globals.asm”: Recoge las constantes como el valor de las piezas, las direcciones de movimiento, los bandos (ratón o gatos), etc.
  • “Init.asm”: Recoge las variables y estructuras de datos principales, como el tablero, el bando que mueve, la profundidad de análisis, el número de nodos / tableros analizados, etc.
  • “Display.asm”: Recoge todo lo que tiene que ver con la impresión por pantalla.
  • “Main.asm”: Es el programa principal. En este primer paso, va a inicializar el tablero y pintarlo.

Inicialización del tablero:

Para inicializar el tablero nos apoyaremos en una tabla como ésta (etiqueta “init_board”):

Obsérvese que tiene un 0 (PIECE_MOUSE) sobre el índice 4 (casilla E1), un 1 (PIECE_CAT1) sobre el índice 57 (casilla B8), un 2 (PIECE_CAT2) sobre el índice 59 (casilla D8), un 3 (PIECE_CAT3) sobre el índice 61 (casilla F8), un 4 (PIECE_CAT4) sobre el índice 63 (casilla H8), y un 6 (PIECE_EMPTY) sobre el resto de casillas.

Pues bien, para inicializar el tablero simplemente definimos una rutina que recorra “init_board”, lea la pieza que hay almacenada en cada casilla, y la escriba en el tablero “board”. Se trata de la rutina “initBoard”:

Además de lo ya mencionado (copiar el tablero inicial sobre “board”), también hace otras labores de inicialización de la partida:

  • Mete el valor “SIDE_MOUSE” en la variable “side”, puesto que el primer bando que mueve al comienzo de la partida es el ratón.
  • Mete cero en “ply” y “hply”. Estas variables controlan la profundidad del árbol de jugadas que se está analizando (“ply”) y el número de movimientos jugados desde el comienzo de la partida (“hply”).
  • También mete cero en “first_move”. Esto es como decir que de momento no hay movimientos generados.

Bueno, pues ya está. Tenemos una rutina que inicializa el tablero y, más en general, para inicializar la partida.

Impresión del tablero:

Para imprimir el tablero inicialmente buscamos una representación de este tipo:

Es decir, primero las letras “ABCDEFGH”, luego las ocho filas del tablero, y finalmente las letras “ABCDEFGH” de nuevo. Los gatos los representaremos con una “C”, aunque podríamos usar letras distintas porque somos capaces de distinguirlos, el ratón con una “M”, las casillas blancas con un “.”, y las casillas negras con una “X”.

Más adelante podemos buscar una representación más sofisticada usando caracteres personalizados o, incluso, sprites.

La impresión la resolvemos con la rutina “displayBoard”, que sigue el mismo esquema anterior:

  • Imprime las letras con la rutina “displayLetters”.
  • Imprime las ocho filas con la rutina “displayRow”.
  • Vuelve a imprimir las letras con la rutina “displayLetters”.
  • E imprime algunos datos adicionales con la rutina “displayOther” (el bando al que le toca mover, la profundidad de análisis actual “ply”, y el número de movimientos de la partida “hply”).

A su vez, las rutinas anteriores se apoyan en las rutinas auxiliares:

  • “displaySq” para imprimir una casilla, ya sea “M” si contiene el ratón, “C” si contiene un gato, o “X” / “.” si está vacía.
  • “displayHex” para imprimir un número en formato hexadecimal.
  • “displayText” para imprimir un texto, ya sea “ABCDEFGH” o cualquier otro texto.

Programa principal:

El programa principal lo iremos complicando poco a poco, igual que los demás programas. De momento, nos vale para probar lo ya programado (inicialización e impresión del tablero) e ir construyendo sobre esa base:

Total, si ensamblamos, cargamos y ejecutamos vemos esto:

El siguiente paso será empezar a generar jugadas.


Código del proyecto: RYG3-01

Representación del tablero

Hay muchas formas de representar el tablero en la memoria del C64. Quizás la más natural o intuitiva sería hacerlo como una matriz de 8 x 8, cuyos valores representen el contenido de las casillas (0 = vacía, 1 = ratón, -1 = gato). De este modo, el tablero inicial se representaría así:

Ahora bien, la memoria del C64 –y la de todos los ordenadores– es lineal, en el sentido de que las posiciones de memoria van una detrás de otra según va creciendo la dirección ($0000 – $ffff). Por ello, para el ordenador es más natural almacenar o representar el tablero como un vector o tabla de 64 posiciones.

Y como en ajedrez se considera que la primera casilla es la A1 y la última es la H8, eso nos da estos índices del 0 al 63:

Es decir, la tabla de 64 posiciones tendría la siguiente pinta en memoria (0 = vacía, 1 = ratón, -1 = gato):

[0, 0, 0, 0, 1, 0, 0, 0] … [0,-1, 0,-1, 0,-1, 0,-1]

Por último, la forma de representar las piezas, por ejemplo, 0 para casilla vacía, 1 para ratón y -1 para gato, es arbitraria. Podemos elegir la que más nos guste.

En el caso de juegos como el ajedrez en que hay dos bandos, pero las piezas de los bandos son iguales, puede resultar natural usar el signo para indicar si una pieza es blanca o negra (ej. +1 = peón blanco y -1 = peón negro). Todavía más, se pueden elegir unos números u otros para representar el valor relativo de las piezas, por ejemplo, +1/-1 para peones, +3/-3 para caballos, +4/-4 para alfiles, +5/-5 para torres, +9/-9 para damas y +10/-10 para reyes. No es lo habitual; más bien se suelen elegir unos números arbitrarios que permiten distinguir las piezas y punto. Ya se encargará la función de evaluación de hacer la valoración material.

En el caso que nos ocupa, aunque tanto ratón como gatos se “pintan” como peones (o como se quiera), no se trata de las mismas piezas. Los gatos se mueven de una manera y el ratón de otra. Por tanto, casi es más lógico usar números diferentes y no usar el signo.

Todavía más, aunque el bando de los gatos tiene cuatro gatos, y todos se mueven igual, si queremos ser capaces de distinguirlos, en el sentido de saber cuál es el gato 1, cuál es el 2, cuál es el 3 y cuál es el 4, independientemente de dónde se ubiquen en el tablero, necesitaremos números distintos para ellos.

Por último, está el tema de la casilla vacía. Parece que lo más natural es usar el 0 para esto. Sin embargo, a la hora de programar será habitual manejar tablas que, para cada tipo de pieza, nos den su valor o sus movimientos. Y como las tablas empiezan en el índice 0, casi mejor reservar ese número para la primera pieza.

Total, al final vamos a representar el tablero así:

  • Valores 0 a 6 para las piezas (constantes “PIECE_*”):
  • Y tabla de 64 posiciones para el tablero (etiqueta “board”):

Por increíble que parezca… ¡¡se puede resolver el juego con un único tablero de 64 bytes!!

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…