Poda alfa-beta

La poda alfa-beta es un algoritmo de búsqueda que busca disminuir la cantidad 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 jugar juegos de dos jugadores (Tic-tac-toe, Chess, Connect 4, 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. Cuando se aplica a un árbol minimax estándar, devuelve el mismo movimiento que lo haría minimax, pero elimina las ramas que posiblemente no puedan influir en la decisión final.

Historia

Allen Newell y Herbert A. Simon, quienes usaron lo que John McCarthy llama una "aproximación" en 1958 escribió que alfa-beta "parece haberse reinventado varias veces". 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. 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. Alexander Brudno concibió de forma independiente el algoritmo alfa-beta y publicó sus resultados en 1963. Donald Knuth y Ronald W. Moore refinó el algoritmo en 1975. Judea Pearl demostró su optimización en términos del tiempo de ejecución esperado para árboles con valores de hoja asignados aleatoriamente en dos artículos. Michael Saks y Avi Wigderson demostraron la optimización de la versión aleatoria de alfa-beta en 1986.

Idea central

Un árbol de juegos puede representar muchos juegos de suma cero para dos jugadores, como el ajedrez, las damas y el 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 en el próximo movimiento.

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 su peor puntuación posible. Siempre que la puntuación máxima asegurada para el jugador que minimiza (es decir, el jugador 'beta') se vuelve menor que la puntuación mínima que asegura el jugador que maximiza (es decir, el jugador 'alfa') de (es decir, beta < alfa), el jugador que maximiza no necesita considerar más descendientes de este nodo, ya que nunca se alcanzarán 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. Mover "A" mejorará la posición del jugador. El jugador continúa buscando movimientos para asegurarse de que no se haya perdido uno mejor. Mover "B" también es un buen movimiento, pero el jugador luego se da cuenta de que le permitirá al oponente forzar el jaque mate en dos movimientos. Por lo tanto, ya no es necesario considerar otros resultados de jugar el movimiento 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 menos que la posición mínima que se encontró previamente; mover "A" no resulta en una pérdida forzada en dos movimientos.

Mejoras sobre el minimax ingenuo

Una ilustración de la poda alfa-beta. Los subárboles grises no necesitan ser explorados (cuando se evalúan movimientos de izquierda a derecha), ya que se sabe que el grupo de subárboles en su conjunto produce el valor de un subárbol equivalente o peor, y como tal no puede influir en el resultado final. Los niveles máximo y min representan el giro del jugador y del 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 forma, el tiempo de búsqueda se puede limitar a los 'más prometedores' subárbol, y una búsqueda más profunda se puede realizar 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 de 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) b, y una profundidad de búsqueda d plies, el número máximo de posiciones de nodos de hoja evaluadas (cuando el pedido de movimiento es pessimal) es O(b×b×b) O()b^d) - lo mismo que una simple búsqueda minimax. Si el pedido de movimiento para la búsqueda es óptimo (que significa que los mejores movimientos son siempre buscados primero), el número de posiciones de nodos de hoja evaluada es sobre O()b× 1b× 1×...b) para la profundidad extraña y O()b× 1b× 1×...×1) para incluso profundidad, o O()bd/2)=O()bd){displaystyle O(b^{d/2})=O({sqrt {b^{d}}}}. En este último caso, donde el ply de una búsqueda es incluso, el factor de ramificación eficaz se reduce a su raíz cuadrada, o, equivalentemente, la búsqueda puede ir dos veces más profunda con la misma cantidad de computación. La explicación de b× 1b× 1×... es que todos los movimientos del primer jugador deben ser estudiados para encontrar el mejor, pero para cada uno, sólo el mejor movimiento del segundo jugador es necesario para refutar todo menos el primer (y mejor) primer jugador movimiento — alpha–beta asegura que ningún otro segundo jugador se mueve necesita ser considerado. Cuando los nodos son considerados en un orden aleatorio (es decir, el algoritmo aleatoriza), asintóticamente, el número esperado de nodos evaluados en árboles uniformes con valores binarios de hoja .. ()()()b− − 1+b2+14b+1)/4)d){displaystyle Theta ((b-1+{sqrt {b^{2}+14b+1})/4)^{d})}. Para los mismos árboles, cuando los valores se asignan a los valores de hoja independientemente unos de otros y dicen cero y uno es igualmente probable, el número esperado de nodos evaluados es .. ()()b/2)d){displaystyle Theta ((b/2)^{d}) }, que es mucho más pequeño que el trabajo realizado por el algoritmo aleatorizado, mencionado anteriormente, y es de nuevo óptimo para tales árboles aleatorios. Cuando los valores de la hoja se eligen independientemente del otro pero del [0,1]{displaystyle [0,1]} intervalo uniformemente al azar, el número esperado de nodos evaluó aumentos a .. ()bd/log()d)){displaystyle Theta (b^{d/log(d)})} en el d→ → JUEGO JUEGO {displaystyle dto infty} límite, que es de nuevo óptimo para estos árboles aleatorios. Tenga en cuenta que el trabajo real para los valores "pequeños" de d{displaystyle d} es mejor aproximado usando 0.925d0,474{displaystyle 0.925d^{0.747}}.

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 2000 nodos terminales, una reducción del 99,8 %.

