MiniMax puede ser mucho más inteligente de lo anteriormente expuesto. Veamos qué tipo de mejoras pueden aplicársele.
Poda Alfa-Beta
Un punto clave que hemos de tener en cuenta es que cuanto más profunda sea la exploración, mejor podremos tomar la decisión sobre qué jugada debemos escoger.
Para juegos con un factor de ramificación elevado, esta profundidad no podrá ser muy grande, ya que el cálculo necesario para cada decisión será prohibitivo. Su tiempo de exploración será prohibitivo.
Para reducir este tiempo se han estudiado los árboles de búsqueda, y se ha llegado a la conclusión de que es muy factible usar heurísticos con poda. En otras palabras, usaremos una técnica de ramificación y poda (branch and bound) con la cual una solución parcial se abandonará cuando se compruebe que es peor que otra solución ya conocida.
La estrategia denominada alfa-beta aprovecha que el algoritmo del MiniMax hace una exploración en profundidad para guardar información sobre cuál es el valor de las mejores jugadas encontradas para cada jugador.
Concretamente guarda dos valores, denominados umbrales alfa y beta (de ahí el nombre del heurístico). El valor alfa representa la cota inferior del valor que puede asignarse en último término a un nodo maximizante, y análogamente el valor beta representará la cota superior del valor que puede asignarse como última opción en un nodo minimizante.
De esta manera el algoritmo podrá acotar el valor de una exploración, pues gracias a los umbrales alfa y beta conocerá si vale la pena explorar un camino o no.
Veamos un ejemplo:
En el árbol superior podemos ver que el valor que propagaría MiniMax al nodo raíz sería 8. Pero si nos fijamos en el nodo marcado, en el segundo descendiente de la raíz ya sabe que el mejor nodo del primer descendiente tiene valor 8. Puesto que el descendiente es un nodo Min, y se ha encontrado por debajo un valor de 6, el algoritmo interpretará que por ese camino como mejor resultado habrá ese 6 (pues el nodo inferior elegirá o el 6 o algo inferior).
Como ya conocemos el posible 8, todos los nodos que cuelgan del Min que elegiría el 6 ya no hace falta explorarlos, pues seguro que ahí no se encuentra nuestra mejor jugada. En este momento se realizaría la poda de esa rama e iría a explorar el tercer posible camino.
Podemos observar también que esta circunstancia se repetirá en el tercer descendiente al explorar su último nodo, pero al no quedar más descendientes la poda no nos ahorraría nada. Significa que la efectividad de esta heurística dependerá del orden de los nodos, pues cuanto antes encuentres un valor penalizado por el umbral, antes podrás podar la rama.
Esta heurística modifica el algoritmo del minimax introduciendo dos parámetros en las llamadas de las funciones, alfa y beta, y representarán el límite del valor que pueden tomar las jugadas que exploramos. Una vez superado ese límite sabremos que podemos parar la exploración porque ya tenemos el valor de la mejor jugada accesible.
Poda de Inutilidades
Realmente la poda de inutilidades es un refinamiento adicional de la poda alfa-beta.
La poda de inutilidades es la finalización de la exploración de un subárbol que ofrece pocas posibilidades de mejora sobre otros caminos que ya han sido explorados. Es decir, es la misma idea de alfa-beta, pero en lugar de podar una rama si sabes que no tendrás resultados mejores, podarás si sabes que no tendrás resultados suficientemente mejores.
En el ejemplo de la figura, después de examinar el nodo B, el jugador maximizante se asegura un valor de 3. Al examinar el nodo G se obtiene un valor 3.1 que es sólo algo mejor que 3. Puesto que si se exploran los nodos H e I no lograremos mejorar este valor desde el punto de vista del jugador maximizante, sería mejor podarlos y dedicar más tiempo a explorar otras partes del árbol donde se puedan obtener más ventajas.
En conclusión, con poda alfa beta podremos ampliar el límite de profundidad de nuestra exploración, ya que con las podas nos ahorramos la exploración de varias parte del árbol de búsqueda, llegándonos a ahorrar así múltiples niveles. De ahí deriva que algunas de las siguientes ampliaciones se basen en mejorar el comportamiento de la poda alfa-beta.
Espera del Reposo
Cuando la condición de corte del algoritmo MINIMAX está basada sólo en una profundidad fija, puede darse el llamado efecto horizonte. Este efecto ocurre cuando se evalúa como buena o mala una posición sin saber que en la siguiente jugada la situación se revierte.
La espera del reposo busca evitar el efecto horizonte.
Una condición adicional de corte de recursión en el algoritmo MiniMax debería ser el alcanzar una situación estable. Si se evalúa un nodo del árbol de juego y este valor cambia drásticamente al evaluar el nodo después de realizar la exploración de un nivel más, la búsqueda debería continuar hasta que ésto dejara de ocurrir.
A esta actuación se la conoce como esperar el reposo y nos asegura que las medidas a corto plazo no influyan indebidamente en la elección, problema siempre presente por no explorar exhaustivamente las jugadas.
Un ejemplo donde podría presentarse el efecto horizonte es en un intercambio de piezas, donde a cada turno el jugador logra intercambiar y así pues la evaluación cambia drásticamente de un lado hacia otro.
Búsqueda Secundaria
Otra forma de mejorar el procedimiento MiniMax es realizar una comprobación del movimiento elegido, asegurándonos que no haya ninguna trampa algunos movimientos más allá de los que exploró la búsqueda inicial.
La idea es muy sencilla. Una vez el procedimiento normal de MiniMax haya elegido un movimiento concreto explorando “n” niveles, la técnica de búsqueda secundaria consistirá en realizar una búsqueda adicional de “d” niveles en la única rama escogida para asegurar que la elección sea buena. Así si encuentra que más adelante todas las posibilidades empeoran, se podrá optar por elegir otra rama antes de caer directo en alguna trampa.
El algoritmo se vuelve más costoso, pero por otra parte la decisión es más robusta.
Búsqueda Sesgada
Otra forma más de podar un árbol de juegos es hacer que el factor de ramificación varíe a fin de dirigir más esfuerzo hacia las jugadas más prometedoras.
Se puede realizar una búsqueda sesgada clasificando cada nodo hijo, quizás mediante un evaluador estático rápido. Es decir, que según los resultados que prometa un movimiento, se buscarán más o menos siguientes situaciones más allá de éste.
Así evitaremos perder tiempo recorriendo situaciones que a priori no destaquen por sus resultados.
MiniMax Dependiente del Adversario
Según realiza la exploración del árbol de juego, el algoritmo MiniMax supone que el oponente siempre elige el camino óptimo.
Si se está frente a un adversario muy inteligente, éste podría llegar a explorar más capas que las exploradas por el algoritmo, y por lo tanto tomar otra decisión que la supuesta, pues el camino que tu no crees óptimo realmente a la larga lo sea para él.
Además, el adversario también podría equivocarse y no elegir el camino óptimo. La consecuencia es que MiniMax elegirá el movimiento basándose en la errada suposición del movimiento óptimo del adversario.
Ante una situación de derrota, según sugiere Berliner (1977), podría ser mejor asumir el riesgo de que el oponente puede cometer un error. Ilustremos la idea con un ejemplo.
En el ejemplo superior, se debe elegir entre dos movimientos B y C que conducen a la derrota siempre que el oponente elija el movimiento óptimo, pues tu eres A.
Según MiniMax, se debería elegir el movimiento menos malo de los dos, es decir, el C, con una valor de derrota -4. Suponga que el movimiento menos prometedor lleva a una situación muy buena para nosotros si el oponente comete un único error. En el ejemplo, el nodo B resulta el menos prometedor por tener un valor de -5, sin embargo, si el oponente comete un error elegirá F, el cual lleva a una situación muy ventajosa para nosotros.
Un punto y aparte
Sin embargo, en C aunque el oponente cometa un error, acabaremos perdiendo. Dado que frente a un oponente que nunca falle no resulta mucho mejor una derrota que otra, se puede asumir el riesgo de que el oponente cometa un error ya que esto conduciría a una situación muy ventajosa. Así pues se elegiría el nodo B en lugar del C dictado por MiniMax básico.
Análogamente, si debe elegirse entre dos movimientos buenos, uno ligeramente mejor que el otro, podría resultar mejor elegir el menos mejor si al asumir el riesgo de que el oponente se equivoque nos conduce a situaciones más ventajosas.
Para tomar esta clase de decisiones correctamente, el algoritmo debería modelar el estilo de juego particular de cada oponente. Ésto permitiría estimar la probabilidad de que cometa distintos errores.
Sin lugar a dudas, esta ampliación es muy difícil de lograr y se necesita contar con técnicas de aprendizaje para que el algoritmo obtenga conocimiento sobre su oponente a lo largo del juego.
Técnica de Bajada Progresiva
Algunas veces la restricción que se nos impone durante el cálculo no es de memoria, sinó de tiempo. Debemos decidir nuestra próximo movimiento en un periodo máximo.
En estos casos, lo mejor sería aprovechar hasta el último segundo computacional disponible, y para ello se diseñó la técnica de bajada progresiva.
Esta técnica consiste en ir recorriendo todos los nodos por niveles hasta que nos llegue la petición de jugada (fin del tiempo), y entonces devolveremos la solución encontrada en el último nivel procesado por completo.
Continuación Heurística
La técnica de Continuación Heurística intenta evitar el peligroso efecto horizonte, provocado por la limitación en profundidad. Es similar a la técnica de “Búsqueda Secundaria”, pero no es el mismo concepto.
En la Continuación Heurística, se realiza previamente una búsqueda en anchura del árbol hasta el nivel de profundidad seleccionado. Una vez realizada la búsqueda, en lugar de elegir el mejor movimiento, aquí será donde añadiremos la modificación: seleccionaremos un conjunto de nodos terminales y los desarrollaremos a mayor profundidad.
Esta selección de terminales a “asegurar” vendrá dada por un conjunto de heurísticas directamente relacionadas con el juego.
Por ejemplo, podría calcularse si en ajedrez en un terminal tienes un rey en peligro o un peón a punto de convertirse en dama, y entonces para estas situaciones críticas buscar a mayor profundidad.
Movimiento Nulo
El Movimiento Nulo, o Null-move forward pruning, fue presentado por Chrilly Donniger en 1993. Esta técnica permite reducir de forma drástica el factor de ramificación con un cierto riesgo de perder información importante.
La idea es dar al oponente una jugada de ventaja, y si tu posición sigue siendo buena, (alfa mayor que beta), se asumirá que el alfa real seguirá siendo mayor que beta, y por tanto podamos esa rama y seguimos examinando otros nodos.
Aun así, esta técnica, a parte del riesgo de perder información, tiene otros dos inconvenientes: inestabilidad en la búsqueda (pues los valores de beta pueden cambiar), y que no se suelen permitir dos movimientos nulos seguidos.
/* el factor de reducción de profundidad */
#define R 2
int search (alpha, beta, depth) { if (depth <= 0)
return evaluate();
/* miramos si es legal y deseado hacer un movimiento nulo */ if (!in_check() && null_ok()) {
make_null_move();
/* movimiento nulo con ventana mínima alrededor de beta */ value = -search(-beta, -beta + 1, depth - R - 1);
if (value >= beta) /* podar en caso de superar beta */
return value;
}
/* continuar con búsqueda NegaScout/PVS */
. . .
}
Y como siempre, pues pueden encontrarse distintas versiones del Movimiento Nulo, como por ejemplo el Verificado (Verified Null-move forward pruning), que sustituye la poda del movimiento nulo por la realización de una búsqueda a poca profundidad.
“Aspiration search”
Esta mejora es simplemente una mejora en la llamada a Alfa-Beta. Normalmente, el nivel superior hará una llamada del tipo:
AlfaBeta(pos, depth, -infinito, +infinito);
Usando búsqueda por aspiración cambiaremos esta llamada por:
AlfaBeta(pos, depth, valor-ventana, valor+ventana) ;
Donde ‘valor’ es una aproximación del resultado esperado, y la ventana es la desviación que creemos podrá tener dicho valor.
Con esta llamada exploraremos menos nodos pues los límites alfa/beta ya se usarán desde buen principio. El peligro es que la búsqueda fallará si el valor no se encuentra dentro de nuestras suposiciones, en cuyo caso habrá que rehacer la búsqueda.
Algoritmo NegaMax
Finalmente presentar el algoritmo NegaMax, que simplemente es una versión más compacta del MiniMax.
En lugar de usar dos subrutinas auxiliares, una para el jugador Max y otra para el Min, simplemente usa la puntuación negada del siguiente aprovechando la siguiente relación matemática:
max(a, b) == -min(-a, -b)
Así pues, ésta sería la pinta aproximada que tendría el algoritmo de NegaMax:
funcion NegaMax( g ) retorna entero
si ( estado_terminal( g ) ) entonces
retorna evalua( g )
fsi
max := -infinito
para cada mov en movs_posibles( g ) hacer valor := -NegaMax( aplicar(mov, g)) si valor > max entonces
max := valor
fpara
fsi
retorna ( max )
ffuncion
Evidentemente a esta versión comprimida del MiniMax también puede aplicársele la poda alfa-beta.
Algoritmo NegaScout
El algoritmo NegaScout, evolución del NegaMax, todavía puede mejorar el rendimiento en juegos de ajedrez en un 10% estimado.
Como Alfa-Beta, NegaScout es un algoritmo de búsqueda direccional para calcular el valor minimax de un nodo en un árbol. La mejora es que NegaScout supera al algoritmo Alfa-Beta en el sentido que el primero jamás examinará un nodo que el segundo podaría, y además podaría otros más.
NegaScout tiene un comportamiento óptimo cuando los movimientos (nodos) están correctamente ordenados. Así producirá más podas que Alfa-Beta al asumir que el primer nodo explorado es el mejor. En otras palabras, el primer nodo a explorar deberá ser el que ofrezca máxima ventaja al jugador actual.
Entonces, dada esta suposición, comprobará si es cierto realizando una búsqueda en los otros nodos con una ventana nula (cuando alfa y beta son iguales), cosa que es más rápida que buscar con una ventana alfa-beta normal y corriente. Si la comprobación falla, significará que el primer nodo no era el de máxima variación (el de mayor ventaja), y la búsqueda proseguirá siendo una alfa-beta típica.
Claramente se aprecia por qué la máxima ventaja en NegaScout aparece si hay definido un buen orden en los movimientos. En cambio, con un orden aleatorio, NegaScout tardará más que Alfa-Beta, pues aunque no explore nodos podados por Alfa-Beta, deberá tratar varias veces los otros.
Su nombre proviene del hecho de aprovechar la relación matemática de negación explicada en el anterior apartado, y del uso de la ventana nula, pues también se la conoce como “scout window”.
Su pseudocódigo es el siguiente:
funcion NegaScout( g , depth, α, β) retorna entero
si ( estado_terminal( g ) ó depth=0) entonces
retorna evalua( g )
fsi
b := β
para cada mov en movs_posibles( g ) hacer
valor := -NegaScout( aplicar(mov, g), depth-1, -b, -α )
si α < valor < β y no-es-primer-nodo-hijo
valor := -NegaScout(aplicar(mov, g), depth-1, -β, -valor)
fsi
α := max(α, valor)
si α ≥ β entonces
retorna (α)
fpara
fsi
b := α+1
retorna (α)
ffuncion
Hoy en día NegaScout todavía está considerado en la práctica el mejor algoritmo de búsqueda por muchos programadores de ajedrez. Y mucha gente también lo conoce como PVS (Principal Variation Search) o como una modificación de éste.
Algoritmo SSS*
Diseñado en 1979 por George Stockman, el algoritmo SSS* introdujo un enfoque radicalmente distinto a la poda Alfa-Beta de búsqueda en árboles MiniMax de profundidad prefijada. Tiene sus similitudes con el algoritmo A*, pues explora caminos tipo best-first.
Este algoritmo es superior al MiniMax Alfa-Beta, pues poda los nodos que alfa-beta podaría, pero además no explora algunos nodos que alfa-beta sí exploraría (así pues delimita todavía más el espacio de búsqueda).
Esta mejora respecto al alfa-beta es debida a que el algoritmo SSS* utilitza subárboles del árbol de juego con los cuales solucionará el problema de la ordenación en los nodos terminales. Sin embargo, la estructura utilizada para manejar los nodos implica un aumento de la complejidad espacial, que es la desventaja de este algoritmo.
Estos subárboles tendrán un valor asignado, que será el límite inferior más alto de sus constituyentes. Este valor siempre será mayor o igual que la mejor solución encontrada dentro de ese subárbol, por lo cuál podremos usarlo para realizar la ordenación.
Además, en esta estructura SSS* utilizará la notación decimal de Dewey para representar los nodos en el árbol, donde el nodo raíz será “Epsilon”, y el resto de nodos serán N.n (hijo n, desde la izquierda, del nodo N):
Otra característica de SSS* es que usa tripletas(N, s, h) para cada estado, donde ‘N’ es la numeración del nodo, ‘s’ es el estado de la solución N, y ‘h’ es el valor del estado [-∞, +∞]. El estado ‘s’ de la solución podrá ser etiquetado como VIVO, que indica que aún pueden generarse más sucesores del nodo, o SOLUCIONADO, que indicará que todos los sucesores ya fueron generados.
Ya introducidos en la notación, centrémonos en el funcionamiento y código del algoritmo.
Podríamos decir que SSS* funciona en dos etapas:
- Generación de un conjunto de ramas, expandiendo el primer hijo si se trata de un nodo MIN y todos los hijos si se trata de un nodo MAX
- Selección de estados según su valor h, generando sucesores de los nodos no solucionados hasta que se solucionen. En el caso de que un nodo esté solucionado se soluciona el padre (si es nodo MIN o el último hermano de un MAX), o se genera el siguiente hermano en el caso de tratarse de un nodo MAX que no sea último hermano.
Para conocer más contenido relacionado sobre la mejora de MiniMax, diríjase a la página de inicio.
