Algoritmo minimax
Transcript of Algoritmo minimax
ALGORITMO MINIMAXINTELIGENCIA ARTIFICIAL II
AUTOR:
• JEFFERSON CLÍDER GUILÉN VALENZUELA
INTRODUCCIÓN
Este algoritmo de decisión se utiliza para minimizar la pérdida máxima aplicada en juegos entre adversarios.La Información es completa ya que cada jugador conoce el estado del otro, y puede elegir el mejor movimiento para cada jugador, suponiendo que el contrincante escogerá el peor.Devuelve la acción correspondiente al movimiento mejor posible, es decir, el movimiento que conduce al resultado con la mejor utilidad, conforme al axioma que el oponente juega para minimizar la utilidad. Las funciones Valor-Max y el Valor-Min pasan por el árbol de juegos entero, por todos los caminos hacia las hojas, para determinar el valor que le llega a un estado.
El algoritmo MINIMAX es un procedimiento recursivo y el corte de la recursión está dado por alguna de las siguientes condiciones: Gana algún jugadorSe han explorado N capas, siendo N el límite establecido Se ha agotado el tiempo de exploraciónSe ha llegado a una situación estática donde no hay grandes cambios de un nivel a otro.
ALGORITMO MINIMAX
• Posición inicial.• Conjunto de operadores o reglas del juego (definen movimientos legales) • Estado terminal • Función de utilidad, ej. gana, pierde, empata
REPRESENTACIÓN DE LOS JUEGOS
PASOS DEL ALGORITMO MINIMAX
1. Generar el árbol de juego. Se generarán todos los nodos hasta llegar a un estado terminal. 2. Calcular 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 nivel superior.
EJEMPLO DEL ALGORITMO MINIMAX
CONCLUSIONES
El algoritmo MINIMAX es un método de decisión para minimizar la pérdida máxima esperada en juegos con adversario y con información perfecta. MINIMAX es un algoritmo recursivo.La desventaja es que debe recorrer todos los nodos del árbol para encontrar la solución óptima.
BIBLIOGRAFÍA
• Russell, S., Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. Segunda Edición. Pearson Education. España
• Ponce, P. 2011. Inteligencia artificial con aplicaciones a la ingeniería. Primera Edición.
• García, A. 2012. Inteligencia artificial, Fundamentos, práctica y aplicaciones. Primera Edición.
• Benítez, R., Escudero, G., Masip, D., Kanaan, S., 2014, Inteligencia artificial avanzada. Primera Edición.