Un ejemplo pedagógico animado que intenta ser amigable con el ser humano sustituyendo valores iniciales infinitos (o arbitrariamente grandes) para el vacío y evitando utilizar las simplificaciones de codificación negamax.

Normalmente, durante 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 verificado por el primer jugador es adecuado, pero todas las respuestas del segundo jugador están obligados a 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 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 dedicar un esfuerzo considerable a clasificar los primeros movimientos. Una ordenación mejorada a cualquier profundidad reducirá exponencialmente el número total de posiciones buscadas, pero ordenar todas las posiciones a 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 más pequeñas anteriores, como por ejemplo mediante la profundización iterativa.

Además, este algoritmo se puede modificar de forma trivial 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:

Las implementaciones de la poda alfa-beta a menudo se pueden delinear según sean "faltas blandas" o "fallar duro". Con alfa-beta de falla suave, 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 a prueba de fallas limita el valor de retorno de su función en el rango inclusivo de α y β. La principal diferencia entre las implementaciones fail-soft y fail-hard 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 no falla.

El siguiente pseudocódigo ilustra la variación a prueba de fallas.

función alfabeto(nodo, profundidad, α, β, maximizingPlayer) es si profundidad = 0 o nodo es un nodo terminal entonces retorno el valor heurístico del nodo
 si maximización Player entoncesvalor:= −∞
 para cada uno niño de nodos dovalor:= máx(valo, alfabeto, profundidad − 1, α, β, FALSE))
 si valor β entonces descanso (* β cutoff *)α:= max(α, value)
 retorno valor
 másvalor:=
 para cada uno niño de nodos dovalor:= min(valor, alphabeta(child, profundidad − 1, α, β, TRUE))
 si valor α entonces descanso (* α cutoff *)β:= min(β, valor)
 retorno valor

(* Primera llamada *)alfabeto (origen, profundidad, −∞, +∞, TRUE)

El siguiente pseudocódigo ilustra una alfa-beta de falla suave.

función alfabeto(nodo, profundidad, α, β, maximizingPlayer) es si profundidad = 0 o nodo es un nodo terminal entonces retorno el valor heurístico del nodo
 si maximización Player entoncesvalor:= −∞
 para cada uno niño de nodos dovalor:= máx(valo, alfabeto, profundidad − 1, α, β, FALSE))
α:= max(α, value)
 si ≥ β entonces descanso (* β cutoff *) retorno valor
 másvalor:=
 para cada uno niño de nodos dovalor:= min(valor, alphabeta(child, profundidad − 1, α, β, TRUE))
β:= min(β, valor)
 si valor ≤ α entonces descanso (* α cutoff *) retorno valor

(* Primera llamada *)alfabeto (origen, profundidad, −∞, +∞, TRUE)

Mejoras heurísticas

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 es probable que 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 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 económica es la heurística asesina, donde el último movimiento que provocó un corte beta en el mismo nivel del árbol en la búsqueda del árbol siempre se examina primero. 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 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 búsqueda de ventana cero, búsqueda de ventana nula o búsqueda de exploración. Esto es especialmente útil para las búsquedas de victorias/derrotas cerca del final de un juego, donde la profundidad adicional que se obtiene de la ventana estrecha y una función simple de evaluación de victorias/derrotas pueden conducir a un resultado concluyente. Si falla una búsqueda de aspiración, es sencillo detectar si falló alto (el borde superior de la ventana era demasiado bajo) o bajo (el borde inferior de la ventana era demasiado alto). Esto brinda información sobre qué valores de ventana podrían ser útiles en una nueva búsqueda de la posición.

Con el tiempo, se sugirieron otras mejoras y, de hecho, la idea de Falphabeta (fail-soft alpha-beta) 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 inherentemente primero en profundidad, una estrategia como la profundización iterativa generalmente se usa junto con alfa-beta para que se pueda devolver un movimiento razonablemente bueno incluso si el algoritmo se interrumpe antes de que haya terminado. ejecución. Otra ventaja de usar la profundización iterativa es que las búsquedas a menor profundidad brindan sugerencias de orden de movimiento, así como estimaciones alfa y beta poco profundas, 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. Esto puede potencialmente hacerlos más eficientes en el tiempo, pero generalmente a un alto costo en la eficiencia del espacio.