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.
• Nodo raíz
A
B
D
• Hojas
C
E
Que es?
• El espacio de estados se presenta mediante
árboles alternados.
•NODO
•SUCESORES DE UN NODO
•NIVEL
Ejemplo:
• MAX
x
x
o x
• MIN
o
x
o
x
o
o
o
x
x
• MAX
x
1
• MIN
• MAX
x
1
2
-2
1
-2
-1
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:
r1
r2
r3
c1
-2,2
-1,1
-8,8
c2
1,-1
2,-2
0,0
c3
10,-10
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
No apoyar a Serbia
A.
Comprometerse
Comprometerse con
Serbia. Poca influencia
Rusa es conservada en
Serbia.
Doble Alianza
(2)
(Austria-Alemania )
B. Rusia humillada y pierde
influencia en los Balcanes;
Austria gana el control de
Serbia y preserva el imperios.
Atacar
(4)
Máximo de las
columnas
4
Apoyar a Serbia
C. Serbia es salvado; la
influencia Rusa en los
Balcanes es preservada;
continua la agitación Serbia;
el imperio Austriaco comienza
a desintegrarse.
(1)
Mínimo de las
filas
1
D. Guerra
(3)
3
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
5
7
3
8
5
5
5
3
1
4
2
8
9
2
1
9
2
9
1
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
9! = 362880 partidas
Conecta cuatro
Nim
Ejemplos de juegos
Damas
Ajedrez
1031 partidas
10123 partidas
Ejemplos de juegos
Go
10360 partidas
Othello
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 1 Pierde
Jugador 1 Pierde
Jugador 2 Pierde
Jugador 1 Pierde
Ejemplo: Rock Piles
MAX
MIN
MAX
1
Jugador 2 Pierde
MAX
Jugador 1 Pierde
MIN
0
1
0
0
0
0
1
Jugador 2 Pierde
Jugador 1 Pierde
0
0
0
1
MAX
Jugador 1 Pierde
Descargar

Slide 1