Minimax (a veces Minmax , MM [1] o punto de silla [2] ) es una regla de decisión utilizada en inteligencia artificial , teoría de decisiones , teoría de juegos , estadística 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 formulada para la teoría de juegos de suma cero de varios jugadores , que cubre 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 general en presencia de incertidumbre.
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; equivalentemente, 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: [3]
Dónde:
El cálculo del valor máximo de un jugador se realiza siguiendo el enfoque del peor caso posible: para cada acción posible del jugador, comprobamos todas las acciones posibles de los demás jugadores y determinamos la peor combinación posible de acciones (la que le da al jugador i el valor más bajo). A continuación, determinamos qué acción puede realizar el jugador i para asegurarnos de que este valor más bajo 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 tres movimientos, etiquetados 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:
(donde el primer número en cada una de las celdas 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, consideraremos únicamente estrategias puras . Compruebe cada jugador por turno:
Si ambos jugadores juegan sus respectivas estrategias maximin , el vector de pago es .
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; equivalentemente, es el valor más grande que el jugador puede estar seguro de obtener cuando conoce las acciones de los otros jugadores. Su definición formal es: [3]
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:
Para cada jugador i , el maximin es como máximo el minimax:
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
el conjunto inicial de resultados depende de ambos y Primero marginalizamos alejándonos de , maximizando sobre (para cada valor posible de ) para obtener un conjunto de resultados marginales que depende solo de Luego minimizamos sobre sobre estos resultados. (A la inversa para maximin.)
Si bien siempre es el caso de que y el vector de pago resultante de que ambos jugadores jueguen sus estrategias minimax, en el caso de o en el caso de no se puede clasificar de manera similar frente al vector de pago resultante de que ambos jugadores jueguen sus estrategias maximin.
En 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] [ verificación fallida ]
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, el mejor pago posible para el Jugador 1 es V , y
- (b) Dada la estrategia del Jugador 1, el mejor pago posible para el Jugador 2 es − V .
De manera 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 un valor .
El siguiente ejemplo de un juego de suma cero, donde A y B hacen movimientos simultáneos, ilustra soluciones maximin . Supongamos que cada jugador tiene tres opciones y consideramos 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 que no haya 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 finalmente ambos jugadores se darán cuenta de la dificultad de hacer una elecció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, sin importar lo que elija B ; 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 realizar 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 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 , no importa lo que elija A , utilizando una estrategia aleatoria de elegir B1 con probabilidad1/ 3 y B2 con probabilidad 2/ 3 Estas estrategias minimax mixtas no se pueden mejorar y ahora son estables .
Con frecuencia, en la teoría de juegos, maximin se distingue de minimax. Minimax se utiliza en juegos de suma cero para indicar que se minimiza la máxima ganancia del oponente. En un juego de suma cero , esto es idéntico a minimizar la pérdida máxima propia y a maximizar la ganancia mínima propia.
"Maximin" es un término que se utiliza habitualmente en los juegos de suma no nula para describir la estrategia que maximiza la ganancia mínima propia. En los juegos de suma no nula, esto no suele ser lo mismo que minimizar la ganancia máxima del oponente ni 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.
En la teoría de juegos combinatorios , existe un algoritmo minimax para las soluciones del juego.
Una versión simple del algoritmo minimax , que se describe a continuación, se aplica a juegos como el tres en raya , en el que cada jugador puede ganar, perder o empatar. Si el jugador A puede ganar en un movimiento, su mejor movimiento es el 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, empatar, entonces el mejor movimiento del jugador B es el que conduce al empate. Más adelante en el juego, es fácil ver cuál es el "mejor" movimiento. El algoritmo minimax ayuda a encontrar el mejor movimiento, trabajando hacia atrás desde el final del juego. En cada paso, supone que el jugador A está tratando de maximizar las posibilidades de que A gane, mientras que en el siguiente turno el jugador B está tratando de minimizar las posibilidades de que A gane (es decir, maximizar las propias posibilidades de B de ganar).
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 por medio de 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 siguientes del oponente. Si es el turno de A de mover, A le da un valor a cada uno de sus movimientos legales.
Un posible método de asignación consiste en asignar una cierta victoria para A como +1 y para 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 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 de 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 solo es posible al final de juegos complicados como ajedrez o go , ya que no es computacionalmente factible mirar hacia el futuro hasta la finalización del juego, excepto hacia el final, y en su lugar, a las posiciones se les dan valores finitos como estimaciones del grado de creencia de que conducirán a una victoria para uno u otro jugador.
Esto se puede ampliar si podemos proporcionar una función de evaluación heurística que dé valores a los estados no finales del juego sin considerar todas las posibles secuencias completas siguientes. Entonces podemos limitar el algoritmo minimax para que observe solo un cierto número de movimientos por delante. Este número se llama "look-ahead", medido en " plies ". Por ejemplo, la computadora de ajedrez Deep Blue (la primera en vencer al campeón mundial reinante, Garry Kasparov en ese momento) miró hacia adelante al menos 12 plies, luego aplicó una función de evaluación heurística. [6]
El algoritmo puede considerarse como una 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 generalmente aumenta 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 el factor de ramificación elevado a la potencia del número de jugadas. Por lo tanto, no es práctico analizar por completo partidas 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 utilizar otros métodos de poda heurística, pero no se garantiza que todos ellos den el mismo resultado que la búsqueda sin poda.
Un algoritmo minimax ingenuo puede modificarse de manera trivial para devolver además una variación principal completa junto con una puntuación minimax.
A continuación se proporciona el pseudocódigo para el algoritmo minimax con profundidad limitada.
La función minimax(nodo, profundidad, maximizingPlayer) es si la profundidad = 0 o el nodo es un nodo terminal , entonces devuelve el valor heurístico del nodo si maximizingPlayer entonces valor := −∞ Para cada hijo del nodo hacer valor := máx(valor, minimáx(hijo, profundidad − 1, FALSO)) valor de retorno else (*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 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 maximizador. Por lo tanto, los nodos que resultan en un resultado favorable, como una victoria, para el jugador maximizador tienen puntuaciones más altas que los nodos más favorables para el jugador minimizador. El valor heurístico para los nodos hoja terminales (final del juego) son puntuaciones correspondientes a la victoria, la derrota o el empate, para el jugador maximizador. 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 la precisión del resultado minimax final.
Minimax trata a los dos jugadores (el jugador que maximiza y el jugador que minimiza) por separado en su código. Basado en la observación de que minimax a menudo puede simplificarse en el algoritmo 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 que maximiza ) y los cuadrados representan los movimientos del oponente ( jugador que minimiza ). Debido a la limitación de los recursos computacionales, como se explicó anteriormente, el árbol está limitado a una previsión de 4 movimientos.
El algoritmo evalúa cada nodo hoja mediante una función de evaluación heurística, obteniendo los valores que se muestran. Las jugadas donde gana el jugador maximizador se asignan con infinito positivo, mientras que las jugadas que llevan a una victoria del jugador minimizador se asignan con infinito negativo. En el nivel 3, el algoritmo elegirá, para cada nodo, el menor de los valores del nodo hijo , y lo asignará a ese mismo nodo (p. ej. el nodo de la izquierda elegirá el mínimo entre "10" y "+∞", asignándose por tanto 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 hijo . Una vez más, los valores se asignan a cada nodo padre . El algoritmo continúa evaluando alternativamente los valores máximo y mínimo de los nodos hijos hasta llegar al nodo raíz , donde elige la jugada con el valor mayor (representado en la figura con una flecha azul). Esta es la jugada que el jugador debe realizar para minimizar la máxima pérdida posible .
La teoría del minimax se ha extendido a decisiones en las que no hay otro jugador, pero cuyas consecuencias dependen de hechos desconocidos. Por ejemplo, decidir buscar minerales implica un coste, que se desperdiciará si los minerales no están presentes, pero que traerá grandes recompensas si están. Un enfoque es tratar esto como un juego contra la naturaleza (véase mover por naturaleza ) y, utilizando una mentalidad similar a la ley de Murphy o al resistencialismo , adoptar un enfoque que minimice la pérdida máxima esperada, utilizando las mismas técnicas que en los juegos de suma cero entre dos personas.
Además, se han desarrollado árboles expectiminimax , para juegos de dos jugadores en los que el azar (por ejemplo, los dados) es un factor.
En la teoría clásica de decisiones estadísticas , tenemos un estimador que se utiliza para estimar un parámetro. También suponemos una función de riesgo que normalmente se especifica como la integral de una función de pérdida . En este marco, se denomina minimax si satisface
Un criterio alternativo en el marco teórico de la decisión es el estimador de Bayes en presencia de una distribución previa. Un estimador es Bayes si minimiza el riesgo promedio .
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 un análisis de escenarios de cuáles son los resultados posibles. Por lo tanto, es robusta a los cambios en las suposiciones, a diferencia de estas otras técnicas de decisión. Existen varias extensiones de este enfoque no probabilístico, en particular la teoría de la decisión minimax sobre el arrepentimiento y la teoría de la brecha de información .
Además, el 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 datos ordinales, utilizando solo 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 del valor esperado, cuya conclusión es de la forma: "Esta estrategia produce ℰ ( X ) = n ." Por lo tanto, el minimax se puede utilizar en datos ordinales y puede ser más transparente.
El concepto de voto por el “ mal menor ” (VML) puede verse como una forma de la estrategia minimax, según la cual los votantes, cuando se enfrentan a dos o más candidatos, eligen al que perciben como el menos dañino o el “mal menor”. Para ello, “el voto no debería verse como una forma de autoexpresión personal o juicio moral dirigido en represalia hacia los candidatos de los principales partidos que no reflejan nuestros valores, o de un sistema corrupto diseñado para limitar las opciones a aquellas aceptables para las élites corporativas”, sino más bien como una oportunidad para reducir el daño o la pérdida. [7]
En filosofía, el término "maximin" se utiliza a menudo en el contexto de la Teoría de la justicia de John Rawls , donde se refiere a él en el contexto de El principio de diferencia . [8] Rawls definió este principio como la regla que establece que las desigualdades sociales y económicas deben organizarse de modo que "sean del mayor beneficio para los miembros menos aventajados de la sociedad". [9] [10]
Durante la partida de 1997, la búsqueda de software extendió la búsqueda a aproximadamente 40 capas a lo largo de las líneas de forzamiento, aunque la búsqueda no extendida alcanzó solo aproximadamente 12 capas.
