Mes: febrero 2022

En la entrada anterior ya vimos qué es el lock: un segundo hash que complementa al hash original de un tablero, y que sirve para reducir la probabilidad de que dos tableros distintos tengan el mismo hash (y lock), de modo que se puedan evitar errores en el uso de las tablas hash como consecuencia de las colisiones.

Vamos a ver cómo introducir el lock en el programa:

Tablas con valores aleatorios para el lock:

El programa original utilizaba las tablas “hash_mouse” y “hash_catN” para almacenar unos valores aleatorios generados a partir del SID y luego utilizar esos valores aleatorios para generar el hash de un tablero.

Pues bien, el programa mejorado tendrá unas nuevas tablas “lock_mouse” y “lock_catN” totalmente equivalentes:

Estas nuevas tablas se rellenarán con valores aleatorios mediante una nueva versión de la rutina “randomize”.

Nueva rutina “randomize”:

La versión original de la rutina “randomize”:

• Inicializaba la frecuencia de la tercera voz del SID ($ffff).
• Configuraba la forma de onda a “ruido” y activaba la tercera voz.
• Leía un primer valor aleatorio de la tercera voz (“seed”).
• Inicializaba las tablas “hash_mouse” y “hash_catN” con valores aleatorios, usando para ello las rutinas auxiliares “randHash*”.

Pues bien, la nueva rutina “randomize” hace todo lo anterior y, además, inicializa las tablas “lock_mouse” y “lock_catN” con valores aleatorios mediante el uso de unas nuevas rutinas auxiliares “randLock*”:

Las nuevas rutinas auxiliares “randLock*” son totalmente equivalentes a las rutinas “randHash*” anteriores.

Generación del lock de un tablero:

Igual que en el programa original había que generar el hash de un tablero, para lo cual se utilizaba la rutina “getHash”, ahora hay que generar el lock de un tablero, para lo cual se utiliza una nueva rutina “getLock”:

La nueva rutina “getLock” es totalmente equivalente a “getHash”, es decir, inicializa el lock a cero y recorre el tablero localizando piezas (ratón o gatos), en función de las cuales consulta las posiciones análogas de las tablas aleatorias (“lock_mouse” y “lock_catN”), haciendo el OR exclusivo (“eor”) de esos valores. El resultado es el lock del tablero.

Nuevas tablas “hashpos_mouse” y “hashpos_cats” con lock:

Los tableros ya tienen un hash y un lock (un segundo hash). Ahora vamos a ver qué hacemos con ellos, especialmente con el lock:

Una primera opción sería que las tablas hash “hashpos_mouse” y “hashpos_cats”, que recordemos que sirven para almacenar el mejor movimiento asociado a un tablero, fueran tablas de doble entrada. Es decir, en vez de usar como índice el hash, podríamos usar como índices el hash y el lock. De este modo, como es muy improbable que dos tableros distintos tengan el mismo hash y el mismo lock, es muy improbable que se dé una colisión.

Ahora bien, el hash ocupa un byte (256 posibles valores) y el lock también. Eso significa que una tabla de doble entrada hash x lock tendría 256 x 256 posiciones, es decir, 65.536 posiciones o, lo que es lo mismo, toda la RAM del C64. Por tanto, este enfoque no es viable.

Una segunda opción consiste en que las tablas hash “hashpos_mouse” y “hashpos_cats” sigan siendo tablas unidimensionales (índice = hash) pero, además de un movimiento (origen, destino), también almacenen el lock del tablero asociado:

• “hashpos_mouse_start”, “hashpos_mouse_dest” y “hashpos_mouse
  _lock”.
• “hashpos_cats_start”, “hashpos_cats_dest” y “hashpos_cats
  _lock”.

De este modo, sigue siendo posible que dos tableros distintos tengan el mismo hash, y sigue siendo posible que el segundo movimiento que se almacene en la tabla hash “machaque” el primero (colisión), pero, tras consultar el mejor movimiento asociado a un tablero, y mediante la verificación del lock almacenado, podemos saber si ese “mejor movimiento” efectivamente proviene del tablero actual o de otro tablero con el mismo hash. Es decir, podemos saber si proviene de una colisión o no y, en caso afirmativo, al menos podemos evitar usar ese movimiento.

Es decir, con el lock no eliminamos las colisiones, ni tampoco reducimos su probabilidad, para ser sinceros, pero al menos las detectamos y evitamos usar información incorrecta.

Nuevas rutinas “addHashPosMouse” y “addHashPosCats”:

Las rutinas “addHashPosMouse” y “addHashPosCats” sirven para almacenar en la tabla hash el mejor movimiento asociado a un tablero, en función de que sea el turno del ratón o los gatos, respectivamente.

Ahora, dado que las tablas hash van a tener un movimiento (origen, destino) y un lock, hay que mejorar estas rutinas para almacenar el lock. En el caso de la rutina “addHashPosMouse” queda así:

