RYG: otra forma mejor de generar el árbol de juego – cambios en el código

Implementar todos los cambios descritos en la entrada anterior no es fácil. Vayamos paso a paso:

Generar el árbol de juego “a lo profundo”:

El árbol de juego se genera en la rutina “desarrollaUnNivel” del fichero principal (“RYG.asm”). Esta rutina tiene dos ramas principales, pero son muy parecidas:

  • La rama “dunGatos”, cuando el turno es de los gatos.
  • La rama “dunRaton”, cuando el turno es del ratón.

Por simplicidad, revisaremos sólo la segunda. La primera es muy parecida.

En la versión 19 del proyecto el código era así:

  • Primero, se generaban todas las jugadas del ratón, dando lugar a tableros hijo (rutina “arbolJugadasRaton”):

dunRaton - jugadas

  • Después, se recorrían los tableros hijos llamando recursivamente a “desarrollaUnNivel”:

dunRaton - bucle

Es decir, que efectivamente el árbol se estaba generando “a lo ancho”, no “a lo profundo”.

En la versión 20 del proyecto ese código queda así:

  • Primero se genera una jugada, dando lugar a un tablero hijo:

dunRaton20 - hijo

  • Después, antes de pasar a generar el siguiente hijo, se llama recursivamente a “desarrollaUnNivel” sobre el hijo recién generado:

dunRaton20 - recursividad

De este modo, el árbol ya se genera “a lo profundo”. Es decir, primero se genera la primera rama hasta su máxima profundidad, luego la segunda rama hasta su máxima profundidad, etc. Y así hasta completar el árbol.

Todavía no hemos cambiado la forma de evaluar el árbol. Ese es el siguiente paso.

Evaluar el árbol según se genera:

En las versiones 19 y 20 del proyecto todavía esperamos a tener todo el árbol completo para evaluarlo. Esto se ve aquí (rutina “decideBDvsArbol”):

Evaluación árbol completo

Sin embargo, como nuestro objetivo es liberar memoria en cuanto podamos, ya no debemos hacerlo así. Tenemos que evaluar sobre la marcha.

Estos cambios se ven en la versión 21 del proyecto:

  • Si estamos ante un nodo intermedio del árbol, dependiendo de que el turno sea de los gatos o del ratón, hay que obtener el mínimo de los hijos (gatos) o el máximo (ratón). Para el caso del ratón / máximo esto se ve aquí:

Máximo hijos

  • Y si estamos ante una hoja del árbol (ya sin más hijos), aplicamos la función de evaluación:

Evaluación hoja

De este modo, ya vamos evaluando el árbol sobre la marcha, según se va construyendo, lo que nos permitirá liberar memoria en el siguiente paso.

Tras evaluar un nodo, liberar la memoria de sus hijos:

En las versiones 19, 20 y 21 construimos el árbol completo en memoria. La memoria sólo se libera tras generar el árbol completo, evaluarlo (al final o sobre la marcha), y decidir la jugada de los gatos.

Esto puede verse aquí. Cada vez que empieza a generarse el árbol para decidir una nueva jugada, se copia el tablero actual a la raíz y el puntero a la memoria libre (libreLo – libreHi) se pone a la raíz más 29 bytes (29 bytes es lo que ocupa la raíz, el tablero de partida). Por tanto, se está “pisando” la memoria del árbol anterior:

Pisar tablero anterior

Pero la gracia de todos estos cambios es generar el árbol de otra manera, evaluarlo según se va generando, y, tras evaluar un nodo a partir de sus hijos, liberar la memoria consumida por ellos. De este modo, la memoria consumida por el árbol de juego crece, decrece, y se reutiliza, lo que nos permite llegar a muchos más niveles de profundidad y, por tanto, a un juego más fuerte.

En la versión 22 del proyecto ya liberamos memoria tras evaluar un nodo a partir de sus hijos. Por ejemplo, si es el turno del ratón:

Liberar memoria

