Lalalala

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: oNodo: 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 uno de los jugadores • El algoritmo Minimax es unprocedimiento 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ón del árbol de juego. Se generarán todos los nodos hasta llegar a un estado terminal. 2. Cálculo de losvalores 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 nodos terminales 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 a estados 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. • Eljugador que espera valores positivos se conoce como maximizador • El jugador que se espera conoce valores como

negativos 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 almenor número negativo • P. ejemplo: Nivel MAX 2 2 7 1 1 8 Nivel MIN Nivel MAX

• El maximizador: o Puede esperar llegar a un valor de 8

http://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 elmaximizador, el minimizador puede escoger 2 ó 1 • Los resultados de un nivel determinan la acción y el resultado del nivel inmediato superior

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

Email: takeyas@itnuevolaredo.edu.mx

Algoritmo Minimax

Ing. Bruno López Takeyas

Cálculo de valores de la función de utilidad

Calcular el valor minimax del nodo J: V(J) SI J es Terminal, V(J) ← ev(J) SI NO...