Programa principal definitivo III

Ahora que ya sabemos cómo mueve el C64 con la rutina “computerTurn”, lo siguiente es estudiar cómo mueve el humano con la rutina “humanTurn”:

Rutina “humanTurn”:

En primer lugar, la rutina “humanTurn” declara unos textos (“GO”, “HELP”, “NEW GAME”, etc.). Luego veremos en qué situaciones se usan:

A continuación, tenemos el bloque principal de “humanTurn”:

En este bloque principal:

  • Se llama a la rutina “command”, que imprime “?“ apoyándose en la rutina del Kernal CHROUT (dirección $ffd2) y lee hasta cuatro caracteres apoyándose en la rutina del Kernal GETIN (dirección $ffe4). Estos cuatro caracteres se almacenan en las variables “command*”.
  • Si el primer carácter (“command1”) es un punto (“.”), entonces se trata de un comando especial, y la ejecución continúa en la etiqueta “commands”.
  • En caso contrario, se trata de un movimiento, y la ejecución continúa en la etiqueta “parse”.

Comandos especiales:

Los comandos especiales empiezan todos por punto, es decir, command1 = “.”. A partir de ahí, hay que analizar el segundo carácter para identificar de qué comando se trata. Y algunos comandos, incluso, aceptan un tercer carácter, como el comando “.DN” para fijar la profundidad de análisis o el comando “.TN” para fijar el tiempo máximo.

Los comandos soportados son:

  • “.B” para mostrar el tablero.
  • “.G” para arrancar el motor de juego.
  • “.H” para mostrar la ayuda.
  • “.M” para mostrar los movimientos posibles.
  • “.N” para empezar una nueva partida.
  • “.O” para parar el motor de juego.
  • “.Q” para terminar y volver a BASIC.
  • “.DN” para fijar la profundidad de análisis.
  • “.TN” para fijar el máximo tiempo por jugada (no implementado).
  • “.S” para que sea el turno del otro bando.
  • “.U” para deshacer la última jugada.
  • “.E” para mostrar el contenido de las tablas hash (depuración).

Se podrían definir otros comandos como, por ejemplo, mostrar los movimientos jugados desde el comienzo de la partida (tabla “game_list”), grabar esos movimientos a un fichero, cargarlos desde un fichero y continuar la partida, etc.

Casi todos los comandos se implementan igual:

  • Se identifica el comando analizando la variable “command2”.
  • A veces se muestra un texto de confirmación, por ejemplo, “GO”, para que el usuario sepa que el C64 le ha entendido. Estos son los textos apuntados por las variables “text*” que se mencionaron al comienzo de la rutina “humanTurn”.
  • Se ejecuta la rutina que haga falta, por ejemplo, “displayBoard” para el comando “.B”. Si la rutina ya muestra algún texto, el texto de confirmación se suele obviar, puesto que no es necesario.

A modo de ejemplo, se comenta detalladamente la implementación del comando “.U”, que es uno de los más complejos, aunque todos son muy similares:

Como se puede observar, el comando “.U” o “undo”:

  • Primero detecta que se trata del comando “undo”.
  • Después imprime el texto apuntado por “textUndo”, es decir, imprime “UNDO”.
  • Después carga en el acumulador el valor de “hply”, es decir, el número de jugadas de la partida.
  • Si el número de jugadas es cero, termina, puesto que no hay ninguna jugada que se pueda deshacer.
  • Si el número de jugadas es mayor que cero, carga el valor #PIECE_EMPTY en “computer_side”, es decir, para el motor de juego.
  • Además, deshace la última jugada con la rutina “takeBack” y deja preparada la siguiente búsqueda inicializando “ply” y “first_move”.

De este modo, la ejecución de “E1F2” y luego “.U” tiene este resultado:

El resto de comandos tienen implementaciones muy similares, por lo que no los revisaremos todos aquí.

Movimientos:

La alternativa a los comandos son los movimientos. Los comandos empiezan por punto, los movimientos no. Y los movimientos ocupan cuatro caracteres, por ejemplo, “E1D2”.

Los movimientos se analizan y ejecutan a partir de la etiqueta “parse”:

Es decir, en primer lugar, llama a la rutina “parseMove”, que pasa de una cadena de caracteres a una pareja (command_start, command_dest), por ejemplo, de “E1D2” a (4, 11). En caso de que el movimiento no sea sintácticamente correcto, es decir, una letra de la A a la H y un número del 1 al 8 para el origen y otro tanto para el destino, “parseMove” devuelve ($ff, $ff).

