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
