Programación Retro del Commodore 64

Es improbable que dos tableros distintos, es decir, con el ratón y/o los gatos en posiciones distintas, den lugar al mismo hash. Es improbable porque, en función de las piezas y sus posiciones, se consultan unas posiciones u otras de las tablas generadas aleatoriamente (“hash_*”) y, por tanto, se utilizan números diferentes para el OR exclusivo. Sin embargo, aunque improbable, no es imposible.

Esto es lo que se llama una “colisión”. Si dos tableros distintos dan lugar al mismo hash, a la hora de insertar el mejor movimiento asociado en la tabla hash (“hashpos_*”), se producirá una colisión, puesto que ambos movimientos se almacenarán en la misma posición de la tabla hash. El que se almacene en segundo lugar “machacará” al que se haya almacenado en primer lugar.

Lógicamente, que haya colisiones no es bueno para el funcionamiento del programa. Las tablas hash valen para almacenar y consultar el mejor movimiento asociado a un tablero. Por tanto, si se producen colisiones esa información se pierde para algunos tableros al sustituirse por la de otros tableros que tienen el mismo hash. Peor que perderse, se sustituye por otra información posterior. Es decir, el programa puede tomar decisiones incorrectas sobre los movimientos a realizar.

Hay técnicas para resolver las colisiones, como se puede ver en https://es.wikipedia.org/wiki/Tabla_hash#Resoluci%C3%B3n_de_colisiones. Y también hay técnicas para reducir la probabilidad de que ocurran sin llegar a reducirla a cero.

Una primera técnica consiste en que las tablas hash sean muy grandes o, lo que es lo mismo, que haya muchos hashes posibles. En nuestro caso, dado que el hash ocupa un byte sólo hay 256 valores posibles y las tablas hash (“hashpos_*”) tienen 256 posiciones. Pero se podrían usar 9 bits para el hash, en vez de 8, en cuyo caso habría 512 hashes posibles y dos tablas hash de 512 posiciones.

Y otra técnica es complementar el hash con un “lock”, que no deja de ser lo mismo, es decir, un segundo hash, pero elaborado a partir de otras tablas aleatorias. De este modo, todo tablero tiene dos hashes (un hash y un lock) y, ahora ya sí, la probabilidad de que dos tableros distintos tengan el mismo hash y el mismo lock ya es prácticamente cero.

El uso de tablas hash con lock se describirá en la entrada siguiente. De momento, baste recordar que cuando las rutinas “addHashPosMouse” y “addHashPosCats” insertan un movimiento (origen, destino) en las tablas “hashpos_mouse” o “hashpos_cats” respectivamente, y la posición del hash ya está ocupada (valor distinto del valor inicial $ff), se detecta una colisión y se incrementa el contador “coll_mouse” o “coll_cats”, lo que al menos servirá para saber si tenemos muchas o pocas colisiones.

Una tabla está claro lo que es: un conjunto de posiciones de memoria contiguas a las que se accede mediante el uso de un índice. El índice empieza en cero y termina en N-1, siendo N el tamaño de la tabla:

Hay tablas unidimensionales, también llamadas vectores o arrays, tablas bidimensionales, etc.

Pues bien, hay un tipo especial de tabla llamada “tabla hash”. Se trata de una tabla convencional a la que se accede mediante un índice que se obtiene de calcular el hash de una estructura de datos más compleja, por ejemplo, de un tablero. Las tablas hash se describen aquí:

https://es.wikipedia.org/wiki/Tabla_hash

Las tablas hash, igual que las tablas convencionales, valen para guardar y recuperar datos. En nuestro caso, vamos a usar dos tablas hash para guardar el mejor movimiento asociado a cada tablero o posición. El motivo de usar dos tablas hash, una para ratón y otra para gatos, radica en que para que un tablero esté totalmente definido no llega con conocer la ubicación de las piezas; además hay que saber a qué bando le toca mover.

Tablas “hashpos_mouse” y “hashpos_cats”:

Según lo visto, vamos a definir dos tablas:

• “hashpos_mouse”: Esta tabla servirá para guardar el mejor movimiento asociado a un tablero cuando sea el turno del ratón.
• “hashpos_cats”: Esta tabla servirá para guardar el mejor movimiento asociado a un tablero cuando sea el turno de los gatos.

Pero, en realidad, dado que los movimientos requieren de un origen y un destino, las tablas anteriores son dobles:

• “hashpos_mouse_start” y “hashpos_mouse_dest”: Para guardar el mejor movimiento (origen y destino) asociado a un tablero cuando sea el turno del ratón.
• “hashpos_cats_start” y “hashpos_cats_dest”: Para guardar el mejor movimiento (origen y destino) asociado a un tablero cuando sea el turno de los gatos.

Gráficamente sería algo así:

Es decir, partiendo de un tablero, si es el turno del ratón, se obtiene el hash del tablero y el mejor movimiento identificado (origen + destino) se guarda en la tabla hash del ratón (“hashpos_mouse”), concretamente en la posición correspondiente al hash del tablero. Y lo mismo si es el turno de los gatos, pero usando para ello la tabla hash de los gatos (“hashpos_cats”).

Para recuperar el mejor movimiento asociado a un tablero se procede de manera análoga. Partiendo del tablero, se obtiene su hash y, en función del turno, se lee el movimiento de una tabla y otra.

Las tablas hash se definen en el fichero “Hash.asm”:

Las tablas se inicializan a $ff, pero igualmente se podría inicializar a $00. El motivo de hacerlo a $ff radica en que $00 = 0 = A1 es una casilla válida de modo que, para evitar confusiones, se prefiere inicializar a $ff.

Rutinas “addHashPosMouse” y “addHashPosCats”:

La forma de almacenar movimientos vinculados a tableros en estas tablas es mediante las rutinas “addHashPosMouse” y “addHashPosCats”. Ambas rutinas son muy parecidas, siendo la principal diferencia que la primera almacena el movimiento en la tabla “hashpos_mouse” y la segunda en “hashpos_cats”. Por este motivo, sólo se revisará la primera:

Como se puede observar, la rutina “addHashPosMouse”:

• Lee el hash del tablero actual (“current_hash”).
• Consulta el valor almacenado en la tabla “hashpos_mouse” correspondiente a ese hash.
• Si el valor es $ff (valor inicial), eso significa que la posición todavía está vacía. Por tanto, no se produce “colisión”. Se almacena el movimiento (origen, destino) en esa posición.
• Si el valor es distinto de $ff, eso significa que la posición ya había sido usada. Por tanto, se produce una “colisión” y se incrementa el contador “coll_mouse”. Igualmente, se almacena el movimiento (origen, destino) en esa posición.

Rutinas “lookUpMouse” y “lookUpCats”:

La forma de leer movimientos vinculados a tableros a partir de estas tablas es mediante las rutinas “lookUpMouse” y “lookUpCats”. Ambas rutinas son muy parecidas, siendo la principal diferencia que la primera lee el movimiento de la tabla “hashpos_mouse” y la segunda de “hashpos_cats”. Por este motivo, sólo se revisará la primera:

Como se puede observar, la rutina “lookUpMouse”:

• Lee el hash del tablero actual (“current_hash”).
• Consulta el valor almacenado en la tabla “hashpos_mouse” correspondiente a ese hash.
• Si el valor es $ff (valor inicial), eso significa que la posición todavía está vacía. Por tanto, almacena $ff en “hash_start” y “hash_dest”, lo cual viene a ser una señal de que el tablero consultado no tiene movimiento asociado.
• Si el valor es distinto de $ff, eso significa que la posición ya ha sido usada y contiene un movimiento. Por tanto, lee el movimiento y lo devuelve en “hash_start” y “hash_dest”.

Nuevo programa principal:

Con el objeto de probar todo esto de las tablas hash mejoramos “Display.asm” con:

• Rutinas para imprimir las tablas aleatorias (“displayHashMouse” y “displayHashCatN”).
• Y rutinas para imprimir el contenido de las tablas hash de ratón y gatos (“displayHashPosMouse” y “displayHashPosCats”).

Además, definimos un nuevo programa principal con este aspecto:

Es decir, el programa inicializa e imprime el tablero, y luego:

• Llama a la rutina “testRandomizeHashes”. Esta rutina imprime el contenido inicial de las tablas aleatorias, luego las inicializa con valores aleatorios, y luego las vuelve a imprimir.
• Llama a la rutina “testAddHashAndLookUp”. Esta rutina consulta el movimiento asociado a un tablero en la tabla hash del ratón (inicialmente no existe), luego inserta el movimiento 4 => 13 (E1 => F2), y luego vuelve a consultar el movimiento.
• Llama a la rutina “testHashPositions”, que pinta el contenido de las tablas hash de ratón y gatos.

En definitiva, todo pruebas orientadas a validar el funcionamiento de las tablas aleatorias, las tablas hash, y las rutinas para guardar y leer movimientos:

---

Código del proyecto: RYG3-03

En informática, un “hash” es una especie de huella o resumen de un conjunto de datos. El hash se elabora aplicando un algoritmo de hashing. Algunos algoritmos habituales son MD5, SHA1, SHA256, etc. Se utilizan mucho en el ámbito de la seguridad, sobre todo para garantizar la integridad de la información: si un solo bit de los datos cambiara, esta situación se detectaría inmediatamente porque también cambiaría el hash. Además, es imposible recuperar los datos originales a partir del hash.

Pues bien, un hash se puede obtener a partir de cualquier conjunto de datos arbitrario. En nuestro caso, nos va a interesar obtener un hash de un tablero porque vamos a utilizar ese hash para guardar y recuperar datos asociados al tablero, concretamente el mejor movimiento a partir de él.

Nuestro algoritmo de hash va a ser inventado. Como dato de entrada, va a tomar el tablero (“board”) y, como dato de salida, va a generar un byte, es decir, un valor entre 0 y 255. Y el algoritmo va a consistir en recorrer todas las casillas del tablero, determinar su contenido (vacía, ratón o gato), en función del contenido leer un valor de unas tablas generadas aleatoriamente, e ir haciendo el OR exclusivo (instrucción “eor”) de estos valores.

De este modo, dados dos tableros distintos, es decir, con las piezas sobre casillas distintas, como se consultarán posiciones distintas de las tablas generadas aleatoriamente, se obtendrán hashes distintos.

Tablas con valores aleatorios:

Todo esto del hash lo vamos a gestionar con un fichero nuevo “Hash.asm”. En este fichero vamos a definir cinco tablas con valores generados aleatoriamente, una tabla por cada pieza (“hash_mouse”, “hash_cat1”, “hash_cat2”, “hash_cat3” y “hash_cat4”):

Las tablas son todas de 64 posiciones, igual que el tablero. Se inicializan a cero, pero posteriormente se les da valores aleatorios.

Generación de valores aleatorios con el SID:

Como se vio en las entradas dedicadas el SID en el Volumen I, el chip de sonido del C64 tiene tres voces, y la tercera voz puede usarse para generar valores aleatorios.

Para ello hace falta:

• Configurar la frecuencia de la tercera voz (registros $d40e y $d40f).
• Activar la tercera voz y configurar su forma de onda (registro $d412).
• Leer los valores aleatorios (señal de ruido) de la salida de la tercera voz (registro $d41b).

Todo esto vamos a hacerlo con la rutina “randomize” y las subrutinas “randHashMouse”, “randHashCat1”, …, “randHashCat4” del fichero “Hash.asm”:

Como se puede observar, la rutina “randomize”:

• Configura la frecuencia $ffff en $d40e – $d40f.
• Configura la forma de onda “ruido” activando el bit 7 de $d412
• Activa la tercera voz activando el bit 0 de $d412.
• Y lee un primer valor aleatorio de $d41b. Lo guarda en “seed”.
• Llama a las cinco subrutinas.

