Poda alfa-beta

Search algorithm that seeks to decrease the number of nodes in the minimax algorithm search tree

Para otros usos, consulte Alphabeta (desambiguación) .

Poda alfa-beta

Clase	Algoritmo de búsqueda
Rendimiento en el peor de los casos	${\displaystyle O(b^{d})}$
Rendimiento en el mejor de los casos	${\displaystyle O\left({\sqrt {b^{d}}}\right)}$

Algoritmos de búsqueda de gráficos y árboles
α – β A* B* Retroceso Haz Bellman – Ford Mejor primero Bidireccional Borůvka Rama y encuadernado BFS Museo Británico D* DFS Dijkstra Edmonds Floyd – Warshall Búsqueda de franjas Montañismo IDA * Profundización iterativa Johnson Punto de salto Kruskal BFS lexicográfico LPA * Remilgado SMA *
Listados
Algoritmos de grafos Algoritmos de búsqueda Lista de algoritmos de gráficos
Temas relacionados
Programación dinámica Recorrido del gráfico Cruce de árboles Buscar juegos
v t mi

La poda alfa-beta es un algoritmo de búsqueda que busca disminuir el número de nodos que son evaluados por el algoritmo minimax en su árbol de búsqueda . Es un algoritmo de búsqueda contradictorio que se usa comúnmente para la reproducción automática de juegos de dos jugadores ( Tic-tac-toe , Ajedrez , Go , etc.). Deja de evaluar un movimiento cuando se ha encontrado al menos una posibilidad que prueba que el movimiento es peor que un movimiento examinado previamente. Tales movimientos no necesitan ser evaluados más a fondo. Cuando se aplica a un árbol minimax estándar, devuelve el mismo movimiento que el minimax, pero elimina las ramas que no pueden influir en la decisión final. ^[1]

Historia

Allen Newell y Herbert A. Simon, que utilizaron lo que John McCarthy llama una "aproximación" ^[2] en 1958, escribieron que alfa-beta "parece haber sido reinventado varias veces". ^[3] Arthur Samuel tenía una versión temprana para una simulación de damas. Richards, Timothy Hart, Michael Levin y / o Daniel Edwards también inventaron alfa-beta de forma independiente en los Estados Unidos . ^[4] McCarthy propuso ideas similares durante el taller de Dartmouth en 1956 y se las sugirió a un grupo de sus estudiantes, incluido Alan Kotok en el MIT en 1961. ^[5] Alexander Brudnoconcibió de forma independiente el algoritmo alfa-beta, publicando sus resultados en 1963. ^[6] Donald Knuth y Ronald W. Moore refinaron el algoritmo en 1975. ^{[7] [8]} Judea Pearl demostró su optimalidad en términos del tiempo de ejecución esperado para los árboles con valores foliares asignados al azar en dos artículos. ^{[9] [10]} Michael Saks y Avi Wigderson demostraron en 1986 la optimización de la versión aleatoria de alfa-beta. ^[11]

Idea central

El algoritmo mantiene dos valores, alfa y beta, que representan respectivamente la puntuación mínima que se asegura al jugador maximizador y la puntuación máxima que se asegura al jugador minimizador. Inicialmente, alfa es infinito negativo y beta es infinito positivo, es decir, ambos jugadores comienzan con su peor puntuación posible. Siempre que la puntuación máxima que se asegura al jugador que minimiza (es decir, el jugador "beta") se vuelve menor que la puntuación mínima que se asegura al jugador maximizador (es decir, el jugador "alfa") (es decir, beta <alfa), la El jugador no necesita considerar más descendientes de este nodo, ya que nunca serán alcanzados en el juego real.

Para ilustrar esto con un ejemplo de la vida real, suponga que alguien está jugando al ajedrez y es su turno. Mover "A" mejorará la posición del jugador. El jugador continúa buscando movimientos para asegurarse de que no se haya perdido uno mejor. El movimiento "B" también es un buen movimiento, pero el jugador se da cuenta de que permitirá al oponente forzar el jaque mate en dos movimientos. Por lo tanto, ya no es necesario considerar otros resultados de la jugada B, ya que el oponente puede forzar una victoria. La puntuación máxima que el oponente podría forzar después de la jugada "B" es infinito negativo: una pérdida para el jugador. Esta es menos que la posición mínima que se encontró anteriormente; la jugada "A" no resulta en una pérdida forzada en dos jugadas.

Mejoras sobre minimax ingenuo

