Algoritmo de búsqueda Minimax

El algoritmo de búsqueda Minimax es un algoritmo para resolver problemas de búsqueda adversarias. Las búsquedas adversarias se dan en entornos multi-agente y competitivos; es decir, en aquellos entornos en donde maximizar la función de utilidad de un jugador afecta a la utilidad del otro o los otros jugadores.

El algoritmo de Minimax se basa en un árbol de búsqueda en donde se representan los movimientos de los adversarios. Por ejemplo, a partir del nodo raíz, el jugador 1, que llamaremos Max, será el que pueda realizar ciertos movimientos. De los nodos expandidos, el jugador 2, que llamaremos Min, podrá realizar diferentes movimientos de acuerdo a los nodos que ha expandido Max.

El árbol buscará un camino hacia un estado final en que alguno de los dos jugadores, Min o Max, haya logrado una victoria, o en donde no se puedan expandir más nodos (lo que podría corresponder a un empate).

Valores para Max y Min

Para el algoritmo de Minimax, ambos jugadores deben buscar los mejores movimientos para lograr ganar el juego. Para esto se definen dos funciones que determinan los movimientos posibles y los valores de estos movimientos. Los valores de Max comienzan en $-\infty$ por lo que se buscarán maximizar sus valores, mientras que Min comienza en $\infty$ para buscar minimizar los valores.

De esta forma, la idea es que los dos jugadores, Max y Min, compitan, uno buscando maximizar el valor, mientras que el otro minimizándolo. La estrategia de Max será como sigue:

1. Comienza con un movimiento y un valor bajos.
2. Se explorarán las acciones, y se verá el valor que Min podrá alcanzar con tal acción, si el valor de Min es mayor al valor actual de Max, se tomará esa acción.
3. Esto se repetirá para todas las acciones, de tal forma que se elegirá la acción que tenga siempre el valor más alto para Max.

Para Min se hará lo mismo pero buscando la acción que minimice el valor. Estas funciones son recursivas y buscan los valores de utilidad que se han alcanzado al final de la búsqueda de los árboles para ir eligiendo las mejores acciones para cada jugador.

import numpy as np

def max_value(game, state):
    """Valores de los movimientos de Max"""
    if game.is_terminal(state):
        #Si el estado es terminal regresa la utilidad
        return game.utility(state), None
    
    #Valores se inicializan bajos
    v, move = -np.inf, -np.inf
    for a in game.actions(state):
        #Revisa los posibles movimientos de Min con acción a
        v2, a2 = min_value(game, game.result(state, a))
        #Si el posible movimiento de Min es mayor, 
        #anticipa dicho valor y tómalo
        if v2 > v:
            v, move = v2, a
            
    return v, move

def min_value(game, state):
    """Valores de los movimientos de Min"""
    if game.is_terminal(state):
        #Si el estado es terminal regresa la utilidad
        return game.utility(state), None
    
    #Valores se inicializan altos
    v, move = np.inf, np.inf
    for a in game.actions(state):
        #Revisa los posibles movimientos de Max con acción a
        v2, a2 = max_value(game, game.result(state, a))
        #Si el posible movimiento de Max es menor, 
        #anticipa dicho valor y tómalo
        if v2 < v:
            v, move = v2, a
            
    return v, move

Algoritmo Minimax

El algoritmo de Minimax hará uso de las funciones anteriores para buscar maximizar las acciones de Max (si se utiliza la función de Min, buscará que este jugador gane).

El algoritmo simplemente llama a la función max_value para elegir la acción actual más conveniente con base en el valor para este jugador. Esto lo repetirá hasta que el juego acabe. Cuando no pueda continuar (pues las búsquedas en el árbol se han agotado) regresará los valores obtenidos.

def minimax(game):
    """Algoritmo de búsqueda Minimax"""
    #Estado inicial del juego
    state = game.board
    #Guarda las jugadas realizadas
    jugadas = []
    value, move = max_value(game, state.copy())
    
    while True:
        #Obtiene valor y movimiento para Max
        value, move = max_value(game, state.copy())
        
        try:
            #Realiza la jugada y cambia de jugador
            state = game.result(state, move)
            jugadas.append((game.player, move))
            game.change_player()
            
        except:
            #Regresa el resultado final
            result = Gato()
            result.board = state
            return result, jugadas, value

Aplicación del algoritmo al juego de gato

Ocupamos el algoritmo de Minimax para el juego del gato. En este caso, buscaremos que el jugador 1 (Max) que marca las casillas con 'o' obtenga la victoria del juego, su utilidad será entonces de 1.

from gato import Gato
#Creación del juego de gato
game = Gato()

#Aplicación del algoritmo
result, jugadas, utilidad = minimax(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

Como podemos observar, llegamos a una conclusión del juego donde el jugador Max se lleva la victoria.