De hecho, una cosa muy curiosa de la versión 22 es ver cómo ahora crece y decrece la memoria utilizada según se va generando y evaluando ramas del árbol. Para facilitar el seguimiento del uso creciente y decreciente de la memoria modificamos temporalmente la traza “PENSANDO: XXXX”, de modo que vemos qué posiciones de memoria se van ocupando sin borrar las anteriores:

Liberación memoria

Obsérvese cómo la memoria crece según se va profundizando en el árbol, y luego decrece según se va evaluando y liberando. Y luego se reutiliza, porque aparecen repetidas las mismas posiciones. La diferencia entre dos posiciones siempre es de 29 bytes, es decir, lo que ocupa un tablero (ej. 310d – 30f0 = 29 bytes).

Pero todo esto lo hemos hecho con un objetivo final, que es el siguiente…

Mayor profundidad de análisis:

Puesto que ahora consumimos mucha menos memoria (consumimos, liberamos y reutilizamos), podemos llegar a muchos más niveles de profundidad y conseguir un juego más fuerte.

Virtualmente, casi podríamos decir que ahora la memoria no nos limita. Cuando más ocupa el árbol es cuando se está desarrollando y evaluando su última rama, porque tiene que conservar en memoria los hijos de primer nivel de las ramas anteriores. Pero ya vimos que para 10 niveles de profundidad estamos hablando de menos de 2 KB. Y tenemos 40 KB disponibles ($d000 – $3000 = 40.960).

Pero como todo en la vida tiene que tener un tope, vamos a limitarlo a 15 niveles ($0f), cosa que ya hacemos en la versión 23 del proyecto:

Profundidad16

Pero con esto no es suficiente porque, al admitir más profundidad de análisis, ahora hay más llamadas recursivas para generar y evaluar el árbol, así que también hay que ampliar la tabla de parámetros de “desarrollaUnNivel”:

TablaParams16

Y eso es todo, que no es poco…

Conclusiones:

Os aconsejo jugar con la versión 23 con profundidades crecientes (2, 4, 6, 8, …). Iréis viendo que, cuanto más profundo analiza el C64, mejor juega. De hecho, jugando a una profundidad de 10 yo no he conseguido ganarle, lo cual me parece una magnífica noticia.

Pero la vida es puñetera, y ahora que nos hemos sacudido la limitación de la memoria, podemos analizar muchos más niveles, y jugar mejor, nos surge otra limitación… ¿Alguna idea de cuál podría ser?

Baste decir que a partir del nivel 8 de profundidad sugiero usar la función “Ward mode” de VICE… (Settings > Warp mode).


Código del proyecto (generar el árbol “a lo profundo”): RYG20

Código del proyecto (evaluar sobre la marcha): RYG21

Código del proyecto (liberar memoria tras evaluar): RYG22

Código del proyecto (ampliar la profundidad): RYG23

RYG: otra forma mejor de generar el árbol de juego

Hacía tiempo que quería retomar el proyecto del ratón y los gatos. Tengo algún avance interesante…

La verdad es que a pesar de nuestros muchos esfuerzos (ampliar la RAM disponible, sucesivas versiones de la función de evaluación, tableros más compactos que permiten aprovechar mejor la memoria, e, incluso, inicios de partida), la versión 19 del proyecto sigue siendo fácil de derrotar. Le he dado muchas vueltas: nuevos criterios de evaluación, etc. Pero nada, con cuatro niveles de profundidad no resulta fácil conseguir nada mucho mejor.

Incluso he hecho una versión del proyecto en Java para PC que, con la misma función de evaluación que la versión en ensamblador para C64, es casi invencible con ocho o diez niveles de profundidad (obviamente un PC tiene mucha más memoria que un C64). Esto me hace pensar que el problema no es la función de evaluación, sino la escasa profundidad que alcanzamos (cuatro niveles).