Una ilustración de la poda alfa-beta. Los subárboles en gris no necesitan ser explorados (cuando los movimientos se evalúan de izquierda a derecha), ya que se sabe que el grupo de subárboles en su conjunto arroja el valor de un subárbol equivalente o peor, y como tal no puede influir el resultado final. Los niveles máximo y mínimo representan el turno del jugador y el adversario, respectivamente.

El beneficio de la poda alfa-beta radica en el hecho de que se pueden eliminar las ramas del árbol de búsqueda. De esta manera, el tiempo de búsqueda se puede limitar al subárbol "más prometedor" y se puede realizar una búsqueda más profunda al mismo tiempo. Al igual que su predecesor, pertenece a la clase de algoritmos de rama y límite . La optimización reduce la profundidad efectiva a un poco más de la mitad de la del minimax simple si los nodos se evalúan en un orden óptimo o casi óptimo (la mejor opción para el lado en movimiento ordenado primero en cada nodo).

Con un factor de ramificación (promedio o constante) de b , y una profundidad de búsqueda de d capas , el número máximo de posiciones de nodo hoja evaluadas (cuando el orden de movimiento es pesimal ) es O ( b × b × ... × b ) = O ( b ^d ): lo mismo que una búsqueda minimax simple. Si el orden de movimiento para la búsqueda es óptimo (lo que significa que los mejores movimientos siempre se buscan primero), el número de posiciones de nodo hoja evaluadas es aproximadamente O ( b × 1 × b × 1 × ... × b ) para profundidad impar y O (b × 1 × b × 1 × ... × 1) para una profundidad uniforme, o . En el último caso, donde la capa de una búsqueda es uniforme, el factor de ramificación efectivo se reduce a su raíz cuadrada o, de manera equivalente, la búsqueda puede llegar al doble de profundidad con la misma cantidad de cálculo. ^[12] La explicación de b × 1 × b${\displaystyle O(b^{d/2})=O({\sqrt {b^{d}}})}$× 1 × ... es que todos los movimientos del primer jugador deben estudiarse para encontrar el mejor, pero para cada uno, solo se necesita el mejor movimiento del segundo jugador para refutar todos menos el primer (y mejor) movimiento del primer jugador — alfa– beta asegura que no es necesario considerar otros movimientos de segundo jugador. Cuando los nodos se consideran en un orden aleatorio (es decir, el algoritmo aleatoriza), asintóticamente, el número esperado de nodos evaluados en árboles uniformes con valores de hoja binarios es . ^[11] Para los mismos árboles, cuando los valores se asignan a los valores de las hojas de forma independiente entre sí y dicen que cero y uno son igualmente probables, el número esperado de nodos evaluados es , que es mucho menor que el trabajo realizado por los aleatorizados. algoritmo, mencionado anteriormente, y nuevamente es óptimo para tales árboles aleatorios. ^[9]${\displaystyle \Theta (((b-1+{\sqrt {b^{2}+14b+1}})/4)^{d})}$${\displaystyle \Theta ((b/2)^{d})}$Cuando los valores de las hojas se eligen independientemente entre sí pero a partir del intervalo uniformemente al azar, el número esperado de nodos evaluados aumenta hasta el límite, ^[10] que es nuevamente óptimo para este tipo de árboles aleatorios. Tenga en cuenta que es mejor aproximar el trabajo real para valores "pequeños" de . ^{[10] [9]}${\displaystyle [0,1]}$${\displaystyle \Theta (b^{d/log(d)})}$${\displaystyle d\to \infty }$${\displaystyle d}$${\displaystyle 0.925d^{0.747}}$

Un ejemplo pedagógico animado que intenta ser amigable con los humanos sustituyendo valores iniciales infinitos (o arbitrariamente grandes) por vacío y evitando el uso de simplificaciones de codificación negamax .

Normalmente durante alfa-beta, los subárboles están dominados temporalmente por la ventaja del primer jugador (cuando muchos movimientos del primer jugador son buenos, y en cada profundidad de búsqueda, el primer movimiento verificado por el primer jugador es adecuado, pero todas las respuestas del segundo jugador son necesarias para tratar de encontrar una refutación), o viceversa. Esta ventaja puede cambiar de lado muchas veces durante la búsqueda si el orden de los movimientos es incorrecto, lo que conduce cada vez a la ineficiencia. Dado que el número de posiciones buscadas disminuye exponencialmente con cada movimiento que se acerca a la posición actual, vale la pena dedicar un esfuerzo considerable a clasificar los primeros movimientos. Una clasificación mejorada a cualquier profundidad reducirá exponencialmente el número total de posiciones buscadas, pero clasificar todas las posiciones en profundidades cercanas al nodo raíz es relativamente económico, ya que hay muy pocas. En la práctica,el orden de los movimientos suele estar determinado por los resultados de búsquedas anteriores más pequeñas, como a través deprofundización iterativa .

