Búsqueda alfa – beta con profundización iterativa

Como ya adelantamos en una entrada anterior, la búsqueda alfa – beta poda mejor o peor en función del orden en que se desarrollen de las jugadas. Si las mejores jugadas se desarrollan antes que las peores, entonces se podan más ramas y el proceso es más eficiente.

Por tanto, interesa encontrar algún método para mejorar la ordenación de los movimientos, que ahora mismo es arbitraria. Ese método es la “profundización iterativa” o “iterative deepening” en inglés.

La idea básica es que no vamos a desarrollar el árbol directamente a máxima profundidad (“max_depth”), sino que vamos a hacer un bucle empezando por profundidad uno, siguiendo por profundidad dos, …, y así sucesivamente hasta la máxima profundidad.

Lógicamente, hacer un bucle en sí mismo no aporta ningún valor a la ordenación. La idea clave es utilizar información de la iteración N (y de las anteriores) para mejorar la ordenación de las jugadas de la iteración N+1.

En particular, si un tablero de la iteración N+1 (y la mejor jugada asociada) ya está en las tablas hash porque ha sido introducido por alguna iteración anterior, entonces supondremos que, igual que fue un buen movimiento para alguna iteración anterior (por eso está en las tablas hash), también será un buen movimiento para iteración actual (N+1) y, por tanto, intentaremos desarrollarlo antes que otros movimientos, favoreciendo así la poda.

Pero para poder hacer esto necesitamos asociar a los movimientos un valor (“score”), de forma similar a cómo hacemos ya con los tableros. Este valor servirá de base para la ordenación de los movimientos. Y como esto exige algo más de trabajo, lo dejamos para una entrada posterior. De momento, nos centramos en la profundización iterativa propiamente dicha, aunque es cierto que su sentido es mejorar la ordenación de movimientos y, por tanto, la poda.

Por otro lado, la profundización iterativa también tiene un coste. En vez de desarrollar el árbol de juego directamente a máxima profundidad, lo vamos desarrollando en varias pasadas (1, 2, …, “max_depth”), porque eso nos permitirá mejorar la ordenación de movimientos y, por tanto, la poda.

Si el factor de ramificación es b:

  • La búsqueda directa a máxima profundidad, sin considerar ahora las podas, genera un árbol de 1 + b + b^2 + … + b^max_depth nodos.
  • Por otro lado, la búsqueda iterativa, también podas aparte, genera varios árboles de tamaños:
    • Profundidad 1 => 1 + b.
    • Profundidad 2 => 1 + b + b^2.
    • …
    • Profundidad “max_depth” => 1 + b + b^2 + … + b^max_depth.

Al final, si sumamos los nodos de todos esos árboles, el sumando que más pesa es el b^max_depth, que está presente en ambos tipos de búsqueda, directa e iterativa, por lo que podemos concluir que el coste adicional de la profundización iterativa (resto de sumandos) merece la pena gracias a lo que ganamos en poda.

Yendo al grano, lo que necesitamos es:

Nueva rutina “thinkIter”:

Igual que antes teníamos una rutina “thinkMax” para la búsqueda a máxima profundidad, ahora vamos a desarrollar una nueva rutina “thinkIter” para la búsqueda iterativa. Esta rutina, que también está en el fichero “Search.asm”, es así:

Es decir:

  • Inicializa a cero “ply”.
  • Inicializa a cero el número de nodos analizados (4 bytes).
  • Llama a la rutina “newPosition”, que prepara todo para el desarrollo del árbol de juego y la decisión de la siguiente jugada.
  • Ejecuta un bucle desde X = 0 hasta X = max_depth – 1. Para cada valor de X, llama a la rutina “search” con depth = X+1, alpha = $00 y beta = $ff. También llama a displayIter.

Por tanto, en la práctica lo que estamos haciendo es ejecutar la búsqueda alfa – beta varias veces, empezando con profundidad 1 y terminando con profundidad “max_depth”. En definitiva, lo que hemos llamado “profundización iterativa”.

Un matiz que es interesante notar es que el contador de nodos desarrollados nodes4 – nodes3 – nodes2 – nodes1 se podría haber inicializado en cada iteración del bucle, pero se ha optado por hacerlo sólo una vez antes de empezar el bucle. Por tanto, cada vez que se imprima ese contador llamando a “displayIter”, el valor presentado no será el número de nodos de la última iteración, sino el acumulado desde el comienzo del bucle.

Esto último se verá más claro tras revisar el nuevo programa principal.

Nuevo programa principal:

El nuevo programa principal es muy similar al último, siendo la principal diferencia que se llama a “thinkIter” en vez de a “thinkMax”:

Si ahora ejecutamos este nuevo programa principal, el resultado es así:

Puede sorprender el número de nodos desarrollados a profundidad 8 ($1522 = 5.410) pero, como ya se ha comentado, ese número es ahora el acumulado de todas las iteraciones. Por tanto, para saber los nodos desarrollados específicamente en esa iteración tenemos que restar los nodos a profundidad 7 ($0774 = 1.908):

5.410 – 1.908 = 3.502 = $0dae

Y este es exactamente el mismo número de nodos que se desarrollaron a profundidad 8 con la búsqueda a máxima profundidad.

¿Cómo es posible? ¿La idea de la profundización iterativa no era mejorar la poda y analizar menos nodos? Sí, lo es. Pero para eso hay que aprovechar la información de un nivel de profundidad, para mejorar la ordenación de las jugadas del siguiente nivel. Y esto lo haremos más adelante.

Por lo demás, se observa que la variante principal al final del bucle sigue siendo la misma que con la búsqueda a máxima profundidad (E1D2, B8A7, D2C3, D8C7, C3B4, F8E7, B4A5 y H8G7). Esto es normal, porque de momento sólo estamos haciendo un bucle sin cambiar la forma de forma de generar ni analizar el árbol. Por otro lado, aunque mejoremos la ordenación de jugadas y la poda, eso no debería afectar al resultado del análisis, sólo a su eficiencia.

Y también se observa que de una profundidad a la siguiente no hay cambio de variante principal. Es decir, a profundidad 7 la variante principal es E1D2, B8A7, D2C3, D8C7, C3B4, F8E7 y B4A5, y a profundidad 8 es esa misma más H8G7. Esto no tiene por qué ser siempre así. Nos encontraremos situaciones en que el programa decide una variante principal a profundidad N y, a profundidad N+1, al analizar más información, decide otra variante principal total o parcialmente distinta.

C´´odigo del proyecto: RYG3-08

Búsqueda alfa – beta a máxima profundidad

La búsqueda alfa – beta, es decir, con poda, la vamos a implementar en la rutina “search” del nuevo fichero “Search.asm”.

De primeras, parece que lo más lógico sería que, si se quiere una profundidad de análisis de ocho niveles, por decir algo, se desarrolle directamente un árbol de juego de profundidad ocho. Esto es lo que llamamos “búsqueda a máxima profundidad”.

