Tablas de historia

Programación retro del Commodore 64

  • Programación retro del Commodore 64
  • “Programación Retro del Commodore 64” es un blog sobre el hardware, el sistema operativo, y la programación del Commodore 64. Y más específicamente sobre programación en ensamblador. Pretende ser un blog con información de calidad, y referencia en español de la programación retro de esta maravillosa máquina.
    • Mi blog
« Publicado el: 27/06/2022 »

Las tablas de historia son una forma adicional de mejorar la ordenación de movimientos y, por tanto, la poda alfa – beta.

La idea básica es definir una tabla de doble entrada (origen, destino) o, lo que es lo mismo, 64 tablas (con 64 destinos cada una), una tabla por cada casilla origen. Por eso hablamos de “tablas de historia”.

Cada vez que un movimiento (origen, destino) se inserta en la tabla hash, además, se incrementa el valor (origen, destino) en la tabla de historia correspondiente. Ese incremento puede ser de un punto o, mejor, de tantos puntos como la profundidad de análisis a la que se produzca la inserción (“depth”).

Posteriormente, cuando la rutina “gen” genera los movimientos, en vez de nacer todos con puntuación 0, pueden nacer con una puntuación igual a la que figure en las tablas de historia.

En el fondo es algo como decir, “si este movimiento fue bueno en el pasado, es probable que vuelva a serlo ahora y, por tanto, voy a desarrollarlo antes”. No se trata de dar ese movimiento por bueno, o de seleccionarlo como mejor movimiento; se trata, simplemente, de desarrollarlo antes que otros confiando en que vuelva a ser bueno y que mejore la poda.

Por último, las tablas de historia pueden inicializarse al comienzo de la partida e ir dándoles valor y utilizándolas durante toda la partida o, según el caso, inicializarlas con cada nuevo movimiento o proceso de búsqueda. En un juego como el ratón y el gato no es probable que un movimiento que fue bueno hace N jugadas vuelva a ser bueno ahora, así que mejor inicializar las tablas de historia en cada proceso de búsqueda.

Desde el punto de vista del código ensamblador, las principales novedades se concentran en un nuevo fichero “History.asm”. Este fichero contiene:

  • La definición de las 64 tablas de historia (una por cada casilla origen).
  • Unos punteros para acceder a las tablas anteriores.
  • La rutina “getHistory” que, dado un movimiento, consulta su puntuación en las tablas de historia.
  • La rutina “incHistory” que, dado un movimiento, incrementa su puntuación en las tablas de historia.
  • La rutina “newHistory” que inicializa las tablas de historia.

Todo esto se revisa a continuación:

Tablas de historia:

Hay 64 tablas de historia, una por cada casilla origen. Y cada tabla de historia tiene 64 posiciones, una por cada casilla destino. Es decir, las tablas de historia ocupan 64 x 64 = 4 KB.

Teniendo en cuenta que no todos los orígenes son posibles, ni tampoco todos los destinos, dado que el ratón y los gatos siempre se mueven por casillas negras (marcadas con “X”), las tablas de historia se podrían compactar. Sin embargo, por facilidad de programación, dado que las posiciones origen y destino se determinan con un índice entre 0 y 63, se van a mantener así.

Podríamos definir las 64 tablas una detrás de otra, en plan:

Sin embargo, esto daría bastante trabajo y ocuparía bastante espacio en el fichero “History.asm”. Por ello, vamos a usar una funcionalidad muy interesante de CBM prg Studio, que consiste en usar directivas:

Esto lo que viene a decir es:

  • Empezando en index = 0.
  • Y terminando en index = 63.
  • Mete una tabla history_index, donde “index” se sustituye por su valor.

De este modo acabamos con 64 tablas de historia, desde history_0 (para la casilla origen 0) hasta history_63 (para la casilla origen 63). Cada tabla de historia tiene 64 destinos posibles.

