Minimax

Algoritmo Minimax

Ing. Bruno López Takeyas

ALGORITMO MINIMAX
• Algoritmo de decisión para minimizar
la pérdida máxima aplicada en juegos
de adversarios
• Información completa (cada jugador
conoce el estado del otro)
• Elección del mejor movimiento para
cada

jugador,

suponiendo

que

el

contrincante escogerá el peor
• El espacio de estados se representa
medianteárboles alternados, donde:
o Nodo: Representa una situación
del juego
o Sucesores

de

un

nodo:

Situaciones del juego a las que se

http://www.itnuevolaredo.edu.mx/takeyas

Email: takeyas@itnuevolaredo.edu.mx

Algoritmo Minimax

Ing. Bruno López Takeyas

accede por movimientos legales
aplicando sus reglas
o Nivel:

Contiene

todas

las

situaciones posibles para unode
los jugadores
• El

algoritmo

Minimax

es

un

procedimiento recursivo y el corte de
la recursión está dado por alguna de
las siguientes condiciones:
o Gana algún jugador
o Se han explorado N capas, siendo
N el límite establecido
o Se ha agotado
exploración

el

tiempo

de

o Se ha llegado a una situación
estática donde no hay grandes
cambios de un nivel a otro.http://www.itnuevolaredo.edu.mx/takeyas

Email: takeyas@itnuevolaredo.edu.mx

Algoritmo Minimax

Ing. Bruno López Takeyas

Representación de los juegos
•

Posición inicial.

•

Conjunto de operadores o reglas del
juego (definen movimientos legales)

•

Estado terminal

•

Función de utilidad, ej. gana, pierde,
empata

Pasos del Algoritmo Minimax
1. Generacióndel

árbol

de

juego.

Se

generarán todos los nodos hasta llegar
a un estado terminal.
2. Cálculo de los valores de la función de
utilidad para cada nodo terminal.

http://www.itnuevolaredo.edu.mx/takeyas

Email: takeyas@itnuevolaredo.edu.mx

Algoritmo Minimax

Ing. Bruno López Takeyas

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 nivel superior.

• El algoritmo explorará los nodos del
árbol asignándoles un valor numérico
mediante

una

función

de

utilidad,

empezando por los nodosterminales y
subiendo hacia la raíz.
• Colocar 0 ó 1 en los nodos terminales
dependiendo si gana MIN o MAX

http://www.itnuevolaredo.edu.mx/takeyas

Email: takeyas@itnuevolaredo.edu.mx

Algoritmo Minimax

Ing. Bruno López Takeyas

• La función de utilidad definirá lo buena
que es la posición para un jugador
cuando la alcanza.
• Se requiere de una estrategia que
garantice llegar aestados terminales
ganadores independientemente de lo
que haga el oponente.
• Un valor positivo indica la ventaja de
un jugador y uno negativo la ventaja
del otro.
• El jugador que espera valores positivos
se conoce como maximizador
• El

jugador

negativos

que
se

espera

valores

conoce

como

minimizador

http://www.itnuevolaredo.edu.mx/takeyas

Email:takeyas@itnuevolaredo.edu.mx

Algoritmo Minimax

Ing. Bruno López Takeyas

• El maximizador busca movimientos
que lo conduzcan al mayor número
positivo
• El minimizador busca movimientos
que lo conduzcan al menor número
negativo
• P. ejemplo:
Nivel MAX
2
2

Nivel MIN

1
7

1

8

Nivel MAX

• El maximizador:
o Puede esperar llegar a un valor de 8http://www.itnuevolaredo.edu.mx/takeyas

Email: takeyas@itnuevolaredo.edu.mx

Algoritmo Minimax

Ing. Bruno López Takeyas

o Sabe que el minimizador puede
escoger un movimiento que lo lleve
a un valor de 1
• Desde

el

punto

de

vista

de

el

maximizador, el minimizador puede
escoger 2 ó 1
• Los resultados de un nivel determinan
la acción y el resultado del nivel
inmediato superior...