Y de repente he caído en un detalle bastante evidente por otro lado… ¿necesitamos todo el árbol completo en memoria? Hombre, con el enfoque que le hemos dado sí, porque primero construimos el árbol y luego evaluamos. Pero… ¿no podríamos ir evaluando sobre la marcha y, según evaluamos, ir liberando y reutilizar memoria? ¡¡Pues claro que sí!! ¡¡Esa es la clave!!

Forma anterior de construir el árbol de juego:

Suponiendo que la profundidad elegida fuera dos (para simplificar), ahora mismo construimos y evaluamos el árbol así:

  • Empezamos copiando el tablero actual a la raíz del árbol:

Arbol de juego - copia actual

  • Desarrollamos el primer nivel por debajo de la raíz:

Arbol de juego - iter1

  • Desarrollamos el segundo nivel para el primer tablero del primer nivel:

Arbol de juego - iter2

  • Y así sucesivamente hasta que…
  • Desarrollamos el segundo nivel para el último tablero del primer nivel:

Arbol de juego - iter3

  • Cuando el árbol está completo, lo evaluamos con minimax, lo que significa que:
    • Si el nodo es una hoja, lo evaluamos con la función de evaluación.
    • Si el nodo no es una hoja, seleccionamos el máximo o el mínimo de los hijos, según el turno. Si es el turno de los gatos, seleccionamos el mínimo; si es el turno del ratón el máximo.

Arbol de juego - iter4Con esta forma de trabajar necesitamos el árbol completo en memoria y, por muy compactos que sean los tableros (unos 30 bytes), con 40 KB de memoria disponible ($d000 – $3000 = 40.960), eso da para unos 1.300 tableros, es decir, para cuatro niveles de profundidad.

Nueva forma de construir el árbol de juego:

Pero ahora observemos esta nueva forma de construir y evaluar el árbol (nuevamente con una profundidad de dos para simplificar):

  • Nuevamente, empezamos copiando el tablero actual a la raíz:

Arbol de juego - copia actual

  • Ahora desarrollamos la primera rama hasta su máxima profundidad:

Arbol de juego - rama1

  • Aplicamos minimax a la primera rama:

Arbol de juego - rama1 - minimax

  • Puesto que la primera rama ya está evaluada, esos nodos ya no son necesarios, de modo que podamos liberar su memoria y reutilizarla para la rama dos:

Arbol de juego - rama1 - liberación

  • Y hacemos lo mismo con la rama dos (generarla hasta su máxima profundidad, evaluarla y liberar su memoria), y con la rama tres, etc., hasta terminar todas las ramas.

Arbol de juego - ramaN

  • Finalmente, repetimos el proceso también con la raíz, es decir, le aplicamos minimax y liberamos la memoria de sus hijos. En el fondo es un proceso recursivo.

Arbol de juego - ramaN

De este modo, el consumo de memoria va creciendo mientras se desarrolla una rama, pero una vez evaluada, al liberar su memoria, el consumo de memoria disminuye, y esa memoria puede reutilizarse para la rama siguiente.

El máximo consumo de memoria se da cuando la última rama está desarrollada hasta su máxima profundidad. Pero, aunque estuviéramos hablando de una profundidad de 10 niveles, eso sería:

  • Nodo raíz.
  • Nivel 1: Un máximo de 8 hijos.
  • Nivel 2: Un máximo de 4 hijos.
  • Nivel 10: Un máximo de 4 hijos.

Por tanto, en total, y como máximo, estamos hablando 61 nodos que, a 30 bytes por nodo (en realidad 29 bytes), nos da… ¡¡1.830 bytes para 10 niveles!!

Conclusiones:

¡¡La diferencia es abrumadora!! Antes con cuatro niveles consumíamos toda la memoria disponible (40 KB). Ahora con 10 niveles ni siquiera llegamos a 2 KB.

En la práctica esto significa que podemos hacer que el C64 juegue prácticamente a cualquier profundidad que se nos antoje: 10 niveles, 20 niveles, 30 niveles, … ¡¡La memoria ya no nos limita!!

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.

