Poda alfa-beta

La poda alfa-beta es un algoritmo de búsqueda en árbol que busca disminuir el número de nodos evaluados por el algoritmo minimax en su árbol de búsqueda . Es un algoritmo de búsqueda adversaria comúnmente utilizado para el juego automático de juegos combinatorios de dos jugadores ( Tres en raya , Ajedrez , Conecta 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 examinado previamente. Dichos movimientos no necesitan ser evaluados más. Cuando se aplica a un árbol minimax estándar, devuelve el mismo movimiento que minimax, pero poda las ramas que no pueden influir en la decisión final. ^{[ 1 ]}

Durante el Taller de Dartmouth, John McCarthy 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 se mostró convencido. ^{[ 2 ]}

Allen Newell y Herbert A. Simon, quienes 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 tuvo 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 . ^{[ 5 ]} McCarthy propuso ideas similares durante el taller de Dartmouth en 1956 y se lo 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, publicando sus resultados en 1963. ^{[ 7 ]} Donald Knuth y Ronald W. Moore refinaron el algoritmo en 1975. ^{[ 8 ] [ 9 ]} Judea Pearl demostró su optimalidad en términos del tiempo de ejecución esperado para árboles con valores de hojas asignados aleatoriamente en dos artículos. ^{[ 10 ] [ 11 ]} La optimalidad de la versión aleatorizada de alfa-beta fue demostrada por Michael Saks y Avi Wigderson en 1986. ^{[ 12 ]}

Un árbol de juego puede representar muchos juegos de suma cero para dos jugadores , como el ajedrez, las damas y el reversi. Cada nodo del árbol representa una situación posible 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 garantizada para el jugador que busca maximizar su puntuación y la puntuación máxima garantizada para el jugador que busca minimizarla. Inicialmente, alfa es infinito negativo y beta es infinito positivo; es decir, ambos jugadores comienzan con su peor puntuación posible. Cuando la puntuación máxima garantizada para el jugador que busca minimizar su puntuación (es decir, el jugador "beta") es menor que la puntuación mínima garantizada para el jugador que busca maximizar su puntuación (es decir, el jugador "alfa") (es decir, beta < alfa), el jugador que busca maximizar su puntuación no necesita considerar los descendientes posteriores de este nodo, ya que nunca se alcanzarán durante la partida.

Para ilustrar esto con un ejemplo real, supongamos que alguien está jugando al ajedrez y es su turno. La jugada "A" mejorará su posición. El jugador continúa buscando jugadas para asegurarse de no haber pasado por alto una mejor. La jugada "B" también es buena, pero el jugador se da cuenta de que permitirá al oponente dar jaque mate en dos jugadas. Por lo tanto, ya no es necesario considerar otros resultados de la jugada "B", puesto que el oponente puede forzar la victoria. La puntuación máxima que el oponente podría forzar tras la jugada "B" es infinito negativo: una derrota para el jugador. Esto es menor que la posición mínima encontrada previamente; la jugada "A" no resulta en una derrota forzada en dos jugadas.

La ventaja de la poda alfa-beta radica en que permite eliminar ramas del árbol de búsqueda. ^{[ 13 ]} De esta forma, el tiempo de búsqueda se limita al subárbol más prometedor y se realiza una búsqueda más profunda simultáneamente. Al igual que su predecesor, pertenece a la clase de algoritmos de ramificación y acotación . La optimización reduce la profundidad efectiva a 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 movimiento lateral se ordena primero en cada nodo).

Con un factor de ramificación (promedio o constante) de b y una profundidad de búsqueda de d , el número máximo de posiciones de nodos hoja evaluadas (cuando el orden de movimiento es pesimista ) es O ( b ^d ), el 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 nodos hoja evaluadas es aproximadamente O ( b × 1 × b × 1 × ... × b ) para profundidad impar y O ( b × 1 × b × 1 × ... × 1) para profundidad par, o${\displaystyle O\left(b^{\frac {d}{2}}\right)=O\left({\sqrt {b^{d}}}\right)}$.

En este último caso, donde el nivel de búsqueda es par, el factor de ramificación efectivo se reduce a su raíz cuadrada , o, equivalentemente, 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, solo se necesita el mejor movimiento del segundo jugador para refutar todos excepto el primer (y mejor) movimiento del primer jugador: alfa-beta garantiza que no sea necesario considerar ningún otro movimiento 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 hoja binarios es${\displaystyle \Theta \left(\left({\frac {b-1+{\sqrt {b^{2}+14b+1}}}{4}}\right)^{d}\right)}$ . ^{[ 12 ]}

Para los mismos árboles, cuando los valores se asignan a los valores de las hojas independientemente unos de otros y digamos que cero y uno son igualmente probables, el número esperado de nodos evaluados es${\displaystyle \Theta \left(\left(b/2\right)^{d}\right)}$, que es mucho menor que el trabajo realizado por el algoritmo aleatorio mencionado anteriormente, y es nuevamente óptimo para tales árboles aleatorios. ^{[ 10 ]} Cuando los valores de las hojas se eligen independientemente unos de otros pero a partir de la${\displaystyle [0,1]}$intervalo uniformemente al azar, el número esperado de nodos evaluados aumenta a${\displaystyle \Theta \left(b^{d/\log(d)}\right)}$en el${\displaystyle d\to \infty }$límite, ^{[ 11 ]} que nuevamente es óptimo para este tipo de árbol aleatorio. Tenga en cuenta que el trabajo real para valores "pequeños" de${\displaystyle d}$se aproxima mejor usando${\displaystyle 0.925d^{0.747}}$. ^{[ 11 ] [ 10 ]}

