Algoritmo $\alpha-\beta$¶

El algoritmo de $\alpha-\beta$ es un algoritmo de búsqueda adversaria similar al algoritmo Minimax, pero que busca simplificar la complejidad de la búsqueda a partir de descartar partes del árbol de búsqueda que no hacen diferencia en los resultados de dicha búsqueda.

El principio del algoritmo de $\alpha-\beta$ se puede pensar como: Cuando $n$ es un nodo en el árbol de búsqueda tal que el jugador en turno puede moverse hacia el estado de este nodo, si existe una mejor opción $m$ en el mismo nivel o más arriba en el árbol, entonces el jugador no se moverá a $n$. Es decir, podemos ignorar el subárbol generado en $n$.

El algoritmo, entonces tomará en cuenta dos parámetros para realizar esto:

  • $\alpha$: El valor de la mejor elección encontrada hasta el momento dentro del camino del jugador Max.
  • $\beta$: El valor de la mejor elección encontrada hasta el momento dentro del camino del jugador Min.

Entonces, si el valor obtenido actualmente es mayor a $\beta$ para Max (o menor a $\alpha$ para Min), el jugador optará por la opción que tenga mayor valor.

Para esto, igual que en el caso anterior, definimos las funciones recursivas para obtener los valores de Max y de Min.

Con esto, el algoritmo de $\alpha-\beta$ se define al tomar el valor y los movimientos para el jugador Max. En principio, tomaremos los parámetros $\alpha = -\infty$ y $\beta = \infty$. El algoritmo, entonces, buscará las mejores jugadas para el jugador.

Aplicación de $\alpha-\beta$ al juego de gato¶

Podemos probar como es que el algoritmo recién definido propone las jugadas para el juego del gato. Como podemos ver, el resultado es similar que el método de Minimax, pero en general, este algoritmo suele ser más eficiente.

In [1]:
from gato import Gato
from AlphaBeta import alpha_beta
#Creación del juego de gato
game = Gato()

#Aplicación del algoritmo
result, jugadas, utilidad = alpha_beta(game)

#Imprime el resultado del juego
print(result)
#Imprime las jugadas realizadas
print('\nJugadas realizadas:')
for j in jugadas:
    print('\tPlayer: {} - Position: {}'.format(j[0], j[1]))
#Imprime la utilidad final
print('\nUtilidad:{}'.format(utilidad))

|o|x|o|
|x|o|x|
|o| | |


Jugadas realizadas:
	Player: 1 - Position: [0 0]
	Player: 2 - Position: [0 1]
	Player: 1 - Position: [0 2]
	Player: 2 - Position: [1 0]
	Player: 1 - Position: [1 1]
	Player: 2 - Position: [1 2]
	Player: 1 - Position: [2 0]

Utilidad:1.0

Finalmente, podemos ver qué tipo de jugadas propone el algoritmo si el estado en que inicia es distinto, por ejemplo, si el otro jugador (Min) ha colocado ya un símbolo en el tablero.

In [2]:
#Toma un juego en donde el jugador 2
#ha iniciado marcando el centro
game2 = Gato()
game2.board[0,2] = -1

#Aplica algoritmo
result2, jugadas2, utilidad2 = alpha_beta(game2)
#Imprime los resultados
print(result2)
print('\nJugadas realizadas:')
for j in jugadas2:
    print('\tPlayer: {} - Position: {}'.format(j[0], j[1]))
print('\nUtilidad:{}'.format(utilidad2))

|o|x|x|
|o|x|o|
|o| |x|


Jugadas realizadas:
	Player: 1 - Position: [0 0]
	Player: 2 - Position: [0 1]
	Player: 1 - Position: [1 0]
	Player: 2 - Position: [1 1]
	Player: 1 - Position: [1 2]
	Player: 2 - Position: [2 2]
	Player: 1 - Position: [2 0]

Utilidad:1.0