Sin embargo, en la práctica no suele ser así. La poda alfa – beta es más o menos eficiente podando en función de cómo se ordenen las jugadas o, lo que es lo mismo, dependiendo de cómo se ordenen los tableros hijo de un tablero dado. Si las mejores jugadas se analizan o desarrollan antes, se poda más y mejor.

Por ello, cualquier enfoque para desarrollar el árbol que no genere las jugadas en un orden arbitrario, sino que favorezca una ordenación lógica de las mismas, adelantando el desarrollo de las mejores jugadas y posponiendo el de las peores, tendrá un efecto favorable en la poda.

En esta entrada vamos a ver la “búsqueda a máxima profundidad”. En la entrada siguiente veremos la “profundización iterativa” (“iterative deepening” en inglés), que es una alternativa para mejorar la ordenación de jugadas y la poda.

Nueva rutina “search”:

La rutina “search” se define en el nuevo fichero “Search.asm”. Su definición es así:

Es decir, recibe:

  • La profundidad de análisis “depth”.
  • Los parámetros “alpha” y “beta” de la poda alfa – beta.

Y devuelve:

  • La puntuación “score”.
  • Y el mejor movimiento encontrado (“best_start”, “best_dest”).

Y para hacer lo anterior necesita:

  • Saber por qué movimiento va de todos los posibles con “current_move”.
  • Y cuál es el último movimiento de todos los posibles con “last_move”.

Quitando “depth”, que es una posición de memoria simple (un byte), el resto de parámetros son tablas de N posiciones a las que accederemos usando “depth” como índice. Esto es necesario porque “search” es una rutina recursiva, es decir, se llama a sí misma, y no debemos perder la cuenta de los sucesivos valores de llamada y retorno.

Y lo primero que hace la rutina “search” es esto:

Es decir:

  • Carga la profundidad “depth” en el índice Y.
  • Si “depth” es cero ya estamos en el final del árbol, es decir, en las hojas y, por tanto, llamamos a la función de evaluación “eval” y el valor de la evaluación “ev” lo devuelve en “score” (indexado por Y).
  • Si “depth” no es cero todavía estamos en un nodo intermedio y, por tanto, llama a “searchMouse” o “searchCats” en función del turno “side”.

Las subrutinas “searchMouse” y “searchCats” son totalmente equivalentes. Lo único que cambia es el bando. La primera es para el ratón, es decir, el jugador maximizador, y la segunda es para los ratones, es decir, el jugador minimizador. Con analizar una de ellas es suficiente, porque la otra es totalmente análoga.

Subrutina “searchMouse”:

Como hemos dicho, las subrutinas “searchMouse” y “searchCats” son totalmente equivalentes. Por tanto, llegará con analizar en detalle la primera.

Lo primero que hace “searchMouse” es así:

Es decir:

  • Incrementa el número de nodos desarrollados llamando a “incNodes”. Esta rutina simplemente incrementa en uno el número de nodos analizados (4 bytes) almacenado en las posiciones nodes4 – nodes3 – nodes2 – nodes1.
  • Inicializa la mejor jugada llamando a “initBest”. Esta rutina simplemente inicializa a ($ff, $ff) el mejor movimiento encontrado (“best_start”, “best_dest”). Lógicamente, $ff es un valor de casilla inválido.
  • Genera la lista de movimientos posibles llamando a “gen”. Recordemos que “gen” almacena los movimientos posibles en la tabla “move_list”, y que la tabla asociada “first_move” nos da punteros para acceder a los movimientos de “move_list” en función del número de jugada “ply”.

Con los movimientos posibles generados con “gen”, “searchMouse” sigue así:

  • Usando “ply” como índice y “first_move”, toma la posición que ocupa el primer movimiento de “move_list”. Esta posición la guarda en “current_move”, que se irá actualizando según se vayan probando movimientos.
  • Usando “ply+1” como índice y “first_move”, toma la posición que ocupa el último movimiento de “move_list”. Esta posición la guarda en “last_move”, que será el tope contra el que comprobar “current_move” para saber si hemos probado todos los movimientos.

Y ahora “searchMouse” sigue así:

Es decir:

  • Usando “current_move” tenemos la posición que ocupa el movimiento a probar en “move_list”.
  • Leemos de “move_list” ese movimiento, es decir, (“move_list_start”, “move_list_dest”).
  • Y probamos ese movimiento con “makeMove”. Decimos “probar” porque a estas alturas para nada está decidido que ese sea el movimiento finalmente elegido. De momento sólo se trata de ir desarrollando el árbol, ir aplicando la búsqueda alfa – beta, y encontrar el mejor movimiento de todo el proceso, que será el que finalmente se aplique.

Una vez probado el movimiento con “makeMove” habrá que deshacerlo con “takeBack”, puesto que de momento no es un movimiento definitivo, sino una prueba para saber cómo de bueno o malo es. Y después de deshacerlo con “takeBack” usaremos su puntuación “score” para compararlo con “alpha”, puesto que estamos analizando “searchMouse”, y el ratón es el jugador maximizador.

Pero antes de seguir con todo esto, tenemos que desarrollar el árbol “en profundidad”. Es decir, tenemos que llamar recursivamente a “search”. Esto se hace aquí:

Es decir:

  • El valor de “alpha” al nivel “depth” lo pasamos como “alpha” del nivel “depth-1”.
  • El valor de “beta” al nivel “depth” lo pasamos como “beta” del nivel “depth-1”.
  • Decrementamos “depth” en 1, puesto que nos estamos acercando un nivel al extremo del árbol, a las hojas.
  • Llamamos recursivamente a “search”.

A la vuelta, es decir, al terminar “search”, lo primero que hacemos es incrementar “depth” en 1 para dejarlo en el valor que estaba y continuar con la búsqueda en ese nivel.

Ahora ya sí, tras volver de la llamada recursiva a “search” y devolver “depth”a su valor, “searchMouse” continúa:

Es decir:

  • Compara el valor de “score” con el valor de “alpha”.
  • Si “score” es estrictamente menor que “alpha” (bcc), entonces no es necesario actualizar “alpha”, y vamos directamente a comparar a comparar “alpha” con “beta” (etiqueta “schMouseAlphaVsBeta”).
  • En caso contrario, es decir, si “score” es mayor o igual que “alpha”, entonces (etiqueta “schMouseUpdateAlpha”) actualizamos “alpha” con el valor de “score” y el mejor movimiento (“best_move_start”, “best_move_dest”) con el valor del movimiento recién probado / deshecho (“move_list_start”, “move_list_dest”).

En ambos casos, tanto si actualizamos “alpha” como si no (en el proceso de cálculo del máximo entre “score” y “alpha”), lo siguiente según el pseudocódigo de la búsqueda alfa – beta es comparar alfa con beta, para determinar si hay una “poda beta”. Y esto es precisamente lo que hace ahora la rutina “searchMouse”:

Es decir:

  • Compara “alpha” con “beta”.
  • Si “alpha” es estrictamente menor (bcc) salta a la etiqueta “schMouseNext”, que lo que hace es probar el siguiente movimiento del ratón (etiqueta “schMouseAgain”), salvo que sea el último de la lista (etiqueta “schMouseEnd”).
  • En caso contrario, es decir, si “alpha” es mayor o igual que “beta”, entonces se produce una “poda beta” (etiqueta “schMouseBetaCutoff”), lo cual señalizamos poniendo el valor 2 = B (de beta) en la posición de pantalla $0400+999 = $07e7 = 2023, es decir, en la esquina inferior derecha de la pantalla. Además, como no hace falta seguir probando movimientos, saltamos a “schMouseEnd”, igual que si hubiéramos llegado al final de la lista de movimientos posibles.

Por último, la rutina “searchMouse” hace esto (etiqueta “schMouseEnd”):

Es decir, tanto si hemos llegado al final de la lista de movimientos posibles como si se ha producido una “poda beta”:

  • Devuelve el valor de “alpha” en “score”.
  • Y mete el mejor movimiento (“best_move_start”, “best_move_dest”) en la tabla hash del ratón con “addHashPosMouse”.

En fin, complejillo, pero se puede seguir. Cualquier función recursiva es compleja de entender, pero es que la búsqueda alfa – beta es especialmente compleja. Y encima en ensamblador…

Subrutina “searchCats”:

Como ya se ha comentado varias veces, la subrutina “searchCats” es totalmente análoga a “searchMouse”, siendo las principales diferencias:

  • Los ratones son el bando minimizador.
  • Calcula el mínimo entre “score” y “beta”.
  • En caso de producirse poda, es una “poda alfa”.
  • Devuelve “beta” y no “alpha”.

Por lo demás, es lo mismo…

Nueva rutina “thinkMax”:

Ahora que ya tenemos la rutina “search” lo siguiente es usarla y, como hemos dicho, en primera instancia la usaremos “a máxima profundidad”. Esto se hace desde la rutina “thinkMax”, que también está en el nuevo fichero “Search.asm”:

Es decir, la rutina “thinkMax”:

  • Inicializa a cero “ply”, porque vamos a empezar a desarrollar el árbol de juego para decidir el siguiente movimiento.
  • Inicializa a cero el número de nodos analizados (4 bytes).
  • Llama a la rutina “newPosition”, que vimos hace unas cuantas entradas, y que básicamente preparaba todo para el desarrollo del árbol de juego y la decisión de la siguiente jugada.
  • Llama a la rutina “search” con depth = max_depth, alpha = $00 y beta = $ff, es decir, que alfa y beta toman sus valores iniciales (menos infinito y más infinito respectivamente) y el análisis se va a realizar a máxima profundidad (“max_depth”).

Que el análisis se vaya a realizar “a máxima profundidad” no quiere decir que sea a una profundidad altísima (ej. 1000), o a la máxima profundidad que soporte el C64, sino a la profundidad o nivel de dificultad elegido por el usuario desde el programa principal (“Main.asm”).

Dicho de otro modo, todavía no tenemos “profundización iterativa”. No tenemos un bucle que vaya llamando a “search” para depth = 1, depth = 2, depth = 3, …, depth = max_depth. Vamos a “max_depth” directamente.

Por último, tras llamar a “search” para decidir la mejor jugada, la rutina “thinkMax” termina llamando a la rutina “displayIter”.

Nueva rutina “displayIter”:

“displayIter” es una rutina sencilla del fichero “Search.asm” que básicamente muestra información por pantalla sobre el proceso de búsqueda:

Como se puede ver, “displayIter” muestra por pantalla:

  • La profundidad de búsqueda “depth”.
  • El número de nodos analizados o desarrollados.
  • La puntuación obtenida durante el proceso de búsqueda.
  • Y la variante principal, es decir, la secuencia de jugadas que, según el C64, es la mejor secuencia de jugadas para ambos bandos.

Lo mejor de todo esto es que el C64 nos va contando cómo piensa que va a discurrir la partida. Nos da pistas de qué es lo que está pensando. Esto lo hace con la rutina “displayPV”.

Nueva rutina “displayPV”:

“PV” viene de variante principal o “principal variation” en inglés. Y como ya comentamos hace tiempo, la variante principal es la secuencia de jugadas que el C64 piensa que va a tener lugar, puesto que entiende que son las mejores jugadas para uno y otro bandos.

Y como la rutina “search” va eligiendo la mejor jugada para cada tablero (“best_start”, “best_dest”), y la almacena en las tablas hash con “addHashPosMouse” o “addHashPosCats”, según el turno, el resultado es que la variante principal la tenemos en las tablas hash.

Por tanto, la rutina “displayPV”, que es del fichero “Search.asm”, tan sólo tiene que ir a las tablas hash para consultar la variante principal:

Es decir, la rutina “displayPV”:

  • Recibe el número de jugadas de la variante principal (“depth”).
  • Mira de quién es el turno con “side”.
  • Si es el turno es del ratón busca el tablero actual en la tabla hash del ratón con “lookUpMouse”.
  • Si el turno es de los gatos busca el tablero actual en la tabla hash de los gatos con “lookUpCats”.
  • En ambos casos, se supone que el mejor movimiento a partir del tablero actual nos retorna en (“hash_start”, “hash_dest”) desde la tabla hash consultada, ya sea la tabla hash de ratón o gatos.

Y sigue así (etiqueta “dpvPrintMake”):

Es decir:

  • Primero mira si el movimiento devuelto (“hash_start”, “hash_dest”) es válido. Esto lo hace comparando “hash_start” contra $ff, que es el valor con el que se inicializan “hash_start” y “hash_dest”.
  • Si el movimiento es válido (diferente de $ff), imprime las casillas origen y destino con la rutina “algebraic”. Además, aplica el movimiento con “makeMove”. Esto lo hace para avanzar en la variante principal, es decir, para poder consultar el siguiente tablero y el siguiente movimiento de la variante principal. Esto se repite hasta alcanzar “depth”, es decir, hasta terminar el número de movimientos de la variante principal.
  • Si el movimiento no es válido (igual a $ff) o, dicho de otro modo, si en la tabla hash no hay un movimiento para el tablero consultado, pasamos directamente a la fase de deshacer con “takeBack” los movimientos de la variante principal. Esto es la etiqueta “dpvTakeBack”.

En definitiva, y dicho de forma simple, la rutina “displayPV” simula que se van ejecutando los movimientos de la variante principal, que están almacenados en las tablas hash. Digo “simula” porque el objeto de esta ejecución es simplemente ir consultando los sucesivos tableros y los movimientos asociados, para imprimirlos e informar al usuario, y termina deshaciendo los mismos.

Nuevo programa principal:

Como siempre, todo esto (“search”, “thinkMax”, “displayIter”, “displayPV”, …) hay que probarlo, para lo que hacemos un nuevo programa principal:

