Mes: abril 2022

Hasta ahora hemos usado el programa principal, es decir, el fichero “Main.asm”, para probar las diferentes funcionalidades que íbamos desarrollando: la representación e impresión del tablero, la generación de jugadas, las tablas hash de movimientos, la función de evaluación, etc.

Ahora nos disponemos a desarrollar el programa principal definitivo:

Objetivos del programa principal:

Los objetivos de este programa principal serán:

• Ejecutar la configuración inicial del juego.
• Ejecutar el bucle de juego, que consiste en alternar los turnos del jugador uno y del jugador dos hasta que termine la partida.

Normalmente un jugador será el C64 y el otro será un humano, pero también es posible que el C64 o un humano jueguen por ambos bandos a la vez. Esto es muy interesante, porque significa que el C64 podrá jugar contra sí mismo. El humano también, pero para esto casi es más práctico tomar un tablero y unas fichas de verdad 🙂 .

Tanto el C64 como el humano podrán jugar por el bando del ratón o los gatos o, incluso, por ambos, como ya se ha dicho.

Cuando sea el turno del C64, da igual que juegue por el ratón o los gatos, el objetivo será ejecutar la búsqueda alfa – beta hasta la profundidad de análisis configurada, aplicar la jugada elegida, y verificar si es el final de la partida.

Cuando sea el turno del jugador humano, da igual que juegue por el ratón o los gatos, el objetivo principal será aceptar el movimiento del humano, verificar que es un movimiento válido, aplicar el movimiento del humano, y verificar si es el final de la partida.

En caso de que sea el turno del humano, además, se aceptarán una serie de “comandos especiales” para funciones como:

• Mostrar el tablero.
• Arrancar o parar el motor de juego.
• Mostrar la ayuda.
• Mostrar los movimientos válidos.
• Empezar una partida nueva.
• Salir del juego.
• Configurar la profundidad de análisis.
• Configurar el tiempo máximo por movimiento (mejora).
• Cambiar el turno.
• Deshacer la última jugada.
• Etc.

En particular, esta opción de que el humano meta “comandos especiales” puede resultar muy útil para imprimir información que facilite la depuración del programa, como el contenido de las tablas hash, el contenido de las tablas de historia (se verán más adelante), etc.

Algunas variables importantes:

Antes de revisar el programa principal, veamos algunas variables importantes:

Estas variables se usan para lo siguiente:

• “computer_side”: Permite parar el motor de juego (computer_side = #PIECE_EMPTY), arrancarlo para que el C64 juegue por el ratón (computer_side = #SIDE_MOUSE), y arrancarlo para que el C64 juegue por los gatos (computer_side = #SIDE_CATS).
• “player”: Sirve para llevar control de quién juega por el ratón (valor almacenado en player[#SIDE_MOUSE = 0]) y por los gatos (valor almacenado en player[#SIDE_CATS = 1]). Ambos pueden ser el humano (#PLAYER_HUMAN = 0) o el C64 (#PLAYER_COMPUTER = 1).
• “fixed_time” y “fixed_depth”: Sirven para configurar que el juego juegue a un tiempo fijo por jugada (fixed_time = 1), a una profundidad fija por jugada (fixed_depth = 1), o a ambas cosas, es decir, a la limitación que salte antes (tiempo límite o profundidad límite). De momento sólo está implementada la opción de profundidad fija.
• “max_time” y “max_depth”: Sirven para configurar el tiempo máximo en minutos por jugada y la profundidad máxima en niveles. De momento sólo se utiliza “max_depth” puesto que sólo está implementada esa opción.
• “turns”: Sirve para llevar cuenta del número de jugadas ejecutadas. En realidad, sólo cuenta las jugadas ejecutadas por el C64. Se podrían contar también las jugadas del humano, caso de quererse así.
• “command1” … “command4”: Sirven para almacenar los movimientos y los “comandos especiales” que introduzca el jugador humano. Los movimientos pueden tener hasta 4 caracteres, por ejemplo “E1D2”, que se almacenan respectivamente en command1, 2, 3 y 4.
• “command_start” y “command_dest”: Cuando el comando del jugador humano sea un movimiento del tipo “E1D2”, “E1” se traducirá por la casilla 4, que se almacenará en “command_start”, y “D2” se traducirá por la casilla 11, que se almacenará en “command_dest”. De este modo la información queda lista para ejecutar la rutina “makeMove”.

Todas estas variables controlan el funcionamiento del programa principal.

Programa principal definitivo:

El nuevo programa “main” del fichero “Main.asm” queda así:

Es decir:

• Primero ejecuta la configuración inicial llamando a la rutina “setup”.
• A partir de ahí, entra en el bucle de juego, que sólo termina cuando el jugador humano teclea el comando especial “.Q”. Los comandos especiales empiezan siempre por punto (“.”).
• Es posible jugar varias partidas seguidas sin salir del programa.

Veamos cómo son la configuración inicial y el bucle de juego.

Configuración inicial:

La configuración inicial es la rutina “setup”, que ya está en el programa principal desde hace un par de versiones. La nueva rutina “setup” es así:

Es decir, la nueva rutina “setup”:

• Configura las tablas aleatorias con “fixedHash” (para depuración) o con “randomize” (para valores aleatorios).
• Inicializa la partida con la rutina “initBoard”.
• Con la rutina “gen”, genera los movimientos posibles desde la posición inicial. De este modo, se podrían mostrar con el comando especial “.M”.
• Mete el valor #PIECE_EMPTY en “computer_side”, de modo que el motor de juego no arranca automáticamente, sino que hay que arrancarlo manualmente con el comando especial “.G”.
• Inicializa “player”, porque de momento no se sabe quién va a jugar por cada bando, si el C64 o el humano.
• Fija el tiempo máximo por jugada en 5 minutos, aun cuando está función de jugar a tiempo fijo no está desarrollada del todo. Implicaría utilizar interrupciones del CIA1. Este tiempo se puede cambiar con el comando especial “.TM”, donde M es el número de minutos.
• Fija la profundidad de análisis a 4 niveles. Esta profundidad también se puede cambiar con el comando especial “.DN”, donde N es el nuevo nivel de profundidad.

Veamos ahora el bucle de juego.

Bucle de juego:

El bucle de juego es esta parte específica del programa principal (inicialización con “setup” aparte):

Como se puede ver:

• Compara el bando al que le toca mover, que está en “side”, con el bando por el que juega el C64, que está en “computer_side”.
• Si son iguales, es decir, si le toca mover al ratón y el C64 juega por el ratón, o si le toca mover a los gatos y el C64 juega por los gatos, entonces ejecuta “computerTurn”. Como veremos más adelante, “computerTurn” básicamente ejecuta la profundización iterativa, es decir, “thinkIter”.
• Por el contrario, si son distintos, es decir, si le toca mover al ratón y el C64 juega por los gatos, o al revés, entonces ejecuta “humanTurn”. Esto permite que el jugador humano mueva o ejecute un “comando especial”.
• El punto anterior tiene un caso especial, que es cuando “computer_side” vale #PIECE_EMPTY, que es su valor inicial. Esto significa que el C64 de momento está parado, que no juega ni por el ratón ni los gatos. En este caso, es imposible que “side” y “computer_side” sean iguales, puesto que “side” sólo puede valer ratón o gatos, así que en este caso siempre se ejecuta “humanTurn”. Es decir, cuando el motor está parado sólo puede mover o ejecutar comandos el humano. Todo ello hasta que se arranque el motor con el comando “.G”, que básicamente lo que hace es darle un valor a “computer_side”.

Gracias a este bucle de juego tan flexible es posible arrancar el juego con “RUN”, que ejecuta el cargador BASIC “10 SYS 2080”, y hacer cosas como:

• Mostrar el tablero con “.B”:

• Mover por el ratón con “E1F2”:

• Volver a mostrar el tablero con “.B”:

• Pedirle al C64 que mueva por los gatos con “.G”:

• Volver a pedirle al C64 que mueva, ahora por el ratón, con “.G”:

• Pedir los movimientos posibles con “.M”:

• Mover ahora por los gatos con “F8E7”. Como el motor está arrancado, el C64 vuelve a mover automáticamente por el ratón con “E3D4”:

• Parar el motor con “.O”:

• Volver a pedir los movimientos posibles con “.M”.

• Volver a mover por los gatos con “D8C7”. Como el motor ahora está parado, el C64 no mueve automáticamente por el ratón:

• Volver a mostrar el tablero con “.B”:

• Salir del juego con “.Q”:

Lógicamente, lo normal será que el C64 juegue por un bando y el humano por otro, pero un bucle de juego como éste permite todo tipo de opciones y cambios.

---

C´´odigo del proyecto: RYG3-09

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

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

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.

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…