RYG: memoria vs tiempo

Efectivamente, ya no tenemos limitaciones de memoria. Esto nos permite analizar muchos niveles de profundidad y, por tanto, que el C64 juegue mejor.

Sin embargo, es cierto que la vida es puñetera y ahora tenemos un nuevo límite: el tiempo. Lógicamente, se trata de no aburrir al personal y de no tirarse media hora en cada jugada. ¿Cuánto puede esperar un jugador al siguiente movimiento del C64? ¿Cinco minutos como máximo?

A modo de ejemplo se muestra la siguiente tabla de datos. Téngase en cuenta que cuando es el turno de los gatos hay un máximo de 8 movimientos (4 gatos x 2 movimientos) y cuando es el turno del ratón hay un máximo de 4 movimientos (1 ratón x 4 movimientos):

Nivel de profundidad Número de tableros a analizar Tiempo para mover Tiempo con Warp mode
2 8×4 = 32 Instantáneo No hace falta
4 8x4x8x4 = 1.024 Pocos segundos No hace falta
6 8x4x8x4x8x4 = 32.768 1 o 2 minutos No hace falta
8 8x4x8x4x8x4x8x4 = 1 millón Unos 15 minutos Unos 4 minutos
10 8x4x8x4x8x4x8x4x8x4 = 33,5 millones Unas 2 horas (*) Unos 30 minutos

(*) Aunque 2 horas puede parecer mucho, y sin duda lo es para un jugador esperando el siguiente movimiento, hay que tener en cuenta que estamos hablando de 33,5 millones de tableros para un ordenador que funciona a 1 MHz.

En definitiva, es fantástico que el C64 juegue fuerte a 10 niveles de profundidad, y que sea imbatible o muy difícil ganarle a ese nivel, pero sería muy conveniente agilizar el proceso. Para ello hay varias estrategias:

Podar el árbol de juego:

Podar el árbol de juego consiste en eliminar aquellas ramas que no tiene sentido generar y evaluar.

Por ejemplo, si en un tablero del árbol de juego el ratón está a la espalda de los gatos, la partida ya está ganada para el ratón (salvo que el humano juegue a perder intencionadamente), por lo que no se hace necesario seguir desarrollando esa rama. Se puede podar.

Poner un límite de tiempo a cada movimiento:

Si el C64 empieza a tener un juego fuerte a partir del nivel 10, pero en ese nivel decidir cada jugada lleva mucho tiempo, simplemente ha llegado el momento de asumir que no es posible generar y evaluar todos los movimientos. Por tanto, nos ponemos un límite de tiempo razonable (ej. X minutos por movimiento) y, cuando se haya agotado ese tiempo, optamos por el mejor movimiento descubierto hasta ese momento.

La forma habitual de implementar esto es mediante una técnica llamada “iterative deepening” o “profundización progresiva”. Es decir, aunque el usuario haya decidido jugar a profundidad 10, la máquina juega a profundidades 1, 2, 3, 4, 5, …, y así sucesivamente hasta que se agote el tiempo disponible. Una vez que se agota el tiempo, sea en el nivel que sea, por ejemplo 7, se elige la mejor jugada descubierta hasta ese momento.

Esta forma de funcionar parte de la base de que no vas a poder desarrollar el árbol completo hasta el nivel N, y que te vas a tener que conformar con lo mejor que encuentres en un tiempo limitado, por lo que se vuelve especialmente interesante ordenar los movimientos y desarrollar primero los que sean más prometedores.

Hasta ahora no hemos hecho esto. Hemos generado todos los movimientos y en un orden un tanto arbitrario. El orden de los movimientos ha venido fijado por las matrices que los generan:

Movimientos ratón

Movimientos gatos

Se podrían generar y desarrollar primero, por ejemplo, aquellos movimientos que mantienen la formación de los gatos, es decir, aquellos que no generan huecos. De este modo, la probabilidad de que el “deadline” nos pille habiendo generado y analizado jugadas malas se reduce.

Otras técnicas:

Hay más técnicas para acelerar el proceso de generar y evaluar el árbol de juego. Por ejemplo, si dos secuencias de jugadas distintas llevan al mismo tablero, no hay necesidad de desarrollar ese tablero dos veces. La segunda vez que se presente el mismo tablero en el árbol de juego, se puede detectar que ya se ha dado antes y copiar su evaluación previa, sin necesidad de desarrollarlo más.

Para que dos tableros sean idénticos las piezas deben ocupar las mismas casillas y, además, el turno de juego debe ser el mismo.

Y como recorrerse todo el árbol generado previamente a la caza y captura de un tablero igual que el actual sería inviable, puesto que costaría más hacerlo que lo que se ahorraría, lo que se suele hacer es definir una especie de “función hash” que, dado un tablero, genera un número (ej. la suma de los offsets de los gatos menos el offset del ratón). Luego estos números se almacenan en una tabla ordenada y, si al generar un nuevo tablero su “hash” ya está en la tabla, asumimos que el tablero es repetido y actuamos en consecuencia.

Bueno, iremos viendo hasta dónde llegamos…

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…