Tablas hash de movimientos

Una tabla está claro lo que es: un conjunto de posiciones de memoria contiguas a las que se accede mediante el uso de un índice. El índice empieza en cero y termina en N-1, siendo N el tamaño de la tabla:

Hay tablas unidimensionales, también llamadas vectores o arrays, tablas bidimensionales, etc.

Pues bien, hay un tipo especial de tabla llamada “tabla hash”. Se trata de una tabla convencional a la que se accede mediante un índice que se obtiene de calcular el hash de una estructura de datos más compleja, por ejemplo, de un tablero. Las tablas hash se describen aquí:

https://es.wikipedia.org/wiki/Tabla_hash

Las tablas hash, igual que las tablas convencionales, valen para guardar y recuperar datos. En nuestro caso, vamos a usar dos tablas hash para guardar el mejor movimiento asociado a cada tablero o posición. El motivo de usar dos tablas hash, una para ratón y otra para gatos, radica en que para que un tablero esté totalmente definido no llega con conocer la ubicación de las piezas; además hay que saber a qué bando le toca mover.

Tablas “hashpos_mouse” y “hashpos_cats”:

Según lo visto, vamos a definir dos tablas:

• “hashpos_mouse”: Esta tabla servirá para guardar el mejor movimiento asociado a un tablero cuando sea el turno del ratón.
• “hashpos_cats”: Esta tabla servirá para guardar el mejor movimiento asociado a un tablero cuando sea el turno de los gatos.

Pero, en realidad, dado que los movimientos requieren de un origen y un destino, las tablas anteriores son dobles:

• “hashpos_mouse_start” y “hashpos_mouse_dest”: Para guardar el mejor movimiento (origen y destino) asociado a un tablero cuando sea el turno del ratón.
• “hashpos_cats_start” y “hashpos_cats_dest”: Para guardar el mejor movimiento (origen y destino) asociado a un tablero cuando sea el turno de los gatos.

Gráficamente sería algo así:

Es decir, partiendo de un tablero, si es el turno del ratón, se obtiene el hash del tablero y el mejor movimiento identificado (origen + destino) se guarda en la tabla hash del ratón (“hashpos_mouse”), concretamente en la posición correspondiente al hash del tablero. Y lo mismo si es el turno de los gatos, pero usando para ello la tabla hash de los gatos (“hashpos_cats”).

Para recuperar el mejor movimiento asociado a un tablero se procede de manera análoga. Partiendo del tablero, se obtiene su hash y, en función del turno, se lee el movimiento de una tabla y otra.

Las tablas hash se definen en el fichero “Hash.asm”:

Las tablas se inicializan a $ff, pero igualmente se podría inicializar a $00. El motivo de hacerlo a $ff radica en que $00 = 0 = A1 es una casilla válida de modo que, para evitar confusiones, se prefiere inicializar a $ff.

Rutinas “addHashPosMouse” y “addHashPosCats”:

La forma de almacenar movimientos vinculados a tableros en estas tablas es mediante las rutinas “addHashPosMouse” y “addHashPosCats”. Ambas rutinas son muy parecidas, siendo la principal diferencia que la primera almacena el movimiento en la tabla “hashpos_mouse” y la segunda en “hashpos_cats”. Por este motivo, sólo se revisará la primera:

Como se puede observar, la rutina “addHashPosMouse”:

• Lee el hash del tablero actual (“current_hash”).
• Consulta el valor almacenado en la tabla “hashpos_mouse” correspondiente a ese hash.
• Si el valor es $ff (valor inicial), eso significa que la posición todavía está vacía. Por tanto, no se produce “colisión”. Se almacena el movimiento (origen, destino) en esa posición.
• Si el valor es distinto de $ff, eso significa que la posición ya había sido usada. Por tanto, se produce una “colisión” y se incrementa el contador “coll_mouse”. Igualmente, se almacena el movimiento (origen, destino) en esa posición.

Rutinas “lookUpMouse” y “lookUpCats”:

La forma de leer movimientos vinculados a tableros a partir de estas tablas es mediante las rutinas “lookUpMouse” y “lookUpCats”. Ambas rutinas son muy parecidas, siendo la principal diferencia que la primera lee el movimiento de la tabla “hashpos_mouse” y la segunda de “hashpos_cats”. Por este motivo, sólo se revisará la primera:

Como se puede observar, la rutina “lookUpMouse”:

• Lee el hash del tablero actual (“current_hash”).
• Consulta el valor almacenado en la tabla “hashpos_mouse” correspondiente a ese hash.
• Si el valor es $ff (valor inicial), eso significa que la posición todavía está vacía. Por tanto, almacena $ff en “hash_start” y “hash_dest”, lo cual viene a ser una señal de que el tablero consultado no tiene movimiento asociado.
• Si el valor es distinto de $ff, eso significa que la posición ya ha sido usada y contiene un movimiento. Por tanto, lee el movimiento y lo devuelve en “hash_start” y “hash_dest”.

Nuevo programa principal:

Con el objeto de probar todo esto de las tablas hash mejoramos “Display.asm” con:

• Rutinas para imprimir las tablas aleatorias (“displayHashMouse” y “displayHashCatN”).
• Y rutinas para imprimir el contenido de las tablas hash de ratón y gatos (“displayHashPosMouse” y “displayHashPosCats”).

Además, definimos un nuevo programa principal con este aspecto:

Es decir, el programa inicializa e imprime el tablero, y luego:

• Llama a la rutina “testRandomizeHashes”. Esta rutina imprime el contenido inicial de las tablas aleatorias, luego las inicializa con valores aleatorios, y luego las vuelve a imprimir.
• Llama a la rutina “testAddHashAndLookUp”. Esta rutina consulta el movimiento asociado a un tablero en la tabla hash del ratón (inicialmente no existe), luego inserta el movimiento 4 => 13 (E1 => F2), y luego vuelve a consultar el movimiento.
• Llama a la rutina “testHashPositions”, que pinta el contenido de las tablas hash de ratón y gatos.

En definitiva, todo pruebas orientadas a validar el funcionamiento de las tablas aleatorias, las tablas hash, y las rutinas para guardar y leer movimientos:

---

Código del proyecto: RYG3-03