Introducción
Contenido
A finales de la década de 1920, John Von Neumann estableció el principal problema de la teoría de juegos que sigue siendo relevante en la actualidad:
Los jugadores s1, s2, …, sn están jugando un juego dado G. ¿Qué movimientos debería jugar el jugador sm para lograr el mejor resultado posible?
Poco después, problemas de este tipo se convirtieron en un desafío de gran importancia para el desarrollo de uno de los campos más populares de la informática: la inteligencia artificial. Algunos de los mayores logros en inteligencia artificial se logran en el tema de los juegos estratégicos: los campeones del mundo en varios juegos estratégicos ya han sido derrotados por las computadoras, por ejemplo, en Ajedrez, Damas, Backgammon y, más recientemente (2016), incluso Go.
Aunque estos programas tienen mucho éxito, su forma de tomar decisiones es muy diferente a la de los humanos. La mayoría de estos programas se basan en algoritmos de búsqueda eficientes y, desde hace poco, también en Machine Learning.
El algoritmo Minimax es un algoritmo relativamente simple que se utiliza para una toma de decisiones óptima en teoría de juegos e inteligencia artificial. Nuevamente, dado que estos algoritmos dependen en gran medida de la eficiencia, el rendimiento del algoritmo de vainilla se puede mejorar considerablemente mediante el uso de la poda alfa-beta; cubriremos ambos en este artículo.
Aunque no analizaremos cada juego individualmente, explicaremos brevemente algunos conceptos generales que son relevantes para juegos simétricos de suma cero no cooperativos para dos jugadores con información perfecta : ajedrez, go, tic-tac-toe, backgammon, reversi. , Damas, Mancala, 4 seguidas, etc …
Como probablemente hayas notado, ninguno de estos juegos son aquellos en los que, por ejemplo, un jugador no sabe qué cartas tiene el oponente, o dónde un jugador necesita adivinar sobre cierta información.
Definición de términos
Las reglas de muchos de estos juegos están definidas por posiciones legales (o estados legales) y movimientos legales para cada posición legal. Para cada puesto legal es posible determinar efectivamente todos los movimientos legales. Algunas de las posiciones legales son posiciones iniciales y algunas son posiciones finales.
La mejor manera de describir estos términos es usando un gráfico de árbol cuyos nodes son posiciones legales y cuyos bordes son movimientos legales. El gráfico está dirigido ya que no significa necesariamente que podamos retroceder exactamente de donde venimos en el movimiento anterior, por ejemplo, en el ajedrez, un peón solo puede avanzar. Este gráfico se llama árbol de juegos. Desplazarse hacia abajo en el árbol del juego representa a uno de los jugadores que hace un movimiento y el estado del juego cambia de una posición legal a otra.
Aquí hay una ilustración de un árbol de juego para un juego de tic-tac-toe:
Las cuadrículas de color azul son los turnos del jugador X, y las cuadrículas de color rojo son los turnos del jugador O. La posición final (hoja del árbol) es cualquier cuadrícula donde uno de los jugadores ganó o el tablero está lleno y no hay un ganador.
Te puede interesar:Agrupación jerárquica con Python y Scikit-LearnEl árbol de juego completo es un árbol de juego cuya raíz es la posición inicial y todas las hojas son posiciones finales. Cada árbol de juego completo tiene tantos nodes como resultados posibles tiene el juego para cada movimiento legal realizado. Es fácil notar que incluso para juegos pequeños como tic-tac-toe, el árbol completo del juego es enorme. Por esa razón, no es una buena práctica crear explícitamente un árbol de juego completo como una estructura mientras se escribe un programa que se supone que predice el mejor movimiento en cualquier momento. Sin embargo, los nodes deben crearse implícitamente en el proceso de visita.
Definiremos la complejidad del espacio de estados de un juego como una cantidad de posiciones legales de juego alcanzables desde la posición inicial del juego, y el factor de ramificación como la cantidad de hijos en cada node (si ese número no es constante, es un factor común práctica para usar un promedio).
Para tic-tac-toe, un límite superior para el tamaño del espacio de estado es 39 = 19683. ¡Imagínese ese número para juegos como el ajedrez! Por lo tanto, buscar en todo el árbol para descubrir cuál es nuestro mejor movimiento cada vez que nos turnamos sería muy ineficiente y lento.
Es por eso que Minimax tiene una gran importancia en la teoría de juegos.
Teoría detrás de Minimax
El algoritmo Minimax se basa en una búsqueda sistemática, o más exactamente, en la fuerza bruta y una función de evaluación simple. Supongamos que cada vez que decidimos el siguiente movimiento buscamos en un árbol completo, hasta las hojas. Efectivamente, analizaríamos todos los resultados posibles y cada vez podríamos determinar el mejor movimiento posible.
Sin embargo, para los juegos no triviales, esa práctica es inaplicable. Incluso la búsqueda a cierta profundidad a veces lleva una cantidad de tiempo inaceptable. Por lo tanto, Minimax aplica la búsqueda a una profundidad de árbol bastante baja con la ayuda de heurísticas apropiadas y una función de evaluación bien diseñada pero simple.
Con este enfoque perdemos la certeza de encontrar el mejor movimiento posible, pero en la mayoría de los casos la decisión que toma minimax es mucho mejor que la de cualquier humano.
Ahora, echemos un vistazo más de cerca a la función de evaluación que hemos mencionado anteriormente. Para determinar una buena (no necesariamente la mejor) jugada para un determinado jugador, tenemos que evaluar de alguna manera los nodes (posiciones) para poder comparar uno con otro por calidad.
La función de evaluación es un número estático, que de acuerdo con las características del propio juego, se le asigna a cada node (posición).
Es importante mencionar que la función de evaluación no debe depender de la búsqueda de nodes anteriores, ni de los siguientes. Simplemente debería analizar el estado del juego y las circunstancias en las que se encuentran ambos jugadores.
Es necesario que la función de evaluación contenga la mayor cantidad de información relevante posible, pero por otro lado, dado que se calcula muchas veces, debe ser simple.
Te puede interesar:Generación de texto con Python y TensorFlow/KerasPor lo general, asigna el conjunto de todas las posiciones posibles en un segmento simétrico:
$$
mathcal {F}: mathcal {P} flecha derecha [-M, M]
$$
El valor de Mse asigna solo a las hojas donde el ganador es el primer jugador, y el valor -Ma las hojas donde el ganador es el segundo jugador.
En los juegos de suma cero, el valor de la función de evaluación tiene un significado opuesto: lo que es mejor para el primer jugador es peor para el segundo, y viceversa. Por lo tanto, el valor de las posiciones simétricas (si los jugadores cambian de rol) debe ser diferente solo por el signo.
Una práctica común es modificar las evaluaciones de hojas restando la profundidad de esa hoja exacta, de modo que de todos los movimientos que conducen a la victoria, el algoritmo puede elegir el que lo hace en el menor número de pasos (o elige el movimiento que pospone pérdida si es inevitable).
Aquí hay una ilustración simple de los pasos de Minimax. Buscamos el valor mínimo, en este caso.
La capa verde llama al Max()método en los nodes de los nodes secundarios y la capa roja llama al Min()método en los nodes secundarios.
- Evaluación de hojas:
- Decidir el mejor movimiento para el jugador verde usando la profundidad 3:
La idea es encontrar el mejor movimiento posible para un node, profundidad y función de evaluación dados.
En este ejemplo, asumimos que el jugador verde busca valores positivos, mientras que el jugador rosa busca valores negativos. El algoritmo evalúa principalmente solo los nodes a la profundidad dada, y el resto del procedimiento es recursivo . Los valores del resto de los nodes son los valores máximos de sus respectivos hijos si es el turno del jugador verde o, análogamente, el valor mínimo si es el turno del jugador rosa. El valor en cada node representa el siguiente mejor movimiento considerando la información dada.
Mientras buscamos en el árbol del juego, estamos examinando solo los nodes en una profundidad fija (dada), no los anteriores ni los posteriores. Este fenómeno a menudo se denomina efecto horizonte .
Abrir libros y Tic-Tac-Toe
En los juegos estratégicos, en lugar de dejar que el programa inicie el proceso de búsqueda desde el principio del juego, es común usar los libros de apertura, una lista de movimientos conocidos y productivos que son frecuentes y se sabe que son productivos mientras todavía no lo hacemos. Tenemos mucha información sobre el estado del juego si miramos el tablero.
Te puede interesar:Tareas asíncronas en Django con Redis y CeleryAl principio, es demasiado pronto en el juego, y el número de posiciones potenciales es demasiado grande para decidir automáticamente qué movimiento conducirá sin duda a un mejor estado de juego (o ganar).
Sin embargo, el algoritmo reevalúa los siguientes movimientos potenciales en cada turno, siempre eligiendo lo que en ese momento parece ser la ruta más rápida hacia la victoria. Por lo tanto, no ejecutará acciones que requieran más de un movimiento para completarse y, por eso, no podrá realizar ciertos «trucos» bien conocidos. Si la IA juega contra un humano, es muy probable que el humano pueda prevenirlo inmediatamente.
Si, por otro lado, echamos un vistazo al ajedrez, rápidamente nos daremos cuenta de la impracticabilidad de resolver el ajedrez mediante la fuerza bruta en todo un árbol de juego. Para demostrar esto, Claude Shannon calculó el límite inferior de la complejidad del árbol de juego del ajedrez, lo que resultó en aproximadamente 10120 juegos posibles .
¿Qué tan grande es ese número? Como referencia, si comparamos la masa de un electrón (10-30 kg) con la masa de todo el universo conocido (1050-1060 kg), la relación sería del orden de 1080-1090.
Eso es ~ 0.0000000000000000000000000000000001% del número de Shannon.
Imagínese asignarle la tarea a un algoritmo para que revise cada una de esas combinaciones solo para tomar una sola decisión. Es prácticamente imposible de hacer.
Incluso después de 10 movimientos, la cantidad de juegos posibles es tremendamente enorme:
Número de movimientos Número de juegos posibles
| 1 | 20 |
| 2 | 40 |
| 3 | 8,902 |
| 4 | 197,281 |
| 5 | 4,865,609 |
| 6 | 119,060,324 |
| 7 | 3,195,901,860 |
| 8 | 84,998,978,956 |
| 9 | 2,439,530,234,167 |
| 10 | 69,352,859,712,417 |
Llevemos este ejemplo a un juego de tic-tac-toe. Como probablemente ya sepa, la estrategia más famosa del jugador X es comenzar en cualquiera de las esquinas, lo que le da al jugador O la mayor cantidad de oportunidades para cometer un error. Si el jugador O juega algo que no sea el centro y X continúa con su estrategia inicial, es una victoria garantizada para X. Los libros de apertura son exactamente esto: algunas formas agradables de engañar a un oponente desde el principio para obtener una ventaja o, en el mejor de los casos, una victoria.
Para simplificar el código y llegar al núcleo del algoritmo, en el ejemplo del próximo capítulo no nos molestaremos en usar libros de apertura o trucos mentales. Dejaremos que el minimax busque desde el principio, así que no se sorprenda de que el algoritmo nunca recomiende la estrategia de esquina.
Implementación de Minimax en Python
En el siguiente código, usaremos una función de evaluación que es bastante simple y común para todos los juegos en los que es posible buscar en todo el árbol, hasta las hojas.
Te puede interesar:Python para PNL: creación de un chatbot basado en reglasTiene 3 valores posibles:
- -1 si el jugador que busca el mínimo gana
- 0 si es un empate
- 1 si el jugador que busca el máximo gana
Dado que implementaremos esto a través de un juego de tic-tac-toe, repasemos los bloques de construcción. Primero, hagamos un constructor y dibujemos el tablero:
# We'll use the time module to measure the time of evaluating
# game tree in every move. It's a nice way to show the
# distinction between the basic Minimax and Minimax with
# alpha-beta pruning :)
import time
class Game:
def __init__(self):
self.initialize_game()
def initialize_game(self):
self.current_state = [['.','.','.'],
['.','.','.'],
['.','.','.']]
# Player X always plays first
self.player_turn = 'X'
def draw_board(self):
for i in range(0, 3):
for j in range(0, 3):
print('{}|'.format(self.current_state[i][j]), end=" ")
print()
print()
Hemos hablado de movimientos legales en las secciones iniciales del artículo. Para asegurarnos de cumplir con las reglas, necesitamos una forma de verificar si una mudanza es legal:
# Determines if the made move is a legal move
def is_valid(self, px, py):
if px < 0 or px > 2 or py < 0 or py > 2:
return False
elif self.current_state[px][py] != '.':
return False
else:
return True
Entonces, necesitamos una forma sencilla de comprobar si el juego ha terminado. En tic-tac-toe, un jugador puede ganar conectando tres símbolos consecutivos en una línea horizontal, diagonal o vertical:
# Checks if the game has ended and returns the winner in each case
def is_end(self):
# Vertical win
for i in range(0, 3):
if (self.current_state[0][i] != '.' and
self.current_state[0][i] == self.current_state[1][i] and
self.current_state[1][i] == self.current_state[2][i]):
return self.current_state[0][i]
# Horizontal win
for i in range(0, 3):
if (self.current_state[i] == ['X', 'X', 'X']):
return 'X'
elif (self.current_state[i] == ['O', 'O', 'O']):
return 'O'
# Main diagonal win
if (self.current_state[0][0] != '.' and
self.current_state[0][0] == self.current_state[1][1] and
self.current_state[0][0] == self.current_state[2][2]):
return self.current_state[0][0]
# Second diagonal win
if (self.current_state[0][2] != '.' and
self.current_state[0][2] == self.current_state[1][1] and
self.current_state[0][2] == self.current_state[2][0]):
return self.current_state[0][2]
# Is whole board full?
for i in range(0, 3):
for j in range(0, 3):
# There's an empty field, we continue the game
if (self.current_state[i][j] == '.'):
return None
# It's a tie!
return '.'
La IA contra la que jugamos busca dos cosas: maximizar su propia puntuación y minimizar la nuestra. Para hacer eso, tendremos un max()método que usa la IA para tomar decisiones óptimas.
# Player 'O' is max, in this case AI
def max(self):
# Possible values for maxv are:
# -1 - loss
# 0 - a tie
# 1 - win
# We're initially setting it to -2 as worse than the worst case:
maxv = -2
px = None
py = None
result = self.is_end()
# If the game came to an end, the function needs to return
# the evaluation function of the end. That can be:
# -1 - loss
# 0 - a tie
# 1 - win
if result == 'X':
return (-1, 0, 0)
elif result == 'O':
return (1, 0, 0)
elif result == '.':
return (0, 0, 0)
for i in range(0, 3):
for j in range(0, 3):
if self.current_state[i][j] == '.':
# On the empty field player 'O' makes a move and calls Min
# That's one branch of the game tree.
self.current_state[i][j] = 'O'
(m, min_i, min_j) = self.min()
# Fixing the maxv value if needed
if m > maxv:
maxv = m
px = i
py = j
# Setting back the field to empty
self.current_state[i][j] = '.'
return (maxv, px, py)
Sin embargo, también incluiremos un min()método que nos servirá de ayuda para minimizar la puntuación de la IA:
# Player 'X' is min, in this case human
def min(self):
# Possible values for minv are:
# -1 - win
# 0 - a tie
# 1 - loss
# We're initially setting it to 2 as worse than the worst case:
minv = 2
qx = None
qy = None
result = self.is_end()
if result == 'X':
return (-1, 0, 0)
elif result == 'O':
return (1, 0, 0)
elif result == '.':
return (0, 0, 0)
for i in range(0, 3):
for j in range(0, 3):
if self.current_state[i][j] == '.':
self.current_state[i][j] = 'X'
(m, max_i, max_j) = self.max()
if m < minv:
minv = m
qx = i
qy = j
self.current_state[i][j] = '.'
return (minv, qx, qy)
Y, en última instancia, hagamos un bucle de juego que nos permita jugar contra la IA:
def play(self):
while True:
self.draw_board()
self.result = self.is_end()
# Printing the appropriate message if the game has ended
if self.result != None:
if self.result == 'X':
print('The winner is X!')
elif self.result == 'O':
print('The winner is O!')
elif self.result == '.':
print("It's a tie!")
self.initialize_game()
return
# If it's player's turn
if self.player_turn == 'X':
while True:
start = time.time()
(m, qx, qy) = self.min()
end = time.time()
print('Evaluation time: {}s'.format(round(end - start, 7)))
print('Recommended move: X = {}, Y = {}'.format(qx, qy))
px = int(input('Insert the X coordinate: '))
py = int(input('Insert the Y coordinate: '))
(qx, qy) = (px, py)
if self.is_valid(px, py):
self.current_state[px][py] = 'X'
self.player_turn = 'O'
break
else:
print('The move is not valid! Try again.')
# If it's AI's turn
else:
(m, px, py) = self.max()
self.current_state[px][py] = 'O'
self.player_turn = 'X'
¡Empecemos el juego!
def main():
g = Game()
g.play()
if __name__ == "__main__":
main()
Ahora veremos lo que sucede cuando seguimos la secuencia recomendada de turnos, es decir, jugamos de manera óptima:
.| .| .|
.| .| .|
.| .| .|
Evaluation time: 5.0726919s
Recommended move: X = 0, Y = 0
Insert the X coordinate: 0
Insert the Y coordinate: 0
X| .| .|
.| .| .|
.| .| .|
X| .| .|
.| O| .|
.| .| .|
Evaluation time: 0.06496s
Recommended move: X = 0, Y = 1
Insert the X coordinate: 0
Insert the Y coordinate: 1
X| X| .|
.| O| .|
.| .| .|
X| X| O|
.| O| .|
.| .| .|
Evaluation time: 0.0020001s
Recommended move: X = 2, Y = 0
Insert the X coordinate: 2
Insert the Y coordinate: 0
X| X| O|
.| O| .|
X| .| .|
X| X| O|
O| O| .|
X| .| .|
Evaluation time: 0.0s
Recommended move: X = 1, Y = 2
Insert the X coordinate: 1
Insert the Y coordinate: 2
X| X| O|
O| O| X|
X| .| .|
X| X| O|
O| O| X|
X| O| .|
Evaluation time: 0.0s
Recommended move: X = 2, Y = 2
Insert the X coordinate: 2
Insert the Y coordinate: 2
X| X| O|
O| O| X|
X| O| X|
It's a tie!
Como habrás notado, ganar contra este tipo de IA es imposible. Si asumimos que tanto el jugador como la IA están jugando de manera óptima, el juego siempre será un empate. Dado que la IA siempre juega de manera óptima, si cometemos un error, perderemos.
Observe de cerca el tiempo de evaluación, ya que lo compararemos con la siguiente versión mejorada del algoritmo en el siguiente ejemplo.
Te puede interesar:Python para PNL: trabajar con archivos de texto y PDFPoda Alfa-Beta
El algoritmo alfa-beta (𝛼 − 𝛽) fue descubierto de forma independiente por algunas investigaciones a mediados del siglo XX. Alpha-beta es en realidad un minimax mejorado que utiliza una heurística. Deja de evaluar un movimiento cuando se asegura de que sea peor que el movimiento examinado anteriormente. Tales movimientos no necesitan ser evaluados más a fondo.
Cuando se agrega a un algoritmo minimax simple, da el mismo resultado, pero corta ciertas ramas que no pueden afectar la decisión final, mejorando drásticamente el rendimiento.
El concepto principal es mantener dos valores durante toda la búsqueda:
- Alpha : la mejor opción ya explorada para el jugador Max
- Beta : la mejor opción ya explorada para el jugador Min
Inicialmente, alfa es infinito negativo y beta es infinito positivo, es decir, en nuestro código usaremos las peores puntuaciones posibles para ambos jugadores.
Veamos cómo se verá el árbol anterior si aplicamos el método alfa-beta:
Cuando la búsqueda llega a la primera área gris (8), verificará la mejor opción actual (con valor mínimo) ya explorada a lo largo de la ruta del minimizador, que es en ese momento 7. Dado que 8 es mayor que 7, se les permite cortar todos los hijos posteriores del node en el que estamos (en este caso no hay ninguno), ya que si jugamos ese movimiento, el oponente jugará un movimiento con valor 8, que es peor para nosotros que cualquier movimiento posible que el oponente podría haber hecho si hubiéramos hecho otro movimiento.
Un mejor ejemplo puede ser cuando se trata de un siguiente gris. Tenga en cuenta los nodes con valor -9. En ese punto, la mejor opción explorada (con el valor máximo) a lo largo del camino para el maximizador es -4. Dado que -9 es menor que -4, podemos cortar a todos los demás hijos del node en el que estamos.
Este método nos permite ignorar muchas ramas que conducen a valores que no serán de ninguna ayuda para nuestra decisión, ni la afectarían de ninguna manera.
Con eso en mente, modifiquemos los métodos min()y max()de antes:
def max_alpha_beta(self, alpha, beta):
maxv = -2
px = None
py = None
result = self.is_end()
if result == 'X':
return (-1, 0, 0)
elif result == 'O':
return (1, 0, 0)
elif result == '.':
return (0, 0, 0)
for i in range(0, 3):
for j in range(0, 3):
if self.current_state[i][j] == '.':
self.current_state[i][j] = 'O'
(m, min_i, in_j) = self.min_alpha_beta(alpha, beta)
if m > maxv:
maxv = m
px = i
py = j
self.current_state[i][j] = '.'
# Next two ifs in Max and Min are the only difference between regular algorithm and minimax
if maxv >= beta:
return (maxv, px, py)
if maxv > alpha:
alpha = maxv
return (maxv, px, py)
def min_alpha_beta(self, alpha, beta):
minv = 2
qx = None
qy = None
result = self.is_end()
if result == 'X':
return (-1, 0, 0)
elif result == 'O':
return (1, 0, 0)
elif result == '.':
return (0, 0, 0)
for i in range(0, 3):
for j in range(0, 3):
if self.current_state[i][j] == '.':
self.current_state[i][j] = 'X'
(m, max_i, max_j) = self.max_alpha_beta(alpha, beta)
if m < minv:
minv = m
qx = i
qy = j
self.current_state[i][j] = '.'
if minv <= alpha:
return (minv, qx, qy)
if minv < beta:
beta = minv
return (minv, qx, qy)
Y ahora, el bucle del juego:
def play_alpha_beta(self):
while True:
self.draw_board()
self.result = self.is_end()
if self.result != None:
if self.result == 'X':
print('The winner is X!')
elif self.result == 'O':
print('The winner is O!')
elif self.result == '.':
print("It's a tie!")
self.initialize_game()
return
if self.player_turn == 'X':
while True:
start = time.time()
(m, qx, qy) = self.min_alpha_beta(-2, 2)
end = time.time()
print('Evaluation time: {}s'.format(round(end - start, 7)))
print('Recommended move: X = {}, Y = {}'.format(qx, qy))
px = int(input('Insert the X coordinate: '))
py = int(input('Insert the Y coordinate: '))
qx = px
qy = py
if self.is_valid(px, py):
self.current_state[px][py] = 'X'
self.player_turn = 'O'
break
else:
print('The move is not valid! Try again.')
else:
(m, px, py) = self.max_alpha_beta(-2, 2)
self.current_state[px][py] = 'O'
self.player_turn = 'X'
El juego es el mismo que antes, aunque si echamos un vistazo al tiempo que tarda la IA en encontrar soluciones óptimas, hay una gran diferencia:
Te puede interesar:El sistema de ayuda de Python.| .| .|
.| .| .|
.| .| .|
Evaluation time: 0.1688969s
Recommended move: X = 0, Y = 0
Evaluation time: 0.0069957s
Recommended move: X = 0, Y = 1
Evaluation time: 0.0009975s
Recommended move: X = 2, Y = 0
Evaluation time: 0.0s
Recommended move: X = 1, Y = 2
Evaluation time: 0.0s
Recommended move: X = 2, Y = 2
It's a tie!
Después de probar e iniciar el programa desde cero varias veces, los resultados de la comparación se muestran en la siguiente tabla:
Algoritmo Tiempo mínimo Tiempo máximo
| Minimax | 4.57s | 5.34s |
| Poda alfa-beta | 0,16 s | 0,2 s |
Conclusión
La poda alfa-beta marca una gran diferencia en la evaluación de árboles de caza grandes y complejos. A pesar de que tic-tac-toe es un juego simple en sí mismo, todavía podemos notar cómo sin las heurísticas alfa-beta, el algoritmo toma mucho más tiempo para recomendar el movimiento en el primer turno.
