La poda alfa-beta es un algoritmo de búsqueda que busca disminuir la cantidad de nodos evaluados por el algoritmo minimax en su árbol de búsqueda . Es un algoritmo de búsqueda adversario que se utiliza comúnmente para juegos combinatorios de dos jugadores ( Tic-tac-toe , Ajedrez , Connect 4 , etc.). Deja de evaluar un movimiento cuando se ha encontrado al menos una posibilidad que demuestra que el movimiento es peor que un movimiento previamente examinado. No es necesario seguir evaluando tales medidas. Cuando se aplica a un árbol minimax estándar, devuelve el mismo movimiento que haría minimax, pero elimina ramas que no pueden influir en la decisión final. [1]
John McCarthy durante el Taller de Dartmouth conoció a Alex Bernstein de IBM , quien estaba escribiendo un programa de ajedrez. McCarthy inventó la búsqueda alfa-beta y se la recomendó, pero Bernstein "no estaba convencido". [2]
Allen Newell y Herbert A. Simon , que utilizaron lo que John McCarthy llama una "aproximación" [3] en 1958, escribieron que alfa-beta "parece haber sido reinventado varias veces". [4] 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 el alfa-beta de forma independiente en los Estados Unidos . [5] 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. [6] Alexander Brudno concibió de forma independiente el algoritmo alfa-beta y publicó sus resultados en 1963. [ 7] Donald Knuth y Ronald W. Moore perfeccionaron el algoritmo en 1975. [8] [9] Judea Pearl demostró en dos artículos su optimización en términos del tiempo de ejecución esperado para árboles con valores de hojas asignados aleatoriamente. [10] [11] Michael Saks y Avi Wigderson demostraron la optimización de la versión aleatoria de alfa-beta en 1986. [12]
Un árbol de juegos puede representar muchos juegos de suma cero para dos jugadores , como ajedrez, damas y reversi. Cada nodo del árbol representa una posible situación en el juego. A cada nodo terminal (resultado) de una rama se le asigna una puntuación numérica que determina el valor del resultado para el jugador con el siguiente movimiento. [13]
El algoritmo mantiene dos valores, alfa y beta, que representan respectivamente la puntuación mínima que tiene asegurado el jugador que maximiza y la puntuación máxima que tiene asegurado el jugador que minimiza. Inicialmente, alfa es infinito negativo y beta es infinito positivo, es decir, ambos jugadores comienzan con la peor puntuación posible. Siempre que la puntuación máxima que tiene asegurado el jugador que minimiza (es decir, el jugador "beta") sea menor que la puntuación mínima que tiene asegurado el jugador que maximiza (es decir, el jugador "alfa") (es decir, beta < alfa), el jugador que maximiza 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, supongamos que alguien está jugando al ajedrez y es su turno. El movimiento "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 luego 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 del movimiento "B" es infinito negativo: una pérdida para el jugador. Esto es menor que la posición mínima que se encontró anteriormente; El movimiento "A" no resulta en una pérdida forzada en dos movimientos.
El beneficio de la poda alfa-beta radica en el hecho de que se pueden eliminar ramas del árbol de búsqueda. [13] 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 enlace . La optimización reduce la profundidad efectiva a un poco más de la mitad que la del minimax simple si los nodos se evalúan en un orden óptimo o casi óptimo (la mejor opción para el movimiento lateral ordenado primero en cada nodo).
Con un factor de ramificación (promedio o constante) de b y una profundidad de búsqueda de d plies , el número máximo de posiciones de nodos de hoja evaluadas (cuando el orden de movimiento es pesimal) es O ( b d ), lo mismo que una búsqueda minimax simple. . Si el orden de los movimientos para la búsqueda es óptimo (lo que significa que los mejores movimientos siempre se buscan primero), el número de posiciones de los nodos de 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, cuando la capa de una búsqueda es par, 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. [14] La explicación de b ×1× b ×1×... es que todos los movimientos del primer jugador deben estudiarse para encontrar el mejor, pero para cada uno, sólo se necesita el mejor movimiento del segundo jugador para refutar todos menos el Primer (y mejor) movimiento del primer jugador: alfa-beta garantiza que no sea necesario considerar otros movimientos del 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 hojas binarios es . [12] 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 ambos igualmente probables, el número esperado de nodos evaluados es , que es mucho menor que el trabajo realizado por los nodos aleatorios. algoritmo, mencionado anteriormente, y nuevamente es óptimo para tales árboles aleatorios. [10] Cuando los valores de las hojas se eligen independientemente unos de otros pero a partir del intervalo uniformemente al azar, el número esperado de nodos evaluados aumenta hasta el límite, [11] que nuevamente es óptimo para este tipo de árboles aleatorios. Tenga en cuenta que el trabajo real para valores "pequeños" de se aproxima mejor utilizando . [11] [10]
Un programa de ajedrez que busca cuatro capas con un promedio de 36 ramas por nodo evalúa más de un millón de nodos terminales. Una poda alfa-beta óptima eliminaría todos menos unos 2.000 nodos terminales, una reducción del 99,8%. [13]
Normalmente durante alfa-beta, los subárboles están temporalmente dominados 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 bando muchas veces durante la búsqueda si el orden de los movimientos es incorrecto, lo que cada vez genera ineficiencia. Como 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 ordenar todas las posiciones en profundidades cercanas al nodo raíz es relativamente barato ya que hay muy pocas. En la práctica, el orden de los movimientos suele estar determinado por los resultados de búsquedas anteriores y más pequeñas, como por ejemplo a través de una profundizació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 dicha modificación.
El pseudocódigo para minimax de profundidad limitada con poda alfa-beta es el siguiente: [15]
Las implementaciones de poda alfa-beta a menudo se pueden delinear según si son "fáciles" o "fáciles". Con falla suave alfa-beta, la función alfabética puede devolver valores (v) que exceden (v < α o v > β) los límites α y β establecidos por sus argumentos de llamada de función. En comparación, el alfa-beta resistente a la falla limita el valor de retorno de su función al rango inclusivo de α y β. La principal diferencia entre las implementaciones de falla suave y de falla dura es si α y β se actualizan antes o después de la verificación de corte. Si se actualizan antes de la verificación, pueden exceder los límites iniciales y el algoritmo falla suavemente.
El siguiente pseudocódigo ilustra la variación de falla difícil. [15]
la función alfabeta (nodo, profundidad, α, β, maximizingPlayer) es si profundidad == 0 o el nodo es terminal , entonces devuelve el valor heurístico del nodo si maximizingPlayer entonces valor := −∞ para cada hijo del nodo hacer valor := max(valor, alfabetoa(niño, profundidad − 1, α, β, FALSO)) si el valor > β entonces romper (* límite de β *) α := máx(α, valor) valor de retorno más valor := +∞ para cada hijo del nodo hacer valor := min(valor, alfabetoa(niño, profundidad − 1, α, β, VERDADERO)) si el valor < α entonces romper (* límite de α *) β := mín(β, valor) valor de retorno
(* Llamada inicial *) alfabético(origen, profundidad, − ∞ , + ∞ , VERDADERO)
El siguiente pseudocódigo ilustra el fallo suave alfa-beta.
la función alfabeta (nodo, profundidad, α, β, maximizingPlayer) es si profundidad == 0 o el nodo es terminal , entonces devuelve el valor heurístico del nodo si maximizingPlayer entonces valor := −∞ para cada hijo del nodo hacer valor := max(valor, alfabetoa(niño, profundidad − 1, α, β, FALSO)) α := máx(α, valor) si el valor ≥ β entonces rompe (* límite β *) valor de retorno en caso contrario valor := +∞ para cada hijo del nodo hacer valor := min(valor, alfabetoa(niño, profundidad − 1, α, β, VERDADERO)) β := mín(β, valor) si el valor ≤ α entonces rompe (* α límite *) valor de retorno
(* Llamada inicial *) alfabético(origen, profundidad, − ∞ , + ∞ , VERDADERO)
Se pueden lograr mejoras adicionales sin sacrificar la precisión mediante el uso de heurísticas de ordenación para buscar partes anteriores del árbol que probablemente fuercen cortes alfa-beta. Por ejemplo, en el ajedrez, los movimientos que capturan piezas pueden examinarse antes que los movimientos que no lo hacen, y los movimientos que obtuvieron una puntuación alta en pasadas anteriores a través del análisis del árbol de 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ápida considerando sólo una ventana de búsqueda estrecha (generalmente determinada por conjeturas basadas en la experiencia). Esto se conoce como ventana de aspiración . En el caso extremo, la búsqueda se realiza con alfa y beta iguales; una técnica conocida como búsqueda de ventana cero , búsqueda de ventana nula o búsqueda de exploración . Esto es particularmente útil para búsquedas de victorias/pérdidas cerca del final de un juego donde la profundidad adicional obtenida gracias a la ventana estrecha y una simple función de evaluación de victorias/pérdidas pueden llevar a un resultado concluyente. Si falla una búsqueda de aspiración, es sencillo detectar si falló en lo alto (el borde superior de la ventana estaba demasiado bajo) o en lo bajo (el borde inferior de la ventana estaba 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 contra 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").
Dado que el algoritmo minimax y sus variantes son inherentemente de profundidad primero , generalmente se usa 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 haya terminado de ejecutarse. Otra ventaja de utilizar la profundización iterativa es que las búsquedas a profundidades menores brindan sugerencias sobre el orden de los movimientos, así como estimaciones alfa y beta superficiales, que pueden ayudar a producir límites para búsquedas de mayor profundidad mucho antes de lo que sería posible de otro modo.
Algoritmos como SSS* , por otro lado, utilizan la estrategia "mejor primero" . Potencialmente, esto puede hacer que ahorren más tiempo, pero generalmente a un alto costo en términos de eficiencia espacial. [dieciséis]
Al igual que su contraparte A* para juegos de un solo jugador, SSS* es óptimo en términos del número promedio de nodos examinados; pero su poder de poda superior queda más que compensado por el importante espacio de almacenamiento y la contabilidad necesarios.
![{\displaystyle [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/738f7d23bb2d9642bab520020873cccbef49768d)