Este nuevo programa principal:

  • Llama a la rutina “setup”, que genera las tablas aleatorias que sirven de base para obtener los hashes con “randomize”, inicializa la partida con “initBoard” y da valor a algunas variables importantes del juego, como “max_depth” (más adelante este valor se lo pediremos al usuario).
  • Llama a la rutina “displayBoard” para mostrar el tablero.
  • Y finalmente llama a “thinkMax” para lanzar el proceso de búsqueda (“search”) a máxima profundidad.

El resultado después de pocos minutos de ejecución es así:

Es decir, para una profundidad de análisis de 8 movimientos (en “setup” se configura max_depth = 8), se analizan o desarrollan $0dae = 3.502 nodos, y el C64 decide que la variante principal es:

  • E1D2.
  • B8A7.
  • D2C3.
  • D8C7.
  • C3B4.
  • F8E7.
  • B4A5.
  • H8G7.

Es decir, el C64 piensa que esos son los movimientos que van a tener lugar porque, conforme a la función de evaluación “eval” que se ha programado, esos son los mejores movimientos para uno y otro bandos. Y si eso efectivamente ocurriera acabaríamos llegando a un tablero de valor $18 = 24.

Obsérvese cómo el ratón siempre avanza, al menos de momento que es posible, ya que eso es lo que hace subir su puntuación (jugador maximizador). Y obsérvese también que los gatos avanzan en formación, ya que hacerlo de otra manera reduciría más su puntuación que, al actuar como sustraendo (ev = $80 + evMouse – evCats), tendría como efecto que la puntuación “ev” sería mayor. Y eso no interesa a los gatos porque son el bando minimizador.

Al menos esto es lo que piensa el C64 que va ocurrir. Cuestión diferente es lo que decida el jugador humano cuando le toque jugar. Puede jugar a perder, jugar al despiste, hacer jugadas heterodoxas, jugadas mejores que las que tiene programadas el C64, etc.

También es muy interesante analizar el número de nodos buscados o desarrollados, que vale $0dae = 3.502. Este valor es muy inferior al número de nodos que cabría esperar aplicando la búsqueda minimax. Esto es gracias a las podas que produce la búsqueda alfa – beta.

Estas podas se marcan con las letras “A” (poda alfa) y “B” (poda beta) que aparecen en la esquina inferior derecha de la pantalla, y que al hacer scroll suben hacia arriba. Esto se puede mejorar definiendo contadores de podas alfa y beta, y mostrando esta información en “displayIter”, como ya se hace con la profundidad de análisis, el número de nodos desarrollados, o la evaluación final. De momento, como sólo se trata de confirmar que efectivamente hay podas, nos vale como está.

En la entrada siguiente le daremos una vuelta de tuerca para, mejor que ir directamente a la máxima profundidad, vayamos paso a paso, lo que nos permitirá mejorar la ordenación de movimientos y la poda.

Código del proyecto: RYG3-07

Búsqueda alfa – beta II

Bueno, pues ya sabemos en qué consiste la búsqueda alfa – beta. Yo cada vez que me acuerdo tengo que volver a analizarla en profundidad, porque no me acabo de creer que funcione. ¡¡Pero funciona!!

Para programar la búsqueda alfa – beta básicamente tenemos que programar una rutina en ensamblador inspirada en el pseudocódigo de la entrada anterior. Repasando el pseudocódigo vemos que hace falta:

  • La función de evaluación (“el valor heurístico del nodo”).
  • Generar y recorrer los movimientos posibles (“para cada hijo…”).
  • Calcular el máximo o el mínimo de dos números.
  • Que la rutina sea capaz de llamarse recursivamente a sí misma.

Además de lo anterior hace falta otra cosa que está implícita en el pseudocódigo. El pseudocódigo se centra en qué son los parámetros alfa y beta, cómo se pasan, y cómo detectar que se produce una poda (“romper”). Pero está claro que, además de eso, el algoritmo o rutina deberá llevar cuenta de cuál es el mejor movimiento hasta el momento, es decir, el de puntación más alta o más baja según el turno, y guardarlo en algún sitio. Ese sitio para nosotros serán las famosas tablas hash.

Función de evaluación:

La función de evaluación es la rutina “eval”. Ya la vimos unas cuantas entradas más atrás, así que no es necesario revisarla aquí. Llegará con usarla.

Movimientos posibles:

La generación de los movimientos posibles es la rutina “gen”. Nuevamente, ya la vimos unas cuantas entradas más atrás y también será suficiente con usarla.

Calcular el máximo o el mínimo de varios números:

Cuando es el turno del jugador maximizador (ratón), tenemos que calcular el máximo entre el alfa actual y la puntuación que nos devuelve el nodo hijo. Esto es tan sencillo como comparar alfa con la puntuación, y quedarnos con el mayor. Ese máximo será el nuevo valor de alfa.

Análogamente, cuando es el turno del jugador minimizador (gatos), tenemos que calcular el mínimo entre el beta actual y la puntuación que nos devuelve el nodo hijo. Nuevamente, esto es tan sencillo como comparar ambos, y quedarnos con el menor, que será el nuevo valor de beta.

Si este proceso se repite para todos los hijos de un tablero, a base de comparar números de dos en dos, comparando alfa con la puntuación o beta con la puntuación, al final del proceso lo que tenemos es el máximo (nuevo alfa) o el mínimo (nuevo beta) de varios números. Es decir, esta forma de calcular el máximo o el mínimo se puede generalizar de dos números a varios números.

Recursividad:

Una función recursiva o una rutina recursiva es una función que se llama a sí misma. Esto es bastante habitual en lenguajes de alto nivel, por ejemplo, para calcular el factorial de un número en C, podemos hacerlo así:

Es decir:

  • El factorial de 1 es 1 (condición de terminación de la recursividad).
  • Y el factorial de N es N por el factorial de N-1 (recursividad).

De este modo, factorial(5) = 5 * factorial(4) = 5 * 4 * factorial(3) = 5 * 4 * 3 * factorial(2) = 5 * 4 * 3 * 2 * factorial(1) = 5 * 4 * 3 * 2 * 1 = 120.

Pues bien, en ensamblador también es posible hacer rutinas recursivas, siendo la principal dificultad apañárselas de algún modo para no perderse en las sucesivas llamadas y en los parámetros que se pasan y retornan. En un lenguaje de alto nivel como C, la forma de no perderse es mediante la “pila de llamadas” del lenguaje.

En el caso de programar en ensamblador, una forma de no perderse con las llamadas y los parámetros podría ser usando la pila del C64 (página 1 de la RAM, posiciones $01ff a $0100) y las instrucciones “pha” y “pla”, que meten y sacan datos de la pila. Sin embargo, dado que las instrucciones “jsr” y “rts” también manipulan la pila, puede resultar farragoso. Por ello, casi es más fácil usar una tabla de parámetros donde almacenar los valores en función de la profundidad:

En la pantalla anterior se puede ver que la rutina “search”, que va a ser recursiva, no tiene los típicos parámetros de entrada y salida que son posiciones de memoria simples, sino más bien unas tablas (alpha, beta, score, best_start, best_dest, current_move y last_move) a las que vamos a acceder usando como índice el valor de “depth”.

Tablas hash / variante principal:

A la vez que vamos pasando alfa y beta, detectando si hay posibilidad de poda, etc., lógicamente tenemos que quedarnos con la mejor jugada a partir de cada tablero. Cuando mueva el ratón será la jugada que maximiza la puntuación; cuando muevan los gatos será la jugada que minimiza la puntuación.

Esta información (la mejor jugada a partir de cada tablero) la guardaremos en las tablas hash, que ya vimos en alguna entrada anterior. Recordemos que hay dos tablas hash: una para los movimientos del ratón (“hashpos_mouse”) y otra para los movimientos de los gatos (“hashpos_cats”).

Para insertar un movimiento en la primera tabla usaremos la rutina “addHashPosMouse” y para insertar un movimiento en la segunda usaremos la rutina “addHashPosCats”.

Con estas cuatro piezas (generación de movimientos, recursividad, función de evaluación y cálculo de máximo / mínimo), ya tenemos todo lo necesario para desarrollar la búsqueda alfa – beta (rutina “search”), que será la clave del juego. Pero esto ya lo haremos en la siguiente entrada.

Búsqueda alfa – beta

Alfa – beta no es un algoritmo diferente a minimax. Es una mejora que se añade a minimax. Podemos tener minimax puro o minimax con poda alfa – beta.

La poda alfa – beta se describe en esta entrada de Wikipedia y en muchas otras fuentes: https://es.wikipedia.org/wiki/Poda_alfa-beta. No es fácil de entender ni tampoco de explicar. Vamos a intentarlo.

Parámetros alfa y beta:

Recordemos que en minimax hay un jugador, en nuestro caso el ratón, que intenta maximizar la puntuación, y otro jugador, en nuestro caso los gatos, que intenta minimizarla. Pues bien, a esto la poda alfa – beta le añade dos parámetros:

  • Alfa: Es la mejor (mayor) puntuación que tiene garantizada hasta el momento el jugador maximizador.
  • Beta: Es la mejor (menor) puntuación que tiene garantizada hasta el momento el jugador minimizador.

Inicialmente alfa empieza con un valor muy bajo, en teoría menos infinito. Y beta empieza con un valor muy alto, en teoría más infinito. En la práctica, como estamos usando un byte sin signo para las evaluaciones, el valor más bajo posible es 0 y el más alto posible es 255. Por tanto, empezamos así:

  • Alfa inicial = 0.
  • Beta inicial = 255.

Ahora vamos desarrollando el árbol de juego en profundidad, es decir, desde la raíz hasta la primera hora. Y vamos pasando los parámetros alfa y beta, primero hacia abajo y luego hacia arriba. Lo mejor es verlo con un ejemplo.

Ejemplo de búsqueda alfa – beta:

El árbol anterior es el resultado final del proceso de búsqueda, en el que se han podado las ramas que están sombreadas. Verlo así es fácil; lo complejo es entender por qué esas ramas sombreadas se pueden podar o, mejor dicho, por qué se puede prescindir directamente de generarlas y evaluarlas.

Proceso paso a paso:

El proceso paso a paso es así:

  • Inicialmente, desarrollamos el árbol de juego hasta la primera hoja, pasando los alfa y beta iniciales “hacia abajo”:
  • En segundo lugar, y como hemos llegado hasta una hoja, aplicamos la función de evaluación sobre la misma, que nos devuelve un valor de 5. Ese valor 5 se devuelve al padre de la hoja que, al ser un nodo minimizador (turno de los gatos), lo compara con beta = 255 y, al ser 5 menor que 255, toma beta = 5:
  • Ahora se desarrolla la segunda hoja, que ya no recibe alfa = 0 y beta = 255, sino alfa = 0 y beta = 5. Al tratarse de una hoja, se evalúa con la función de evaluación, que devuelve un valor de 6:
  • Ese valor de 6 se retorna al padre, de forma análoga al caso anterior con 5, y, al ser el padre un nodo minimizador (turno de los gatos), compara 6 con beta = 5 pero, en este caso, al ser 6 mayor que 5, no se actualiza beta. Beta se queda con el valor de 5, que es el valor que se retorna al abuelo:
  • Ahora el abuelo es un nodo maximizador (turno del ratón) y, por tanto, compara 5 con alfa = 0. Y como 5 es mayor que 0, toma alfa = 5. Ahora los valores de alfa = 5 y beta = 255 son los que se pasan al siguiente padre:
  • Y de ese padre, alfa = 5 y beta = 255 se pasan a la tercera hoja que, al ser hoja, se evalúa con la función de evaluación, que ahora devuelve 7. Y ese 7 se devuelve al padre:
  • Y como el padre es un nodo minimizador (turno de los gatos), compara 7 con beta = 255, y, como 7 es menor que 255, se queda con beta = 7. Ahora los valores alfa = 5 y beta = 7 se pasan a la cuarta hoja:
  • Y como la cuarta hoja es una hoja, se evalúa con la función de evaluación, que devuelve 4. Y este 4 se pasa al padre que, al ser un nodo minimizador (turno de los gatos), lo compara con beta = 7 y, al ser 4 menor que 7, se queda con beta = 4:
  • Por último, y antes de devolver ese 4 al abuelo, se da una situación muy interesante: alfa (5) >= beta (4). Eso significa que, aunque habría un tercer hijo de valor 5 (quinta hoja), no es necesario desarrollarlo ni evaluarlo. Esto es lo que se llama una “poda alfa”, porque se produce en un nodo minimizador, siendo la “poda beta” la situación equivalente cuando se produce en un nodo maximizador:

Y para entender por qué ese tercer hijo no es necesario conviene volver al árbol completo:

En este caso esa quinta hoja hubiera valido 5 según la función de evaluación, pero, en realidad, da igual lo que valga. Por eso se puede podar o, mejor dicho, no es necesario ni generarla ni evaluarla.

Si esa quinta hoja hubiera valido 4 o más (por ejemplo, 5) es evidente que no hubiera afectado al proceso de búsqueda, porque tiene un hermano de 4 y su padre busca el valor mínimo. Y si hubiera valido menos de 4 (por ejemplo, 3), dado que el abuelo busca el valor máximo y tiene garantizado un 5 hacia la rama de la izquierda, nunca hubiera tomado el camino de la derecha.

En definitiva, los valores de alfa y beta que se van pasando hacia abajo y luego hacia arriba determinan que, cuando alfa es mayor o igual que beta, no es necesario desarrollar ni evaluar los siguientes nodos. Esto ocurre en todas las ramas del árbol anterior que están sombreadas.

Simulación de la búsqueda alfa – beta:

Otra forma buena de entender la búsqueda alfa – beta es mediante un simulador, de los cuales hay muchos en Internet. Algunos ejemplos son:

https://raphsilva.github.io/utilities/minimax_simulator/#

http://homepage.ufp.pt/jtorres/ensino/ia/alfabeta.html

El primer simulador usa siempre el mismo ejemplo. El segundo permite configurar el árbol que se quiere analizar (número de nodos, profundidad, evaluaciones de las hojas, etc.). Por ejemplo, con los valores:

  • Enter the game tree structure => 3 2 2 2 2 1 2 1 1 2 2 3 1 1 2 1 1 2 1.
  • Enter the game tree terminal values => 5 6 7 4 5 3 6 6 9 7 5 9 8 6.

es posible configurar el mismo árbol que en Wikipedia, y simular su búsqueda paso a paso o completa, señalando las ramas que se podan y la variante principal.

Pseudocódigo de la búsqueda alfa – beta:

Por último, una forma condensada de describir la búsqueda alfa – beta es mediante su descripción en pseudocódigo, que es así:

Como se puede observar es una definición recursiva, es decir, en términos de sí misma. Y, sí, en ensamblador se pueden programar rutinas recursivas…

Búsqueda minimax

Ya sabemos generar los movimientos posibles para ambos bandos, tenemos unas estructuras de datos (tablas hash) donde guardar el mejor movimiento para cada tablero (siendo la secuencia de esos mejores movimientos la variante principal), sabemos desarrollar el árbol de juego (probar movimientos con “makeMove” y deshacerlos con “takeBack”) y ya, por último, somos capaces de evaluar las hojas del árbol con la función de evaluación. Por tanto, tenemos todas las piezas para montar la búsqueda, es decir, el proceso por el cual el C64 decidirá su siguiente jugada.

Hasta ahora, hemos dicho que ese proceso de búsqueda sería minimax, es decir, un proceso consistente en:

  • Desarrollar el árbol de juego hasta las hojas.
  • Aplicar la función de evaluación sobre las hojas.
  • Hacer subir la evaluación hacia la raíz, seleccionando el máximo o el mínimo en función del turno de juego (ratón = máximo, gatos = mínimo).

Esto se puede hacer, y funciona, pero tiene un problema: el factor de ramificación.

El factor de ramificación es el número de tableros hijo que tiene un tablero. De media, si mueve el ratón, el factor de ramificación será cuatro, porque hay cuatro movimientos posibles, y si mueven los gatos será ocho, porque hay dos movimientos posibles por cuatro gatos. Al final, si la profundidad de análisis es ocho, eso nos da:

4 x 8 x 4 x 8 x 4 x 8 x 4 x 8 ≈ 1 millón de tableros

Es decir, habría que generar y evaluar más de un millón de tableros. Y eso a profundidad máxima (ocho), sin tener en cuenta los tableros intermedios a profundidad siete, a profundidad seis, a profundidad cinco, etc.

Total, aunque estemos hablando de poco tiempo para generar y evaluar cada tablero, al multiplicar por un millón de tableros, nos vamos a bastantes minutos. Téngase en cuenta que el C64 es un ordenador de 1 MHz.

La conclusión es que no podemos generar y evaluar el árbol completo. No es viable. Hay que podarlo. Y aquí es donde entra la búsqueda alfa – beta que veremos en las entradas que siguen.

Función de evaluación

La función de evaluación es una rutina que recibe un tablero (tablero “board”) y devuelve un número que nos indica cómo de bueno o malo es ese tablero para ratón y gatos. Se aplica sobre las hojas del árbol de juego, y luego esas evaluaciones se hacen subir por el árbol aplicando minimax, es decir, calculando el máximo o el mínimo en función del bando que mueve:

Las funciones de evaluación pueden llegar a ser muy sofisticadas en juegos complejos como el ajedrez. Suelen tener en cuenta muchos criterios, que se suelen clasificar en:

  • Posicionales: Los que tienen que ver con la posición de las piezas.
  • Materiales: Los que tienen que ver con el número y valor de las piezas.

En el caso del ratón y el gato, como no hay capturas, las piezas son siempre las mismas y, por tanto, no hay criterios materiales. Sólo hay criterios posicionales.

Tablas de evaluación:

La función de evaluación se apoya en unas tablas llamadas “tablas de evaluación”. Estas tablas están definidas en el fichero “Init.asm”, aunque igualmente se podrían haber definido en el nuevo fichero “Eval.asm”, que tiene que ver con la evaluación.

Hay una tabla por cada tipo de pieza y, puesto que en su momento decidimos que los gatos eran cuatro piezas distintas (“PIECE_CAT1”, …, “PIECE_CAT4”), con el objeto de poder distinguirlos, eso da lugar a cinco tablas:

La tabla de evaluación “mouse_scores” nos dice cuánto vale el ratón en función de su posición (criterio posicional). Si el ratón está en la fila cero vale cero, si está en la fila uno vale uno, y así sucesivamente. Es decir, vale tanto más cuanto más cerca esté de la última fila, porque el objetivo del ratón es llegar a la última fila.

En el caso de un gato, la tabla de evaluación “cat*_scores” nos dice que vale 28 cuando está en la fila siete (fila inicial de los gatos), 27 cuando está en la fila seis, 25 cuando está en la fila cinco, y así sucesivamente. Aquí hay que observar dos cuestiones importantes:

  • De la fila siete a la seis el gato pierde un punto (28-27=1), pero de la seis a la cinco pierde dos (27-25=2), de la cinco a la cuatro pierde tres (25-22=3), y así sucesivamente. Cuanto más avanza más valor pierde.
  • Aunque el gato 1, por ejemplo, puede moverse en teoría por todo el tablero (respetando sus reglas de movimiento, claro), en la práctica, por cómo hemos diseñado su tabla de evaluación, el gato 1 va a intentar no salirse de las columnas 1 y 0. Si se saliera de ahí, lo cual está permitido por las reglas de movimiento, perdería todo su valor.

Estos dos “trucos” tienen como efecto combinado que, antes que mover un gato varias veces seguidas y romper la formación de gatos, el C64 preferirá mover los gatos en formación, es decir manteniendo la fila, y de este modo intentará impedir que el ratón los rebase, lo cual le daría la victoria.

En definitiva, las tablas de evaluación están diseñadas para que el ratón y los gatos busquen sus respectivos objetivos en el juego, que son llegar a la última fila en el caso del ratón, y acorralar al ratón en el caso de los gatos.

Rutina “eval”:

Una vez vistas las tablas de evaluación, lo que hace la función de evaluación, que es la rutina “eval” del nuevo fichero “Eval.asm”, es esto:

Es decir:

  • Define tres valores, “evMouse” con la valoración del tablero para el ratón, “evCats” con la valoración para los gatos, y “ev” que es la valoración global.
  • Inicializa los tres valores a cero.
  • Recorre el tablero “board” con el índice X.
  • Si una posición X contiene el ratón (“#PIECE_MOUSE”), usa la tabla de evaluación del ratón (“mouse_scores”) para determinar el valor de “evMouse”.
  • Si una posición X contiene un gato (“#PIECE_CAT*”), usa la tabla de evaluación de ese gato (“cat*_scores”) para determinar el valor de “evCats”. Se va sumando al valor anterior.
  • Si la posición está vacía, lógicamente se pasa a la siguiente.

Por último, queda hacer algunos cálculos:

Como se puede ver, en la parte final de “eval”, a partir de la etiqueta “evEnd”, se aplica la siguiente fórmula:

ev = $80 + evMouse – evCats

Es decir, la evaluación global “ev” es igual a $80 = 128, más la evaluación del ratón, menos la evaluación de los gatos.

Y como la evaluación máxima de los gatos es 28 x 4 = 112, eso da lugar a una evaluación mínima de 128 + 0 – 112 = 16 = $10. Esta evaluación es la que corresponde al tablero inicial. A partir de ahí, los gatos irán bajando y el ratón, en general, irá subiendo, lo que en teoría podría dar lugar a una evaluación máxima de 128 + 7 – 0 = 135 = $87.

Es decir, la evaluación global es un número que oscila entre $10 = 16 y $87 = 135. De hecho, el objetivo de sumar $80 = 128 es manejar y comparar siempre números positivos, lo cual es más fácil que manejar números positivos y negativos.

Nuevo programa principal:

Ya sólo nos queda probar todo esto para lo que, como siempre, hacemos un nuevo programa principal:

Este nuevo programa principal:

  • Inicializa el tablero y la partida con “initBoard”.
  • Inicializa las tablas aleatorias para el hash y el lock con “randomize”.
  • Inicializa el proceso de búsqueda con “newPosition”, aunque de momento todavía no vamos a buscar la mejor jugada, aunque nos vamos acercando.
  • Muestra el tablero con “displayBoard”, que ha sido mejorada para mostrar la evaluación asociada a un tablero.
  • Con “makeMove”, realiza el movimiento 4 => 13, es decir, el movimiento E1 => F2, y vuelve a mostrar el tablero.
  • Con “makeMove”, realiza el movimiento 57 => 48, es decir, el movimiento B8 => A7, y vuelve a mostrar el tablero.

Si lo ejecutamos observamos estos tres tableros:

Es decir, la evaluación empieza en $10, con el movimiento del ratón pasa a $11, y con el movimiento del gato pasa a $12.

Como podemos ver, la evaluación del tablero depende de las posiciones de las piezas. Y como el C64 elegirá como óptimos los movimientos que maximizan o minimizan la evaluación, en función del turno, en el fondo lo que tenemos es que las tablas de evaluación (“*_scores”) influyen en los movimientos que se eligen y realizan.

Código del proyecto: RYG3-06

Árbol de juego / actualización del tablero III

Ya sabemos aplicar un movimiento con “makeMove” y deshacerlo con “takeBack”. Ahora vamos a probar estas rutinas, pero antes una rutina preparatoria que es necesaria.

Rutina “newPosition”:

La rutina “newPosition” es una nueva rutina del fichero “Init.asm”:

Esta rutina es parecida en su función a “InitBoard” pero, en vez de inicializar el tablero y la partida, inicializa el siguiente movimiento. Es decir, prepara todo para que se pueda decidir el siguiente movimiento:

  • Mete cero en la puntuación del ratón (“mouse_score”).
  • Mete cero en la puntuación de los gatos (“cats_score”).
  • Obtiene el hash del tablero actual con “getHash” y lo guarda en “current_hash”.
  • Obtiene el lock del tablero actual con “getLock” y lo guarda en “current_lock”.

Todavía no hemos llegado a la fase de elegir la mejor jugada. Para esto habrá que evaluar las hojas y aplicar minimax.

Todavía estamos en la fase previa de desarrollar el árbol de juego con “makeMove” y “takeBack”. Pero cuando llegue el momento de decidir la siguiente jugada, antes de hacerlo, habrá que llamar a “newPosition” para preparar el proceso de decisión, metiendo cero en las puntuaciones y actualizando hash y lock.

Nuevo programa principal:

Con el objeto de probar “makeMove” y “takeBack” hacemos un nuevo programa principal sencillo:

Este nuevo programa principal:

  • Inicializa el tablero llamando a “initBoard”.
  • Llamando a “randomize”, asigna valores aleatorios a las tablas que se utilizan para generar el hash y el lock. Nota: si en vez de llamar a “randomize” se llama a “fixedHash” se usan unos valores fijos para las tablas aleatorias, lo cual facilita la depuración por usar siempre los mismos valores, y así facilitar la repetición y la comparación.
  • Inicializa el proceso de decisión de la siguiente jugada llamando a “newPosition”. De momento, no vamos hacer un proceso de decisión completo, sólo vamos a probar “makeMove” y “takeBack”, pero la llamada a “newPosition” sirve para calcular el hash y el lock del tablero actual (que es el tablero inicial).
  • Imprime el tablero llamando a “displayBoard”.
  • Hace un movimiento desde la casilla 4 hasta la casilla 13, es decir, mueve el ratón desde la casilla E1 = 4 hasta la casilla F2 = 13. Esto lo hace con “makeMove”.
  • Vuelve a imprimir el tablero con “displayBoard”.
  • Deshace el último movimiento, es decir, devuelve el ratón desde la casilla F2 hasta la casilla E1.
  • Vuelve a imprimir el tablero con “displayBoard”. Obsérvese que, además del ratón, el hash y el lock, el bando, y el número de jugadas también vuelven a sus valores originales.

De este modo, el resultado es así:

Tras aplicar el movimiento E1F2, obsérvese que, además de cambiar la posición del ratón a F2, también cambian el bando que mueve (S: C), el número de jugadas (P:01 y H:01), el hash (#:42) y el lock (L:BE).

Contrariamente, tras deshacer el movimiento, obsérvese que, además de volver el ratón a la posición E1, también vuelven a sus valores originales el bando que mueve (S: M), el número de jugadas (P:00 y H:00), el hash (#:F3) y el lock (L:63).

Por tanto, parece que “makeMove” y “takeBack” funcionan bien. Así que el siguiente paso ya será evaluar los tableros.

Código del proyecto: RYG3-05

Árbol de juego / actualización del tablero II

Nos acercamos ya a dos de las rutinas principales del juego, que son las rutinas:

  • Rutina “makeMove”: Esta rutina sirve para ejecutar un movimiento, ya sea con carácter definitivo (porque se ha seleccionado como el mejor) o con carácter provisional (porque se va a analizar en el proceso de desarrollo del árbol de juego o búsqueda).
  • Rutina “takeBack”: Esta rutina sirve para deshacer el último movimiento. Esto sólo tiene sentido durante el proceso de búsqueda, o si se ofrece una funcionalidad de rectificar el último movimiento.

Estas rutinas están al mismo nivel de importancia que otras ya vistas, por ejemplo, “gen” para generar las jugadas posibles, o “think” y “search” que veremos más adelante, y que sirven para desarrollar el árbol de juego hasta una profundidad N.

Rutina “makeMove”:

Como ya se ha adelantado, esta rutina sirve para ejecutar un movimiento. Está en el fichero “Update.asm”:

Esta rutina recibe un movimiento, es decir, una casilla de origen y una casilla de destino, y hace lo siguiente:

  • Guarda el movimiento (origen, destino) en la lista “game_list”. Esto es lo que va a permitir deshacer el movimiento más adelante, si fuera necesario.
  • Incrementa el número de jugadas históricamente jugadas desde el comienzo de la partida (“hply”) y el número de jugadas de la variante actual (“ply”).
  • Busca la pieza que está en la posición de origen, y la mueve a la posición de destino con “updatePiece”. Recordemos que “updatePiece” actualiza el tablero “board” y el hash / lock con “updateHash”.
  • Cambia el bando al que le toca mover (“side”).

Rutina “takeBack”:

Por su parte, la rutina “takeBack”, que también es del fichero “Update.asm”, es así:

Viene a hacer lo contrario que la rutina “makeMove”:

  • Vuelve a cambiar el bando al que le toca mover (“side”).
  • Decrementa el número de jugadas de la variante actual (“ply”) y las históricamente jugadas (“hply”) desde el inicio de la partida.
  • Busca en “game_list” el origen y el destino del último movimiento.
  • Usando “updatePiece”, mueve la pieza que hay en el destino desde el destino hasta el origen. Es decir, deshace el último movimiento.

Con estas dos rutinas, “makeMove” y “takeBack”, ya somos capaces de ejecutar y deshacer movimientos. Y es importante tener claro que hay dos situaciones en las que se ejecutan movimientos:

  • Durante el proceso de búsqueda o desarrollo del árbol de juego. En esta situación los movimientos se ejecutan para probar cómo de buenos o malos son. Estos movimientos hay que deshacerlos.
  • A partir del proceso de búsqueda anterior, y una vez que el C64 ha decidido cuál es la jugada que más le interesa, para ejecutar esa jugada con carácter definitivo.

Todo esto lo probaremos ya en la siguiente entrada.

Código del proyecto: RYG3-05

Árbol de juego / actualización del tablero I

Recapitulando, ya sabemos:

  • Cómo representar el tablero en memoria del C64.
  • Como inicializar e imprimir el tablero.
  • Cómo generar jugadas para ambos bandos.
  • Cómo calcular el hash de un tablero.
  • Cómo guardar el mejor movimiento asociado a un tablero en una tabla hash, reduciendo el impacto de las colisiones mediante un lock.

Por tanto, parece lógico que los siguientes pasos deberían ser:

  • Desarrollar el árbol de juego hasta una profundidad N.
  • Evaluar las hojas del árbol.
  • Llevar esa evaluación hacia la raíz aplicando minimax.
  • En cada tablero del árbol, seleccionar la mejor jugada del bando que mueva y almacenarlo en la tabla hash.

De este modo, al terminar el proceso, en la tabla hash (en realidad, en las tablas hash, puesto que hay una por bando) quedará almacenada la variante principal. Es decir, quedará almacenada la línea de juego que, según el C64, es la mejor secuencia de jugadas para ambos bandos con la información conocida.

Desarrollar el árbol de juego:

Para “desarrollar el árbol de juego” vamos a generar y aplicar movimientos, pero no vamos a almacenar en memoria el árbol de jugadas completo. Este enfoque consumiría demasiada memoria. Lo que vamos a hacer, en cambio, es ir aplicando movimientos al tablero “board” y luego ir deshaciéndolos.

Es decir, desde un punto visual es como si fuéramos moviendo el tablero o la variante actual por el árbol de jugadas (1º, 2º, 3º, 4º, …):

Cuando la variante actual esté en las hojas del árbol invocaremos la función de evaluación (a detallar más adelante) para evaluar los tableros, y cuando esté en un nodo intermedio calcularemos el máximo o el mínimo de las evaluaciones de los tableros hijo, según el bando al que le toque mover (minimax).

Al final lo que hacemos es recorrer el árbol de juego “en profundidad”: primero la primera rama hasta su máxima profundidad, luego la segunda rama hasta su máxima profundidad, y así sucesivamente hasta la última rama. Y lo mejor de todo es que no necesitamos almacenar en memoria todos los tableros del árbol a la vez. Llega con un único tablero (“board”) sobre el que vamos aplicando y deshaciendo movimientos.

Deshacer movimientos:

Lógicamente, para poder deshacer un movimiento tenemos que saber cuál fue el último movimiento que se aplicó. Sólo el último movimiento se puede deshacer. Para esto se utiliza la lista “game_list” del fichero “Init.asm”.

“game_list” es similar a “move_list”, pero en vez de almacenar los movimientos posibles a partir de un tablero, almacena los movimientos jugados en el pasado, de modo que el último movimiento de “game_list” es el único que se puede deshacer. “game_list”, igual que “move_list”, es doble en realidad, ya que los movimientos tienen un origen y un destino. Por tanto, tenemos “game_list_start” y “game_list_dest”.

Veamos cómo actualizar el tablero para ir recorriendo el árbol de juego.

Rutina “updatePiece”:

La rutina “updatePiece” forma parte de un nuevo fichero “Update.asm”. En este fichero van a estar todas las rutinas relativas a la actualización del tablero, es decir, relativas a aplicar y deshacer movimientos.

Es decir, esta rutina básicamente:

  • Añade una pieza (“upPiece”) a la casilla de destino (“upDest”).
  • Y mete vacío (“#PIECE_EMPTY”) en la casilla de origen (“upStart”).

Pero además de eso, llama a la rutina “updateHash” para actualizar el hash y el lock del tablero como consecuencia de la pieza movida (recordemos que el hash y el lock se derivan de las piezas y sus posiciones).

La rutina “updateHash”, que es del fichero “Hash.asm”, es muy similar a la ya vista “getHash”. “getHash” calcula el hash del tablero teniendo en cuenta todas sus piezas; “updateHash” actualiza el hash y el lock del tablero teniendo en cuenta la pieza de una posición concreta.

De hecho, “updatePiece” llama dos veces a la rutina “updateHash”:

  • La primera vez con la pieza que se mueve (“upPiece”) y la casilla de origen (“upStart”). Esto es para reflejar en el hash y en el lock que la pieza ya no está en la casilla de origen.
  • Y la segunda vez con la pieza que se mueve (“upPiece”) y la casilla de destino (“upDest”). Esto es para reflejar en el hash y en el lock que la pieza ahora está en la casilla de destino.

Con todos estos mimbres (lista de jugadas “game_list” y rutina “updatePiece”) ya es posible abordar las rutinas para hacer y deshacer movimientos. Pero esto ya lo haremos en la siguiente entrada.

Código del proyecto: RYG3-05

Tablas hash con lock

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