RYG: inicios y finales de partida

Los aficionados al ajedrez sabrán que es muy habitual estudiar aperturas y finales de partida, porque son situaciones especiales en las que conviene saber cómo actuar. Pues bien, una funcionalidad interesante para el juego consiste en añadir una “base de datos” de inicios y/o finales de partida.

Los inicios de partida son fáciles de añadir, porque es fácil identificar cuándo una partida se encuentra al inicio. Por ejemplo, si el número de movimientos aplicados es menor que X está claro que estamos ante un inicio de partida.

Por el contrario, los finales de partida son mucho más difíciles de identificar y, por tanto, de aplicar. No hay un umbral de movimientos a partir del cual podemos suponer que estamos ante un final de partida. Por tanto, se trata más bien de reconocer situaciones o patrones (ej. número de piezas, posiciones, etc.). En consecuencia, es algo bastante más complejo de implementar.

En el caso que nos ocupa, siempre que el número de movimientos esté por debajo de 8, el ratón no habrá podido alcanzar la formación de los gatos y, por tanto, no podrá condicionar ni limitar los movimientos de estos. Por tanto, por debajo de 8 movimientos podremos aplicar una secuencia de movimientos fija (o varias) que sea de interés para los gatos. A partir del movimiento 9, en cambio, el ratón ya habrá podido alcanzar a los gatos y, por tanto, los movimientos posibles para los gatos ya dependerán de cómo se haya movido el ratón.

Inicios de partida

Como a los gatos les interesa mantener una formación cerrada, una posible “base de datos” de movimientos al inicio de la partida consiste hacer los movimientos 1, 3, 5 y 7 como se muestra en la imagen anterior.

Implementar lo anterior es fácil. En vez de construir un árbol de jugadas, evaluarlo, aplicar minimax y elegir la jugada que minimiza la evaluación en todo caso, haremos lo siguiente:

  • Por debajo de la jugada 8, aplicaremos la “base de datos” de movimientos. Da igual lo que haya movido el ratón.
  • Por encima de la jugada 8, actuaremos como hasta ahora, es decir, construiremos el árbol de jugadas, lo evaluaremos, aplicaremos minimax, y optaremos por la jugada que minimiza el valor (porque el C64 mueve a los gatos).

Para ello, en el fichero principal “RYG.asm” dotamos la nueva rutina “decideBDvsArbol” que lo primero que hace es mirar en qué número de movimiento estamos (nivel):

Rutina decideBDvsArbol

Por debajo de 8 (bcc), saltamos a la etiqueta “dbdaBaseDatos”, que se encarga de aplicar la “base de datos” de jugadas de inicio. Por encima de 8, continuamos con la etiqueta “dbdaArbol”, es decir, continuamos con la operativa normal hasta ahora:

Arbol

En cambio, cuando se trata de aplicar la “base de datos” de jugadas la novedad es como sigue:

Base de datos inicio

Es decir, movemos el nivel o número de jugada (que en ese momento está en el acumulador) al registro X y, usando X como índice, accedemos a una tabla doble de gatos y offsets:

Base datos gatos y offsets

Esta tabla doble es propiamente la “base de datos de jugadas” ya que, para un número de jugada (valor del índice X), nos dice qué gato hay que mover (tabla “tablaNumGatos”) y a qué offset hay que moverlo (tabla “tablaOffsets”).

A los gatos les corresponden los movimientos 1, 3, 5 y 7. En el movimiento 1 hay que mover el gato 0 al offset 9, en el movimiento 3 hay que mover el gato 1 al offset 11, en el movimiento 5 hay que mover el gato 2 al offset 13 y, por último, en el movimiento 7 hay que mover el gato 3 al offset 15. Todo lo demás son ceros de relleno que corresponden a los movimientos del ratón.