Por su parte, las cinco subrutinas son casi iguales, cambiando sólo la tabla en que se guardan los valores aleatorios generados, por lo que sólo revisaremos “randHashMouse”:

La subrutina “randHashMouse” hace lo siguiente:

• Con el registro X, ejecuta 64 iteraciones, tantas como posiciones tiene el tablero y la tabla aleatoria “hash_mouse”.
• Lee otro valor aleatorio de $d41b.
• Hace el OR exclusivo (“eor”) del valor recién leído y “seed”.
• El resultado lo guarda en “seed” y en la posición X de “hash_mouse”.

Y las otras cuatro subrutinas hacen algo totalmente análogo, cambiando únicamente la tabla en la que guardan los datos aleatorios.

Tras ejecutar “randomize” la tabla “hash_mouse” y las otras tablas quedarán con un contenido similar a este. Además, el contenido cambiará de una ejecución a otra, al ser valores aleatorios generados a partir del SID:

Generación del hash de un tablero:

Una vez que tenemos las cinco tablas, una por pieza, con los valores aleatorios, ya podemos generar el hash del tablero. Esto lo hacemos con la rutina “getHash” de “Hash.asm”:

El algoritmo es el ya comentado anteriormente:

• Partimos de un resultado inicializado a cero.
• Con el índice X, recorremos todas las casillas del tablero “board”.
• Determinamos el contenido de cada casilla (vacía, ratón o gato).
• Si el contenido es ratón, lee el valor de “hash_mouse” correspondiente a la casilla X y hace el OR exclusivo.
• Si el contenido es el gato N, lee el valor de “hash_catN” correspondiente a la casilla X y hace el OR exclusivo.
• Si el contenido es vacío, pasa a la siguiente casilla.

De este modo, y tras mejorar la rutina “displayBoard” para añadir el hash, ya es posible obtener e imprimir el hash del tablero:

---

Código del proyecto: RYG3-03

Ahora que ya sabemos cómo generar los movimientos (con las direcciones de movimiento, las tablas de movimientos de ratón y gatos, y la tabla “move_list”), vamos a ello:

Lo primero es definir un nuevo fichero “Gen.asm”, que va a contener las rutinas relativas a la generación de movimientos:

• Rutina “gen” para generar los movimientos de ratón o gatos, según de quién sea el turno (“side”).
• Rutina “genMouse” para generar un movimiento del ratón a partir de una posición de origen y una dirección de movimiento.
• Rutina “genCat” para generar un movimiento de un gato a partir de una posición de origen y una dirección de movimiento.
• Rutina “addMove” para añadir un movimiento a “move_list”.

Además de lo anterior, vamos a definir una nueva rutina “displayMoves” en el fichero “Display.asm” y un nuevo programa principal.

Rutina “gen”:

La rutina “gen” tiene esta pinta:

Lo primero que hace tiene un poco de truco. Si vamos a generar los movimientos a profundidad “ply”, los movimientos de esa profundidad se almacenarán empezando en first_move(ply) y terminando en first_move(ply+1). En realidad, first_move(ply+1) ya es el primer movimiento de la profundidad siguiente. Por tanto, lo primero que hace es la asignación first_move(ply+1) := first_move(ply), es decir, viene a decir que la lista de movimientos del nivel “ply” nace vacía. A partir de ahí irá incrementando el final de la lista first_move(ply+1) con cada nuevo movimiento que genere.

A partir de ahí:

• Recorre el tablero “board” con el índice X.
• Analiza quién mueve (“side”), si ratón o gatos.
• Si mueve el ratón y la pieza en el índice X es un ratón, llama a “genMouse” para las cuatro direcciones.
• Si mueven los gatos y la pieza en el índice X es un gato, llama a “genCat” para las dos direcciones permitidas.
• Continúa hasta terminar el tablero.

Rutinas “genMouse” y “genCat”:

Por su parte, las rutinas “genMouse” y “genCat” son muy parecidas, por lo que sólo analizaremos la primera:

Esta rutina hace lo siguiente:

• Partiendo de la casilla de origen, la multiplica por cuatro (asl + asl). Recordemos que la tabla de movimientos del ratón tiene cuatro movimientos por casilla de origen, aunque algunos pueden ser inválidos.
• Tras multiplicar por cuatro, le suma la dirección.
• Usando ese valor (origen * 4 + dirección) como índice Y, accede a la tabla de movimientos “mouse_moves” y obtiene la casilla de destino.
• Si la casilla de destino es -1 = $ff, la dirección de movimiento no es válida para esta casilla origen y termina.
• Si la casilla de destino no está vacía (PIECE_EMPTY), la dirección de movimiento tampoco es válida y termina.
• En el resto de casos, llama a “addMove” pasando la casilla origen y la casilla destino.

Rutina “addMove”:

Por último, la rutina “addMove” hace lo siguiente tanto para los movimientos del ratón como de los gatos:

Es decir:

• Determina el primer movimiento libre para el nivel “ply”, que es el apuntado por first_move(ply+1).
• En esa posición libre almacena el movimiento (origen, destino).
• Incrementa first_move(ply+1), es decir, incrementa el final de la lista de movimientos para el nivel “ply”.

Rutina “displayMoves”:

Tanto para probar la generación de movimientos como para más adelante, cuando el programa esté más avanzado, nos interesa imprimir por pantalla los movimientos generados. Esto lo hacemos con la rutina “displayMoves” de “Display.asm”:

Se puede hacer una rutina que imprima los movimientos generados para una profundidad dada, o que imprima todos los movimientos desde la profundidad 0 hasta la profundidad “ply”. Pero en general, es suficiente con conocer sólo los movimientos de la siguiente jugada, es decir, los movimientos almacenados en “move_list” desde first_move(0) hasta first_move(1).

Y eso es lo que hace “displayMoves”:

• Toma como primer movimiento el almacenado en first_move(0).
• Toma como último movimiento el almacenado en first_move(1). En realidad, este movimiento ya no se imprimirá.
• Recorre esos movimientos, es decir, va leyendo origen (“move_list_start”) y destino (“move_list_dest”), y los imprime con la rutina “algebraic”.

La rutina “algebraic”, por su parte, es una rutina sencilla que convierte una posición en su notación algebraica. Por ejemplo, la casilla 0 se imprime como A1, y la casilla 63 se imprime como H8. Está definida en “Init.asm”.

Nuevo programa principal:

Por último, desarrollamos un nuevo programa principal que nos permite probar todo lo desarrollado hasta el momento. Queda así:

Es decir:

• Inicializa el tablero y lo pinta.
• Configura que mueve el ratón, genera sus movimientos, y los imprime.
• Configura que mueven los gatos, genera sus movimientos, y los imprime.

Y el resultado es como sigue:

Por tanto, parece que ya sabemos mover…

---

Código del proyecto: RYG3-02

Para generar las jugadas o movimientos necesitamos varios elementos:

• Las direcciones de movimiento.
• Las tablas de movimientos de ratón y gatos.
• La lista de movimientos generados.

Vamos a verlos poco a poco:

Direcciones de movimiento:

Tanto el ratón como los gatos se mueven en diagonal. El ratón puede moverse en las cuatro direcciones diagonales, mientras que los gatos sólo hacia abajo.

Estas cuatro direcciones de movimiento, que llamamos DIR_SW = 0 = suroeste, DIR_SE = 1 = sureste, DIR_NE = 2 = noreste y DIR_NW = 3 = noroeste, las definimos como constantes en “Globals.asm”:

Los valores 0, 1, 2 y 3 nos servirán como índice para leer los movimientos, es decir, la casilla de destino, de las tablas de movimientos de ratón y gatos.

El orden de las direcciones es arbitrario, pero como ratón y gatos comparten la posibilidad de moverse en las direcciones DIR_SW y DIR_SE, lo lógico es que estas direcciones tomen los valores 0 y 1.

Tablas de movimientos de ratón y gatos:

En el fichero “Init.asm” es donde recogemos las variables principales (“side”, “ply”, “hpy”, “nodes”, etc.) y las estructuras de datos principales (“board”, “init_board”, etc.). Entre estas últimas, tenemos las tablas:

• “mouse_moves”.
• “cat_moves”.

La tabla “mouse_moves” recoge los movimientos posibles del ratón. La tabla “cat_moves” recoge los movimientos posibles de los gatos.

Estas tablas se manejan así:

Supongamos que es el turno de ratón. Por tanto, usamos la tabla “mouse_moves”. Supongamos, también, que el ratón está en la casilla E1, es decir, en el índice 4 del tablero. Por tanto, vamos a la fila 4 de la tabla “mouse_moves” y ahí tenemos los 4 movimientos posibles:

Los movimientos posibles, es decir, las casillas de destino del ratón partiendo de la casilla E1 = 4, son:

• DIR_SW = 0 => -1, es decir, no es posible mover en esta dirección.
• DIR_SE = 1 => -1, es decir, tampoco es posible mover en esta dirección.
• DIR_NE = 2 => 13, es decir, la casilla F2.
• DIR_NW = 3 => 11, es decir, la casilla D2.

Por tanto, partiendo de la casilla E1 = 4, el ratón puede moverse a las casillas F2 = 13 y D2 = 11. No puede moverse hacia el sur o hacia abajo, porque se saldría del tablero. Y efectivamente es así:

Si en vez de mover el ratón movieran los gatos el proceso sería totalmente análogo, siendo las principales diferencias que usaríamos la tabla “cat_moves” y que en este caso sólo habría dos movimientos posibles:

Por ejemplo, para la casilla H8 = 63 el único destino posible sería la casilla G7 = 54.

Por supuesto, para que un movimiento sea posible, además de estar registrado en la tabla de movimientos de ratón o gatos, el destino tiene que estar vacío.

Lista de movimientos posibles generados:

Los movimientos posibles generados conforme a las reglas anteriores se guardan en una lista llamada “move_list”. En realidad, como los movimientos tienen una casilla de origen y otra de destino, la lista anterior es doble, “move_list_start” y “move_list_dest”:

Además, recordemos que el juego consiste en generar todos los movimientos posibles a partir de una posición, intentarlos o probarlos, evaluar si el resultado es más o menos favorable, deshacerlos, y finalmente elegir el mejor movimiento posible. Y todo esto, hasta una profundidad N, que es la profundidad de análisis o nivel de juego que haya elegido el usuario.

Por tanto, si en un momento dado el proceso de búsqueda nos ha llevado hasta el tablero de la izquierda, es decir, si la variante actual es esa rama, en la tabla “move_list” necesitaremos tener los tres movimientos posibles desde la posición actual (ply = 0) y, además, los dos movimientos posibles del tablero de la izquierda (ply = 1).

Todo esto se gestiona gracias a la tabla “first_move” que, para una profundidad dada (ply = X), nos dice donde empiezan sus movimientos en “move_list”. Gráficamente sería así:

En definitiva, la tabla “first_move” nos dice dónde empiezan y terminan los movimientos de cada nivel de profundidad. En la figura anterior, los movimientos del tablero actual (ply = 0) empiezan en el índice 0 (s0=>d0, s1=>d1 y s2=>d2) y los movimientos del tablero que se está analizando a profundidad uno (ply = 1), el tablero de la izquierda, empiezan en el índice 3 (s3=>d3 y s4=>d4).

De este modo es posible ir moviendo la variante actual por el árbol, probando movimientos a una profundidad, deshaciéndolos, probando otros movimientos de profundidad menor que estuvieran pendientes de probar, etc.

Todos estos juegos de tablero, da un poco igual de qué juego se trate (ej. ajedrez, damas, Othello, etc.) o de los detalles de su implementación, se basan en los mismos principios:

• Partiendo de la posición actual (raíz), el programa genera todos los movimientos posibles.
• El proceso anterior se repite recursivamente hasta una profundidad N, dando lugar a un árbol de jugadas.
• El árbol de jugadas se evalúa. Se parte de las hojas (tableros a profundidad N) aplicándoles una función de evaluación que establece cómo de buenos o malos son esos tableros para un bando y para el otro.
• Las evaluaciones se llevan desde las hojas hasta la raíz aplicando un procedimiento llamado “minimax”, que consiste en suponer que ambos bandos elegirán su mejor jugada cuando sea su turno. Un bando elegirá las jugadas que maximizan la puntuación, y el otro las que la minimizan. De ahí el nombre “minimax”.
• En ocasiones, se podan las ramas del árbol que no interesa analizar. Esto es muy importante para que el rendimiento sea bueno.
• Finalmente, el ordenador elige su mejor jugada, lo que da lugar a una nueva posición actual.
• Si el ordenador juega contra sí mismo se repite el proceso anterior desde la nueva posición actual. Si juega contra un humano se le pide su jugada.

Desde un punto de vista gráfico sería algo así:

Al proceso anterior se le denomina “búsqueda”, puesto que en el fondo lo que hace el ordenador es buscar la mejor jugada para su bando, asumiendo que el bando contrario también optará por su mejor jugada. La búsqueda puede ser “minimax” pura o, si incluye poda, puede ser búsqueda alfa – beta. Los detalles los veremos más adelante.

El resultado de la búsqueda, en realidad, no es sólo la siguiente jugada (en el caso del árbol anterior la jugada hacia la derecha que da lugar a un tablero valorado en 3), sino la secuencia de jugadas de uno y otro bando desde la raíz hasta una hoja. Es lo que se llama la “variante principal”, y en el fondo no es más que la “ruta” que el ordenador piensa que va a seguir la partida con los datos conocidos hasta ese momento, que siempre son imperfectos, porque la profundidad de análisis no es infinita:

En un momento dado de la ejecución, el programa estará generando y/o evaluando un determinado tablero del árbol. La ruta desde la raíz hasta ese tablero que se está generando y/o evaluando es lo que se llama la “variante actual”.

Todo lo anterior (el árbol de juego, la búsqueda “minimax” o alfa-beta, la variante actual, la variante principal, etc.) son ideas teóricas, son conceptos. Luego hay diferentes formas de implementarlas o llevarlas a la práctica.

Por ejemplo, alguien podría plantearse desarrollar todo el árbol de juego completo, almacenarlo en memoria, evaluarlo y elegir la siguiente jugada. No es la mejor opción, en primer lugar, porque consume mucha memoria (se almacena el árbol completo) y, en segundo lugar, porque no admite poda. La poda se hace en función de las evaluaciones y, aunque fuera posible hacerla en algunas circunstancias, con el árbol completo en memoria ya no tendría sentido hacerlo, porque ya se habría incurrido en el coste de construirlo y almacenarlo.

Por todo ello, en la práctica el árbol de juego se construye y se evalúa sobre la marcha, según se va construyendo. La construcción del árbol se hace “en profundidad”, es decir, primero se desarrolla la primera rama completa hasta la primera hoja, luego la segunda rama completa hasta la segunda hoja, etc. Y se va podando lo que, en función de las evaluaciones, no tiene sentido construir o desarrollar.

Es más, con un único tablero de 64 bytes es suficiente para gestionar el árbol de juego completo. Con ese tablero almacenamos la posición actual de la partida y, cuando toca decidir la siguiente jugada, generamos los movimientos posibles y los vamos “probando” y deshaciendo. Probarlos consiste en ejecutarlos o aplicarlos hasta la profundidad de análisis, evaluar las hojas con la función de evaluación, aplicar “minimax” para propagar las evaluaciones hacia la raíz, podar las ramas que se puedan podar, determinar la variante principal, y elegir el siguiente movimiento.

Por tanto, aunque desde un punto de vista conceptual el programa desarrolla y evalúa un árbol de jugadas, en la práctica todo se maneja con un único tablero. Todo esto quedará más claro según vayamos avanzando con el proyecto.

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

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!!

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.

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…