Además, este algoritmo se puede modificar trivialmente para devolver una variación principal completa además de la puntuación. Algunos algoritmos más agresivos como MTD (f) no permiten fácilmente tal modificación.

Pseudocódigo

El pseudocódigo para minimax de profundidad limitada con poda alfa-beta es el siguiente: ^[12]

función alphabeta (nodo, profundidad, α, β, maximizingPlayer) es  si la profundidad = 0 o el nodo es un nodo terminal, entonces  devuelve el valor heurístico del nodo si maximizingPlayer entonces valor: = −∞ para cada hijo del nodo hacer valor: = max (valor, alfabeta (hijo, profundidad - 1, α, β, FALSO)) α: = max (α, valor) si α ≥ β entonces  rompa  (* β corte *) valor de retorno de lo contrario valor: = + ∞ para cada hijo del nodo hacer valor: = min (valor, alfabeta (hijo, profundidad - 1, α, β, VERDADERO)) β: = min (β, valor) si β ≤ α entonces  rompe  (* α corte *) valor de retorno

(* Llamada inicial *)
alfabeta (origen, profundidad, - ∞ , + ∞ , VERDADERO)

Las implementaciones de la poda alfa-beta a menudo se pueden delinear si son "suaves" o "difíciles de fallar". El pseudocódigo ilustra la variación de falla suave. Con alfa-beta suave ante fallos, la función alfabeta puede devolver valores (v) que excedan (v <α o v> β) los límites α y β establecidos por sus argumentos de llamada de función. En comparación, alfa-beta resistente a fallos limita el valor de retorno de su función en el rango inclusivo de α y β.

Mejoras heurísticas

Se pueden lograr mejoras adicionales sin sacrificar la precisión mediante el uso de heurísticas de ordenamiento para buscar partes anteriores del árbol que probablemente forzarán cortes alfa-beta. Por ejemplo, en el ajedrez, los movimientos que capturan piezas pueden examinarse antes que los que no lo hacen, y los movimientos que han obtenido una puntuación alta en pases anteriores a través del análisis del árbol del juego pueden evaluarse antes que otros. Otra heurística común y muy barata es la heurística asesina , donde siempre se examina primero el último movimiento que provocó un corte beta en el mismo nivel de árbol en la búsqueda de árbol. Esta idea también se puede generalizar en un conjunto de tablas de refutación .

La búsqueda alfa-beta se puede hacer aún más rápido considerando solo una ventana de búsqueda estrecha (generalmente determinada por conjeturas basadas en la experiencia). Esto se conoce como búsqueda por aspiración . En el caso extremo, la búsqueda se realiza con alfa y beta iguales; una técnica conocida como la búsqueda de cero ventana , búsqueda null-ventana , o de búsqueda del explorador . Esto es particularmente útil para búsquedas de ganar / perder cerca del final de un juego donde la profundidad adicional obtenida de la ventana estrecha y una función simple de evaluación de ganar / perder puede llevar a un resultado concluyente. Si una búsqueda de aspiración falla, es sencillo detectar si falló alto (el borde alto de la ventana era demasiado bajo) o bajo(el borde inferior de la ventana era demasiado alto). Esto proporciona información sobre qué valores de ventana podrían ser útiles en una investigación de la posición.

Con el tiempo, se han sugerido otras mejoras y, de hecho, la idea de Falphabeta (alfa-beta suave en caso de fallas) de John Fishburn es casi universal y ya se incorporó anteriormente en una forma ligeramente modificada. Fishburn también sugirió una combinación de la heurística asesina y la búsqueda de ventana cero bajo el nombre Lalphabeta ("último movimiento con búsqueda alfa-beta de ventana mínima").

Otros algoritmos

Dado que el algoritmo minimax y sus variantes son intrínsecamente en profundidad , se suele utilizar una estrategia como la profundización iterativa junto con alfa-beta para que se pueda devolver un movimiento razonablemente bueno incluso si el algoritmo se interrumpe antes de que finalice la ejecución. Otra ventaja de utilizar la profundización iterativa es que las búsquedas en profundidades menores dan pistas de orden de movimiento, así como estimaciones alfa y beta poco profundas, que pueden ayudar a producir puntos de corte para búsquedas de mayor profundidad mucho antes de lo que sería posible de otra manera.