De este modo, al arrancar la partida veremos que el C64, es decir, los gatos, mueve siempre la secuencia anterior. Ni siquiera veremos que aparece “PENSANDO: XXXX”, ya que el C64 no está pensando nada, no está generando un árbol de jugadas, sino que juega “a tiro hecho”.

Todo esto da lugar a la versión 19 del proyecto.


Código del proyecto: RYG19

RYG: tableros más compactos – cambios en el código

Los cambios en el diseño del tablero tienen su impacto en el código del juego. Además de una reducción obvia en el tamaño de la estructura de datos (de 88 a 29 bytes) hay un cambio en el enfoque de los datos: antes teníamos una matriz de 8×8 casillas que podían estar vacías, ocupadas por un ratón o por gatos; ahora tenemos directamente la posición de los cinco protagonistas y todo lo demás se presupone vacío.

Lógicamente tienen que cambiar cosas en el código como la forma de generar las jugadas o la forma de evaluar los tableros. Sin embargo, como veremos más adelante, y sorprendentemente, los cambios son mucho más acotados de lo que podría parecer en un principio.

Nuevo tablero actual:

Si la estructura de datos del tablero cambia, lo primero que cambia es el tablero actual, el que controla la situación actual de la partida (ver fichero “Arbol.asm”). En vez de tener 88 bytes, tendrá 29.

Nuevas rutinas para el manejo de tableros:

Más importante que lo anterior, también cambian las rutinas que permiten manejar tableros, es decir, las rutinas del fichero “Tableros.asm”. Sorprendentemente, muchas rutinas no cambian porque sólo manejan los datos de los tableros que no hemos tocado (nivel, turno, valor, padre o hijos).

