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

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s