La rutina “addHasPosCats” es totalmente equivalente.

Nuevas rutinas “lookUpMouse” y “lookUpCats”:

Las rutinas “lookUpMouse” y “lookUpCats” sirven para consultar en las tablas hash el mejor movimiento asociado a un tablero. Anteriormente, había dos opciones:

• La posición de la tabla hash correspondiente al hash del tablero estaba vacía (valor = $ff). En ese caso se devolvía una señal.
• La posición de la tabla hash correspondiente al hash del tablero tenía un movimiento (valor <> $ff). En ese caso se devolvía el movimiento (start, dest) en (hash_start, hash_dest).

Pues bien, ahora hay una opción intermedia, consistente en que la posición de la tabla hash no está vacía (valor <> $ff), sino que tiene un movimiento, pero tiene un lock diferente al del tablero actual. Es decir, se trata de una colisión. En este caso, se devuelve una señal igual que en el caso vacío, que puede ser exactamente la misma señal o una diferente, si se quieren distinguir las situaciones:

Nótese la instrucción “bne lumFalse” de la línea 980 de “Hash.asm”. En esa línea se está detectando la colisión al consultar el mejor movimiento asociado al tablero.

Nuevo programa principal:

Por último, hacemos un nuevo programa principal para probar el lock. El nuevo programa principal es muy parecido al anterior:

Es decir:

• Inicializa e imprime el tablero.
• Llama a la rutina “testRandomizeLocks”. Esta rutina imprime el contenido inicial de las tablas aleatorias del lock, 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), ya con el lock, 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.

De este modo, el resultado de la ejecución es así (el “00” que se ve a la derecha del movimiento “E1F2” es el lock almacenado en la tabla hash):

---

Código del proyecto: RYG3-04

Es improbable que dos tableros distintos, es decir, con el ratón y/o los gatos en posiciones distintas, den lugar al mismo hash. Es improbable porque, en función de las piezas y sus posiciones, se consultan unas posiciones u otras de las tablas generadas aleatoriamente (“hash_*”) y, por tanto, se utilizan números diferentes para el OR exclusivo. Sin embargo, aunque improbable, no es imposible.

Esto es lo que se llama una “colisión”. Si dos tableros distintos dan lugar al mismo hash, a la hora de insertar el mejor movimiento asociado en la tabla hash (“hashpos_*”), se producirá una colisión, puesto que ambos movimientos se almacenarán en la misma posición de la tabla hash. El que se almacene en segundo lugar “machacará” al que se haya almacenado en primer lugar.

Lógicamente, que haya colisiones no es bueno para el funcionamiento del programa. Las tablas hash valen para almacenar y consultar el mejor movimiento asociado a un tablero. Por tanto, si se producen colisiones esa información se pierde para algunos tableros al sustituirse por la de otros tableros que tienen el mismo hash. Peor que perderse, se sustituye por otra información posterior. Es decir, el programa puede tomar decisiones incorrectas sobre los movimientos a realizar.

Hay técnicas para resolver las colisiones, como se puede ver en https://es.wikipedia.org/wiki/Tabla_hash#Resoluci%C3%B3n_de_colisiones. Y también hay técnicas para reducir la probabilidad de que ocurran sin llegar a reducirla a cero.

Una primera técnica consiste en que las tablas hash sean muy grandes o, lo que es lo mismo, que haya muchos hashes posibles. En nuestro caso, dado que el hash ocupa un byte sólo hay 256 valores posibles y las tablas hash (“hashpos_*”) tienen 256 posiciones. Pero se podrían usar 9 bits para el hash, en vez de 8, en cuyo caso habría 512 hashes posibles y dos tablas hash de 512 posiciones.

Y otra técnica es complementar el hash con un “lock”, que no deja de ser lo mismo, es decir, un segundo hash, pero elaborado a partir de otras tablas aleatorias. De este modo, todo tablero tiene dos hashes (un hash y un lock) y, ahora ya sí, la probabilidad de que dos tableros distintos tengan el mismo hash y el mismo lock ya es prácticamente cero.

El uso de tablas hash con lock se describirá en la entrada siguiente. De momento, baste recordar que cuando las rutinas “addHashPosMouse” y “addHashPosCats” insertan un movimiento (origen, destino) en las tablas “hashpos_mouse” o “hashpos_cats” respectivamente, y la posición del hash ya está ocupada (valor distinto del valor inicial $ff), se detecta una colisión y se incrementa el contador “coll_mouse” o “coll_cats”, lo que al menos servirá para saber si tenemos muchas o pocas colisiones.

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

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:

---

Código del proyecto: RYG3-03

Ahora que ya sabemos cómo generar los movimientos (con las direcciones de movimiento, las tablas de movimientos de ratón y gatos, y la tabla “move_list”), vamos a ello:

Lo primero es definir un nuevo fichero “Gen.asm”, que va a contener las rutinas relativas a la generación de movimientos:

• Rutina “gen” para generar los movimientos de ratón o gatos, según de quién sea el turno (“side”).
• Rutina “genMouse” para generar un movimiento del ratón a partir de una posición de origen y una dirección de movimiento.
• Rutina “genCat” para generar un movimiento de un gato a partir de una posición de origen y una dirección de movimiento.
• Rutina “addMove” para añadir un movimiento a “move_list”.

Además de lo anterior, vamos a definir una nueva rutina “displayMoves” en el fichero “Display.asm” y un nuevo programa principal.

Rutina “gen”:

La rutina “gen” tiene esta pinta:

Lo primero que hace tiene un poco de truco. Si vamos a generar los movimientos a profundidad “ply”, los movimientos de esa profundidad se almacenarán empezando en first_move(ply) y terminando en first_move(ply+1). En realidad, first_move(ply+1) ya es el primer movimiento de la profundidad siguiente. Por tanto, lo primero que hace es la asignación first_move(ply+1) := first_move(ply), es decir, viene a decir que la lista de movimientos del nivel “ply” nace vacía. A partir de ahí irá incrementando el final de la lista first_move(ply+1) con cada nuevo movimiento que genere.

A partir de ahí:

• Recorre el tablero “board” con el índice X.
• Analiza quién mueve (“side”), si ratón o gatos.
• Si mueve el ratón y la pieza en el índice X es un ratón, llama a “genMouse” para las cuatro direcciones.
• Si mueven los gatos y la pieza en el índice X es un gato, llama a “genCat” para las dos direcciones permitidas.
• Continúa hasta terminar el tablero.

Rutinas “genMouse” y “genCat”:

Por su parte, las rutinas “genMouse” y “genCat” son muy parecidas, por lo que sólo analizaremos la primera:

Esta rutina hace lo siguiente:

• Partiendo de la casilla de origen, la multiplica por cuatro (asl + asl). Recordemos que la tabla de movimientos del ratón tiene cuatro movimientos por casilla de origen, aunque algunos pueden ser inválidos.
• Tras multiplicar por cuatro, le suma la dirección.
• Usando ese valor (origen * 4 + dirección) como índice Y, accede a la tabla de movimientos “mouse_moves” y obtiene la casilla de destino.
• Si la casilla de destino es -1 = $ff, la dirección de movimiento no es válida para esta casilla origen y termina.
• Si la casilla de destino no está vacía (PIECE_EMPTY), la dirección de movimiento tampoco es válida y termina.
• En el resto de casos, llama a “addMove” pasando la casilla origen y la casilla destino.

Rutina “addMove”:

Por último, la rutina “addMove” hace lo siguiente tanto para los movimientos del ratón como de los gatos:

Es decir:

• Determina el primer movimiento libre para el nivel “ply”, que es el apuntado por first_move(ply+1).
• En esa posición libre almacena el movimiento (origen, destino).
• Incrementa first_move(ply+1), es decir, incrementa el final de la lista de movimientos para el nivel “ply”.

Rutina “displayMoves”:

Tanto para probar la generación de movimientos como para más adelante, cuando el programa esté más avanzado, nos interesa imprimir por pantalla los movimientos generados. Esto lo hacemos con la rutina “displayMoves” de “Display.asm”:

Se puede hacer una rutina que imprima los movimientos generados para una profundidad dada, o que imprima todos los movimientos desde la profundidad 0 hasta la profundidad “ply”. Pero en general, es suficiente con conocer sólo los movimientos de la siguiente jugada, es decir, los movimientos almacenados en “move_list” desde first_move(0) hasta first_move(1).

Y eso es lo que hace “displayMoves”:

• Toma como primer movimiento el almacenado en first_move(0).
• Toma como último movimiento el almacenado en first_move(1). En realidad, este movimiento ya no se imprimirá.
• Recorre esos movimientos, es decir, va leyendo origen (“move_list_start”) y destino (“move_list_dest”), y los imprime con la rutina “algebraic”.

La rutina “algebraic”, por su parte, es una rutina sencilla que convierte una posición en su notación algebraica. Por ejemplo, la casilla 0 se imprime como A1, y la casilla 63 se imprime como H8. Está definida en “Init.asm”.

Nuevo programa principal:

Por último, desarrollamos un nuevo programa principal que nos permite probar todo lo desarrollado hasta el momento. Queda así:

Es decir:

• Inicializa el tablero y lo pinta.
• Configura que mueve el ratón, genera sus movimientos, y los imprime.
• Configura que mueven los gatos, genera sus movimientos, y los imprime.

Y el resultado es como sigue:

Por tanto, parece que ya sabemos mover…

---

