Aprendizaje por refuerzo (RL) — Capítulo 4: Min-Max y Alpha-Beta Pruning — Parte 3: Implementación en Python

5 min readDec 7, 2023

En la dos partes anteriores de esta capítulo vimos los algoritmos de Min-Max y Alpha-Beta Pruning, analizamos un ejemplo y realizamos la implementación en pseudocódigo. En esta última parte del capítulo vamos a implementarlos en Python.

Prepare su café y arranquemos.

Min-Max

Arranquemos por el algoritmo de Min-Max.

Lo primero que vamos a hacer es escribir el código que se encarga de calcular el valor del estado. Este tiene que recorrer todas las posibles ramificaciones desde una posición dada y, mediante las reglas de Min-Max, propagar el valor de los nodos finales (los nodos hojas) al estado actual (el nodo raíz):

def MinMax(state, depth, maximizing_player):
    done = env.get_winner(state)!=None
    if ((done) | (depth==0)):
        return env.get_winner(state)

    valid_actions = [(i,j) for i in range(state[0].shape[0]) for j in range(state[0].shape[1]) 
                     if env.get_valid(state)[i,j]==1] 
    next_states = [env.get_next_state(state, action) for action in valid_actions]
    
    if maximizing_player:
        maxEva = float('-inf')
        for child_state in next_states:
            eva = MinMax(child_state, depth-1, False) 
            maxEva = max(maxEva, eva)
        return maxEva
    else:
        minEva = float('inf')
        for child_state in next_states:
            eva = MinMax(child_state, depth-1, True) 
            minEva = min(minEva, eva)
        return minEva

Esta función toma como input el estado actual (el tablero), la profundidad del árbol y si es el turno del jugador “maximizador” (nosotros) o el contrincante.

Primero comprobamos si la partida finalizó o si alcanzamos la profundidad máxima; si se da el caso, retornamos el resultado de la partida.

Luego analizamos todas las posibles acciones desde la posición actual y obtenemos los tableros resultantes al aplicar dicha acción.

Posteriormente, dependiendo si es nuestro turno o de nuestro adversario, recorremos todas las posiciones del tablero, resultado de aplicar la acción del paso anterior, y repetimos el proceso conservando siempre el valor máximo o mínimo del estado según corresponda.

El resultado de aplicar esta función, a un estado, es el valor de dicho estado. Pero, eso no es suficiente para saber que acción debemos aplicar, solo sabemos si el estado actual es bueno o no.

Para encontrar la acción óptima vamos a implementar la siguiente función:

def select_best_action(state, depth=100):
    valid_actions = [(i,j) for i in range(state[0].shape[0]) for j in range(state[0].shape[1]) 
                     if env.get_valid(state)[i,j]==1]
    next_states = [env.get_next_state(state, action) for action in valid_actions]
    maximizing_player = state[1]!=1
    min_max_values = [MinMax(new_state, depth, maximizing_player) for new_state in next_states]
    best_action = valid_actions[np.argmin(min_max_values) if maximizing_player else np.argmax(min_max_values)]
    return best_action

Esta función parte de un estado del tablero, y para cada una de las posibles acciones del estado actual aplica la función que vimos al principio. El resultado de esto es que podemos valorizar el estado de los tableros luego de hacer cada una de las acciones válidas en la posición actual. Luego solo queda tomar la acción que nos lleve a un estado de mayor (o menor para el contrincante) probabilidades de ganar.

Alpha-Beta Pruning

El segundo y último algoritmo que vamos a implementar en este capítulo es Min-Max con Alpha-Beta Pruning.

Acá, al igual que antes, primero necesitamos implementar la función que realiza la exploración y nos valoriza la posición actual del tablero:

def AlphaBetaPruning(state, depth, maximizing_player, alpha, beta):
    done = env.get_winner(state)!=None
    if ((done) | (depth==0)):
        return env.get_winner(state)

    valid_actions = [(i,j) for i in range(state[0].shape[0]) for j in range(state[0].shape[1]) 
                     if env.get_valid(state)[i,j]==1] 
    next_states = [env.get_next_state(state, action) for action in valid_actions]
    
    if maximizing_player:
        best_score = float('-inf')
        for child_state in next_states:
            eva = AlphaBetaPruning(child_state, depth-1, False, alpha, beta) 
            best_score = max(best_score, eva)
            alpha = max(best_score, alpha)
            if alpha >= beta:
                break
    else:
        best_score = float('inf')
        for child_state in next_states:
            eva = AlphaBetaPruning(child_state, depth-1, True, alpha, beta) 
            best_score = min(best_score, eva)
            beta = min(best_score, beta)
            if alpha >= beta:
                break
                
    return best_score

Nuevamente, primero comprobamos si la partida finalizó o si alcanzamos la profundidad máxima y, si se da el caso, retornamos el resultado de la partida.

Luego analizamos todas las posibles acciones desde la posición actual y obtenemos los tableros resultantes al aplicar dicha acción.

El paso siguiente es, dependiendo de si es el turno del jugador maximizador o minimizador, recorrer todas las posiciones del tablero, resultado de aplicar la acción del paso anterior.

hasta aquí todo igual.

El cambio radica en que no vamos a necesitar recorrer todos los posibles estados. Al analizar cada estado vamos arrastrando el valor de alpha y beta (como vimos en la parte anterior de este capítulo) y cuando llegamos a la condición α > β, podamos toda la rama por lo que no necesitamos seguir explorando el resto de acciones y estados.

Esta función nos devuelve el valor del estado que pasamos como entrada. Pero, ya sabemos que esto no es suficiente para saber que acción debemos aplicar. Aca simplemente hacemos uso de la misma función que ya creamos para Min-Max que nos permite valorizar la acción y así saber como actuar en la posición que nos encontramos.

Y eso es todo lo que necesitamos para implementar Min-Max y Alpha-Beta Pruning en Python, ¿simple verdad?. Recuerde que tiene en el repositorio de Git las notebooks con los códigos que acabamos de analizar:

GitHub - jcerretani/AprendizajePorRefuerzo

Contribute to jcerretani/AprendizajePorRefuerzo development by creating an account on GitHub.

github.com

En el próximo capitulo vamos a ver los algoritmos de programación dinámica. Los algoritmos de programación dinámica son poderosas técnicas que permiten a las máquinas aprender a tomar decisiones secuenciales de manera óptima. Estos algoritmos utilizan la idea de descomponer un problema complejo en subproblemas más pequeños y resolverlos de manera eficiente, lo que les permite encontrar soluciones óptimas en entornos donde la exploración y la toma de decisiones secuenciales son fundamentales. Esto convierte a los algoritmos de programación dinámica en una pieza fundamental en la creación de sistemas de inteligencia artificial capaces de tomar decisiones autónomas en situaciones en constante cambio como juegos, robótica y muchas otras aplicaciones. Los veo en el próximo capítulo!.