Esto se puede comprobar fácilmente en el “assembly dump” al ensamblar con Ctrl + F5 desde CBM prg Studio:

Por tanto, hemos definido 64 tablas. Veamos cómo acceder a ellas.

Punteros para acceso a las tablas de historia:

Dado un movimiento (origen, destino), tendremos que acceder a la tabla de historia de ese origen, ya sea para incrementar o para leer el valor del destino en esa tabla.

Esto lo vamos a lograr con una técnica similar:

De este modo conseguimos dos tablas:

  • Una llamada “histLo” con las partes low (partes menos significativas) de los punteros de acceso a las tablas de historia.
  • Otra llamada “histHi” con las partes high (partes más significativas) de los punteros de acceso a las tablas de historia.

De este modo, accediendo a ese par de tablas usando la casilla origen como índice podemos fácilmente componer un puntero (lo, hi) para acceder a la tabla de historia correspondiente.

Aquí puede verse que al ensamblar con Ctrl + F5, efectivamente, se ha formado una tabla con las partes low (<) de los punteros y otra con las partes high (>):

Rutina “getHistory”:

Con las piezas anteriores resulta fácil leer o escribir en las tablas de historia. Por ejemplo, para leer el valor de historia del movimiento (start, dest) se utilizaría la rutina “getHistory”, que es así:

Esta rutina:

  • Carga la posición origen “ghStart” en el índice Y.
  • Usando Y / “ghStart” como índice, lee la parte low del puntero de acceso a la tabla de historia. Este valor lo graba en $fb.
  • Usando Y / “ghStart” como índice, lee la parte high del puntero de acceso a la tabla de historia. Este valor lo graba en $fc.
  • Carga la posición destino “ghDest” en el índice Y.
  • Usando el direccionamiento indirecto – indexado (lda ($fb),y), es decir, usando $fb – $fc como puntero base y sumando Y / “ghDest”, accede al valor de historia.

En este caso el valor de historia se devuelve directamente en el acumulador, porque se va a usar desde ahí. En otras rutinas este valor se hubiera guardado en una variable “ghScore” o similar.

Rutina “incHistory”:

Para incrementar el valor de historia la rutina es muy similar a la anterior:

Las ideas son muy parecidas, es decir, se monta un puntero a la tabla de historia correspondiente con ($fb – $fc), siendo las principales diferencias:

  • Se lee el valor de la tabla de historia con lda($fb),y, pero además se suma con adc la puntuación pasada en el parámetro “ihAdd”.
  • Si el resultado de la suma excede $ff = 255, se topa a 255.
  • El nuevo valor resultante se guarda en la tabla de historia con sta($fb),y.

En definitiva, se incrementa el valor de la tabla de historia en “ihAdd”, pero a su vez se pone un tope de $ff = 255.

Rutina “newHistory”:

La rutina “newHistory” sirve para inicializar las tablas de historia. Esto puede hacerse al comienzo de la partida o, como vamos a hacer, al comenzar el proceso de búsqueda alfa – beta.

Como se puede ver, esta rutina es un doble bucle:

  • El bucle exterior va desde X=0 hasta X=63.
  • Lo primero que hace es preparar un puntero ($fb – $fc) a la base de la tabla de historia X.
  • El bucle interior va desde Y=0 hasta Y=63, es decir, recorre las 64 posiciones de la tabla de historia X.
  • En cada una de esas 64 posiciones se almacena un 0 (sta($fb),y).

Esta rutina también se puede optimizar puesto que, como ya se ha dicho, hay posiciones (las casillas blancas o marcadas con “.”) que no se usan como origen ni como destino y, por tanto, no hace falta inicializarlas. Esto es especialmente cierto en el caso de las casillas origen, porque de forma directa te ahorras inicializar la mitad de las tablas de historia (porque no se usan).

Con esto acabamos la descripción de las tablas de historia, aunque ahora falta utilizarlas, cosa que ya haremos en la entrada siguiente.


Código del proyecto: RYG3-11