Alfabeta: Haciendo Minimax Factible

Un estudio más cuidadoso del algoritmo Minimax concluye que existen muchas variantes en el árbol de búsqueda las cuales no necesitan ser examinadas debido a que no afectan la decision del movimiento ya elegido para realizar. La idea bajo este algoritmo es el desechar rápidamente alternativas que se ven inferiores a una alternativa ya analizada, convirtiendo el algoritmo Minimax en una búsqueda sobre un árbol muy simplificado. La idea fue propuesta en 1950 por John McCarthy quien en ese entonces era profesor del MIT. Hart y Edwards, también del MIT, publicaron en 1961 un paper en el cual describían el algoritmo mientras que A.L.Brudno describió el algoritmo en la literatura soviética en 1963. Esencialmente, el algoritmo alfa-beta corresponde al algoritmo de Minimax pero con la capacidad de descartar tempranamente variantes que son inferiores a la preseleccionada. En la secuencia de variantes mostrada en la figura , utilizando el algoritmo alfa-beta sólo 3 de los 4 nodos terminales necesitarán ser examinados. La búsqueda determina primero la puntuación para la posición D. Luego de asignar su valor (0) éste es asignado a la posición de origen B. Este score establece un "techo" para la evaluación siguiente. La evaluación de la posición E con un score de +2 significa que para el adversario en la posición B el movimiento 1...Txd5 es mejor que 1...Axc3, por lo cual la posición B mantiene el valor 0, que es el mejor valor al que el primer jugador puede optar luego de 1.Axc3 . La posición base puede tener ahora un score provisional de 0. Este será el valor de tope, sin importar los valores de las posiciones terminales luego de 1.Txd5. Al analizar la posición F un valor de -4 es asignado a ella, por lo cual no será necesario analizar las siguientes posiciones terminales, puesto que de todas maneras conviene seguir por la rama de la posición B. En otras palabras, el movimiento 1...Dxa5 refuta inmediatamente 1.Txd5, por lo cual esta continuación es descartada en preferencia de 1.Axc3, con lo que nos "ahorramos" el analizar otra rama luego de la posición C.

Figura: Aplicación de la poda alfa-beta dentro del algoritmo minimax

Más generalmente, el algoritmo alfa-beta dice que un movimiento y en la posición Y refuta al movimiento predecesor x en la posición X bajo un mismo nivel si el score provisional de cualquier posición al mismo nivel en la continuación desde la posición base X tiene un score mayor o igual al score mantenido asignado a la posición Y por el movimiento y. En 1969 James Slagle, uno de los mejores jugadores ciegos de ajedrez de los Estados Unidos y un distinguido científico computacional, junto con J.Dixon demostraron que para un árbol de variantes uniforme, con igual cantidad de movimientos en cada posición (digamos, con anchura B) y cuyas posiciones terminales se encuentran todas a una igual profundidad la cual denominaremos d, el número de posiciones terminales computadas por el algoritmo alfa-beta es de al menos 2B^(d/2)-1 para un d par y B^((d+1)/2)+B^((d-1)/2)-1 para un d impar. En un partida normal de ajedrez una posición posee cerca de 36 movimientos posibles. Realizando el modelamiento con un árbol de anchura 36 encontramos que para una profundidad de 2 movimientos al menos 2*36^1 = 71 posiciones terminales son examinadas. Para el mismo árbol uniforme pero con profundidad 3 al menos 36^2 + 36 - 1 = 1331 posiciones son examinadas y al menos 2*36^(5)-1 = 3.359.431 posiciones para un árbol con profundidad d = 10 movimientos. Esencialmente el árbol de búsqueda se incrementa en tamaño en un factor de 6 (la raíz de 36) por cada nivel de profundidad al que se avanza. Esto implica que para buscar en un nivel extra de profundidad la computadora debe procesar 6 veces más rápido o tomar una cantidad de tiempo 6 veces mayor.