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
Programación Retro del Commodore 64 