Sin embargo, otras rutinas sí tienen que cambiar:

  • La rutina “inicializaTablero” ya no tiene que rellenar un tablero con 64 casillas vacías. Ahora sólo tiene que fijar las posiciones iniciales del ratón (offset = 59) y los gatos (offsets = 0, 2, 4 y 6), ya que todo lo demás se presupone vacío.
  • Las rutinas “dameContenido” y “fijaContenido” dejan de tener sentido. Ya no tenemos 64 casillas que rellenar con un contenido (#Raton, #Gato o #Vacio). Ahora tenemos cinco bytes con las posiciones (offsets) de ratón y gatos. Estas posiciones se especifican con las nuevas rutinas “fijaPosicionRaton” y “fijaPosicionGato”.
  • Las rutinas “dameOffset” y “dameFilaCol” antes empezaban a contar los offsets desde el comienzo de la estructura de datos. Por tanto, la casilla (0, 0) del tablero recibía el offset 24. Ahora cambiamos el criterio y a la casilla (0, 0) le asignamos el offset 0.
  • Las rutinas “dameRaton” y “dameGato” antes recorrían la matriz de 8×8 casillas para buscar y localizar el ratón o el gato enésimo (su offset). Ahora no hace falta buscar nada; tenemos la información a tiro hecho en los cinco bytes que sustituyen a la matriz de 8×8. Por tanto, esas rutinas se sustituyen por las nuevas rutinas “damePosicionRaton” y “damePosicionGato”.

Y poco más hasta aquí.

Nueva generación de jugadas:

La generación de jugadas del ratón está en el fichero “GenJugadasRaton.asm”. La pieza clave anteriormente eran las tablas con los movimientos permitidos:

Movimientos ratón

Es decir, los cambios en la posición (fila, columna) podían ser:

  • ($ff, $ff) = (-1, -1).
  • ($ff, $01) = (-1, 1).
  • ($01, $01) = (1, 1).
  • ($01, $ff) = (1, -1).

Como ahora no tenemos una matriz de 8×8 posiciones, ni tampoco gestionamos las posiciones en formato (fila, columna), sino en formato offset, esa pieza clave se convierte en esta otra:

Movimientos ratón - offsets

Es decir, el offset del ratón puede variar en:

  • $f7 = -9.
  • $f9 = -7.
  • $09 = +9.
  • $07 = +7.

Estas variaciones corresponden a estos cuatro movimientos (suponiendo que el ratón estuviera en el offset 43):

Movimientos offsets

De este modo, generar los movimientos posibles consiste en tomar el offset actual (43), recorrer las cuatro posiciones de la tabla, e ir sumando:

  • 43-9=34.
  • 43-7=36.
  • 43+9=52.
  • 43+7=50.

En el fondo, muy parecido a lo que ya hacíamos antes, pero manejando variaciones en el offset (-9, -7, +9, +7) en vez de variaciones en filas y columnas.

Otra pieza importante es la validación de las jugadas. Para que éstas sean válidas las reglas son (antes y ahora):

  • Tienen que generarse conforme a las reglas de movimiento de las piezas.
  • El destino tiene que estar vacío.
  • El destino tiene que caer dentro de los márgenes del tablero.

La primera condición se garantiza por la forma de generar las jugadas, partiendo de una tabla (antes tablas) que recogen los movimientos válidos.

La segunda es igual de fácil de comprobar ahora que antes. Antes teníamos la (fila, columna) destino; ahora tenemos el offset destino. Si el offset destino está ocupado por el ratón o algún gato, no será un destino válido. En caso contrario, sí lo será.

Y la tercera condición cambia un poco. Antes comprobábamos si la fila o la columna eran menores que cero o mayores que siete. Ahora tenemos un offset entre 0 y 63, y sumar o restar 7 o 9 puede hacer que se traspasen los bordes del tablero sin detectarlo, si no hacemos nada especial. Por ejemplo, 47-7=40 o 47+9=56:

Movimientos offsets - bordes

Una forma inteligente de impedir estos traspasos es dándose cuenta de que ratón y gatos siempre se mueven por las casillas blancas (offsets en blanco) y, cuando tiene lugar un traspaso ilegal de este tipo, acaban en una casilla negra (ver 40 o 56). Por tanto, llega con validar que el offset de destino es blanco (0, 2, 4, 6, 9, 11, 13, 15, …, 61, 63). Esto se puede hacer con una tabla de offsets válidos:

Offsets válidos

Por lo demás, todas las rutinas de “GenJugadasRaton.asm” (generar jugadas, validar jugadas, generar jugadas válidas, etc.) son esencialmente iguales a las que ya había antes, con la salvedad de que las posiciones de origen y destino se especifican mediante offsets, y no mediante parejas (fila, columna).

Y lo mismo se puede decir de “GenJugadasGatos.asm”.

Otros cambios:

Los cambios principales son los ya comentados: rutinas para manejar tableros y generación de jugadas. En el código surgen más cambios (evaluación de tableros, etc.) pero son cambios derivados de los anteriores.

En particular, el hecho de cambiar las rutinas “dameRaton” y “dameGato”, que buscaban en la matriz 8×8, por las nuevas rutinas “damePosicionRaton” y “damePosicionGato”, que devuelven las posiciones a tiro hecho, implica bastantes cambios en la evaluación de tableros (“EvalTableros.asm”), pero son más estéticos (por el cambio de nombre en las rutinas) que otra cosa.

También hay cambios menores en “PintaTableros.asm”. Antes los tableros tenían una matriz 8×8 que pintar (con “G”, “R” o un “.”). Ahora gráficamente hay que pintar la misma matriz 8×8, porque la representación gráfica del tablero no ha cambiado, pero la información de partida es muy distinta (cinco offsets).

Los cambios en el programa principal “RYG.asm” también se limitan a manejar las posiciones mediante offsets, en vez de mediante filas y columnas, o bien cambios en los nombres de algunas rutinas llamadas. Además, está el cambio obvio de pasar de tres a cuatro niveles de profundidad que, no olvidemos, es el motivo por el que hemos montado todo este lío 🙂 .

Cuatro niveles

Por último, un cambio de presentación. Como ahora podemos analizar hasta cuatro niveles de profundidad, es decir, hasta 1024 tableros, pintar “PENSANDO:” y un punto por cada tablero son muchos puntos. Por ello, se prefiere pintar la dirección del tablero que se está generando. De este modo, consumimos menos pantalla, hacemos menos scroll, tenemos igual idea del avance, y encima sabemos si el árbol consume más o menos memoria:

Nuevo pensando

Todos estos cambios pueden verse en la versión 18 del proyecto. Lo bueno de esta versión es que ya permite hasta cuatro niveles de profundidad.

Ah, y una lección que ganamos: lo más intuitivo para el programador (ej. tener un tablero de 8×8) no es siempre lo más intuitivo ni lo mejor para la máquina.


Código del proyecto: RYG18

RYG: tableros más compactos – mayor profundidad de análisis

Ya llevamos tres versiones de la función de evaluación que permite al C64, junto con el procedimiento minimax, decidir sus jugadas.

En la primera versión, hemos considerado como criterios la fila del ratón y el número de jugadas que puede hacer (incluyendo las situaciones particulares de que la fila del ratón sea cero – en cuyo caso gana el ratón – y de que su número de jugadas sea cero – en cuyo caso ganan los gatos –). En la segunda versión, hemos añadido como criterio que los gatos guarden una formación (una fila o dos). Y en la tercera versión, hemos añadido como criterio detectar si el ratón rebasa a los gatos. Y así deberíamos continuar añadiendo y revisando criterios hasta conseguir que el juego sea lo suficientemente fuerte.

Si a pesar de añadir muchos criterios no se consigue un juego fuerte, una medida complementaria (no sustitutiva) es ampliar la profundidad de análisis. Para ello ya sabemos que necesitamos más memoria y, si no disponemos de ella, hay que aprovechar mejor la disponible. Dicho de otro modo, hay que compactar las estructuras de datos.

Esto ya lo habíamos comentado muchas veces, y hasta ahora nos habíamos resistido por no complicar la programación, pero por fin ha llegado el momento.

Nueva estructura de datos compactada:

Los tableros usados hasta ahora eran así:

  • Cabecera: 3 bytes.
  • Nivel, turno y valor: 3 bytes.
  • Dirección del padre: 2 bytes.
  • Direcciones de los hijos: 2 x 8 = 16 bytes.
  • Tablero propiamente dicho: 8 x 8 = 64 bytes.
  • Total: 88 bytes.

De esos 88 bytes, la gran mayoría (64 bytes, el 73%) son el tablero propiamente dicho, es decir, el escaqueado de 8 x 8 casillas. Por tanto, éste es el gran candidato a una fuerte reducción.

Teniendo en cuenta que sólo tenemos cinco piezas, y que no hay capturas, esos 64 bytes se puede reducir a sólo cinco:

  • Un byte para guardar la posición del ratón.
  • Cuatro bytes para guardar las posiciones de los gatos.

Todas las demás posiciones del tablero, se consideran vacías.

Las posiciones del ratón y los gatos se podrían guardar en formato (fila, columna) pero, puestos a ahorrar memoria, casi mejor guardar los offsets (desplazamientos) respecto a la casilla (0, 0) del tablero, es decir, esto:

Offsets

Es decir, en la posición inicial del juego los offsets serían:

  • Gatos = 0, 2, 4 y 6.
  • Ratón = 59.

De este modo, el tablero compactado queda así:

  • Cabecera: 3 bytes.
  • Nivel, turno y valor: 3 bytes.
  • Dirección del padre: 2 bytes.
  • Direcciones de los hijos: 2 x 8 = 16 bytes.
  • Tablero propiamente dicho: 5 bytes.
  • Total: 29 bytes.

Es decir, hemos conseguido una reducción de 88 – 29 = 59 bytes, del 67%.

Reducciones adicionales:

El tablero se puede seguir compactando. El siguiente candidato por tamaño sería la tabla con las direcciones de los hijos (16 bytes), ya que no todos los tableros tendrán ocho hijos.

Se podría hacer una tabla de tamaño variable, marcando el final de la misma con algún marcador. O se podrían diseñar dos estructuras de datos, una con un máximo de ocho hijos para cuando muevan los gatos y otra con un máximo de cuatro hijos para cuando mueva el ratón.

En cualquier caso, es improbable que ahorrar 4 hijos / 8 bytes, y sólo en algunos tableros, permita ganar niveles adicionales en la profundidad de análisis, especialmente si se tiene en cuenta que el crecimiento del árbol de juego (número de tableros) es exponencial con la profundidad.

También se podría quitar la cabecera (tres bytes), aunque facilita la depuración de los datos y los programas, porque facilita identificar dónde empiezan los tableros en memoria.

Como no parecen opciones muy prometedoras, de momento, nos conformaremos con los tableros de 29 bytes.

Nueva profundidad de análisis:

Con este nuevo tamaño de tablero, las previsiones de consumo de memoria en función de los niveles de profundidad quedan así:

  • 1 nivel => 29 bytes x 8 movimientos = 232 bytes.
  • 2 niveles => 29 bytes x 8 x 4 = 928 bytes.
  • 3 niveles => 29 bytes x 8 x 4 x 8 = 7424 bytes.
  • 4 niveles => 29 bytes x 8 x 4 x 8 x 4 = 29696 bytes.
  • 5 niveles => 29 bytes x 8 x 4 x 8 x 4 x 8 = 237568 bytes.

Por tanto, al compactar los tableros de 88 a 29 bytes conseguimos subir de tres a cuatro niveles en la profundidad de análisis (29 KB). No podemos subir a cinco niveles porque el C64 no tiene esos 237 KB.

Es decir, a la hora de decidir su jugada, ahora el C64 podrá tener en cuenta los efectos de su jugada inmediata, la siguiente jugada del humano, nuevamente la jugada del C64 y, por último, la siguiente jugada del humano.

El número máximo de tableros a analizar por cada jugada será de 8 x 4 x 8 x 4 = 1024 tableros, aunque con frecuencia serán menos porque no siempre serán posibles todas las jugadas que en principio permiten las reglas de movimiento.

Todos estos cambios tienen su impacto en el código. Esto lo veremos ya en la entrada que sigue, aunque se adelanta la versión 18 del proyecto.


Código del proyecto: RYG18

RYG: función de evaluación – más mejoras

Como decíamos, el C64 ya juega mejor. Tras mejorar la formación de los gatos y detectar los rebases, ya es más difícil ganarle. Sin embargo, todavía es posible hacerlo, por lo que el proceso de mejora de la función de evaluación debería continuar.

De hecho, el proceso de mejora de la función de evaluación puede continuar casi indefinidamente. Iterativamente se pueden identificar nuevos criterios, introducirlos en el juego, probarlos y, en función de su contribución a la fortaleza del juego, mantenerlos o retirarlos.

Otra forma de mejorar la función de evaluación sería jugando muchas partidas, ya sea contra un humano o incluso contra sí mismo. Para esto último habría que adaptar un poco el juego, pero tampoco tanto, puesto que el C64 ya “sabe” mover el ratón. En vez de pedir la jugada del ratón al humano, debería decidirla el C64 en base a un árbol de juego, igual que ya hace en el caso de los gatos.

Sea como fuere, cuando el C64 pierda, se deberá identificar el movimiento que ha sido clave en la derrota y, más en particular, el criterio que ha hecho que el C64 se haya decantado por ese movimiento, reduciendo su peso o su puntuación para evitar que se repita. Y si esto (aislar el criterio clave en la derrota y ajustar su peso) fuéramos capaces de hacerlo automáticamente, sin intervención de un programador, ya casi estaríamos hablando de machine learning.

En cualquier caso, la mejora de la función de evaluación es un proceso iterativo y largo. Y si después del proceso no se han conseguido los resultados esperados habría que plantearse alternativas, como ampliar la profundidad de análisis compactando las estructuras de datos.