Inteligencia Artificial
Búsqueda de Soluciones:
Algoritmo miniMAX
Que es?
• En teoría de juegos, Minimax es un método
de decisión para minimizar la perdida
máxima esperada en juegos con adversario
con información completa.
Que es?
• Esta diseñado para dos jugadores.(Max y
Min).
• Es un procedimiento recursivo, hasta que se
cumple alguna de las condiciones siguientes:
• Gana algún jugador.
• Se han explorado N capas, siendo N el limite
establecido.
• Se ha agotado el tiempo de exploración.
• Se ha llegado a una situación estática donde no hay
grandes cambios de un nivel a otro.
Representación de los juegos.
• Posición inicial.
• Conjunto de operadores o reglas del juego.
• Estado terminal.
• Función de utilidad.
Representación de los juegos.
• Heurística:
• No garantiza el éxito.
• El camino seleccionado es “razonablemente” un
camino hacia la victoria o empate.
• Imita el comportamiento humano al examinar por
anticipado un pequeño numero de jugadas antes de
decidirse por una.
Estructuras utilizadas.
• El algoritmo Minimax utiliza la estructura de
un árbol.
• En estructuras de datos un árbol esta formado por:
• Nodos. A • Nodo raíz
B C
D E
• Hojas
Que es?
• El espacio de estados se presenta mediante
árboles alternados.
•NODO
•SUCESORES DE UN NODO
•NIVEL
Ejemplo:
• MAX
x
x x
• MIN
o o
o x x o o
o x x x x • MAX
• MAX 1
• MIN 1 -2 -1
2 1 -2 0 -1 0
• MAX
Historia
• La teoría de juegos.
• ¿Qué es un juego?
• Principales exponentes de la teoría de
juegos:
– Emile Borel
– John Von Neumman
– Oskar Morgenster
Teorema Minimax
• ¿Quién fue John Von Neumman?
• El teorema minimax.
• Ejemplo:
c1 c2 c3
r1 -2,2 1,-1 10,-10
r2 -1,1 2,-2 0,0
r3 -8,8 0,0 -15,15
Teorema Minimax
• La suma de los valores maximin de los dos
jugadores es igual a cero.
• La solución maximin es la misma que el la
teoría del equilibrio de Nash
• El punto de equilibrio de Nash.
Un ejemplo: Crisis 1914
Rusia-Francia
Mínimo de las
filas
No apoyar a Serbia Apoyar a Serbia
A. Comprometerse con C. Serbia es salvado; la
Serbia. Poca influencia influencia Rusa en los
Rusa es conservada en Balcanes es preservada;
Comprometerse Serbia. continua la agitación Serbia;
el imperio Austriaco comienza
a desintegrarse.
Doble Alianza (2) (1) 1
(Austria-Alemania ) B. Rusia humillada y pierde D. Guerra
influencia en los Balcanes;
Atacar Austria gana el control de
Serbia y preserva el imperios.
(3) 3
(4)
Máximo de las
columnas 4 3
Historia
• ¿Quién fue Claude Shannon?
• “Programando una Computadora para que Juegue
Ajedrez” artículo que describe la aplicación de
MINIMAX en el procedimiento para que una
computadora juegue ajedrez.
• 1 punto para los peones,
• 3 puntos para los caballos o alfiles,
• 5 puntos para las torres y 9 puntos para la reina.
• 200 puntos para jaque mate.
Funcionamiento de Minimax
• Planteamiento general:
– 2 jugadores: MAX y MIN (MAX mueve primero)
– Estado inicial
– Función sucesora
– Función objetivo
– Función de utilidad (función u)
Funcionamiento de Minimax
• Algoritmo minimax
– Tiene por objetivo decidir un movimiento para
MAX.
– HIPÓTESIS
– Jugador MAX trata de maximizar su beneficio (función de
utilidad).
– Jugador MIN trata de minimizar su pérdida.
Funcionamiento de Minimax
– Aplicación algoritmo:
• 1) Generar árbol entero hasta nodos terminales
• 2) Aplicar función de utilidad a nodos terminales
• 3) Propagar hacia arriba para generar nuevos valores
de utilidad para todos los nodos
• 4) Elección jugada con máximo valor de utilidad
Decisiones imperfectas
• Dada una función de evaluación f, se puede
aplicar una búsqueda minimax con límite de
profundidad
• Uso de valores heurísticos para juegos con
un espacio de estados extremadamente
grande
Ejemplo: Juego imaginario
5 3 1
7 8 3 4 2 1
5 9
5 2 1 9
5 8 9 2 9 1
Funcionamiento: Pseudo código
MINIMAX(posicion, nivel)
/* casos base */
if (esGanador(posicion)) then
devolver +∞
else if (esPerdedor(posicion)) then
devolver −∞
else if (esEmpate(posicion)) then
devolver 0
else if (nivel = limite) then
devolver evaluacion(posicion)
else
/* caso recursivo */
for all sucesor i de posicion do
valores[i] := MINIMAX(sucesor i, nivel+1)
if (esNodoMAX(nivel)) then
devolver maximo(valores)
end if
if (esNodoMIN(nivel)) then
devolver minimo(valores)
end if
end for
end if
Ejemplos de juegos
Gato Conecta cuatro
9! = 362880 partidas
Nim
Ejemplos de juegos
Damas Ajedrez
1031 partidas 10123 partidas
Ejemplos de juegos
Go Othello
10360 partidas
Ejemplos de juegos
• Juegos que no aplica
Bridge, Solitario, Backgammon
Ejemplo: Rock Piles
• Dos jugadores
• Los jugadores toman piedras de la pila
• Reglas
– Inicialmente hay 2 piedras en una pila y
1 en otra
– MAX empieza y se alternan movimientos
• MAX gana si MIN saca la última piedra
• MIN gana si MAX saca la última piedra
Ejemplo: Rock Piles
MAX
MIN
MAX Jugador 2 Pierde Jugador 2 Pierde
Jugador 1 Pierde Jugador 1 Pierde Jugador 1 Pierde
Ejemplo: Rock Piles
MAX
MIN
MAX Jugador 2 Pierde Jugador 2 Pierde
1 MAX
Jugador 1 Pierde Jugador 1 Pierde Jugador 1 Pierde
MIN 0 1 0
0 0 1 0 1 MAX
0 0 0
