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:
- Desarrollamos el primer nivel por debajo de la raíz:
- Desarrollamos el segundo nivel para el primer tablero del primer nivel:
- Y así sucesivamente hasta que…
- Desarrollamos el segundo nivel para el último tablero del primer nivel:
- 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.
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:
- Ahora desarrollamos la primera rama hasta su máxima profundidad:
- Aplicamos minimax a la primera rama:
- 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:
- 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.
- 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.
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!!
