Minimax, La teoría de juegos, La teoría de juegos Combinatoria, Minimax para las decisiones individuales, Maximin en la filosofía

Minimax es una regla de decisión utilizado en teoría de la decisión, la teoría de juegos, la estadística y la filosofía para reducir al mínimo la pérdida posible para un escenario del peor caso. Alternativamente, puede ser pensado como la maximización de la ganancia mínima. Originalmente formulado para dos jugadores en la teoría de juegos de suma cero, que abarca tanto los casos en que los jugadores tienen movimientos alternativos y aquellos donde se hacen movimientos simultáneos, sino que también se ha extendido a los juegos más complejos y de toma de decisiones en presencia de incertidumbre en la decisión general.

La teoría de juegos

En la teoría de juegos simultáneos, una estrategia minimax es una estrategia mixta que es parte de la solución a un juego de suma cero. En los juegos de suma cero, la solución minimax es el mismo que el equilibrio de Nash.

Teorema Minimax

El teorema minimax

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

Teniendo en cuenta la estrategia del jugador 2, la mejor recompensa posible para el jugador 1 es V, y dada la estrategia del jugador 1, la mejor recompensa posible para el jugador 2 es-V.

Equivalente, la estrategia del jugador 1 le garantiza un pago de V, independientemente de la estrategia del jugador 2, y del mismo modo el jugador 2 puede garantizar a sí mismo una recompensa de-V. El nombre minimax se debe a que cada jugador minimiza la máxima rentabilidad posible para el otro, ya que el juego es de suma cero, sino que también minimiza su pérdida máxima.

Este teorema fue creado por John von Neumann, quien es citado diciendo "Por lo que puedo ver, no puede haber teoría de juegos sin que el teorema pensé que no había nada digno de publicarse hasta que el teorema Minimax se demostró".

Ver minimax teorema de Sion y el teorema de Parthasarathy de generalizaciones, véase también el ejemplo de un juego sin un valor.

Ejemplo

El siguiente ejemplo de un juego de suma cero, donde A y B hacen movimientos simultáneos, ilustra soluciones minimax. Supongamos que cada jugador tiene tres opciones y considerar la matriz de pagos para A se muestra a la derecha. Supongamos que la matriz de pagos para B es la misma matriz con las señales invertidas. Entonces, la elección minimax para A es A2 ya que el resultado posible peor es luego tener que pagar 1, mientras que la elección minimax simple para B es B2 ya que el peor resultado posible es entonces ningún pago. Sin embargo, esta solución no es estable, ya que si B cree que A se elige A2 entonces B elegirá B1 para obtener 1, entonces si A cree que B escogerá B1 entonces A elegir A1 para ganar 3, y luego B elegirán B2, y finalmente, los dos jugadores se darán cuenta de la dificultad de hacer una elección. Por lo tanto se necesita una estrategia más estable.

Algunas de las opciones están dominados por otros y pueden ser eliminados: A no elegirán A3 ya sea A1 o A2 producirán un mejor resultado, no importa lo elige B; B no elegirán B3 ya que algunas mezclas de B1 y B2 se producirá un mejor resultado , sin importar lo que A elige.

A puede evitar tener que hacer un pago esperado de más de 1/3 por la elección de A1 con una probabilidad de 1/6 y A2 con una probabilidad de 5/6: El pago esperado para A sería 3 * -1 * = -1/3 en el caso B eligió B1 y -2 * 0 * = -1/3 en el caso B eligió B2 - Del mismo modo, B puede garantizar una ganancia esperada de al menos 1/3, no importa lo que A elige, mediante el uso de una estrategia aleatorizado de elegir B1 con una probabilidad de 1/3 y B2 con una probabilidad de 2/3 - Estas estrategias minimax mixtos son ahora estable y no se pueden mejorar.

Maximin

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

"Maximin" es un término comúnmente utilizado para los juegos de no-cero-suma para describir la estrategia que maximiza la propia rentabilidad mínima. En juegos de no-cero-suma, esto no es generalmente el mismo que minimizar la ganancia máxima que el rival, ni la misma que la estrategia de equilibrio de Nash.

La teoría de juegos Combinatoria

En la teoría de juegos combinatoria, hay un algoritmo Minimax para soluciones de juego.

Una versión simple del algoritmo minimax, que a continuación, se refiere a juegos como el tic-tac-dedo del pie, donde cada jugador puede ganar, perder o dibujar. Si el jugador A puede ganar en un solo movimiento, la mejor jugada es la jugada ganadora. Si el jugador B sabe que una medida dará lugar a la situación en la que el jugador A puede ganar en un solo movimiento, mientras que otra medida dará lugar a la situación en la que el jugador A puede, como mucho, dibujar, entonces mejor jugada del jugador B es el que conduce a una dibujar. Al final del partido, es fácil ver por qué la "mejor" decisión es. El algoritmo Minimax ayuda a encontrar la mejor jugada, trabajando hacia atrás desde el final del juego. En cada paso se supone que el jugador A está tratando de maximizar las posibilidades de una victoria, mientras que en el siguiente turno el jugador B está tratando de reducir al mínimo las posibilidades de una victoria.

Algoritmo Minimax con movimientos alternativos

Un algoritmo minimax es un algoritmo recursivo para elegir el siguiente movimiento en un juego de n-jugador, por lo general un juego de dos jugadores. Un valor está asociado con cada posición o estado del juego. Este valor se calcula por medio de una función de evaluación de la posición e indica lo bueno que sería para un jugador en alcanzar esa posición. Entonces, el jugador hace el movimiento que maximiza el valor mínimo de la posición resultante de posibles siguientes movimientos del oponente. Si se trata de un turno para mover, A da un valor a cada uno de sus movimientos legales.

Un método de asignación posible consiste en asignar un cierto triunfo para A como para la B y 1 como -1 - Esto nos lleva a la teoría de juegos combinatorios como el desarrollado por John Horton Conway. Una alternativa utiliza una regla de que si el resultado de un movimiento es una victoria inmediata para A se le asigna infinito positivo y, si se trata de una victoria inmediata para B, infinito negativo. El valor de 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 llama el jugador maximización y B se llama el jugador minimizando, por lo tanto, el algoritmo Minimax nombre. El algoritmo anterior asignará un valor de infinito positivo o negativo a cualquier posición ya que el valor de todas las posiciones será el valor de alguna de ganar final o perder la posición. A menudo, generalmente esto sólo es posible en el final de los juegos complicados como el ajedrez o ir, ya que no es computacionalmente factible para mirar hacia adelante en cuanto a la terminación del juego, excepto hacia el final, y en lugar de posiciones se dan como valores finitos estimaciones del grado de creencia que van a llevar a una victoria de un jugador u otro.

Esto se puede ampliar si se puede suministrar una función de evaluación heurística, que da valores a los estados de caza, no finales sin tener en cuenta todas las posibles siguientes secuencias completas. A continuación, puede limitar el algoritmo minimax para que busque sólo en un cierto número de movimientos por delante. Este número se conoce como el "look-ahead", medida en "capas". Por ejemplo, la computadora de ajedrez Deep Blue miraba hacia delante al menos 12 capas, a continuación, se aplica una función de evaluación heurística.

El algoritmo puede ser pensado como la exploración de los nodos de un árbol de juego. El factor de ramificación efectiva del árbol es el número promedio de hijos de cada nodo. El número de nodos a ser explorado por lo general aumenta exponencialmente con el número de capas. Por consiguiente, el número de nodos a ser exploradas para el análisis de un juego es aproximadamente el factor de ramificación elevado a la potencia del número de capas. Por lo tanto, es poco práctico para analizar completamente juegos como el ajedrez usando el algoritmo Minimax.

El rendimiento del algoritmo Minimax nave puede mejorarse drásticamente, sin afectar el resultado, por el uso de la poda alfa-beta. Otros métodos heurísticos de poda también se pueden utilizar, pero no todos ellos están garantizados para dar el mismo resultado que la búsqueda de la ONU-podados.

Un algoritmo minimax nave puede ser trivialmente modificado para volver, además, toda una Variación Principal junto con una puntuación minimax.

Lua ejemplo

función minimax si la profundidad <= 0, entonces los valores positivos son buenas para el jugador que maximiza los valores negativos son buenas para el jugador retorno objective_value fines jugador maximizar minimizar se minimiza jugador es alfa = locales-node.player * agencia local INFINITY = next_child mientras el niño ~ = nil do local Resultado = minimax alfa = node.player == 1 y Math.Max o hijo Math.min = next_child end end alfa regreso

