Teoria de juegos. MAXIMIN Y MINIMAX


República Bolivariana de Venezuela
Ministerio del Poder Popular para la Educación Superior
Universidad del Zulia
Núcleo Luz Punto Fijo
Programa de Administración y Contaduría Pública
Área: Investigación de Operaciones









TEORIA DE JUEGOS
MAXIMIN Y MINIMAX











Punto fijo, junio 2009
¿Qué es la teoría de juegos?
La Teoría de Juegos consiste enrazonamientos circulares, los cuales no pueden ser evitados al considerar cuestiones estratégicas. Por naturaleza, a los humanos no se les da muy bien pensar sobre los problemas de las relaciones estratégicas, pues generalmente la solución es la lógica a la inversa.
En la Teoría de Juegos la intuición no educada no es muy fiable en situaciones estratégicas, razón por la que se debe entrenar tomando enconsideración ejemplos instructivos, sin necesidad que los mismos sean reales. Por lo contrario en muchas ocasiones disfrutaremos de ventajas sustanciales estudiando juegos, si se eligen cuidadosamente los mismos. En estos juegos-juegos, se pueden desentender de todos los detalles.

Si en lugar de utilizar personajes ficticios utilizamos personajes reales para los juegos si se observase qué tanhonesto es ese personaje, cómo manipularía la información obtenida, etc. Para un especialista en Teoría de Juegos el ser deshonesto, etc., sería un error comparable al de un matemático que no respeta las leyes de la aritmética porque no le gustan los resultados que está obteniendo

Minimax
En teoría de juegos, Minimax es un método de decisión para minimizar la pérdida máxima esperada enjuegos con adversario y con información perfecta. Minimax es un algoritmo recursivo.
El funcionamiento de Minimax puede resumirse como elegir el mejor movimiento para ti mismo suponiendo que tu contrincante escogerá el peor para ti.

Algoritmo Minimax con movimientos alternativos



Pasos del algoritmo Minimax:
1. Generación del árbol de juego. Se generarán todos los nodos hasta llegar a unestado terminal.
2. Cálculo de los valores de la función de utilidad para cada nodo terminal.
3. Calcular el valor de los nodos superiores a partir del valor de los inferiores. Alternativamente se elegirán los valores mínimos y máximos representando los movimientos del jugador y del oponente, de ahí el nombre de Minimax.
4. Elegir la jugada valorando los valores que han llegado al nivelsuperior.
El algoritmo explorará los nodos del árbol asignándoles un valor numérico mediante una función de utilidad, empezando por los nodos terminales y subiendo hacia la raíz. La función de utilidad definirá lo buena que es la posición para un jugador cuando la alcanza. En el caso del ajedrez los posibles valores son (+1,0,-1) que se corresponden con ganar, empatar y perder respectivamente. Enel caso del backgammon los posibles valores tendrán un rango de [+192,-192], correspondiéndose con el valor de las fichas. Para cada juego pueden ser diferentes.
Si Minimax se enfrenta con el dilema del prisionero escogerá siempre la opción con la cual maximiza su resultado suponiendo que el contrincante intenta minimizarlo.
Ejemplo
En el siguiente ejemplo puede verse el funcionamiento deMinimax en un árbol generado para un juego imaginario. Los posibles valores de la función de utilidad tienen un rango de [1-9]. En los movimientos del contrincante suponemos que escogerá los movimientos que minimicen nuestra utilidad, en nuestros movimientos suponemos que escogeremos los movimientos que maximizan nuestra utilidad.
El primer paso será calcular los nodos terminales, en verde.Posteriormente calcularemos el cuarto nivel, movimiento min, minimizando lo elegido (5, 2 y 1). Después podremos calcular el tercer nivel, movimiento max, maximizando la utilidad (5, 9). El segundo nivel es un movimiento min (5, 3 y 1). Finalmente llegamos al primer nivel, el movimiento actual, elegiremos el nodo que maximice nuestra utilidad (5).

Optimización
En la práctica el método Minimax es...