Hermann Pollack (hpollack95)

Posted on May 14

Minimax, Teoría de Juegos y el "gato"

#ai #programming #python

Corría el año 2014, en mi final de semestre de Programación Orientada a Objetos en la Universidad Católica del Maule. El profesor nos planteó crear un juego del gato (o tres en raya). Mi aplicación se desvió un poco de lo pedido, pero investigué herramientas para que la CPU jugara de manera eficiente. El resultado: un juego imposible de ganar para un humano.

El gato es un juego simple pero entretenido. Lo jugaba de niño con compañeros: 9 casillas, una X para un jugador y una O para el otro. Gana quien complete una línea horizontal, vertical o diagonal.

Teoría de Juegos

La Teoría de Juegos es una rama de las matemáticas y la economía que estudia la toma de decisiones estratégicas. Su objetivo es entender cómo se comportan individuos, empresas o naciones cuando el resultado de sus acciones depende de las acciones de los demás. En simple: analiza la interdependencia.

Ejemplos:

En el gato, tu decisión depende de lo que el rival escoja.
En el trabajo, muchas acciones de mis colegas dependen de lo que yo autorice en una máquina.
En el fútbol, la estrategia depende de la habilidad de los jugadores y las decisiones que toman en la cancha.

En el gato, las posibilidades matemáticas son 255.168 combinaciones desde el quinto turno (pues antes no se puede completar una línea). Se denota con la fórmula:

\large S_{total} = \sum_{t=5}^{9} \text{Ganadas}(t) + \text{Empatadas}(9)

Tabla de secuencias posibles

Turno (t)	Jugador que mueve	Secuencias que terminan aquí	Resultado
5	X	1.440	Victoria de X
6	O	5.328	Victoria de O
7	X	47.952	Victoria de X
8	O	72.576	Victoria de O
9	X	81.792	Victoria de X
9	-	46.080	Empate
TOTAL		255.168	Caminos posibles

Para un humano es imposible calcular todas esas variantes mentalmente. Una máquina sí puede, incluso con un Pentium 4, porque no cae en la trampa psicológica que afecta a los jugadores humanos (como en el póker, donde las expresiones son clave). Al ser un juego de dos, siempre tiende a ser de suma cero: cada victoria de uno ( $+1$ ) es la derrota del otro ( $-1$ ).

Minimax

Concepto

El algoritmo Minimax es un método de decisión usado en Inteligencia Artificial y en juegos de suma cero como el gato. Busca el movimiento óptimo, asumiendo que ambos jugadores juegan de manera perfecta.

Su representación matemática es:

V(s) = \begin{cases} \text{utilidad}(s) & \text{si } s \text{ es un estado terminal} \ \max_{a \in A(s)} V(\text{resultado}(s, a)) & \text{si el jugador es MAX} \ \min_{a \in A(s)} V(\text{resultado}(s, a)) & \text{si el jugador es MIN} \end{cases}

Donde:

$V(s)$ : valor de utilidad del estado actual.
$utilidad(s)$ : valor final del juego (+1 victoria, -1 derrota, 0 empate).
$MAX$ : jugador que busca maximizar (CPU).
$MIN$ : jugador que busca minimizar (oponente).
$A(s)$ : conjunto de movimientos legales.
$resultado(s, a)$ : nuevo tablero tras aplicar la acción.

En simple:

Si el juego terminó, el valor es el resultado.
Si es turno de MAX: la CPU calcula todos los tableros y escoge el más beneficioso.
Si es turno de MIN: la IA asume que el humano elegirá la opción que más la perjudique.

Implementación en Python

def __minimax(self, player):
    if self.won():
        if player:
            return (-1, None)
        else:
            return (+1, None)
    elif self.tied():
        return (0, None)
    elif player:
        best = (-2, None)
        for x, y in self.fields:
            if self.fields[x, y] == self.empty:
                value = self.move(x, y).__minimax(not player)[0]
                if value > best[0]:
                    best = (value, (x, y))
        return best
    else:
        best = (+2, None)
        for x, y in self.fields:
            if self.fields[x, y] == self.empty:
                value = self.move(x, y).__minimax(not player)[0]
                if value < best[0]:
                    best = (value, (x, y))
        return best

Explicación paso a paso

Caso base

El algoritmo es recursivo: se llama a sí mismo en cada movimiento.

if self.won(): si el juego terminó, retorna -1 si ganó el humano, +1 si ganó la CPU.
elif self.tied(): si hay empate, retorna 0.

Maximizador (`elif player:`)

La IA simula sus movimientos buscando maximizar el resultado.

Inicializa best = (-2, None) como valor centinela.
Explora casillas vacías.
Simula un movimiento y llama recursivamente a __minimax.
Si el valor obtenido es mayor al mejor actual, lo guarda.

Minimizador (`else:`)

La IA simula al oponente, que busca minimizar el resultado.

Inicializa best = (+2, None).
Explora casillas vacías.
Simula un movimiento y llama recursivamente a __minimax.
Si el valor obtenido es menor al mejor actual, lo guarda.

Propagación de valores

La línea clave es:

value = self.move(x, y).__minimax(not player)[0]

Esto construye un árbol de decisiones:

Los nodos MIN eligen el valor más bajo.
Los nodos MAX eligen el valor más alto.

Así, la IA explora todas las ramas posibles y selecciona siempre la jugada óptima. En consecuencia, nunca pierde.

Conclusión.

Este trabajo ya hace 12 años, me inició en el conocimiento de lo que se conoce como Inteligencia Artificial, que hoy es muy común y sorprendente para el usuario común, pero que algunos ya conocíamos desde la época de los videojuegos arcade. Ahora bien, mas que razonar, lo que hace este algoritmo es simular en base a la probabilidad, toda opción en base a la opción de su oponente humano, eligiendo la que más le conviene (máximo beneficio y mínimo riesgo).

Debo decir que no me saqué la mejor nota (un 5.6 de 7), pero le gustó la explicación de lo que hice, porque en realidad, el conocer un método como este, me hizo darme cuenta, como hacer "pensar" a la CPU.

En fin, antes de irme, estoy ya terminando de ver la serie Persona de Interés a la que le hice reseña. Eso, Dejó un pequeño video del resultado de este juego. Lo iré refactorizando y lo subiré a mi repositorio pronto. Que estén bien.

DEV Community

Minimax, Teoría de Juegos y el "gato"