Minimax

El valor maximin es el valor más alto que el jugador puede estar seguro de obtener sin conocer las acciones de los demás jugadores; equivalentemente, es el valor más bajo que los demás jugadores pueden obligar al jugador a recibir cuando conocen la acción del jugador. Su definición formal es: ^{[ 3 ]}

${\displaystyle {\underline {v_{i}}}=\max _{a_{i}}\min _{a_{-i}}{v_{i}(a_{i},a_{-i})}}$

Dónde:

• i es el índice del jugador de interés.
• ${\displaystyle -i}$denota a todos los demás jugadores excepto al jugador i .
• ${\displaystyle a_{i}}$es la acción realizada por el jugador i .
• ${\displaystyle a_{-i}}$Indica las acciones realizadas 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 mediante un enfoque de peor caso: para cada acción posible del jugador, se comprueban todas las acciones posibles de los demás jugadores y se determina la peor combinación posible de acciones, aquella que le da al jugador i el valor más pequeño. Luego, se determina qué acción puede realizar el jugador i para asegurar que este valor mínimo sea el más alto posible.

Por ejemplo, consideremos el siguiente juego para dos jugadores, donde el primer jugador ("jugador de fila") puede elegir cualquiera de tres movimientos, etiquetados como T , M o B , y el segundo jugador ("jugador de columna") puede elegir cualquiera de 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|cc}\hline &L&R\\\hline T&3,1&2,-20\\M&5,0&-10,1\\B&-100,2&4,4\\\hline \end{array}}}$

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

A modo de ejemplo, consideraremos únicamente estrategias puras . Analicemos a cada jugador por separado:

• El jugador de fila puede jugar T , lo que le garantiza una recompensa de al menos2 (jugar B es arriesgado ya que puede llevar a una recompensa)−100 y jugar M puede resultar en una recompensa de−10 ). Por lo tanto:${\displaystyle {\underline {v_{row}}}=2}$.
• El jugador de columna puede jugar L y asegurar una ganancia de al menos0 (jugar R los pone en riesgo de obtener${\displaystyle -20}$). Por eso:${\displaystyle {\underline {v_{col}}}=0}$.

Si ambos jugadores aplican sus respectivas estrategias 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 demás jugadores pueden obligarle a recibir, sin conocer sus acciones; equivalentemente, es el valor más grande que el jugador puede estar seguro de obtener cuando conoce las acciones de los demás jugadores. Su definición formal es: ^{[ 3 ]}

${\displaystyle {\overline {v_{i}}}=\min _{a_{-i}}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}}$

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

• El jugador de la fila puede obtener un valor máximo de 4 (si el otro jugador juega R ) o5 (si el otro jugador juega L ), entonces:${\displaystyle {\overline {v_{row}}}=4\ .}$
• El jugador de la columna puede obtener un valor máximo de 1 (si el otro jugador juega T ),1 (si M ) o4 (si B ). Por lo tanto:${\displaystyle {\overline {v_{col}}}=1\ .}$

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

${\displaystyle {\underline {v_{i}}}\leq {\overline {v_{i}}}}$

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 harán los demás; en minimax la maximización viene antes de la minimización, por lo que el jugador i está en una posición mucho mejor: maximiza su valor sabiendo lo que hicieron los demás.

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

${\displaystyle {\overline {v_{i}}}=\min _{a_{-i}}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}=\min _{a_{-i}}{\Big (}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}{\Big )}}$

el conjunto inicial de resultados${\displaystyle \ v_{i}(a_{i},a_{-i})\ }$depende de ambos${\displaystyle \ {a_{i}}\ }$y${\displaystyle \ {a_{-i}}\ .}$Primero marginamos${\displaystyle {a_{i}}}$de${\displaystyle v_{i}(a_{i},a_{-i})}$, maximizando sobre${\displaystyle \ {a_{i}}\ }$(para cada posible valor de${\displaystyle {a_{-i}}}$) para producir un conjunto de resultados marginales${\displaystyle \ v'_{i}(a_{-i})\,,}$que depende únicamente de${\displaystyle \ {a_{-i}}\ .}$Luego minimizamos sobre${\displaystyle \ {a_{-i}}\ }$sobre estos resultados. (Por el contrario, para maximin.)

Aunque siempre es así que${\displaystyle \ {\underline {v_{row}}}\leq {\overline {v_{row}}}\ }$y${\displaystyle \ {\underline {v_{col}}}\leq {\overline {v_{col}}}\,,}$el vector de pagos resultante de que ambos jugadores apliquen 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 de manera similar frente al vector de pago${\displaystyle \ (3,1)\ }$como resultado de que ambos jugadores aplicaran su estrategia maximin.

En los juegos de suma cero para 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: ^{[ 4 ]}

Para cada juego de suma cero de dos personas con un número finito de estrategias, existe un valor V y una estrategia mixta para cada jugador, tal que

(a) Dada  la estrategia del Jugador 2, la mejor recompensa posible para el Jugador  1 es V y

(b) Dada  la estrategia del Jugador 1, la mejor recompensa posible para el Jugador 2 es − V .

De forma equivalente,  la estrategia del Jugador 1 le garantiza una ganancia de V independientemente de  la estrategia del Jugador 2, y de manera similar, el Jugador  2 puede garantizarse una ganancia de −V . El nombre minimax surge porque cada jugador minimiza la ganancia máxima 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 ganancia mínima). Véase también el ejemplo de un juego sin valor .

