RYG: tableros más compactos – mayor profundidad de análisis #Programación retro del Commodore 64

Ya llevamos tres versiones de la función de evaluación que permite al C64, junto con el procedimiento minimax, decidir sus jugadas.

En la primera versión, hemos considerado como criterios la fila del ratón y el número de jugadas que puede hacer (incluyendo las situaciones particulares de que la fila del ratón sea cero – en cuyo caso gana el ratón – y de que su número de jugadas sea cero – en cuyo caso ganan los gatos –). En la segunda versión, hemos añadido como criterio que los gatos guarden una formación (una fila o dos). Y en la tercera versión, hemos añadido como criterio detectar si el ratón rebasa a los gatos. Y así deberíamos continuar añadiendo y revisando criterios hasta conseguir que el juego sea lo suficientemente fuerte.

Si a pesar de añadir muchos criterios no se consigue un juego fuerte, una medida complementaria (no sustitutiva) es ampliar la profundidad de análisis. Para ello ya sabemos que necesitamos más memoria y, si no disponemos de ella, hay que aprovechar mejor la disponible. Dicho de otro modo, hay que compactar las estructuras de datos.

Esto ya lo habíamos comentado muchas veces, y hasta ahora nos habíamos resistido por no complicar la programación, pero por fin ha llegado el momento.

Nueva estructura de datos compactada:

Los tableros usados hasta ahora eran así:

  • Cabecera: 3 bytes.
  • Nivel, turno y valor: 3 bytes.
  • Dirección del padre: 2 bytes.
  • Direcciones de los hijos: 2 x 8 = 16 bytes.
  • Tablero propiamente dicho: 8 x 8 = 64 bytes.
  • Total: 88 bytes.

De esos 88 bytes, la gran mayoría (64 bytes, el 73%) son el tablero propiamente dicho, es decir, el escaqueado de 8 x 8 casillas. Por tanto, éste es el gran candidato a una fuerte reducción.

Teniendo en cuenta que sólo tenemos cinco piezas, y que no hay capturas, esos 64 bytes se puede reducir a sólo cinco:

  • Un byte para guardar la posición del ratón.
  • Cuatro bytes para guardar las posiciones de los gatos.

Todas las demás posiciones del tablero, se consideran vacías.

Las posiciones del ratón y los gatos se podrían guardar en formato (fila, columna) pero, puestos a ahorrar memoria, casi mejor guardar los offsets (desplazamientos) respecto a la casilla (0, 0) del tablero, es decir, esto:

Offsets

Es decir, en la posición inicial del juego los offsets serían:

  • Gatos = 0, 2, 4 y 6.
  • Ratón = 59.

De este modo, el tablero compactado queda así:

  • Cabecera: 3 bytes.
  • Nivel, turno y valor: 3 bytes.
  • Dirección del padre: 2 bytes.
  • Direcciones de los hijos: 2 x 8 = 16 bytes.
  • Tablero propiamente dicho: 5 bytes.
  • Total: 29 bytes.

Es decir, hemos conseguido una reducción de 88 – 29 = 59 bytes, del 67%.

Reducciones adicionales:

El tablero se puede seguir compactando. El siguiente candidato por tamaño sería la tabla con las direcciones de los hijos (16 bytes), ya que no todos los tableros tendrán ocho hijos.

Se podría hacer una tabla de tamaño variable, marcando el final de la misma con algún marcador. O se podrían diseñar dos estructuras de datos, una con un máximo de ocho hijos para cuando muevan los gatos y otra con un máximo de cuatro hijos para cuando mueva el ratón.

En cualquier caso, es improbable que ahorrar 4 hijos / 8 bytes, y sólo en algunos tableros, permita ganar niveles adicionales en la profundidad de análisis, especialmente si se tiene en cuenta que el crecimiento del árbol de juego (número de tableros) es exponencial con la profundidad.

También se podría quitar la cabecera (tres bytes), aunque facilita la depuración de los datos y los programas, porque facilita identificar dónde empiezan los tableros en memoria.

Como no parecen opciones muy prometedoras, de momento, nos conformaremos con los tableros de 29 bytes.

Nueva profundidad de análisis:

Con este nuevo tamaño de tablero, las previsiones de consumo de memoria en función de los niveles de profundidad quedan así:

  • 1 nivel => 29 bytes x 8 movimientos = 232 bytes.
  • 2 niveles => 29 bytes x 8 x 4 = 928 bytes.
  • 3 niveles => 29 bytes x 8 x 4 x 8 = 7424 bytes.
  • 4 niveles => 29 bytes x 8 x 4 x 8 x 4 = 29696 bytes.
  • 5 niveles => 29 bytes x 8 x 4 x 8 x 4 x 8 = 237568 bytes.

Por tanto, al compactar los tableros de 88 a 29 bytes conseguimos subir de tres a cuatro niveles en la profundidad de análisis (29 KB). No podemos subir a cinco niveles porque el C64 no tiene esos 237 KB.

Es decir, a la hora de decidir su jugada, ahora el C64 podrá tener en cuenta los efectos de su jugada inmediata, la siguiente jugada del humano, nuevamente la jugada del C64 y, por último, la siguiente jugada del humano.

El número máximo de tableros a analizar por cada jugada será de 8 x 4 x 8 x 4 = 1024 tableros, aunque con frecuencia serán menos porque no siempre serán posibles todas las jugadas que en principio permiten las reglas de movimiento.

Todos estos cambios tienen su impacto en el código. Esto lo veremos ya en la entrada que sigue, aunque se adelanta la versión 18 del proyecto.


Código del proyecto: RYG18


Editar

Josepzin

No hay comentarios:

Publicar un comentario