Búsqueda alfa-beta
La búsqueda alfa-beta (también llamado corte alfa-beta o poda alfa-beta ) es una variante optimizada del proceso de búsqueda minimax , es decir, un algoritmo para determinar un movimiento óptimo en los juegos con dos partes opuestas. Durante la búsqueda, se actualizan dos valores, Alfa y Beta , para indicar qué resultado pueden lograr los jugadores con un juego óptimo. Con la ayuda de estos valores, se puede decidir qué partes del árbol de búsqueda no deben examinarse porque no pueden influir en el resultado de la solución del problema .
La búsqueda alfa-beta simple (no optimizada) ofrece exactamente el mismo resultado que la búsqueda minimax.
Descripción informal
El algoritmo Minimax analiza el árbol de búsqueda completo. Al hacerlo, también se consideran los nodos que no están incluidos en el resultado (la elección de la rama en la raíz). La búsqueda alfa-beta ignora todos los nodos de los cuales, en el momento en que la búsqueda los alcanza, ya es seguro que no pueden influir en el resultado.
Un claro ejemplo de cómo funciona es un juego de dos personas en el que el primer jugador selecciona una de varias bolsas y recibe de su oponente el artículo con el valor más bajo de esta bolsa.
El algoritmo Minimax busca por completo la selección en todos los bolsillos y, por lo tanto, lleva mucho tiempo. La búsqueda alfa-beta, por otro lado, inicialmente solo busca en la primera bolsa por completo el artículo con un valor mínimo. Todos los demás bolsillos solo se registran hasta que el valor de un objeto alcanza o cae por debajo de este mínimo. Entonces es seguro que esta bolsa no es mejor que la primera para el primer jugador, y la búsqueda en ella puede detenerse. De lo contrario, esta bolsa será una mejor opción y su valor mínimo servirá como una nueva frontera para seguir buscando.
Situaciones similares le resultan familiares a todo jugador de ajedrez que esté comprobando un movimiento específico para ver si le parece ventajoso. Si, durante su análisis del movimiento, encuentra una respuesta del oponente que es desfavorable para él, entonces considerará este movimiento como "refutado" y lo rechazará. No tendría sentido investigar más respuestas del oponente para determinar si el oponente tiene refutaciones más efectivas y qué tan mala es la jugada que se está considerando.
El algoritmo
La búsqueda alfa-beta funciona de la misma manera que la descripción informal anterior. La idea es que se pasen dos valores (alfa y beta) que describan el peor de los casos para los jugadores. El valor alfa es el resultado mínimo que logrará el jugador A, el valor beta es el resultado máximo que logrará el jugador B. (Cabe señalar aquí que para el jugador B se trata de obtener el resultado más bajo posible, ¡ya que está jugando "minimizando"!)
Si un nodo maximizador (del jugador A) tiene un movimiento cuyo retorno excede el valor beta, se aborta la búsqueda en este nodo ( corte beta , porque el jugador B ni siquiera ofrecería esta opción a A porque tendría su máximo anterior La concesión excedería). Si, en cambio, el tren entrega un resultado que excede el valor alfa actual, este se aumenta en consecuencia.
Lo mismo se aplica a los nodos de minimización, con los valores inferiores a alfa cancelados (corte alfa) y el valor beta ajustado a la baja.
La figura anterior muestra un árbol de ejemplo con 18 hojas, de las cuales solo se evalúan 12. Los tres valores bordeados de un nodo interno describen el valor alfa, el valor de retorno y el valor beta.
El algoritmo de búsqueda utiliza una ventana denominada alfa-beta, cuyo límite inferior es el valor alfa y el límite superior es el valor beta. Esta ventana se pasa a los nodos secundarios, comenzando en la raíz con la ventana máxima [-inf, inf]. Las hojas 1, 2 y 3 son evaluadas por un nodo maximizador y el mejor valor 10 se pasa al nodo padre minimizador . Esto ajusta el valor beta y transfiere la nueva ventana [-inf, 10] al siguiente nodo hijo maximizador , que tiene hojas 4, 5 y 6. El valor de retorno 12 de la hoja 5 es tan bueno que supera el valor beta 10. Por tanto, la hoja 6 ya no necesita ser considerada porque el resultado 12 de este subárbol es mejor que el del subárbol izquierdo y, por lo tanto, nunca sería seleccionado por el jugador minimizador.
Lo mismo se aplica al nodo minimizador con el límite de 3 alfa. Aunque este subárbol sólo se evaluó parcialmente, está claro que el nodo raíz maximizador nunca elegiría esta variante, porque el nodo minimizador podría forzar un resultado de como máximo 3, mientras que el resultado 12 está asegurado desde el subárbol medio.
implementación
Nota: Las diferencias con el algoritmo Minimax simple están resaltadas en amarillo.
Programa principal (extracto):
gespeicherterZug = NULL;
int gewuenschteTiefe = 4;
int bewertung = max(gewuenschteTiefe,
-unendlich, +unendlich);
if (gespeicherterZug == NULL)
es gab keine weiteren Zuege mehr (Matt oder Patt);
else
gespeicherterZug ausführen;
La variante normal es:
int max(int tiefe,
int alpha, int beta) {
if (tiefe == 0 or keineZuegeMehr(spieler_max))
return bewerten();
int maxWert = alpha;
Zugliste = generiereMoeglicheZuege(spieler_max);
for each (Zug in Zugliste) {
fuehreZugAus(Zug);
int wert = min(tiefe-1,
maxWert, beta);
macheZugRueckgaengig(Zug);
if (wert > maxWert) {
maxWert = wert;
if (tiefe == gewuenschteTiefe)
gespeicherterZug = Zug;
if (maxWert >= beta)
break;
}
}
return maxWert;
}
int min(int tiefe,
int alpha, int beta) {
if (tiefe == 0 or keineZuegeMehr(spieler_min))
return bewerten();
int minWert = beta;
Zugliste = generiereMoeglicheZuege(spieler_min);
for each (Zug in Zugliste) {
fuehreZugAus(Zug);
int wert = max(tiefe-1,
alpha, minWert);
macheZugRueckgaengig(Zug);
if (wert < minWert) {
minWert = wert;
if (minWert <= alpha)
break;
}
}
return minWert;
}
La variante NegaMax es:
int miniMax(int spieler, int tiefe,
int alpha, int beta) {
if (tiefe == 0 or keineZuegeMehr(spieler))
return bewerten(spieler);
int maxWert = alpha;
Zugliste = generiereMoeglicheZuege(spieler);
for each (Zug in Zugliste) {
fuehreZugAus(Zug);
int wert = -miniMax(-spieler, tiefe-1,
-beta, -maxWert);
macheZugRueckgaengig(Zug);
if (wert > maxWert) {
maxWert = wert;
if (tiefe == gewuenschteTiefe)
gespeicherterZug = Zug;
if (maxWert >= beta)
break;
}
}
return maxWert;
}
Nota: Mientras que la implementación estándar maximiza para un jugador y la minimiza para el otro jugador, la variante Negamax maximiza para ambos jugadores e intercambia y niega alfa y beta durante la recursividad. De ello se deduce que la función de evaluación debe comportarse de manera diferente en ambas implementaciones.
- Implementación estándar: cuanto mejor sea la posición en el tablero para el jugador maximizador, mayor será el valor de retorno de la función de evaluación (función de evaluación ()). Cuanto mejor sea para el jugador que minimiza, menor será el valor de retorno.
- Implementación Negamax: Dado que ambos jugadores maximizan, la función de evaluación debe entregar valores más altos cuanto mejor sea la posición en el tablero de la persona que dibuja actualmente (función de evaluación (jugador)). El valor siempre se da desde su punto de vista.
Optimizaciones
Si el árbol del juego solo se puede calcular hasta una cierta profundidad debido a la complejidad del juego en cuestión, básicamente son posibles dos enfoques de optimización. Por un lado, se puede mejorar la función de evaluación y, por otro lado, el algoritmo alfa-beta en sí mismo ofrece potencial de optimización. Cuanto mejor sea la función de evaluación, menos profundamente se debe ver el árbol del juego para lograr un cierto nivel de juego.
A continuación, solo se analizan las optimizaciones de la búsqueda alfa-beta.
Preclasificación de trenes
A diferencia del algoritmo Minimax, el orden en el que se procesan los nodos secundarios (trenes) juega un papel importante en la búsqueda alfa-beta. Cuanto más rápido se reduce la ventana alfa-beta, más cortes se logran. Por eso es importante mirar primero los movimientos que dan el mejor resultado. En la práctica se utilizan varias heurísticas . En ajedrez z. B. puede ordenar los movimientos según si captura o qué pieza, o qué pieza captura. "La torre le gana a la dama" se ordena antes de que "la torre le gana a la torre" y "el granjero le gana a la torre" se clasifique entre los dos.
Búsqueda de variación principal
Un nodo en la búsqueda alfa-beta pertenece a una de las tres categorías (según la variante NegaMax):
- Nodo alfa: cada movimiento posterior devuelve un valor menor o igual que alfa, lo que significa que aquí no es posible un buen movimiento.
- Nodo beta: al menos un movimiento posterior entrega un valor mayor o igual que beta, lo que significa un corte.
- Nodo de variación principal: al menos un tren posterior ofrece un valor mayor que alfa, pero todos entregan un valor menor que beta.
A veces puede saber desde el principio qué nodo es. Si el primer tren posterior probado entrega un valor mayor o igual que beta, entonces es un nodo beta. Si entrega un valor menor o igual que alfa, entonces posiblemente sea un nodo alfa (siempre que los trenes estén bien clasificados previamente). Sin embargo, si entrega un valor entre alfa y beta, puede ser un nodo de variación principal .
La búsqueda de la variación principal ahora asume que un movimiento posterior que ofrece un valor entre alfa y beta resultará ser el mejor movimiento posible. Por lo tanto, la ventana alfa-beta por debajo del mínimo se reduce (alfa, alfa + 1) (ventana cero) para alcanzar un número máximo de cortes, pero para demostrar que los trenes restantes son peores.
Si, al buscar con esta ventana cero, resulta que el tren tiene un valor mayor que alfa (pero el resultado sigue siendo menor que beta , de lo contrario, puede hacer un corte beta de inmediato ), la búsqueda debe repetirse con una ventana más grande: Allí Si ya conoce un límite inferior para el valor de tensión de la búsqueda de ventana cero, la ventana debería extenderse desde este valor a beta durante la búsqueda repetida . Debido a la búsqueda de repetición a veces necesaria, este método solo se puede utilizar para lograr el éxito si los trenes se han preclasificado bien, porque esto minimiza las asignaciones incorrectas en una de las tres categorías mencionadas. Es decir, es poco probable que un movimiento posterior tenga un valor mejor que alfa y que la búsqueda deba repetirse. Por otro lado, los nodos de variación principales también se pueden utilizar junto con la profundización iterativa para clasificar previamente los trenes.
int AlphaBeta(int tiefe, int alpha, int beta)
{
if (tiefe == 0)
return Bewerten();
BOOL PVgefunden = FALSE;
best = -unendlich;
Zugliste = GeneriereMoeglicheZuege();
for each (Zug in Zugliste)
{
FuehreZugAus(Zug);
if (PVgefunden)
{
wert = -AlphaBeta(tiefe-1, -alpha-1, -alpha);
if (wert > alpha && wert < beta)
wert = -AlphaBeta(tiefe-1, -beta, -wert);
} else
wert = -AlphaBeta(tiefe-1, -beta, -alpha);
MacheZugRueckgaengig(Zug);
if (wert > best)
{
if (wert >= beta)
return wert;
best = wert;
if (wert > alpha)
{
alpha = wert;
PVgefunden = TRUE;
}
}
}
return best;
}
Búsqueda de profundización iterativa (profundización iterativa)
La búsqueda iterativa en profundidad es el aumento paso a paso en la profundidad del árbol de búsqueda. Dado que la búsqueda alfa-beta es una búsqueda en profundidad , por lo general no es posible determinar de antemano cuánto tiempo llevará el cálculo. Por lo tanto, comienza con una profundidad de búsqueda reducida y la aumenta gradualmente. El resultado de un cálculo se puede utilizar para clasificar mejor los trenes si se aumenta la profundidad de búsqueda.
Ventanas de aspiración
Las ventanas de aspiración se utilizan junto con la primera búsqueda en profundidad iterativa . Básicamente, la búsqueda alfa-beta comienza en la raíz con una ventana máxima. Con la primera búsqueda de profundidad iterativa, se puede suponer que un nuevo cálculo con una profundidad mayor proporcionará un valor de resultado similar. Por lo tanto, la ventana de búsqueda se puede establecer inicialmente en un área (relativamente) pequeña alrededor del valor de resultado del cálculo anterior. Si resulta que esta ventana era demasiado pequeña, la búsqueda debe repetirse con una ventana más grande o máxima (similar a la búsqueda de variación principal ).
Asesino heurístico
La heurística asesina es un tipo especial de preclasificación de trenes. Se asume aquí que los movimientos que han causado un corte también causarán un corte en otras partes del árbol de búsqueda (a la misma profundidad). Por lo tanto, en el futuro siempre se considerarán en primer lugar, siempre que representen movimientos válidos en la posición de juego que se acaba de considerar. Esta heurística no puede usarse con sensatez en todos los juegos, ya que la perspectiva de que estos llamados movimientos asesinos sigan siendo movimientos válidos en otras partes del árbol de búsqueda depende del tipo de juego.
Búsqueda silenciosa
Con la búsqueda alfa-beta o el algoritmo Minimax, no es muy beneficioso si la búsqueda finaliza cuando se alcanza una profundidad de búsqueda fija . De esta manera, en el ajedrez, por ejemplo, capturar un peón cubierto por la dama podría parecer ventajoso si el retroceso está por debajo del horizonte de búsqueda y, por lo tanto, el algoritmo lo “pasa por alto”. Por este motivo, el paso de la búsqueda alfa-beta a la función de evaluación se realiza de forma dinámica, en concreto de tal manera que se espera una constancia aproximada por debajo de la profundidad de búsqueda mínima con respecto a la función de evaluación. Esta "paz" es en términos de los valores de la función de evaluación del mismo nombre para el procedimiento que se denomina una búsqueda resto ( Inglés quiescencia de búsqueda ). En el ajedrez, la búsqueda de la paz lleva a que se analice hasta el final un intercambio de golpes.
Búsqueda de movimiento cero
La búsqueda de movimiento cero es una optimización que aprovecha el hecho de que en algunos juegos (por ejemplo, ajedrez) el movimiento a la derecha es una ventaja.
Comparación de Minimax y AlphaBeta
La siguiente tabla muestra un ejemplo de cálculo de una posición de ajedrez con una profundidad de búsqueda constante de cuatro medios movimientos (cada jugador se mueve dos veces). Se utilizó el algoritmo normal Minimax y alfa-beta sin clasificación de trenes y con clasificación de trenes (simple). La información porcentual en los puntos de corte se relaciona con todo el árbol de búsqueda y describe qué parte de todo el árbol de búsqueda no se evaluó. Estas son estimaciones basadas en el hecho de que los subárboles son aproximadamente del mismo tamaño (con cortes, no se sabe qué tan grande sería realmente el subárbol).
| algoritmo | críticas | Tejanos cortados | Proporción de cortes | Calculando el tiempo en segundos |
|---|---|---|---|---|
| Minimax | 28,018,531 | 0 | 0,00% | 134,87 segundos |
| Alfa Beta | 2.005.246 | 136,478 | 91,50% | 9,88 segundos |
| Clasificación de trenes AlphaBeta + | 128.307 | 27,025 | 99,28% | 0,99 s |
Se puede ver claramente que la búsqueda alfa-beta significa un aumento considerable de velocidad en comparación con el Minimax. La clasificación de trenes también mejora el tiempo de cálculo en este ejemplo en un factor de 10. El hecho de que el número de cortes disminuya absolutamente con la clasificación de trenes se puede explicar por el hecho de que ocurren en niveles más altos en el árbol de búsqueda y, por lo tanto, se cortan partes más grandes.
historia
Si bien la importancia central del algoritmo Minimax para la programación de ajedrez ya fue enfatizada por sus pioneros Alan Turing y Claude Shannon en la década de 1940, la búsqueda alfa-beta comenzó a fines de la década de 1950, con solo cortes alfa al principio. fueron usados. No fue hasta la década de 1960 que el algoritmo alfa-beta se convirtió en una parte integral de los programas de ajedrez. Una primera descripción, aunque no publicada, proviene de 1963. El primer estudio detallado apareció en 1975.
literatura
- Jörg Bewersdorff : suerte, lógica y farol. Matemáticas en el juego: métodos, resultados y límites. 5ª edición. Vieweg + Teubner, Wiesbaden 2010, ISBN 978-3-8348-0775-5 , doi: 10.1007 / 978-3-8348-9696-4 , págs. 177-197 (Capítulo 2.10).
- Alexander Reinefeld: Desarrollo del método de búsqueda del árbol de juego: del cerebro ajedrecístico de Zuse al ordenador de ajedrez moderno. En: Wolfgang Reisig y Johann-Christoph Freytag (Hrsg.): Informatik. Temas de actualidad en un contexto histórico. Springer, Berlín / Heidelberg / Nueva York 2006, ISBN 978-3-540-32742-4 , doi: 10.1007 / 3-540-32743-6_11 , págs. 241-276.
- Wolfgang Ertel: Curso básico de inteligencia artificial : una introducción orientada a la práctica, inteligencia computacional . 4ª edición. Springer Vieweg, Wiesbaden 2016, ISBN 978-3658135485 , doi: 10.1007 / 978-3-658-13549-2 , págs. 125–127.
enlaces web
- Burkhard Monien, Ulf Lorenz y Daniel Warner: el algoritmo alfabético para búsquedas de árbol de juegos . 2006.
- Visualización de la búsqueda alfa-beta como un applet de Java para cualquier árbol de juego
Notas al pie
- ↑ Jörg Bewersdorff: Suerte, lógica y engaño. Matemáticas en el juego: métodos, resultados y límites. 5ª edición. 2010, pág.184.
- ^ Allen Newell , JC Shaw y HA Simon : programas de ajedrez y el problema de la complejidad. En: IBM Journal of Research and Development. Volumen 2, Número 4, 1958, doi: 10.1147 / rd.24.0320 , págs. 330-335 ( PDF; 2.172 MB ).
- ↑ DJ Edwards y TP Hart: La heurística alfa-beta (= AI Memos. 030). Instituto de Tecnología de Massachusetts, 1963 ( PDF; 288 kB ).
- ^ Donald E. Knuth y Ronald W. Moore: un análisis de la poda alfa-beta. En: Inteligencia artificial. Volumen 6, Número 4, 1975, doi: 10.1016 / 0004-3702 (75) 90019-3 , págs. 293-326