Un programa de ajedrez que busca cuatro jugadas con un promedio de 36 ramificaciones por nodo evalúa más de un millón de nodos terminales. Una poda alfa-beta óptima eliminaría todos los nodos terminales excepto unos 2000, una reducción del 99,8 %. ^{[ 13 ]}

Normalmente, durante la fase alfa-beta, los subárboles están temporalmente dominados por una ventaja del primer jugador (cuando muchos movimientos del primer jugador son buenos, y en cada profundidad de búsqueda el primer movimiento comprobado por el primer jugador es adecuado, pero todas las respuestas del segundo jugador deben intentar 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 conduce cada vez a la ineficiencia. Como el número de posiciones buscadas disminuye exponencialmente con cada movimiento que se acerca a la posición actual, vale la pena invertir un esfuerzo considerable en ordenar los primeros movimientos. Una ordenación mejorada en 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 son muy pocas. En la práctica, el orden de los movimientos a menudo se determina por los resultados de búsquedas anteriores más pequeñas, como a través de la profundización iterativa .

Además, este algoritmo puede modificarse fácilmente para devolver la variación principal completa , además de la puntuación. Algunos algoritmos más complejos, como MTD(f), no permiten fácilmente dicha modificación.

El pseudocódigo para el minimax con limitación de profundidad y poda alfa-beta es el siguiente: ^{[ 15 ]}

función alphabeta(nodo, profundidad, α, β, jugadormaximizador) es si profundidad == 0 o nodo es terminal entonces devolver el valor heurístico de nodo si jugadormaximizador entonces valor := − ∞ para cada hijo de nodo hacer valor := max(valor, alphabeta(hijo, profundidad − 1, α, β, FALSO)) si valor ≥ β entonces salir (* β corte *) α := max(α, valor) Devuelve un valor en caso contrario valor := +∞ para cada hijo del nodo hacer valor := min(valor, alphabeta(hijo, profundidad − 1, α, β, VERDADERO)) si valor ≤ α entonces salir (* α corte *) β := min(β, valor) valor de retorno

(* Llamada inicial *) alphabeta(origen, profundidad, − ∞ , + ∞ , VERDADERO)

Las implementaciones de poda alfa-beta suelen clasificarse según sean de tolerancia a fallos o de tolerancia a fallos. El pseudocódigo ilustra la variante de tolerancia a fallos. En la poda alfa-beta de tolerancia a fallos, la función `alphabeta` puede devolver valores (v) que superen (v < α o v > β) los límites α y β establecidos por los argumentos de la llamada a la función. En cambio, la poda alfa-beta de tolerancia a fallos limita el valor de retorno de la función al rango inclusivo de α y β.

Se puede lograr una mayor mejora 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 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 pasadas anteriores del análisis del árbol de juego pueden evaluarse antes que otros. Otra heurística común y muy económica es la heurística del asesino , donde el último movimiento que causó un corte beta en el mismo nivel del árbol en la búsqueda del árbol siempre se examina primero. Esta idea también puede generalizarse en un conjunto de tablas de refutación .

La búsqueda alfa-beta puede hacerse aún más rápida considerando solo una ventana de búsqueda estrecha (generalmente determinada por estimación basada 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/derrotas cerca del final de una partida, donde la mayor profundidad obtenida con la ventana estrecha y una función de evaluación simple de victorias/derrotas puede llevar a un resultado concluyente. Si una búsqueda de aspiración falla, es fácil detectar si falló por exceso (el límite superior de la ventana era demasiado bajo) o por defecto (el límite inferior de la ventana era demasiado alto). Esto proporciona información sobre qué valores de ventana podrían ser útiles en una nueva búsqueda de la posición.

Con el tiempo, se han sugerido otras mejoras, y de hecho, la idea de Falphabeta (fail-soft alpha–beta) de John Fishburn es casi universal y ya está incorporada arriba en una forma ligeramente modificada. Fishburn también sugirió una combinación de la heurística killer y la búsqueda de ventana cero bajo el nombre de Lalphabeta ("último movimiento con búsqueda alfa–beta de ventana mínima").

Dado que el algoritmo minimax y sus variantes son intrínsecamente de búsqueda en profundidad , se suele utilizar una estrategia como la de profundización iterativa junto con alfa-beta para que se pueda obtener un movimiento razonablemente bueno incluso si el algoritmo se interrumpe antes de finalizar su ejecución. Otra ventaja de usar la profundización iterativa es que las búsquedas a menor profundidad proporcionan pistas sobre el orden de los movimientos, así como estimaciones de alfa y beta superficiales, que pueden ayudar a establecer límites para búsquedas a mayor profundidad mucho antes de lo que sería posible de otro modo.

Por otro lado, algoritmos como SSS* utilizan la estrategia de búsqueda primero del mejor . Esto puede hacerlos potencialmente más eficientes en términos de tiempo, pero generalmente a un alto costo en eficiencia de espacio. ^{[ 16 ]}

• Russell, Stuart J.; Norvig , Peter. (2021). Inteligencia artificial: un enfoque moderno (4.ª  ed.). Hoboken: Pearson. ISBN 9780134610993. LCCN 20190474 . 
• Heineman, George T.; Pollice, Gary; Selkow, Stanley (2008). «7. Búsqueda de rutas en IA». Algoritmos en pocas palabras . Oreilly Media . págs. 217–223 . ISBN  978-0-596-51624-6.
• Pearl, Judea (1984). Heurísticas: Estrategias de búsqueda inteligentes para la resolución de problemas informáticos . Addison-Wesley. ISBN 978-0-201-05594-8OCLC 1035596197​​ 
• Fishburn, John P. (1984). «Apéndice A: Algunas optimizaciones de la búsqueda α-β». Análisis de la aceleración en algoritmos distribuidos (revisión de la tesis doctoral de 1981) . UMI Research Press. págs. 107-111 . ISBN  0-8357-1527-2.