Código del proyecto: RYG3-02

Para generar las jugadas o movimientos necesitamos varios elementos:

• Las direcciones de movimiento.
• Las tablas de movimientos de ratón y gatos.
• La lista de movimientos generados.

Vamos a verlos poco a poco:

Direcciones de movimiento:

Tanto el ratón como los gatos se mueven en diagonal. El ratón puede moverse en las cuatro direcciones diagonales, mientras que los gatos sólo hacia abajo.

Estas cuatro direcciones de movimiento, que llamamos DIR_SW = 0 = suroeste, DIR_SE = 1 = sureste, DIR_NE = 2 = noreste y DIR_NW = 3 = noroeste, las definimos como constantes en “Globals.asm”:

Los valores 0, 1, 2 y 3 nos servirán como índice para leer los movimientos, es decir, la casilla de destino, de las tablas de movimientos de ratón y gatos.

El orden de las direcciones es arbitrario, pero como ratón y gatos comparten la posibilidad de moverse en las direcciones DIR_SW y DIR_SE, lo lógico es que estas direcciones tomen los valores 0 y 1.

Tablas de movimientos de ratón y gatos:

En el fichero “Init.asm” es donde recogemos las variables principales (“side”, “ply”, “hpy”, “nodes”, etc.) y las estructuras de datos principales (“board”, “init_board”, etc.). Entre estas últimas, tenemos las tablas:

• “mouse_moves”.
• “cat_moves”.

La tabla “mouse_moves” recoge los movimientos posibles del ratón. La tabla “cat_moves” recoge los movimientos posibles de los gatos.

Estas tablas se manejan así:

Supongamos que es el turno de ratón. Por tanto, usamos la tabla “mouse_moves”. Supongamos, también, que el ratón está en la casilla E1, es decir, en el índice 4 del tablero. Por tanto, vamos a la fila 4 de la tabla “mouse_moves” y ahí tenemos los 4 movimientos posibles:

Los movimientos posibles, es decir, las casillas de destino del ratón partiendo de la casilla E1 = 4, son:

• DIR_SW = 0 => -1, es decir, no es posible mover en esta dirección.
• DIR_SE = 1 => -1, es decir, tampoco es posible mover en esta dirección.
• DIR_NE = 2 => 13, es decir, la casilla F2.
• DIR_NW = 3 => 11, es decir, la casilla D2.

Por tanto, partiendo de la casilla E1 = 4, el ratón puede moverse a las casillas F2 = 13 y D2 = 11. No puede moverse hacia el sur o hacia abajo, porque se saldría del tablero. Y efectivamente es así:

Si en vez de mover el ratón movieran los gatos el proceso sería totalmente análogo, siendo las principales diferencias que usaríamos la tabla “cat_moves” y que en este caso sólo habría dos movimientos posibles:

Por ejemplo, para la casilla H8 = 63 el único destino posible sería la casilla G7 = 54.

Por supuesto, para que un movimiento sea posible, además de estar registrado en la tabla de movimientos de ratón o gatos, el destino tiene que estar vacío.

Lista de movimientos posibles generados:

Los movimientos posibles generados conforme a las reglas anteriores se guardan en una lista llamada “move_list”. En realidad, como los movimientos tienen una casilla de origen y otra de destino, la lista anterior es doble, “move_list_start” y “move_list_dest”:

Además, recordemos que el juego consiste en generar todos los movimientos posibles a partir de una posición, intentarlos o probarlos, evaluar si el resultado es más o menos favorable, deshacerlos, y finalmente elegir el mejor movimiento posible. Y todo esto, hasta una profundidad N, que es la profundidad de análisis o nivel de juego que haya elegido el usuario.

Por tanto, si en un momento dado el proceso de búsqueda nos ha llevado hasta el tablero de la izquierda, es decir, si la variante actual es esa rama, en la tabla “move_list” necesitaremos tener los tres movimientos posibles desde la posición actual (ply = 0) y, además, los dos movimientos posibles del tablero de la izquierda (ply = 1).

Todo esto se gestiona gracias a la tabla “first_move” que, para una profundidad dada (ply = X), nos dice donde empiezan sus movimientos en “move_list”. Gráficamente sería así:

En definitiva, la tabla “first_move” nos dice dónde empiezan y terminan los movimientos de cada nivel de profundidad. En la figura anterior, los movimientos del tablero actual (ply = 0) empiezan en el índice 0 (s0=>d0, s1=>d1 y s2=>d2) y los movimientos del tablero que se está analizando a profundidad uno (ply = 1), el tablero de la izquierda, empiezan en el índice 3 (s3=>d3 y s4=>d4).

De este modo es posible ir moviendo la variante actual por el árbol, probando movimientos a una profundidad, deshaciéndolos, probando otros movimientos de profundidad menor que estuvieran pendientes de probar, etc.