algoritmo de minimax
DESCRIPTION
Teorema Explicación Ventajas y desventajasTRANSCRIPT
Minimax
Kerly CarreraValeria FloresJeannette Laverde
¿Qué es Minimax?• En teoría de juegos, 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.
• El funcionamiento de Minimax puede resumirse como elegir el mejor movimiento para ti mismo suponiendo que tu contrincante escogerá el peor para ti.
Teorema Minimax
• “Un juego es una situación conflictiva en la que uno debe tomar una decisión sabiendo que los demás también toman decisiones, y que el resultado del conflicto se determina, de algún modo, a partir de todas las decisiones realizadas”
John von Neumann Creador del teorema Minimax
• También afirmó que: "Siempre existe una forma racional de actuar en juegos de dos participantes, si los intereses que los gobiernan son completamente opuestos."
Algoritmo de 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 algoritmo Minimax es un procedimiento recursivo y el corte de la recursión está dado por alguna de las siguientes condiciones:
– Gana algún jugador .– Se han explorado N capas, siendo N el límite 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.
Explicación• Jugar al error del oponente sin buscar
beneficio en el turno siguiente.• Almacenar jugadas realizadas.• Aplicar experiencia a nuevos escenarios de un
juego.• Esperar a que el oponente realice jugadas que
no beneficien tanto su estrategia de juego.• Aprovechar las jugadas mas optimas que el
oponente no realizo y aplicarlas a futuros movimientos o juegos futuros
• El algoritmo tiene la capacidad de aprender de acuerdo a una base de datos histórica de movimientos realizado, es decir, aprende con la experiencia.
• El algoritmo será infalible o un gran oponente a vencer entre mas juegos y movimientos tenga en su historial.
• Aprende del oponente y al tiempo le da ventaja.
Ventajas
• El algoritmo tiene una complejidad muy elevada de implementación, pues el hecho de estructurar una base de datos de experiencia requiere de armar y estructurar un esquema de aprendizaje optimo.
• Es lento de aprendizaje. Pues por cada jugada realizada y el conjunto de las que tiene almacenadas lo obliga a implementar algoritmos de comparación. búsqueda, inserción, etc.
• Por cada nuevo oponente deberá implementar estructuras de aprendizaje, pues no todos los oponentes juegan de la misma forma.
• El algoritmo solo funciona para enfrentar un oponente a la vez .
Desventajas