Mes: mayo 2022

Si recordamos, en alguna entrada anterior introdujimos el concepto de “profundización iterativa”, que consiste en no buscar directamente a la profundidad de análisis configurada, sino empezar por profundidad uno, luego dos, luego tres, etc., hasta llegar a la profundidad configurada. Y todo ello con el objeto de mejorar la ordenación de los movimientos y, por tanto, optimizar la poda alfa – beta.

Aunque los movimientos se generen e inserten en “move_list” con un orden arbitrario, que en nuestro caso es y va a seguir siendo suroeste – sureste – noreste – noroeste (ver rutina “gen”), eso no quiere decir que esos movimientos tengan que desarrollarse en ese mismo orden. Pueden reordenarse en función del algún criterio antes de desarrollarlos recursivamente. Y esto es, precisamente, lo que vamos que vamos a hacer en esta entrada, de modo que saquemos provecho de la profundización iterativa.

Movimientos con puntuación:

Lo primero que vamos a hacer es asignar a los movimientos una puntuación, de modo que desarrollemos primero aquellos movimientos de mayor puntuación. Es importante no confundir la puntuación de los movimientos con la puntuación o evaluación de los tableros, que sirve para que elegir qué tableros son mejores.

De este modo, los movimientos de “move_list” pasan de tener un origen y un destino a tener un origen, un destino y una puntuación:

Como se puede ver, ahora los movimientos tienen:

• “move_list_start”: origen.
• “move_list_dest”: destino.
• “move_list_score”: puntuación (nuevo).

Por otro lado, la rutina que genera los movimientos permitidos a partir del tablero actual, es decir, la rutina “gen”, sigue generando los movimientos en el mismo orden (suroeste – sureste – noreste – noroeste), pero ahora los genera con una puntuación inicial de cero. Ver su subrutina “addMove”:

Esta puntuación inicial la modificaremos más adelante, de modo que podamos reordenar los movimientos y desarrollar primero los mejores, de modo que se optimice la poda.

Aprovechar la profundización iterativa:

Ahora es cuando por fin vamos a aprovechar la profundización iterativa. Si un movimiento ha sido bueno en alguna iteración anterior, por ejemplo, porque ha dado lugar a una poda alfa o beta, estará en la tabla hash desde esa iteración.

Por tanto, en las rutinas “searchMouse” y “searchCats”, después de generar los movimientos posibles con “gen”, vamos a llamar a una nueva rutina “hashMove”:

Esta nueva rutina “hashMove” hace esto:

Es decir, “hashMove” busca el tablero actual, aquel para el que “gen” ha generado los movimientos posibles, en la tabla hash de ratón o gatos, según el turno, y, si el tablero está en la tabla hash, llama a la rutina “addHashMove”:

La rutina “addHashMove”, por su parte, recorre los movimientos generados por “gen”, es decir, los movimientos posibles a partir del tablero actual, y, al que coincida con el movimiento almacenado en la tabla hash (hash_start, hash_dest), que se supone que es el mejor movimiento, le suma a su puntuación el valor “#HASH_SCORE”.

Dicho de forma sencilla, de todos los movimientos posibles a partir del tablero actual, si alguno está en la tabla hash proveniente de alguna iteración anterior (profundización iterativa), le sumamos “#HASH_SCORE” a su puntuación, lo que (en breve) va a hacer que se desarrolle antes.

“#HASH_SCORE” es una nueva constante definida en el fichero “Globals.asm” e inicialmente toma el valor de 10.

Ordenación de movimientos antes de desarrollarlos:

Los movimientos ya tienen una puntuación (“move_list_score”) y ya sabemos cuándo incrementamos su valor: cuando ese movimiento está en la tabla hash como consecuencia de una iteración anterior de la profundización iterativa.

Ahora falta, por fin, reordenar los movimientos, es decir, desarrollar primero los movimientos con mejor puntación. Esto lo hacemos también en “searchMouse” y “searchCats” con una llamada a la nueva rutina “sort”:

En cada iteración del bucle que prueba y desarrolla cada jugada, es decir, el bucle que empieza en la etiqueta “schMouseAgain” o “schCatsAgain”, vemos la llamada a “sort”:

“Sort” lo que hace es comparar la puntación de la jugada actual con la puntuación de todas las jugadas que quedan por probar / desarrollar y, si alguna tiene puntuación mayor, las reordena en “move_list”, para lo cual se apoya en la rutina auxiliar “shift” (ordenación por inserción):

De este modo, se prueban y desarrollan primero las jugadas con mayor puntuación que, de momento, son aquellas que la profundización iterativa ha decidido que son buenas. Luego se pueden añadir otros criterios para modificar la puntuación y la ordenación, como las tablas de historia.

Mejora en la poda:

Si todo lo que hemos dicho es cierto, que ordenar los movimientos de forma lógica favorece la poda, debería notarse este efecto al comparar la versión anterior del proyecto (versión 9) con la nueva versión (versión 10).

En la versión 9 del proyecto, con una profundidad de 8, se analizaban estos movimientos en la primera jugada de los gatos tras E1F2:

Es decir, se analizaban $4535 = 17.717 nodos. Recordemos que este es el número de nodos acumulado para los ocho niveles, no el valor específico para el octavo nivel.

Sin embargo, con la versión 10 del proyecto, que es la que ya tiene ordenación de movimientos, se analizan estos nodos (también para nivel 8, claro):

Como se puede observar, se han analizado $29F8 = 10.744, que es un 40% menos.

De hecho, una cosa que puede llamar la atención es que los movimientos elegidos no son el mismo. Con la versión 9 del proyecto era el H8G7, mientras que con la versión 10 es el B8A7. Ni la poda alfa – beta ni la ordenación de movimientos deberían tener este efecto. El origen del mismo radica en que en la versión 10 del proyecto se han hecho algunos ajustes en la rutina “search” cuando la puntuación retornada coincide con alfa o beta (cálculo del máximo o mínimo).

Con la versión 10 del proyecto, con una profundidad de 8 niveles o superior, jugando el humano con el ratón y el C64 con los gatos, yo no he conseguido ganarle, lo cual es muy buena noticia. A esa profundidad el C64 tarda menos de minuto y medio en decidir su siguiente jugada.

Por tanto, el proyecto está prácticamente terminado, aunque, por supuesto, admite muchas mejoras.

---

Código del proyecto: RYG3-10

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

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