El siguiente ejemplo de un juego de suma cero, donde A y B realizan movimientos simultáneos, ilustra las soluciones maximin . Supongamos que cada jugador tiene tres opciones y consideremos la matriz de pagos para A que se muestra en la mesa ("Matriz de pagos para el jugador  A"). Supongamos 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 opción maximin para A es A2, ya que el peor resultado posible es tener que pagar  1, mientras que la opción maximin simple para B es B2, ya que el peor resultado posible es no pagar nada. 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. Por lo tanto, se necesita una estrategia más estable.

Algunas opciones están dominadas por otras y pueden eliminarse: A no elegirá A3 ya que tanto A1 como A2 producirán un mejor resultado, independientemente de lo que elija B ; B no elegirá B3 ya que algunas combinaciones de B1 y B2 producirán un mejor resultado, independientemente de 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 : La ganancia esperada para A sería 3 × 1/6 - 1 × 5/6 = - +1/3 en caso de que B eligiera B1 y -2 × 1/6 + 0 × 5/6 = - +1/3 en caso de que B eligiera B2 . ​​ De manera similar , B puede asegurar una ganancia esperada de al menos 1/3 , sin importar lo que elija A , mediante una estrategia aleatoria de elegir B1 con probabilidad 1/3 y B2 con probabilidad 2/3 . Estas estrategias minimax mixtas no se pueden mejorar y ahora son estables.

En teoría de juegos, el término maximin suele distinguirse del término minimax. En juegos de suma cero, minimax se utiliza para denotar la minimización de la ganancia máxima del oponente. En un juego de suma cero , esto equivale a minimizar la propia pérdida máxima y a maximizar la propia ganancia mínima.

"Maximin" es un término comúnmente utilizado en juegos de suma no nula para describir la estrategia que maximiza la propia ganancia mínima. En juegos de suma no nula, esto generalmente no es lo mismo que minimizar la ganancia máxima del oponente, ni tampoco es lo mismo que la estrategia de equilibrio de Nash .

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.

Un algoritmo minimax ^{[ 5 ]} es un algoritmo recursivo para elegir el siguiente movimiento en un juego de n jugadores , generalmente un juego de dos jugadores. A cada posición o estado del juego se le asocia un valor. 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. El jugador entonces realiza el movimiento que maximiza el valor mínimo de la posición resultante de los posibles movimientos siguientes del oponente. Si es ACuando le toca mover a A, A le da un valor a cada uno de sus movimientos legales.

Un posible método de asignación consiste en asignar una determinada victoria a A como +1 y a B como −1. Esto conduce a la teoría de juegos combinatorios desarrollada por John H. Conway . Una alternativa es utilizar una regla según la cual, si el resultado de un movimiento es una victoria inmediata para A , se le asigna infinito positivo, y si es una victoria inmediata para B , infinito negativo. El valor para A de cualquier otro movimiento es el máximo de los valores resultantes de cada uno de los movimientos de B.posibles respuestas. Por esta razón, A se llama el jugador maximizador y B se llama el jugador minimizador , de ahí el nombre 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 final ganadora o perdedora. A menudo, esto generalmente solo es posible al final de juegos complicados como el ajedrez o el go , ya que no es computacionalmente factible anticipar hasta la finalización del juego, excepto hacia el final, y en cambio, a las posiciones se les dan valores finitos como estimaciones del grado de creencia de que conducirán a una victoria para un jugador u otro.

Esto se puede ampliar si podemos proporcionar una función de evaluación heurística que asigne valores a estados de juego no finales sin considerar todas las posibles secuencias completas subsiguientes. Entonces podemos limitar el algoritmo minimax para que solo considere un cierto número de movimientos por adelantado. Este número se denomina "anticipación" y se mide en " plies ". Por ejemplo, el ordenador de ajedrez Deep Blue (el primero en vencer a un campeón mundial vigente, Garry Kasparov en ese momento) anticipó al menos 12  plies y luego aplicó una función de evaluación heurística. ^{[ 6 ]}

El algoritmo puede concebirse como la exploración de los nodos de un árbol de juego . 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 jugadas (es menor que exponencial si se evalúan movimientos forzados o posiciones repetidas). Por lo tanto, el número de nodos a explorar para el análisis de una partida es aproximadamente igual al factor de ramificación elevado al número de jugadas. En consecuencia, resulta poco práctico analizar completamente juegos como el ajedrez utilizando el algoritmo minimax.

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

Un algoritmo minimax ingenuo puede modificarse fácilmente para que, además, devuelva una variación principal completa junto con una puntuación minimax.

A continuación se muestra el pseudocódigo del algoritmo minimax con limitación de profundidad.

La función minimax(nodo, profundidad, jugadormaximizador) es si profundidad = 0 o nodo es un nodo terminal entonces devuelve el valor heurístico de nodo si jugadormaximizador entonces valor := −∞ para cada hijo del nodo hacer valor := max(valor, minimax(hijo, profundidad − 1, FALSO)) valor de retorno de lo contrario (* minimizando jugador *) valor := +∞ para cada hijo del nodo hacer valor := min(valor, minimax(hijo, profundidad − 1, VERDADERO)) valor de retorno

(* Llamada inicial *) minimax(origen, profundidad, VERDADERO)

La función minimax devuelve un valor heurístico para los nodos hoja (nodos terminales y nodos en la profundidad de búsqueda máxima). Los nodos no 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 busca maximizar. Por lo tanto, los nodos que resultan en un resultado favorable, como una victoria, para el jugador que busca maximizar tienen puntuaciones más altas que los nodos más favorables para el jugador que busca minimizar. El valor heurístico para los nodos hoja terminales (que finalizan el juego) corresponde a las puntuaciones de victoria, derrota o empate para el jugador que busca maximizar. Para los nodos hoja no terminales en la profundidad de búsqueda máxima, una función de evaluación estima un valor heurístico para el nodo. La calidad de esta estimación y la profundidad de búsqueda determinan la calidad y precisión del resultado final de minimax.

Minimax trata a los dos jugadores (el jugador que maximiza y el jugador que minimiza) por separado en su código. Basándose en la observación de que${\displaystyle \ \max(a,b)=-\min(-a,-b)\ ,}$El algoritmo minimax a menudo se puede simplificar al algoritmo negamax .

Supongamos que el juego solo permite un máximo de dos movimientos 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 que maximiza ) y los cuadrados representan los movimientos del oponente ( jugador que minimiza ). Debido a la limitación de recursos computacionales, como se explicó anteriormente, el árbol solo permite anticipar cuatro  movimientos.

El algoritmo evalúa cada nodo hoja utilizando una función de evaluación heurística, obteniendo los valores mostrados. A los movimientos donde gana el jugador que maximiza se les asigna infinito positivo, mientras que a los movimientos que llevan a una victoria del jugador que minimiza se les asigna infinito negativo. En el nivel  3, el algoritmo elegirá, para cada nodo, el menor de los valores del nodo hijo y se 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"). El siguiente paso, en el nivel  2, consiste en elegir para cada nodo el mayor de los valores del nodo hijo . Una vez más, los valores se asignan a cada nodo padre . El algoritmo continúa evaluando los valores máximo y mínimo de los nodos hijos alternativamente hasta que llega 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 pérdida máxima posible .

La teoría minimax se ha extendido a decisiones en las que no hay otro jugador, pero cuyas consecuencias dependen de hechos desconocidos. Por ejemplo, decidir explorar en busca de minerales implica un coste, que se desperdiciará si no se encuentran, pero que reportará grandes beneficios si sí se encuentran. Un enfoque consiste en tratar esto como un juego contra la naturaleza (véase " movimiento por la naturaleza ") y, utilizando una mentalidad similar a la de la ley de Murphy o el resistencialismo , adoptar una estrategia que minimice la pérdida máxima esperada, empleando las mismas técnicas que en los juegos de suma cero para dos jugadores.

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

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 asumimos una función de riesgo.${\displaystyle \ R(\theta ,\delta )\ .}$generalmente se especifica como la integral de una función de pérdida . En este marco,${\displaystyle \ {\tilde {\delta }}\ }$Se denomina minimax si satisface

${\displaystyle \sup _{\theta }R(\theta ,{\tilde {\delta }})=\inf _{\delta }\ \sup _{\theta }\ R(\theta ,\delta )\ .}$

Un criterio alternativo en el marco de la teoría de la decisión es el estimador bayesiano en presencia de una distribución a priori.${\displaystyle \Pi \ .}$Un estimador es bayesiano si minimiza el riesgo promedio.

${\displaystyle \int _{\Theta }R(\theta ,\delta )\ \operatorname {d} \Pi (\theta )\ .}$

Una característica clave de la toma de decisiones minimax es su carácter no probabilístico: a diferencia de las decisiones que utilizan el valor esperado o la utilidad esperada , no presupone ninguna probabilidad de los distintos resultados, sino que se limita a analizar los posibles escenarios. Por lo tanto, es robusta ante cambios en las suposiciones, a diferencia de otras técnicas de decisión. Existen diversas extensiones de este enfoque no probabilístico, como el arrepentimiento minimax y la teoría de la decisión de la brecha de información .

Además, el método minimax solo requiere mediciones ordinales (que los resultados se comparen y clasifiquen), no mediciones de intervalo (que los resultados incluyan "cuánto mejor o peor"), y devuelve datos ordinales, utilizando únicamente los resultados modelados: la conclusión de un análisis minimax es: "esta estrategia es minimax, ya que el peor caso es (resultado), que es menos malo que cualquier otra estrategia". Compárese con el análisis de valor esperado, cuya conclusión es de la forma: "Esta estrategia produce ℰ ( X ) = n ". Por lo tanto, minimax se puede utilizar con datos ordinales y puede ser más transparente.