En la entrada "RYG: programa principal" ya hicimos una estimación de la profundidad de análisis que puede tener el juego. Si actualizamos aquellos cálculos para tableros de 88 bytes quedan así:
- 1 nivel => 88 bytes x 8 movimientos = 704 bytes.
- 2 niveles => 88 bytes x 8 x 4 = 2816 bytes.
- 3 niveles => 88 bytes x 8 x 4 x 8 = 22528 bytes.
- 4 niveles => 88 bytes x 8 x 4 x 8 x 4 = 90112 bytes.
Por tanto, para trabajar con 4 niveles de profundidad necesitaríamos unos 90 KB. Y lógicamente el C64 no los tiene.
Pero es que, además, como la versión 10 del proyecto ya es capaz de generar el árbol de juego completo, podemos comprobarlo empíricamente:
Árbol de profundidad 3:
Si el usuario pide el árbol de profundidad 3, el último tablero que se genera después de unos minutos de "pensar" es éste:
La dirección $6100 todavía está por debajo de la dirección de base del intérprete de BASIC, es decir, $a000.
De hecho, si de $6100 restamos $19d8, que es el valor que toma la etiqueta "raizArbol" en esta versión del proyecto, el resultado es $6100 – $19d8 = $4728 = 18216 bytes. Es decir, 18216/88 = 207 tableros. En realidad 208, si incluimos también el último tablero, el que empieza en $6100.
Esto viene a ser casi lo mismo que 8 movimientos de los gatos x 4 movimientos del ratón x 8 movimientos de los gatos = 256 tableros, si no fuera porque no siempre los gatos tienen ocho movimientos ni el ratón cuatro. A veces tienen menos. Todo encaja.
Árbol de profundidad 4:
Sin embargo, si el usuario pide el árbol de profundidad 4, a partir de $a000 se generan tableros así:
Obsérvese que el tablero no está bien generado, pero el programa tampoco "casca" de momento. El motivo es el modelo de "RAM bajo ROM" del C64. Por encima de la dirección $a000, los "sta" operan sobre RAM, pero los "lda" leen de ROM. El resultado es que los tableros no están bien, pero el programa como tal tampoco falla.
Y a partir de $d000, es decir, cuando ya llegamos al VIC, se empieza a ver esto:
Esto es porque los "sta" que vamos ejecutando para generar el árbol van modificando los registros del VIC y, en particular, cambian los modos gráficos.
Por último, el VICE se acaba quedando "tostado".
Alternativas:
Ante esta situación, tenemos varias alternativas:
- Conformarnos con tres niveles de profundidad.
- Ampliar la memoria disponible desactivando la ROM del intérprete de BASIC y la del Kernal.
- Aprovechar más la memoria disponible diseñando estructuras de datos más compactas.
Estas medidas no son necesariamente excluyentes; pueden ser complementarias.
Conformarse con tres niveles de profundidad es perfectamente posible, especialmente si la función de evaluación es buena. Como ya se comentó en la entrada "La función de evaluación" el árbol de juego y la función de evaluación conforman un compromiso. Si el árbol de juego pudiera ser ilimitado, la función de evaluación podría ser muy tonta (llegaría con que detectara que un bando gana). Contrariamente, dado que el árbol normalmente tendrá que ser limitado, hará falta una función de evaluación "fuerte" que sirva para valorar cómo de prometedora es una línea de juego.
Por otro lado, uno de los fuertes del C64 es su capacidad para configurar su memoria. Efectivamente, actuando sobre los bits del registro R6510 = $0001 es posible ampliar la RAM disponible desactivando el intérprete de BASIC ($a000 – $bfff) y el Kernal ($e000 – $ffff). En nuestro caso, es posible desactivar el intérprete de BASIC, puesto que no lo usamos, pero sí usamos rutinas del Kernal como "chrout".
Por último, es posible diseñar estructuras de datos más compactas. Por ejemplo, en vez de usar una matriz de 8 x 8 = 64 bytes para guardar el tablero, es posible guardar información equivalente con sólo 5 bytes:
- 1 byte = offset respecto a la casilla (0, 0) del ratón.
- 1 byte = offset respecto a la casilla (0, 0) del gato 1.
- …
- 1 byte = offset respecto a la casilla (0, 0) del gato 4.
Con sólo 5 bytes has resuelto la misma papeleta que antes resolvías con 64. Y se pueden tomar medidas similares con el resto de campos que acompañan a un tablero (nivel, turno, valor, padre e hijos).
El problema de hacer esto es que se te complica la programación, por ejemplo, la generación de jugadas. Generar jugadas sobre un tablero de 8 x 8 es relativamente fácil; basta con sumar los incrementos / decrementos permitidos por las reglas de juego en las coordenadas (X, Y) de las piezas. Pero si en vez de tener las posiciones (X, Y) tienes el offset respecto al origen…
Una posibilidad es guardar los tableros en RAM en formato comprimido, pero trabajar con ellos (ej. generar jugadas) en formato descomprimido. Ganas espacio, pero pierdes capacidad de cómputo en comprimir / descomprimir tableros.
Conclusiones:
Sea como fuere, las medidas que vamos a aplicar a nuestro caso son dos:
- Vamos a limitar el número de niveles a tres.
- Vamos a ampliar la RAM disponible desactivando el intérprete de BASIC.
La primera medida la tomamos ya en la versión 11 del proyecto.
La segunda media la aplicamos en alguna versión posterior, casi más por ponerla en práctica que por su efectividad, puesto que ganar los $bfff – $a000 = 8 KBytes del intérprete de BASIC tampoco es suficiente para alcanzar un nivel extra de profundidad.
El siguiente paso será ya la función de evaluación. ¿Conseguiremos que sea lo suficientemente fuerte como para compensar un árbol de profundidad limitada?
Código del proyecto: RYG11
No hay comentarios:
Publicar un comentario