Siguiendo con el código de “parse”:

  • Verifica si “command_start” vale $ff.
  • En caso afirmativo, el movimiento introducido por el usuario es sintácticamente incorrecto, y se ejecuta “parseKo”. Por tanto, se imprime “ILLEGAL” y termina. Se vuelve a pedir un comando o un movimiento al usuario.
  • En caso negativo, el movimiento introducido por el usuario es sintácticamente correcto, pero aun así puede ser inválido. Por tanto, hay que verificar el movimiento, es decir, hay que comprobar que se trata de un movimiento válido. Por ello, se generan los movimientos permitidos con “gen” y se ejecuta “verifyMove”.
  • La rutina “verifyMove” básicamente recorre los movimientos generados y almacenados en “move_list”, desde first_move(0) hasta first_move(1), y se comparan con (command_start, command_dest). Si alguno de los movimientos permitidos, es decir, almacenados en “move_list”, coincide con (command_start, command_dest), entonces se trata de un movimiento válido y se señaliza con vmOK = 0.

Si el movimiento es sintácticamente correcto, pero no es válido, entonces se ejecuta igualmente “parseKo”, es decir, se imprime “ILLEGAL” y se vuelve a pedir un comando o movimiento al usuario.

Por último, si se han superado todos los controles, es decir, si el movimiento es sintácticamente correcto y válido, se ejecuta “parseMove2”:

A partir de “parseMove2” lo que ocurre es:

  • Se ejecuta el movimiento (command_start, command_dest) con la rutina “makeMove”.
  • Se imprime el movimiento (command_start, command_dest) con dos llamadas a “algebraic”.
  • Se inicializa “ply” y “first_move” para dejar preparado el siguiente proceso de búsqueda.
  • Se vuelve a generar las jugadas posibles con “gen”, en previsión de que el humano quiera consultarlas con el comando “.M”.
  • Se podría imprimir el tablero con “displayBoard”, igual que cuando mueve el C64, aunque ahora mismo lo tenemos comentado.
  • Finalmente, se comprueba si es el final de la partida con “checkResult”, que es una de las rutinas vistas en la entrada anterior (verificaba si el ratón estaba acorralado o si estaba en la última fila).

De este modo, el intento de ejecución de un movimiento sintácticamente incorrecto sería así:

Por otro lado, el intento de ejecución de un movimiento sintácticamente correcto, pero inválido, sería así:

Y, por último, la ejecución de un movimiento sintácticamente correcto y válido sería así (añadimos el comando “.B” para ver el tablero resultante):


Código del proyecto: RYG3-09

Programa principal definitivo II

Como hemos visto en la entrada anterior, el bucle de juego básicamente consiste en alternar los turnos del jugador uno y del jugador dos, ya que la variable “side” va cambiando de valor en cada iteración (ratón => gatos => ratón => gatos => …). Así hasta que el humano salga del juego con el comando “.Q”.

Y, aunque se ha visto que hay otras opciones, lo normal será que el C64 juegue toda la partida por un bando, por ejemplo, los gatos, y el humano juegue toda la partida por el otro bando, por ejemplo, el ratón.

Por tanto, lo que nos interesa ahora es revisar las rutinas “computerTurn” y “humanTurn”:

Rutina “computerTurn”:

La rutina “computerTurn” está en el fichero “Main.asm” y se encarga de que el C64 mueva. Tiene cuatro partes principales:

  • Ejecutar la búsqueda alfa – beta con profundización iterativa.
  • Localizar el movimiento decidido por la búsqueda.
  • Comunicar el movimiento decidido y aplicarlo con “makeMove”.
  • Verificar si la partida ha terminado.

La primera parte es así:

Es decir:

  • Declara unas cadenas de texto que se usarán más adelante.
  • Graba en la posición de “player” correspondiente a “side” (índice Y) que el C64 (#PLAYER_COMPUTER) está jugando por ese bando.
  • Llama a “thinkIter”, que es donde está el grueso de la inteligencia.
  • Incrementa el número de movimientos de “turns”.

La rutina “thinkIter” es la búsqueda alfa – beta con profundización iterativa. Por tanto, es el proceso que decide qué jugada debe hacer el C64.

Lo que puede que no esté muy claro a estas alturas es dónde queda la jugada decidida o elegida por el C64. Aunque no sea obvio del todo, esa jugada queda en las tablas hash después del proceso de búsqueda. Llega con buscar en las tablas hash a partir del tablero actual, y eso nos dará el mejor movimiento.

Por eso la segunda parte de “computerTurn” es así:

Es decir:

  • Recalcula el hash y el lock del tablero actual con “getHash” y “getLock”.
  • En función del bando por el que juega el C64, ratón o gatos, busca el tablero actual / hash actual en la tabla hash de ratón con “lookUpMouse” o en la tabla hash de gatos con “lookUpCats”.
  • El resultado de esa búsqueda, que es el mejor movimiento a partir del tablero actual, se guarda en (hash_start, hash_dest).

Si “hash_start” (o “hash_dest”) vale $ff, el proceso de búsqueda no consiguió determinar un mejor movimiento. No será lo normal; más que nada es una previsión del programa. En ese caso se ejecutaría la rama “ctNoLegalMove”, que tampoco tiene mucho interés, ya que básicamente avisa al usuario y para el motor.

Si “hash_start” es distinto de $ff, entonces pasamos a la tercera parte de “computerTurn”:

En esta tercera parte, la rutina “computerTurn”:

  • Muestra el texto “COMPUTER’S MOVE:” y el movimiento decidido (hash_start, hash_dest) en notación algebraica.
  • Y ejecuta el movimiento elegido (hash_start, hash_dest) con “makeMove”.

Por último, la rutina “computerTurn”:

Es decir, por último, la rutina “computerTurn”:

  • Inicializa “ply” y “first_move”, puesto que este proceso de búsqueda ha terminado, y hay que dejar preparado el siguiente.
  • Vuelve a generar las jugadas posibles con “gen”, en previsión de que el humano quiera consultarlas con el comando “.M”.
  • Muestra el tablero actualizado con “displayBoard”.
  • Y llama a la nueva rutina “checkResult”.

La rutina “checkResult” también se llama desde el final “humanTurn”, y lo que hace es verificar si la partida ha terminado.

Rutina “checkResult”:

La rutina “checkResult”, que también es parte del fichero “Main.asm”, es así:

Por tanto, “checkResult” verifica a quien le toca mover ahora (recordemos que “makeMove” ya ha modificado “side” con la instrucción “eor #%00000001”) y:

  • Si ahora ya le toca mover al ratón, es decir, si acaban de mover los gatos, verifica si el ratón puede mover o si está acorralado, llamando para ello a la rutina “mouseNoMoves”.
  • Si ahora ya le toca mover a los gatos, es decir, si acaba de mover el ratón, verifica si el ratón ha llegado a la fila 7 con “mouseInRow7” y si los gatos no pueden mover con “catsNoMoves”.

Rutina “mouseInRow7”:

La rutina “mouseInRow7” es sencilla:

Básicamente lo que hace es revisar las casillas 56 a 63, es decir, la última fila, y verificar si el ratón está ahí. Si está en alguna de esas casillas imprime “*** MOUSE WINS!! ***” y ejecuta “newGame”, que se verá más adelante, pero que lógicamente prepara una nueva partida.

En caso contrario, la rutina “mouseInRow7” termina y “checkResult” continúa con otras verificaciones.

Rutinas “mouseNoMoves” y “catsNoMoves”:

Las rutinas “mouseNoMoves” y “catsNoMoves” son muy parecidas, casi idénticas. La única diferencia es el mensaje que se presenta en caso de que el ratón o los gatos no puedan mover:

Ambas rutinas:

  • Leen el valor de la posición first_move(1). Recordemos que “first_move” es una tabla con punteros a “move_list”, concretamente con los puntos de entrada de “move_list” donde empiezan los movimientos a profundidad 1 (first_move(0)), a profundidad 2 (fisrt_move(1)), a profundidad 3 (first_move(2)), etc.
  • Si el valor almacenado en first_move(1) es 0 o, lo que es lo mismo, si first_move(0) = first_move(1) = 0, es que no hay movimientos posibles. Por tanto, ambas rutinas terminan con un mensaje (“*** MOUSE WINS!! ***” o “*** CATS WIN!! ***”) y preparando una partida nueva llamando a “newGame”.
  • En caso contrario, es decir, si sí hay movimientos posibles, entonces las rutinas terminan y “checkResult” continúa con otras verificaciones, si es el caso.

Gracias a todas estas rutinas que forman parte o son llamadas por “computerTurn” (“thinkIter” para ejecutar la búsqueda alfa – beta con profundización iterativa, “lookUp*” para localizar el mejor movimiento, “makeMove” para mover y “checkResult” para comprobar el final de partida), un movimiento del C64 tendría esta pinta:


Código del proyecto: RYG3-09

Programa principal definitivo I

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

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