Minimax: Juegos con adversario

En entradas anteriores hemos visto estrategias para encontrar soluciones a problemas de búsqueda que se pueden expresar por medio de un espacio con estructura en forma de árbol o de grafo. Una de las fuentes más fructíferas de problemas que se pueden resolver por los procedimientos de búsqueda estudiados nos la proporciona la teoría de juegos unipersonales (o solitarios).

Sin embargo, es difícil aplicar directamente estos procedimientos a juegos en los que intervienen dos jugadores que compiten, lo que se conoce como juego con adversario. En este contexto, Minimax es un método de decisión para minimizar la pérdida máxima esperada en juegos con adversario y con información perfecta (para maximizar la ganancia mínima esperada). Su funcionamiento puede resumirse en: elegir el mejor movimiento para ti mismo suponiendo que tu contrincante escogerá el peor movimiento para ti.

John von Neumann dio la siguiente definición de lo que era un juego:

Un juego es una situación conflictiva en la que uno debe tomar una decisión sabiendo que los demás también toman decisiones, y que el resultado del conflicto se determina, de algún modo, a partir de todas las decisiones realizadas.

Y demostró en 1926 que siempre existe una forma racional (una estrategia óptima) de actuar en juegos de dos participantes, si los intereses que los gobiernan son completamente opuestos. A este resultado se le conoce como Teorema Minimax.

Este resultado establece que en los juegos bipersonales de suma cero (aquellos en los que los intereses que los gobiernan son completamente opuestos, o lo que es lo mismo, que lo que gana un jugador lo pierde el otro), donde además cada jugador conoce de antemano la estrategia de su oponente y sus consecuencias, existe una estrategia que permite a ambos jugadores minimizar la pérdida máxima esperada. En particular, cuando se examina cada posible estrategia, un jugador debe considerar todas las respuestas posibles del jugador adversario y la pérdida máxima que puede acarrear. El jugador juega, entonces, con la estrategia que resulta en la minimización de su máxima pérdida. Tal estrategia es llamada óptima para ambos jugadores sólo en caso de que sus minimaxes sean iguales (en valor absoluto) y contrarios (en signo). Si el valor común es cero el juego se convierte en un sinsentido. En los juegos de suma no nula, existe tanto la estrategia Minimax como la Maximin. La primera intenta minimizar la ganancia el rival, es decir, busca que el rival tenga el peor resultado, mientras que la segunda intenta maximizar la ganancia propia, es decir, busca que el jugador obtenga el mejor resultado.

Búsquedas con Adversario

La búsqueda con adversarios se usa normalmente en juegos en los que intervienen más de un jugador, aunque también la podemos encontrar en contextos en los que se han de tomar decisiones (acciones futuras) en entornos con cierta incertidumbre.

Existen muchos tipos de juegos, pero vamos a considerar fundamentalmente aquellos en los que se verifican las siguientes condiciones:

• Es determinista.
• De dos jugadores.
• Basado en turnos.
• De suma nula: lo que un jugador gana, lo pierde el otro.
• Con información perfecta: cada jugador tiene conocimiento completo del estado del mundo en todo momento.

La forma más directa de formalizar un juego de estas características es por medio de un árbol:

• Conjunto de estados/nodos, $S$, comenzando por una situación inicial, $s_0$.
• Los jugadores se notarán por $P=\{1,\dots,n\}$ (normalmente, $n=2$).
• Las acciones/movimentos se notarán por $A$ (pueden depender del jugador y del estado).
• La función de transición: $S\times A \to S$.
• Tenemos un test de terminación: $S\to \{true,false\}$.
• Disponemos de una función de utilidad de estados terminales, que indica lo bueno que es un estado terminal para cada jugador: $S\times P\to R$.

Buscamos que un algoritmo de búsqueda adversario nos devuelva una estrategia (política) que, esencialmente, devuelve una acción para cada estado: $S\to A$, que indica la "jugada" a realizar. Contrasta con la devolución de un plan, que indicaría el procedimiento completo de juego de principio a fin. La razón es que no podemos planificar por completo una jugada, sino solo responder a las diferentes jugadas que el oponente puede realizar.

El algoritmo Minimax

