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.