Método o Teorema Minimax

Minimax (a veces MinMax) es un método en la teoría de decisión para minimizar la máxima pérdida posible. De manera alternativa, puede pensarse que maximiza la ganancia mínima. Comenzó como una teoría de juegos de dos jugadores de suma cero, que abarca tanto los casos en los cuales los jugadores alternan movimientos como aquellos en los que hacen movimientos simultáneos. También se ha extendido a juegos más complejos y a la toma de decisiones en general bajo la presencia de incertidumbre. Una versión simple del algoritmo maneja juegos como el tic-tac-dedo del pie, donde cada jugador puede ganar, perder o empatar. Si el jugador A puede ganar en un movimiento, su mejor mejor jugada es esa. Si el jugador B sabe que un movimiento llevará a la situación donde el jugador A puede ganar con un movimiento, mientras que otro movimiento lo llevará a la situación en la cual el jugador A cuando mucho puede empatar, entonces el mejor movimiento del jugador B es aquel que lleva al empate. Teorema Minimax con movimientos simultáneos. El siguiente ejemplo de un juego de suma cero, donde A y B hacen movimientos simultáneos, ilustra el algoritmo minimax. Cada jugador tiene tres opciones y la matriz de pago para A es:

	B ESCOGE B1	B ESCOGE B2	B ESCOGE B3
A escoge A1	+3	-2	+2
A escoge A2	-1	0	+4
A escoge A3	-4	-3	+1

Y si B tiene la misma matriz de pago con las signos invertidos (por ejemplo: si las opciones son A1 y B1 entonces B paga 3 a A), entonces la opción Minimax sencilla para A es A2, ya que el peor resultado posible es tener que pagar 1, mientras que la opción Minimax sencilla para B es B2 ya que el peor resultado posible es no pagar. Sin embargo, esta solución no es estable, ya que si B cree que A elegirá A2 entonces B elegirá B1 para ganar 1; entonces si A cree que B escogerá B1 entonces A escogerá A1 para ganar 3; y después B escogerá B2; y así, eventualmente ambos jugadores se darán cuenta de la dificultad para hacer una elección. Una estrategia más estable es necesaria. Algunas opciones están dominadas por otras y pueden ser eliminadas: A no escogerá A3 ya que tanto 1 como A2 darán mejor resultado, sin importar lo que B elija; B no escogerá B3 ya que B2 producirá un mejor resultado sin importar lo que A escoja. A puede evitar tener que hacer un pago anticipado de más de 1/3 si eligiendo A1 con probabilidad 1/6 y A2 con probabilidad 5/6 sin importar lo que B elija. B puede asegurar una ganancia de por lo menos 1/3 utilizando una estrategia aleatoria de elegir B1 con probabilidad de 1/3 y B2 con probabilidad 2/3, sin importar lo que A elija. Estas estrategias mixtas Minimax ahora son estables y no pueden mejorarse. La teoría Minimax ha sido extendida a decisiones cuando no hay otro jugador, pero donde las consecuencias de decisiones dependen de hechos desconocidos. Además,, loa árboles Expectiminimax se han desarrollado para juegos de dos jugadores en que el azar es un factor. Si los juegos tienen suma cero en términos de la ganancia entre jugadores, aparentemente con estrategias no óptimas, éstos pueden evolucionar. Por ejemplo, en el dilema del prisionero, la estrategia Minimax para cada prisionero es traicionar al otro, aunque hubiera sido mejor que ninguno confesara su culpabilidad. Por lo tanto, para los juegos de suma cero, la mejor estrategia no es necesariamente Minimax.