De forma más detallada, la idea consiste en comenzar en la posición actual del juego y usar el generador de movimientos legales para generar las posibles posiciones sucesivas hasta un cierto límite de niveles (si es posible porque el juego lo permita, se desarrolla el árbol completo de juego hasta las posiciones finales). A continuación, se aplica una función de evaluación estática a los últimos estados obtenidos, que es capaz de decir lo bueno o malo que es cada estado, y se elige la mejor posición para el jugador correspondiente, llevando los valores un nivel hacia atrás para continuar la evaluación en todos los niveles anteriores.

Habitualmente, se suele trabajar con una función de evaluación que devuelve valores positivos para indicar buenas situaciones para el jugador que hace uso del algoritmo, y valores negativos para indicar buenas situaciones para el adversario. Así planteado, el objetivo es maximizar el valor de esta función estática sobre las posibles jugadas que se pueden hacer desde la posición actual del juego.

De este mecanismo es de donde viene el nombre del algoritmo: dada la función evaluadora estática, el jugador que hace uso del algoritmo intenta maximizar su valor, mientras que el adversario intenta minimizarlo. En un árbol de juego donde los valores de la función evaluadora se calculan en relación al jugador maximizante, se maximiza y minimiza alternadamente de un nivel a otro hasta llegar al nivel actual de juego.

Formalmente, los pasos del algoritmo Minimax son:

1. Generación del árbol de juego: A partir del nodo que representa el estado actual, se generan todos los nodos hasta llegar a un estado terminal (si no podemos afrontar la generación del árbol completo, es posible aplicar los pasos siguientes sobre una sección del mismo, aunque entonces no podremos asegurar la optimalidad de los resultados).
2. Se calculan los valores de la función de evaluación para cada nodo terminal (o las hojas que hayamos conseguido si no hemos podido construirlo entero) del árbol construido.
3. Se evalúan los nodos superiores a partir del valor de los inferiores. Según si estos nodos pertenecen a un nivel MAX o un nivel MIN, se elegirán los valores mínimos y máximos representando los movimientos del jugador y del oponente.
4. Se repite el paso 3 hasta llegar al nodo superior (estado actual).
5. Se selecciona la jugada-nodo directamente accesible desde el nodo actual que optimiza el valor de la evaluación.

Debe destacarse que, si no es posible realizar el árbol completo de jugadas, pero sí disponemos de una función que permite evaluar lo bueno que es un estado intermedio (por medio de una heurística), aún podemos hacer uso del algoritmo minimax para decidir cuál es el mejor movimiento posible a partir del estado actual. Por supuesto, dependerá de la calidad de la función heurística el que la estrategia que proporciona la ejecución del algoritmo sea ganadora o no. El problema de muchos juegos (como el ajedrez o el Go) es que no es posible trabajar con el árbol completo de jugadas posibles (ya que requiere un árbol con una cantidad de nodos que supera los \(10^{40}\)), y tampoco se conoce una heurística que asegure una estrategia ganadora.

Tal y como está definido, una de las formas más sencillas de implementar Minimax es por medio de un procedimiento recursivo de contrucción del árbol. Cuando no es posible realizar la construcción completa, hay que decidir cuándo se realiza el corte, que puede venir dado por alguna de las condiciones siguientes:

• Gana algún jugador.
• Se han explorado \(N\) niveles (con \(N\) un parámetro prefijado).
• Se ha agotado el tiempo de exploración (parámetro prefijado).
• Se ha llegado a una situación estática donde no hay grandes cambios de un nivel a otro.

Gracias al uso de agentes, implementar este algoritmo en NetLogo es bastante directo y sencillo.

Al igual que hemos hecho en las implementaciones de búsquedas en espacios de estados, modelaremos los estados como una especie de agentes con las propiedades que necesitemos durante la ejecución del algoritmo:

; Tipo de agente que representa los estados del juego
breed [estados estado]

estados-own [
  evaluacion ; Almacena la evaluación del estado (solo válido para los estados finales,
             ; ya que el resto se calcula por minimax)
  player     ; Quién juega desde este estado (para saber si se aplica min o max)
  gameover?  ; Dice si el estado es final o no
  nivel      ; Indica el nivel dentro del árbol (distancia a la raíz)
]

Para hacerlo lo más general posible, supongamos que tenemos dos funciones: una que devuelve los estados sucesores a uno dado (es un report de tortuga), y otra que recibe como entrada uno de estos estados sucesores y devuelve el movimiento legal que nos lleva a él:

; Función general de sucesores legales (depende del problema que se está resolviendo,
; en este caso es simplemente el sucesor del grafo)
to-report legal-successors 
  report out-link-neighbors
end

; Función general de obtener el movimiento legal que nos lleva a un estado s'
; (depende del problema que se está resolviendo, en este caso es simplemente 
; el link que los une)
to-report legal-move-to [a]
  report out-link-to a
end

Supuesto que tenemos una evaluación en los estados finales (el valor de bondad que representa ese estado para el jugador principal), la siguiente función calcula de forma recursiva la evaluación de los estados intermedios, usando el máximo o el mínimo dependiendo de si es un estado en el que mueve el jugador principal o el oponente, hasta llegar al estado raíz sobre el que queremos decidir el mejor movimiento.

Realmente, la función de evaluación asocia a cada estado un par [ ev suc ] que indica no solo la evaluación en este estado (que será el máximo o mínimo de las evaluaciones de sus sucesores, dependiente del jugador), sino también en qué sucesor se consigue ese extremo:

; La función de evaluación es la que hace el cálculo Minimax.
; Lo que calcula en cada nodo es un par (evaluacion sucesor) que indica no solo
; la evaluación (min o max de la evaluacion de los sucesores), sino también en qué
; sucesor se consigue ese extremo (uno de ellos, si hay más de uno)
to-report eval
  ; Si es un estado final, se devuelve su evaluación directa
  ifelse gameover?
  [ set label evaluacion
    report (list self evaluacion) 
  ]
  ; Si no, se calcula el máximo o mínimo (dependiendo de si es un nodo en que
  ; debe jugar el jugador o el oponente) de las evaluaciones de sus sucesores
  [ let selected nobody
    ifelse player = "me" 
    [ set selected max-one-of legal-successors [last eval] ]
    [ set selected min-one-of legal-successors [last eval] ]
    ask legal-move-to selected [
      set color blue 
      set thickness .2 
      ]
    set label [last eval] of selected
    report (list selected [last eval] of selected)
  ]
end

En el procedimiento anterior no solo se hace el cálculo de las evaluaciones, sino que se muestran junto al estado correspondiente y se marca el movimiento (link) que suponen las mejores jugadas. En el modelo se representan los estados del jugador MAX en verde y con un triángulo hacia arriba, y los del jugador MIN en rojo y con el triángulo hacia abajo. El estado superior (o más a la izquierda) es el correspondiente a la jugada actual.

En el modelo que puedes encontrar aquí se muestra el algoritmo minimax aplicado sobre árboles aleatorios de partidas de un juego en el que los nodos finales tienen una valoración de 0 a 10. Adicionalmente, en el modelo se proporciona un sencillo método que permite representar árboles de forma equilibrada.

La mayoría de juegos interesantes tienen árboles de juego excesivamente grandes, de forma que no podemos expandir completamente el árbol hasta llegar a los nodos terminales. Por ello, suele ser común usar un algoritmo de profundidad limitada que solo expande algunos niveles del árbol, sin llegar a los nodos terminales. Pero en este caso, ¿cómo se calcula entonces la utilidad de un movimiento determinado?

Normalmente, para poder trabajar con una expansión limitada y poder usar algoritmos como Minimax se hace uso de funciones de evaluación que calculan la utilidad de estados no terminales, es decir, estiman el valor de una acción. 

Otra posible generalización es hacia juegos donde no hay suma nula o hay más de 2 jugadores. En estos casos suele ser común considerar nodos que disponen de valores de utilidad como tuplas, y cada jugador intenta maximizar su propia componente, lo que a veces podría llevar a estrategias de entre jugadores.

Poda alfa-beta de la búsqueda Minimax

El problema de la búsqueda Minimax es que el número de estados a explorar puede llegar a ser exponencial respecto al número de movimientos. Si $r$ es el factor de ramificación (cuántos hijos tiene cada nodo), y $m$ es el nivel de profundidad que vamos a alcanzar, entonces la complejidad en tiempo es del orden $O(r^m)$ y la complejidad en espacio del orden $O(rm)$.

La Poda alfa-beta es una técnica que reduce el número de nodos evaluados en el árbol de juego construido por el algoritmo Minimax. Para ello, trata de eliminar partes grandes del árbol que se va construyendo de forma que se devuelva el mismo movimiento que devolvería este, podando ramas que se sepa que no van a influir en la decisión final.

