« Métodos combinados de… « || Inicio || » Programación Funciona… »

Minimax: Juegos con adversario

Última modificación: 18 de Octubre de 2016, y ha tenido 1415 vistas

Etiquetas utilizadas: || ||

En entradas anteriores hemos visto estrategias de búsqueda para encontrar soluciones a problemas que se pueden expresar por medio de un espacio de búsqueda 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).

Por otra parte, es difícil aplicar directamente estos procedimientos a juegos en los que intervienen dos jugadores, es decir, cuando se tiene un 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 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, y viceversa), 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.

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, que es capaz de decir lo bueno o malo que es cada estado, a los últimos estados obtenidos 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: 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 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.
  5. Se selecciona la jugada-nodo directamente accesible desde la jugada actual que optimiza el valor de la evaluación.

Se debe tener en cuenta 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 (lo que se llama 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) 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 tortugas 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 es 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. En este caso, las funciones anteriores se materializan en:

; 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

La función que genera este árbol artificial es:

to setup
ca
ask patches [set pcolor white]
set-default-shape estados "triangle 2"
create-estados 1 [
set color green
set player "me"
set gameover? true
set shape "triangle 2"
set nivel 0
]
repeat 2 [
ask estados with [gameover?] [
hatch-estados random ramificacion [
set color red
set player "op"
set nivel nivel + 1
create-link-from myself]
set gameover? false
]
ask estados with [gameover?] [
hatch-estados random ramificacion [
set color green
set player "me"
set nivel nivel + 1
create-link-from myself]
set gameover? false
]
]
layout-tree (estado 0) ori
ask estados [
set gameover? false
set heading ifelse-value (player = "op") [180][0]
set label-color black
set size .5 + 6 / (1 + nivel)
]
ask estados with [not any? out-link-neighbors] [
set gameover? true
set evaluacion random 10
set label evaluacion
]
; Labels
create-estados 1 [
set color green
set size 2
set heading 0
set shape "triangle 2"
setxy min-pxcor + 1 max-pycor - 1
ask patch-at 7 0 [
set plabel-color black
set plabel "MAX player"]
]
create-estados 1 [
set color red
set size 2
set heading 180
set shape "triangle 2"
setxy min-pxcor + 1 (max-pycor - 3)
ask patch-at 7 0 [
set plabel-color black
set plabel "MIN player"]
]
end

Adicionalmenrte, en el modelo se proporciona un sencillo método que permite representar árboles de forma equilibrada:

; Función de representación de árbol a partir de un nodo raiz. 
; Orientacion puede ser "v" (vertical) o "h" (horizontal)
to layout-tree [raiz orientacion]
let PriDir ifelse-value (orientacion = "h") [world-width] [world-height]
let SecDir ifelse-value (orientacion = "v") [world-width] [world-height]
; MaxN : Número de niveles en el árbol
let MaxN max [nivel] of estados
; incx: distacia entre niveles en el eje X
let incP Pridir / (1 + MaxN)
; xini: posición X inicial de los niveles
let iniP ifelse-value (orientacion = "h") [min-pxcor + incP / 2][max-pycor - incP / 2]
; niv: nivel actual de trabajo
let niv 0
; estadosNiv: estados del nivel actual
let estadosNiv (list raiz)
; Vamos a ir por niveles poniendo los estados correspondientes en una columna
; uniformemente distribuidos
foreach (n-values (1 + MaxN) [?]) [
; tamNivel: Número de estados en el nivel actual
let tamNivel length estadosNiv
; incy: distancia vertical entre estados de este nivel
let incS SecDir / (1 + tamNivel)
; yini: posición Y inicial de los estados del nivel actual
let iniS ifelse-value (orientacion = "h") [min-pycor + incS] [max-pxcor - incS]
; Colocamos los estados de este nivel en la columna
foreach estadosNiv [
ask ? [
ifelse orientacion = "h"
[ setxy iniP iniS ]
[ setxy iniS iniP ]
]
; Se incrementa la posición Y para el siguiente estado
set iniS ifelse-value (orientacion = "h") [iniS + incS][iniS - incS]
]
; Se incrementa la posición X para el siguiente nivel
set iniP ifelse-value (orientacion = "h") [iniP + incP][iniP - incP]
; Se incrementa el nivel
set niv niv + 1
; Se calculan los estados del siguiente nivel, como una lista ordenada de estados:
; Son los sucesores del nivel actual
; Para que no haya cruces el bloque de sucesores de cada estado actual se añaden
; en el mismo orden en le que están los padres (por medio de un map)
; Dentro de cada bloque de sucesores se aplica un orden que depende del peso
; del subarbol que hay debajo (el peso es el número de hojas)
; El orden aplicado va alternando valores altos con bajos
set estadosNiv reduce sentence ; Aplanamos la lista
map ; nos quedamos con los sucesores de los estados actuales
; (en el mismo orden que están los actuales)
; Ordenamos los estados descendentemente por el peso de
; su subárbol
[ equilibra sort-by
[[peso-subarbol] of ?1 > [peso-subarbol] of ?2]
([out-link-neighbors] of ?)]
estadosNiv
]
end

; Devuelve el peso (número de estados finales) de un subárbol (determinado por su raíz)
to-report peso-subarbol
ifelse gameover?
[ report ifelse-value (nivel = max[nivel] of estados) [1][0] ]
[ report sum [peso-subarbol] of out-link-neighbors ]
end

; Equilibra una lista de valores (que recibe ordenada de mayor a menor),
; situando los maximos en los extremos e intercalando los demás:
; equilibra [10 9 8] -> [10 8 9]
; equilibra [10 9 8 7] -> [10 7 8 9]
; equilibra [10 9 8 7 6] -> [10 7 8 6 9]
; equilibra [10 9 8 7 6 5] -> [10 5 7 8 6 9]
; equilibra [10 9 8 7 6 5 4] -> [10 5 7 4 8 6 9]
; equilibra [10 9 8 7 6 5 4 3] -> [10 5 7 4 8 3 6 9]
; equilibra [10 9 8 7 6 5 4 3 2] -> [10 5 7 4 8 3 6 2 9]
; equilibra [10 9 8 7 6 5 4 3 2 1] -> [10 1 5 7 4 8 3 6 2 9]
to-report equilibra [s]
let res s
; Si solo tiene 2 elementos, no se cambia
if length s > 2 [
; comenzamos con los 2 primeros elementos (los máximos)
; y el resto (que se irán intercalando)
set res sublist s 0 2
set s sublist s 2 length s
while [not empty? s] [
; seleccionamos los elementos necesarios del resto para intercalar
let j min (list (length s) (-1 + length res))
set res intercalate res (sublist s 0 j)
set s sublist s j length s
]
report res
end

; Dadas 2 listas (la primera más larga) intercala los elementos de s en los de r
to-report intercalate [r s]
if empty? s [report r]
report (sentence (first r) (first s) intercalate (bf r) (bf s))
end

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. La Poda alfa-beta es una técnica de búsqueda que reduce el número de nodos evaluados en un árbol de juego 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 poda alfa-beta toma su nombre por el uso de dos parámetros que fijan ciertas cotas para el proceso de propagación hacia arriba que efectúa el algoritmo.

  • \(\alpha\) es el valor de la mejor opción hasta el momento a lo largo del camino para MAX, que representa, por tanto, una cota superior. El valor \(\alpha\) representa la cota inferior del valor que puede asignarse en último término a un nodo maximizante.
  • \(\beta\) es el valor de la mejor opción hasta el momento a lo largo del camino para MIN, que representa, por tanto, una cota inferior. El valor \(\beta\) representa la cota superior del valor que puede asignarse en último término a un nodo minimizante.

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.

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 \(d\) con poda alfa-beta es el doble de los nodos terminales considerados en una búsqueda de profundidad \(d/2\) sin poda alfa-beta. Esto significa que en el caso perfecto, una búsqueda que haga uso de la poda alfa-beta nos proporciona ganancia considerable, ya que permite explorar con igual costo 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:

Análisis y Simulación de Decisiones de José Enrique Alvarez Estrada

« Métodos combinados de… « || Inicio || » Programación Funciona… »