Hash de un tablero

En informática, un “hash” es una especie de huella o resumen de un conjunto de datos. El hash se elabora aplicando un algoritmo de hashing. Algunos algoritmos habituales son MD5, SHA1, SHA256, etc. Se utilizan mucho en el ámbito de la seguridad, sobre todo para garantizar la integridad de la información: si un solo bit de los datos cambiara, esta situación se detectaría inmediatamente porque también cambiaría el hash. Además, es imposible recuperar los datos originales a partir del hash.

Pues bien, un hash se puede obtener a partir de cualquier conjunto de datos arbitrario. En nuestro caso, nos va a interesar obtener un hash de un tablero porque vamos a utilizar ese hash para guardar y recuperar datos asociados al tablero, concretamente el mejor movimiento a partir de él.

Nuestro algoritmo de hash va a ser inventado. Como dato de entrada, va a tomar el tablero (“board”) y, como dato de salida, va a generar un byte, es decir, un valor entre 0 y 255. Y el algoritmo va a consistir en recorrer todas las casillas del tablero, determinar su contenido (vacía, ratón o gato), en función del contenido leer un valor de unas tablas generadas aleatoriamente, e ir haciendo el OR exclusivo (instrucción “eor”) de estos valores.

De este modo, dados dos tableros distintos, es decir, con las piezas sobre casillas distintas, como se consultarán posiciones distintas de las tablas generadas aleatoriamente, se obtendrán hashes distintos.

Tablas con valores aleatorios:

Todo esto del hash lo vamos a gestionar con un fichero nuevo “Hash.asm”. En este fichero vamos a definir cinco tablas con valores generados aleatoriamente, una tabla por cada pieza (“hash_mouse”, “hash_cat1”, “hash_cat2”, “hash_cat3” y “hash_cat4”):

Las tablas son todas de 64 posiciones, igual que el tablero. Se inicializan a cero, pero posteriormente se les da valores aleatorios.

Generación de valores aleatorios con el SID:

Como se vio en las entradas dedicadas el SID en el Volumen I, el chip de sonido del C64 tiene tres voces, y la tercera voz puede usarse para generar valores aleatorios.

Para ello hace falta:

Configurar la frecuencia de la tercera voz (registros $d40e y $d40f).
Activar la tercera voz y configurar su forma de onda (registro $d412).
Leer los valores aleatorios (señal de ruido) de la salida de la tercera voz (registro $d41b).

Todo esto vamos a hacerlo con la rutina “randomize” y las subrutinas “randHashMouse”, “randHashCat1”, …, “randHashCat4” del fichero “Hash.asm”:

Como se puede observar, la rutina “randomize”:

Configura la frecuencia $ffff en $d40e – $d40f.
Configura la forma de onda “ruido” activando el bit 7 de $d412
Activa la tercera voz activando el bit 0 de $d412.
Y lee un primer valor aleatorio de $d41b. Lo guarda en “seed”.
Llama a las cinco subrutinas.

Por su parte, las cinco subrutinas son casi iguales, cambiando sólo la tabla en que se guardan los valores aleatorios generados, por lo que sólo revisaremos “randHashMouse”:

La subrutina “randHashMouse” hace lo siguiente:

Con el registro X, ejecuta 64 iteraciones, tantas como posiciones tiene el tablero y la tabla aleatoria “hash_mouse”.
Lee otro valor aleatorio de $d41b.
Hace el OR exclusivo (“eor”) del valor recién leído y “seed”.
El resultado lo guarda en “seed” y en la posición X de “hash_mouse”.

Y las otras cuatro subrutinas hacen algo totalmente análogo, cambiando únicamente la tabla en la que guardan los datos aleatorios.

Tras ejecutar “randomize” la tabla “hash_mouse” y las otras tablas quedarán con un contenido similar a este. Además, el contenido cambiará de una ejecución a otra, al ser valores aleatorios generados a partir del SID:

Generación del hash de un tablero:

Una vez que tenemos las cinco tablas, una por pieza, con los valores aleatorios, ya podemos generar el hash del tablero. Esto lo hacemos con la rutina “getHash” de “Hash.asm”:

El algoritmo es el ya comentado anteriormente:

Partimos de un resultado inicializado a cero.
Con el índice X, recorremos todas las casillas del tablero “board”.
Determinamos el contenido de cada casilla (vacía, ratón o gato).
Si el contenido es ratón, lee el valor de “hash_mouse” correspondiente a la casilla X y hace el OR exclusivo.
Si el contenido es el gato N, lee el valor de “hash_catN” correspondiente a la casilla X y hace el OR exclusivo.
Si el contenido es vacío, pasa a la siguiente casilla.

De este modo, y tras mejorar la rutina “displayBoard” para añadir el hash, ya es posible obtener e imprimir el hash del tablero: