Minimax

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Minimax (a veces MinMax, MM o silla de montar) es una regla de decisión utilizada en inteligencia artificial, teoría de decisiones, teoría de juegos, estadísticas y filosofía para minimizar la posible pérdida en el peor de los casos (pérdida máxima). Cuando se trata de ganancias, se denomina "maximin" – para maximizar la ganancia mínima. Originalmente formulado para la teoría de juegos de suma cero de varios jugadores, cubriendo tanto los casos en los que los jugadores realizan movimientos alternativos como aquellos en los que realizan movimientos simultáneos, también se ha extendido a juegos más complejos y a la toma de decisiones en general en presencia de incertidumbre.

Teoría de juegos

En juegos en general

El valor maximin es el valor más alto que el jugador puede estar seguro de obtener sin conocer las acciones de los otros jugadores; de manera equivalente, es el valor más bajo que los otros jugadores pueden obligar al jugador a recibir cuando conocen la acción del jugador. Su definición formal es:

{fnMicrosoft}=máx ¿Qué? ¿Qué?

Dónde:

$i$ es el índice del jugador de interés.
${displaystyle -i}$ denota todos los demás jugadores excepto jugador $i$ .
${displaystyle A_{i}$ es la acción tomada por el jugador $i$ .
${displaystyle A_{-i}$ denota las acciones tomadas por todos los demás jugadores.
${displaystyle V_{i}$ es la función de valor del jugador $i$ .

El cálculo del valor maximin de un jugador se realiza en el peor de los casos: para cada acción posible del jugador, verificamos todas las acciones posibles de los otros jugadores y determinamos la peor combinación posible de acciones: la que le da al jugador $i$ el valor más pequeño. Luego, determinamos qué acción puede tomar el jugador $i$ para asegurarnos de que este valor más pequeño sea el más alto posible.

Por ejemplo, considere el siguiente juego para dos jugadores, donde el primer jugador ("jugador de fila") puede elegir cualquiera de los tres movimientos, etiquetados como $T$ , $M$ o $B$ , y el segundo jugador (jugador de la "columna") puede elegir cualquiera de los dos movimientos, $L$ o $R$ . El resultado de la combinación de ambos movimientos se expresa en una tabla de pagos:

{displaystyle {begin{array}{c vidascc}hline > L ventajaR\hline T simultáneamente3,1 círculo2,-20\M simultáneamente5,0 diez,1B mutuamente,2 3,4\hline end{array}}

(donde el primer número en cada celda es el pago del jugador de la fila y el segundo número es el pago del jugador de la columna).

A modo de ejemplo, consideramos solo estrategias puras. Revisa cada jugador por turno:

El jugador de la fila puede jugar $T$ , que les garantiza un pago de al menos 2 (jugando) $B$ es arriesgado ya que puede dar lugar a un pago 100 - 100, y jugar $M$ puede resultar en un pago de −10). Por lo tanto: ${displaystyle {compline {v_{row}}=2}$ .
El jugador de la columna puede jugar $L$ y asegurar un pago de al menos 0 (jugando) $R$ los pone en riesgo de conseguir ${displaystyle -20}$ ). Por lo tanto: ${displaystyle {compline {v_{col}}=0}$ .

Si ambos jugadores juegan sus respectivas estrategias de maximin ${displaystyle (T,L)}$ , el vector de pago es ${displaystyle (3,1)}$ .

El valor minimax de un jugador es el valor más pequeño que los otros jugadores pueden obligar al jugador a recibir, sin conocer las acciones del jugador; de manera equivalente, es el mayor valor que el jugador puede estar seguro de obtener cuando conoce las acciones de los otros jugadores. Su definición formal es:

{displaystyle {bis}=min} ##{a_{-i}max ¿Qué?

La definición es muy similar a la del valor maximin: solo el orden de los operadores máximo y mínimo es inverso. En el ejemplo anterior:

El jugador de fila puede obtener un valor máximo $4$ (si el otro jugador juega $R$ ) o 5 (si el otro jugador juega $L$ Así que... ${fnMicrosoft Sans Serif}=4$
El jugador de columna puede obtener un valor máximo $1$ (si el otro jugador juega $T$ ), 1 (si $M$ ) o 4 (si $B$ ). Por lo tanto: ${fnMicrosoft Sans Serif}=1.}$

Para cada jugador $i$ , el maximin es como máximo el minimax:

{displaystyle {compline {v_{i}}leq {fnK}}}

Intuitivamente, en maximin la maximización viene después de la minimización, por lo que el jugador $i$ intenta maximizar su valor antes de saber lo que hacen los demás servirá; en minimax, la maximización viene antes que la minimización, por lo que el jugador $i$ está en una posición mucho mejor: maximiza su valor sabiendo lo que hacen los demás hizo.

Otra manera de entender la notación es leyendo de derecha a izquierda: Cuando escribimos

{displaystyle {bis}=min} ##{a_{-i}max ¿Qué? ¿Qué? Grande ¿Por qué? Grande.

el conjunto inicial de resultados ${displaystyle v_{i}(a_{i},a_{-i}) }$ depende de ambos ${displaystyle {a_{i}}$ y ${fnMicrosoft Sans Serif}$ Primero marginar ${displaystyle {a_{i}}}$ desde ${displaystyle v_{i}(a_{i},a_{-i}}$ , maximizando sobre ${displaystyle {a_{i}}$ (por cada valor posible de ${displaystyle {a_{-i}}$ ) para producir un conjunto de resultados marginales ${displaystyle v'_{i}(a_{-i},}$ que depende sólo de ${fnMicrosoft Sans Serif}$ Luego minimizamos ${displaystyle {}}}$ sobre estos resultados. (En cambio para maximizar.)

Aunque siempre es el caso ${displaystyle {compline {v_{row}}leq {fnK}}$ y ${displaystyle {compline {v_{col}}leq {fnMicrosoft Sans Serif}$ el vector de pago resultante de ambos jugadores jugando sus estrategias minimax, ${displaystyle (2,-20)}$ en el caso de ${displaystyle (T,R)}$ o ${displaystyle (-10,1)}$ en el caso de ${displaystyle (M,R),}$ no se puede clasificar igualmente contra el vector de payoff ${displaystyle (3,1) }$ resultado de ambos jugadores jugando su estrategia máxima.

En juegos de suma cero

En los juegos de suma cero de dos jugadores, la solución minimax es la misma que el equilibrio de Nash.

En el contexto de los juegos de suma cero, el teorema minimax es equivalente a:

Para cada dos personas, cero-sum juego con finitamente muchas estrategias, existe un valor $V$ y una estrategia mixta para cada jugador, tal que
a) Dado la estrategia del jugador 2, el mejor pago posible para el jugador 1 es $V$ , y
(b) Given Player 1's strategy, the best payoff possible for Player 2 is − $V$ .

De manera equivalente, la estrategia del Jugador 1 les garantiza un pago de $V$ independientemente de la estrategia del Jugador 2, y del mismo modo, el jugador 2 puede garantizarse un pago de − $V$ . El nombre minimax surge porque cada jugador minimiza el pago máximo posible para el otro; dado que el juego es de suma cero, también minimizan su propia pérdida máxima (es decir, maximizan su pago mínimo). Ver también ejemplo de un juego sin valor.

Ejemplo

Matriz de Payoff para el jugador A
	B elige B1	B elige B2	B elige B3
A elige A1	+3	−2	+2
A elige A2	−1	+0	+4
A elige A3	−4	−3	+ 1

El siguiente ejemplo de un juego de suma cero, donde A y B realizan movimientos simultáneos, ilustra las soluciones maximin. Suponga que cada jugador tiene tres opciones y considere la matriz de pagos para A que se muestra en la tabla ("matriz de pagos para el jugador A"). Suponga que la matriz de pagos para B es la misma matriz con los signos invertidos (es decir, si las opciones son A1 y B1, entonces B paga 3 a A). Entonces, la elección maximin para A es A2, ya que el peor resultado posible es tener que pagar 1, mientras que la elección maximin simple para B es B2, ya que el peor resultado posible es entonces sin pago. Sin embargo, esta solución no es estable, ya que si B cree que A elegirá A2, entonces B elegirá B1 para ganar 1; luego, si A cree que B elegirá B1, entonces A elegirá A1 para ganar 3; y luego B elegirá B2; y eventualmente ambos jugadores se darán cuenta de la dificultad de tomar una decisión. Así que se necesita una estrategia más estable.

Algunas opciones están dominadas por otras y pueden eliminarse: A no elegirá A3 ya que A1 o A2 producirán un mejor resultado, pase lo que pase B elige; B no elegirá B3 ya que algunas mezclas de B1 y B2 producirán un mejor resultado, sin importar lo que elija A.

El jugador A puede evitar tener que hacer un pago esperado de más de 1 /3 eligiendo A1 con probabilidad 1/6 y A2 con probabilidad 5/ 6: El pago esperado para A sería 3 × 1/6 − 1 × 5/ 6 = −+1/3 en caso de que B elija B1 y −2 × 1/ 6 + 0 × 5/6 = −+1/< span class="den">3 en caso de que B elija B2. Del mismo modo, B puede garantizar una ganancia esperada de al menos 1/3, sin importar lo que elija A, usando una estrategia aleatoria de elegir B1 con probabilidad 1/3 y B2 con probabilidad 23. Estas estrategias minimax mixtas no se pueden mejorar y ahora son estables.

Maximín

Con frecuencia, en teoría de juegos, maximin es distinto de minimax. Minimax se usa en juegos de suma cero para denotar minimizar el pago máximo del oponente. En un juego de suma cero, esto es idéntico a minimizar la pérdida máxima propia y maximizar la ganancia mínima propia.

"Maximin" es un término comúnmente utilizado para los juegos de suma distinta de cero para describir la estrategia que maximiza el pago mínimo propio. En los juegos de suma distinta de cero, esto generalmente no es lo mismo que minimizar la ganancia máxima del oponente, ni lo mismo que la estrategia de equilibrio de Nash.

En partidas repetidas

Los valores minimax son muy importantes en la teoría de juegos repetidos. Uno de los teoremas centrales de esta teoría, el teorema popular, se basa en los valores minimax.

Teoría de juegos combinatorios

En la teoría de juegos combinatorios, existe un algoritmo minimax para soluciones de juegos.

Una versión simple del algoritmo minimax, que se indica a continuación, se ocupa de juegos como el tres en raya, donde cada jugador puede ganar, perder o empatar. Si el jugador A puede ganar en un movimiento, su mejor movimiento es ese movimiento ganador. Si el jugador B sabe que un movimiento conducirá a la situación en la que el jugador A puede ganar en un movimiento, mientras que otro movimiento conducirá a la situación en la que el jugador A puede, en el mejor de los casos, hacer tablas, entonces el jugador B&# 39; s mejor movimiento es el que conduce a un empate. Al final del juego, es fácil ver cuál es el "mejor" mover es. El algoritmo minimax ayuda a encontrar el mejor movimiento, trabajando hacia atrás desde el final del juego. En cada paso, se supone que el jugador A intenta maximizar las posibilidades de que A gane, mientras que en el siguiente turno el jugador B intenta minimizar las posibilidades de que A gane (es decir,, para maximizar las propias posibilidades de ganar de B).

Algoritmo Minimax con movimientos alternativos

Un algoritmo minimax es un algoritmo recursivo para elegir el siguiente movimiento en un juego de n jugadores, generalmente un juego de dos jugadores. Se asocia un valor a cada posición o estado del juego. Este valor se calcula mediante una función de evaluación de posición e indica qué tan bueno sería para un jugador alcanzar esa posición. Luego, el jugador realiza el movimiento que maximiza el valor mínimo de la posición resultante de los posibles movimientos posteriores del oponente. Si es el turno de A de moverse, A asigna un valor a cada uno de sus movimientos legales.

Un posible método de asignación consiste en asignar una determinada ganancia a A como +1 ya B como −1. Esto conduce a la teoría de juegos combinatoria desarrollada por J.H. Conway. Una alternativa es usar una regla que si el resultado de un movimiento es una ganancia inmediata para A, se le asigna infinito positivo y si es una ganancia inmediata para B, infinito negativo.. El valor para A de cualquier otro movimiento es el mínimo de los valores resultantes de cada una de las posibles respuestas de B. Por esta razón, A se denomina jugador maximizador y B se denomina jugador minimizador, de ahí el nombre < i>algoritmo minimax. El algoritmo anterior asignará un valor de infinito positivo o negativo a cualquier posición, ya que el valor de cada posición será el valor de alguna posición ganadora o perdedora final. A menudo, esto generalmente solo es posible al final de juegos complicados como el ajedrez o el go, ya que no es computacionalmente factible mirar hacia adelante hasta la finalización del juego, excepto hacia el final, y en su lugar, las posiciones reciben valores finitos. como estimaciones del grado de creencia de que conducirán a una victoria para un jugador u otro.

Esto se puede extender si podemos proporcionar una función de evaluación heurística que dé valores a los estados del juego no finales sin considerar todas las secuencias completas siguientes posibles. Luego, podemos limitar el algoritmo minimax para observar solo un cierto número de movimientos por delante. Este número se denomina "anticipación" y se mide en "capas". Por ejemplo, la computadora de ajedrez Deep Blue (la primera en vencer al actual campeón mundial, Garry Kasparov en ese momento) anticipó al menos 12 capas y luego aplicó una función de evaluación heurística.

Se puede considerar que el algoritmo explora los nodos de un árbol de juegos. El factor de ramificación efectivo del árbol es el número promedio de hijos de cada nodo (es decir, el número promedio de movimientos legales en una posición). El número de nodos a explorar suele aumentar exponencialmente con el número de capas (es menos que exponencial si se evalúan movimientos forzados o posiciones repetidas). El número de nodos a explorar para el análisis de un juego es, por tanto, aproximadamente el factor de ramificación elevado a la potencia del número de capas. Por lo tanto, no es práctico analizar completamente juegos como el ajedrez utilizando el algoritmo minimax.

El rendimiento del algoritmo minimax ingenuo se puede mejorar drásticamente, sin afectar el resultado, mediante el uso de la poda alfa-beta. También se pueden usar otros métodos de poda heurística, pero no se garantiza que todos den el mismo resultado que la búsqueda no podada.

Un algoritmo minimax ingenuo puede modificarse de forma trivial para devolver además una variación principal completa junto con una puntuación minimax.

Pseudocódigo

El pseudocódigo para el algoritmo minimax de profundidad limitada se proporciona a continuación.

función  minimax(nodo, profundidad, maximizingPlayer) es si profundidad = 0 o nodo es un nodo terminal entonces retorno el valor heurístico del nodo
 si maximización Player entoncesvalor:= −∞
 para cada uno niño de nodos dovalor:= max(value, minimax(child, deep − 1, FALSE))
 retorno valor
 más (* minimizing player *)valor:=
 para cada uno niño de nodos dovalor:= min(valor, minimax(niño, profundidad − 1, TRUE)
 retorno valor

(* Primera llamada *)minimax(origen, profundidad, TRUE)

La función minimax devuelve un valor heurístico para los nodos hoja (nodos terminales y nodos en la máxima profundidad de búsqueda). Los nodos que no son hoja heredan su valor de un nodo hoja descendiente. El valor heurístico es una puntuación que mide la favorabilidad del nodo para el jugador que maximiza. Por lo tanto, los nodos que dan como resultado un resultado favorable, como una victoria, para el jugador que maximiza tienen puntajes más altos que los nodos más favorables para el jugador que minimiza. El valor heurístico para los nodos de hoja terminal (fin del juego) son puntajes correspondientes a ganar, perder o empatar, para el jugador que maximiza. Para nodos de hoja no terminales en la máxima profundidad de búsqueda, una función de evaluación estima un valor heurístico para el nodo. La calidad de esta estimación y la profundidad de la búsqueda determinan la calidad y precisión del resultado minimax final.

Minimax trata a los dos jugadores (el jugador maximizador y el reproductor de minimización) por separado en su código. Sobre la base de la observación de que ${displaystyle max(a,b)=-min(-a,-b)}$ minimax puede a menudo ser simplificado en el algoritmo negamax.

Ejemplo

Un ejemplo de árbol minimax

Un ejemplo pedagógico animado que intenta ser amigable con el ser humano sustituyendo valores iniciales infinitos (o arbitrariamente grandes) para el vacío y evitando utilizar las simplificaciones de codificación negamax.

Supongamos que el juego que se está jugando solo tiene un máximo de dos movimientos posibles por jugador en cada turno. El algoritmo genera el árbol de la derecha, donde los círculos representan los movimientos del jugador que ejecuta el algoritmo (jugador maximizador), y los cuadrados representan los movimientos del oponente (jugador minimizador). Debido a la limitación de los recursos informáticos, como se explicó anteriormente, el árbol está limitado a una anticipación de 4 movimientos.

El algoritmo evalúa cada nodo hoja usando una función de evaluación heurística, obteniendo los valores mostrados. Los movimientos en los que el jugador que maximiza gana se asignan con infinito positivo, mientras que los movimientos que conducen a una victoria del jugador que minimiza se asignan con infinito negativo. En el nivel 3, el algoritmo elegirá, para cada nodo, el más pequeño de los valores del nodo secundario y lo asignará a ese mismo nodo (por ejemplo, el nodo de la izquierda elegir el mínimo entre "10" y "+∞", asignándose así el valor "10" a sí mismo). El siguiente paso, en el nivel 2, consiste en elegir para cada nodo el mayor de los valores del nodo secundario. Una vez más, los valores se asignan a cada nodo principal. El algoritmo continúa evaluando los valores máximo y mínimo de los nodos secundarios alternativamente hasta llegar al nodo raíz, donde elige el movimiento con el mayor valor (representado en la figura con una flecha azul). Este es el movimiento que el jugador debe hacer para minimizar la máxima pérdida posible.

Minimax para decisiones individuales

Minimax ante la incertidumbre

La teoría Minimax se ha extendido a decisiones en las que no hay otro jugador, pero en las que las consecuencias de las decisiones dependen de hechos desconocidos. Por ejemplo, decidir prospectar minerales implica un costo, que se desperdiciará si los minerales no están presentes, pero traerá grandes recompensas si los hay. Un enfoque es tratar esto como un juego contra la naturaleza (ver mover por naturaleza), y usando una mentalidad similar a la ley de Murphy o el resistcialismo, adoptar un enfoque que minimice la pérdida máxima esperada, usando las mismas técnicas que en los juegos de suma cero de dos personas.

Además, se han desarrollado árboles expectiminimax, para juegos de dos jugadores en los que el azar (por ejemplo, dados) es un factor.

Criterio minimax en teoría de decisión estadística

En la teoría clásica de la decisión estadística, tenemos un estimador ${displaystyle delta }$ que se utiliza para estimar un parámetro ${displaystyle theta in Theta .}$ También asumen una función de riesgo ${displaystyle R(thetadelta).}$ generalmente especificado como la parte integral de una función de pérdida. En este marco, ${displaystyle {tilde {delta}}$ se llama minimax si es satisfizo

{displaystyle sup _{theta }R(theta{tilde {delta })=inf _{delta }sup _{theta } R(thetadelta).}

Un criterio alternativo en el marco teórico de la decisión es el estimador de Bayes en presencia de una distribución previa ${displaystyle Pi .}$ Un estimador es Bayes si minimiza el promedio riesgo

{displaystyle int _{Theta }R(thetadelta) operatorname {d} Pi (theta).}

Teoría de la decisión no probabilística

Una característica clave de la toma de decisiones minimax es que no es probabilística: a diferencia de las decisiones que utilizan el valor esperado o la utilidad esperada, no hace suposiciones sobre las probabilidades de varios resultados, solo analiza escenarios de cuáles son los posibles resultados. Por lo tanto, es robusto a los cambios en los supuestos, en contraste con estas otras técnicas de decisión. Existen varias extensiones de este enfoque no probabilístico, en particular, el arrepentimiento minimax y la teoría de decisión Info-gap.

Además, minimax solo requiere una medición ordinal (que los resultados se comparen y clasifiquen), no mediciones de intervalo (que los resultados incluyan "cuánto mejor o peor"), y devuelve ordinal datos, usando solo los resultados modelados: la conclusión de un análisis minimax es: "esta estrategia es minimax, ya que el peor de los casos es (resultado), que es menos malo que cualquier otra estrategia". Compare con el análisis del valor esperado, cuya conclusión es de la forma: "Esta estrategia produce $ℰ$ ( $X$ ) = $n$ ." Minimax por lo tanto se puede utilizar en datos ordinales y puede ser más transparente.

Maximin en filosofía

En filosofía, el término "maximin" se usa a menudo en el contexto de Una teoría de la justicia de John Rawls, donde se refiere a ella en el contexto de El principio de diferencia. Rawls definió este principio como la regla que establece que las desigualdades sociales y económicas deben arreglarse de manera que "deben beneficiar al máximo a los miembros menos favorecidos de la sociedad".

Contenido relacionado

Más resultados...