La ides de esta técnica es que cada nodo se analiza teniendo en cuenta el valor que por el momento tiene y el valor que por el momento tiene su padre, lo que determina en cada momento un intervalo $(\alpha,\beta)$ de posibles valores que podría tomar el nodo. El significado intuitivo de estos parámetros en cada momento es:

• En los nodos MAX: $\alpha$ es el valor actual del nodo (que tendrá ese valor o superior), y $\beta$ es el valor actual del padre (que tendrá ese valor o inferior).
• En los nodos MIN: $\beta$ es el valor actual del nodo (que tendrá ese valor o inferior), y $\alpha$ es el valor actual del padre (que tendrá ese valor o superior).
• La poda se produce si en algún momento $\alpha \geq \beta$, y en ese momento no hace falta analizar los restantes sucesores del nodo. En nodos MIN, se denomina poda $\beta$, y en nodos MAX, poda $\alpha$.

El cambio que se introduce en el minimax habitual es que en esta nueva versión con poda se va actualizando el valor de los parámetros según se recorre el árbol. El método realizará la poda de las ramas restantes cuando el valor actual que se está examinando sea peor que el valor actual de \(\alpha\) o \(\beta\) para MAX o MIN, respectivamente:

function alphabeta(nivel, α, β): (función de nodo)
    
    Si nivel = 0 o el nodo es una hoja:
      return valor del nodo (valor terminal o valor heurístico)
    
    Si player = MAX:
      Para cada hijo del nodo:
        α = max(α, alphabeta(nivel-1, α, β)
        Si β <= α: parar
      return α
    
    Si player = MIN:
      Para cada hijo del nodo :
        β = min(β, alphabeta(nivel-1, α, β)
        Si β <= α: parar
      return β

La llamada a la función por primera vez sería sobre el nodo raíz:
    alphabeta(D, -∞, +∞)

En el modelo anterior también puedes encontrar este algoritmo implementado para comparar su funcionamiento con el algoritmo minimax sin poda. 

Es interesante estudiar cómo mejora el rendimiento del algoritmo en el mejor de los casos, para saber si realmente se ha mejorado de alguna forma el algoritmo original. Según Knuth y Moore, si los nodos están perfectamente ordenados, el número de nodos terminales considerados en una búsqueda de profundidad \(m\) con poda alfa-beta es el doble de los nodos terminales considerados en una búsqueda de profundidad \(m/2\) sin poda alfa-beta. Esto significa que en el caso perfecto, una búsqueda que haga uso de la poda alfa-beta proporciona una ganancia considerable, ya que permite explorar con igual coste la mitad de los nodos finales de un árbol con el doble de profundidad.

Hay otras opciones para realizar podas, como por ejemplo dejar de explorar un subárbol que ofrece pocas posibilidades de mejora sobre otros caminos que ya han sido explorados, es decir, que su evaluación sea solo ligeramente más favorable que otra rama ya explorada.

El siguiente conjunto de transparencias expone las ideas anteriores sobre el caso del 3 en raya:

De la Búsqueda con Adversario a la Búsqueda con Incertidumbre

Muchas veces el resultado de la acción no es determinista y conlleva un cierto grado de incertidumbre. Hay algunas formas de abordar este problema, pero una de las más comunes, y que reutiliza lo que hemos presentado hasta aquí, es considerar que el adversario es un jugador que juega al azar (o con cierto grado de azarosidad).

Mientras que en el Minimax clásico se presupone que el adversario va a hacer la mejor jugada posible para él (la peor para nosotros), en este caso consideramos que el resultado será el promedio de los resultados posibles, es decir, la esperanza de la utilidad, y por eso el método se llama ExpectiMax.

En este caso, la utilidad de un nodo se calcula como la media (ponderada) de las posibles salidas de sus hijos. Como no tomamos el máximo, sino la media, no podemos usar podas al estilo alfa-beta vistas anteriormente.

Si mezclamos adversarios reales y cierto grado de azar, podemos dar una extensión mezcla de las dos anteriores que se denomima ExpectiMinimax.

De todas formas, veremos en una entrada posterior otra forma de abordar este tipo de problemas por medio de un procedimiento inspirado en búsquedas aleatorias en el árbol de jugadas: Monte Carlo Tree Search.