Los algoritmos como SSS * , por otro lado, utilizan la mejor estrategia. Potencialmente, esto puede hacerlos más eficientes en el tiempo, pero generalmente a un alto costo en eficiencia espacial. ^[13]

Ver también

• Minimax
• Expectiminimax
• Negamax
• Poda (algoritmo)
• Ramificar y enlazar
• Optimización combinatoria
• Búsqueda de variación principal
• Tabla de transposición

Referencias

1. Russell, Stuart J .; Norvig, Peter (2010). Inteligencia artificial: un enfoque moderno (3ª ed.). Upper Saddle River, Nueva Jersey: Pearson Education, Inc. p. 167. ISBN 978-0-13-604259-4.
2. McCarthy, John (27 de noviembre de 2006). "La IA de nivel humano es más difícil de lo que parecía en 1955" . Consultado el 20 de diciembre de 2006 .
3. Newell, Allen; Simon, Herbert A. (1 de marzo de 1976). "La informática como investigación empírica: símbolos y búsqueda" . Comunicaciones de la ACM . 19 (3): 113–126. doi : 10.1145 / 360018.360022 .
4. Edwards, DJ; Hart, TP (4 de diciembre de 1961). "La heurística alfa-beta (AIM-030)". Instituto de Tecnología de Massachusetts . hdl : 1721,1 / 6098 .
5. Kotok, Alan (3 de diciembre de 2004). "Memo 41 de inteligencia artificial del MIT" . Consultado el 1 de julio de 2006 .
6. Marsland, TA (mayo de 1987). "Métodos de ajedrez informático (PDF) de la Enciclopedia de Inteligencia Artificial. S. Shapiro (editor)" (PDF) . J. Wiley & Sons. págs. 159-171. Archivado desde el original (PDF) el 30 de octubre de 2008 . Consultado el 21 de diciembre de 2006 .
7. Knuth, Donald E .; Moore, Ronald W. (1975). "Un análisis de la poda alfa-beta". Inteligencia artificial . 6 (4): 293–326. doi : 10.1016 / 0004-3702 (75) 90019-3 . S2CID 7894372 . 
8. Abramson, Bruce (1 de junio de 1989). "Estrategias de control para juegos de dos jugadores". Encuestas de computación ACM . 21 (2): 137-161. doi : 10.1145 / 66443.66444 . S2CID 11526154 . 
9. Pearl, Judea (1980). "Propiedades asintóticas de árboles Minimax y procedimientos de búsqueda de juegos". Inteligencia artificial . 14 (2): 113–138. doi : 10.1016 / 0004-3702 (80) 90037-5 .
10. Pearl, Judea (1982). "La solución para el factor de ramificación del algoritmo de poda alfa-beta y su optimización". Comunicaciones de la ACM . 25 (8): 559–64. doi : 10.1145 / 358589.358616 . S2CID 8296219 . 
11. Saks, M .; Wigderson, A. (1986). "Árboles de decisión booleanos probabilísticos y la complejidad de evaluar árboles de juego". 27º Simposio Anual sobre Fundamentos de la Informática . págs. 29–38. doi : 10.1109 / SFCS.1986.44 . ISBN 0-8186-0740-8. S2CID  6130392 .
12. Russell, Stuart J .; Norvig, Peter (2003), Inteligencia artificial: un enfoque moderno (2a ed.), Upper Saddle River, Nueva Jersey: Prentice Hall, ISBN 0-13-790395-2
13. Perla, Judea ; Korf, Richard (1987), "Técnicas de búsqueda", Annual Review of Computer Science , 2 : 451–467, doi : 10.1146 / annurev.cs.02.060187.002315 , Al igual que su contraparte A * para juegos de un solo jugador, SSS * es óptimo en términos del número medio de nodos examinados; pero su poder de poda superior está más que compensado por el considerable espacio de almacenamiento y la contabilidad necesarios.

Bibliografía

• George T. Heineman; Gary Pollice; Stanley Selkow (2008). "Capítulo 7: búsqueda de caminos en la IA". Algoritmos en pocas palabras . Oreilly Media . págs. 217-223. ISBN 978-0-596-51624-6.
• Judea Pearl , Heurística , Addison-Wesley, 1984
• John P. Fishburn (1984). "Apéndice A: algunas optimizaciones de búsqueda α-β". Análisis de aceleración en algoritmos distribuidos (revisión de la tesis doctoral de 1981) . Prensa de investigación UMI. págs. 107-111. ISBN 0-8357-1527-2.