Pseudocódigo

Pseudocódigo de la versión Negamax del algoritmo minimax es la siguiente.

El código se basa en la observación de que. Esto evita la necesidad de que el algoritmo para el tratamiento de los dos jugadores por separado, pero no se puede utilizar para los juegos donde un jugador puede tener dos vueltas en sucesión.

función entero minimax si el nodo es un nodo terminal o profundidad <= 0: devuelve el valor heurístico del nodo a: = -8 para el niño en el nodo: # evaluación es idéntica para ambos jugadores a: = max devuelve un

Ejemplo

Supongamos que el juego está jugado sólo tiene un máximo de dos posibles 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, y los cuadrados representan los movimientos del oponente. Debido a la limitación de los recursos de cálculo, como se explicó anteriormente, el árbol se limita a un aspecto de la ventaja de 4 mueve.

El algoritmo evalúa cada nodo de la hoja usando una función de evaluación heurística, la obtención de los valores que se muestran. Los movimientos en los triunfos del jugador maximización se asignan con el infinito positivo, mientras que los movimientos que conducen a la victoria del jugador de minimización se asignan con el infinito negativo. En el nivel 3, el algoritmo elegirá, para cada nodo, el más pequeño de los valores de nodo secundario, y asignarlo a ese mismo nodo. El siguiente paso, en el nivel 2, consiste en elegir para cada nodo de la más grande de los valores de nodo secundario. Una vez más, los valores son asignados a cada nodo padre. El algoritmo continúa la evaluación de los valores máximos y mínimos de los nodos secundarios alternativamente hasta que se alcanza el nodo raíz, donde se elige el movimiento con el valor más grande. Este es el movimiento que el jugador debe hacer con el fin de minimizar la pérdida máxima posible.

Minimax para las decisiones individuales

Minimax en un contexto de incertidumbre

Teoría Minimax se ha extendido a las decisiones donde no hay otro jugador, pero donde las consecuencias de las decisiones dependerá de hechos desconocidos. Por ejemplo, la decisión de la prospección de minerales conlleva un coste que será desperdiciado si los minerales que no están presentes, pero traerá grandes recompensas si que son. Un método consiste en tratar esto como un juego contra la naturaleza y el uso de una mentalidad similar a la ley de Murphy, adoptar un enfoque que minimiza la pérdida máxima esperada, utilizando las mismas técnicas que en los juegos de suma cero de dos personas.

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

Minimax criterio en la teoría de la decisión estadística

En la teoría de decisión estadística clásica, tenemos un estimador que se utiliza para estimar un parámetro. También asumimos una función de riesgo, por lo general se especifica como la integral de una función de pérdida. En este marco, se llama minimax si satisface

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

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

Una característica clave de la toma de decisión minimax es ser no probabilística: en contraste con las decisiones con valor esperado o utilidad esperada, que no hace suposiciones acerca de las probabilidades de los distintos resultados, sólo el análisis de escenarios de lo que los resultados son posibles. Por tanto, es robusta a los cambios en los supuestos, como estas otras técnicas de decisión no lo son. Existen varias extensiones de este método no probabilístico, arrepentimiento minimax particular y teoría de la decisión Info-gap.

Además, minimax sólo requiere la medición ordinal, no mediciones de intervalos, y devuelve los datos ordinales, utilizando sólo los resultados del modelo: la conclusión de un análisis de minimax es: "esta estrategia minimax, como el peor caso es, que es menos malo que cualquier otro estrategia ". Compare con el análisis del valor esperado, cuya conclusión es de la forma: "esto produce la estrategia E = n." Minimax por lo tanto se puede utilizar en los datos ordinales, y puede ser más transparente.

Maximin en la filosofía

En filosofía, el término "maximin" se utiliza a menudo en el contexto de John Rawls A Theory of Justice, donde se hace referencia a ella en el contexto del principio de la diferencia. Rawls define este principio como norma que establece que las desigualdades sociales y económicas deben estar dispuestas de modo que "van a ser de gran beneficio para los miembros menos favorecidos de la sociedad". En otras palabras, una distribución desigual puede ser igual cuando se maximiza el beneficio mínimo para aquellos que tienen la asignación más baja de bienestar que confieren recursos.