RYG: otra forma mejor de generar el árbol de juego ��� cambios en el código #Programación retro del Commodore 64

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"):

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

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:

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

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"):

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í:

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

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:

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:

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:

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:

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":

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