Objetivo del método de poda alfa-beta
PREGUNTA:
No entiendo el criterio para elegir la mejor estrategia en el
algoritmo alfa-beta. Una vez aplicado el algoritmo, ¿para qué
sirve? Es decir, ¿por qué se elige una u otra estrategia?
RESPUESTA:
El método de poda alfa-beta se utiliza en el contexto de problemas
de juegos entre dos adversarios de turno alternativo (por ejemplo,
el ajedrez). Dada una situación de la partida (estado del tablero
de ajedrez), interesa saber cuál de las posibles
jugadas que podemos realizar a partir de esa situación es la más
prometedora para intentar ganar a nuestro adversario.
(Éste es en realidad el problema que hay que resolver.)
Para ello se genera el árbol que resulta de establecer todas las
posibles jugadas que podemos realizar a partir de la situación actual,
todas las posibles respuestas de nuestro contrincante a cada una de
las jugadas anteriores, todas nuestras posibles respuestas a las jugadas
del contrincante... y así sucesivamente. Normalmente se establece un
límite en el número de turnos de movimiento considerados (dependiendo
de la memoria de la que disponga nuestro ordenador) y se considera el
árbol formado hasta ese nivel de profundidad. Un experto puede asociar
un valor numérico heurístico a cada nodo hoja, que indique lo
prometedora que es esa situación de la partida para que gane yo.
Normalmente se supone que a números mayores, más prometedora es esa
situación de la partida para mí. Por tanto, lo único que queda por hacer
es establecer qué camino de los que parten del nodo raíz nos lleva a un
nodo hoja con valor máximo de la función de evaluación heurística.
Una posibilidad para ello es examinar todo el árbol que hemos generado
mediante una búsqueda en profundidad. Lo único que hay que tener en
cuenta es que en cada nodo por el que pasamos debemos anotar cuál es
la jugada más prometedora que cuelga del mismo. (Es como si los valores
numéricos de los nodos hoja viajaran hacia arriba de manera que en cada
nodo con hijos seleccionáramos la mejor jugada y el valor que obtenemos
al elegirla.) Al final de la búsqueda en profundidad, en el nodo raíz
tendremos señalada cuál es la mejor jugada (o arco hacia uno de sus
nodos hijo) y el valor de la función heurística que obtendríamos al
elegir ese camino. Hay que tener en cuenta que cuando movamos nosotros
intentaremos elegir la jugada que nos permita acceder a un nodo con
el máximo valor posible de la función de evaluación, mientras que
cuando le toque mover a nuestro contrincante ocurrirá lo contrario (in-
tentará minimizar dicha función).
El método que he descrito es el llamado MINIMAX. Ocurre que este método
es ineficiente, ya que explora todo el árbol que hemos construido, dada
una situación de la partida. Es ineficiente porque resulta que hay
subárboles de este árbol que no es necesario explorar. El método de
poda alfa-beta se encarga de identificar esos subárboles y podarlos.
Para ello utiliza dos variables a lo largo del proceso de búsqueda
en profundidad: alfa y beta. Al principio del proceso de búsqueda
alfa toma el valor -infinito, mientras que beta toma el valor
+infinito. Desde un nodo en que nos toque mover a nosotros, iremos
actualizando el valor de alfa a medida que vayamos explorando cada
arco que cuelgue de ese nodo. Dicha actualización consiste en
comparar el valor obtenido por cada arco con el valor actual de
alfa. Si el valor obtenido es mayor, ése será el nuevo valor de alfa.
Por tanto, alfa almacena el mejor valor que hemos encontrado
desde el nodo en que estamos. Sólo nos interesará
proseguir la búsqueda desde ese nodo si podemos
mejorar alfa. En caso de que estemos en un nodo en el que mueve
nuestro contricante, iremos actualizando el valor de beta a medida
que vayamos explorando cada arco que cuelgue de ese nodo. Dicha
actualización consiste en comparar el valor obtenido por cada arco
con el valor actual de beta. Si el valor obtenido es menor, ése
será el nuevo valor de beta. Por tanto, beta almancena el peor
valor (para nosotros) encontrado por nuestro contrincante hasta el
momento. Sólo interesará que la búsqueda prosiga si nuestro
contrincante pudiera reducir beta. El intervalo (alfa,beta) de
la recta real viene a indicar el conjunto de valores que se puede
seguir consiguiendo en el proceso de búsqueda. Cuando alfa crece
tanto que sobrepasa a beta, o cuando beta disminuye tanto que
se hace menor que alfa, se puede hacer una poda y no seguir
explorando el subárbol que cuelga desde el nodo en que nos
encontramos, prosiguiendo la búsqueda en profundidad desde su nodo
padre.
Al final del proceso de búsqueda en profundidad con podas, ¿con qué
jugada nos quedamos? Es decir, ¿qué arco de los que cuelga del nodo
raíz del árbol elegimos? Pues bien, elegiremos el último arco que
haya actualizado el valor de alfa. Con "actualizar" me refiero a que
ese arco nos ha proporcionado un valor para alfa mejor (mayor) al que
existía antes de que la búsqueda prosiguiera por ese arco.
Reconozco que seguir la explicación de arriba es un poco difícil.
Una explicación más detallada viene en el libro:
Problemas resueltos de inteligencia artificial aplicada: búqueda
y representación
Severino Fdez. Galán, Jesús Glez. Boticario y José Mira
Addison-Wesley