El Algoritmo
Minimax
¿QUE ES MINIMAX?
Es un algoritmo recursivo, y se aplica como
un método de decisión que se utiliza para
minimizar la pérdida esperada en en juegos
con adversarios y con información perfecta
Cómo tomar la mejor decisión suponiendo que el otro
jugador escogerá el peor escenario para ti
BREVE HISTORIA
1921. Emilé Borel ofreció un tratamiento
riguroso en los juegos de suma cero.
1928. John Von Neumann puso las bases de
la moderna teoría de juegosy probó el
teorema fundamental de minimax.
¿QUIEN LO INVENTÓ?
El teorema minimax es atribuidp a John Von
Neumann quien estableció las siguientes
nociones: "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."
METODOLOGÍA
En la figura se muestran los niveles
del árbol de decisión.
El juego inicia abajo y termina en la
´parte superior.
PROCEDIMIENTO
En la base del árbol, el jugador adversario
hace el primer movimiento, por lo que se
espera el pero resultado. luego en el
siguiente nivel, cambia de jugador x, quien
trata de maximizar su beneficio
considerando la decisión tomada por su
adversario.
Los resultado del juego corresponden al
jugador X:
1er nivel: Decisión del oponente puede RESULTADOS
perder -10 o ganar 5
2do nivel: decisión del Jugador x, puede
perder 10 o ganar 1, y Ganar 5 o ganar 7.
3er nivel: Adversario puede elegir que
pierda -3 y 4, y en el cuarto nivel (Max),
el jugador X elige ganar 4.
por lo que el resultado es una ganacia
de 4
FINTYEGRANTES:
Elaborado por:
1.- Castillo Cordero, Luz U18307219
2.- Sulca Lliuyacc, Frank U18215263
3.- Junior Mejía Vizarres U19207814
4.- Torres Escalante, Irvin U19305894
5.- Rodríguez Ochoa, Hilton U18102440
El Algoritmo
Poda Alfa -Beta
QUÉ ES PODA ALFA-BETA?
Es una técnica de búsqueda que permite
reducir el número de nodos evaluados en un
árbol de juego
¿QUIÉN LO INVENTÓ?
El uso de está técnica fue plasmada en
algunas obras como por ejemplo:
1963. T.P. Hart (The Alpha Beta Heuristic)
1987. Alexander Brudno (Computer Chess
Methods)
METODOLOGIA
Utiliza dos parametros:
α es el valor de la mejor opción hasta el
momento a lo largo del camino para MAX (el
valor más alto)
β es el valor de la mejor opción hasta el
momento a lo largo del camino para MIN (el
valor más bajo)
METODOLOGÍA (REGLAS)
En los nodos MAX la condición de poda es αp ≥ βp-1
(Se puede podar por debajo de un nodo MAX si su
valor alfa es mayor o igual que al menos un beta
antecesor)
En los nodos MIN la condición de poda es βp ≤ αp-1
(Se puede podar por debajo de un nodo MIN si su
valor beta es menor o igual que al menos un alfa
antecesor)
PROCEDIMIENTO
A tiene β = 3 (A no será mayor que 3)
B: se poda por debajo de este nodo MAX porque 5 > 3
C tiene α = 3 (C no será menor de 3 al ser un nodo MAX)
D: se poda por debajo de este nodo MIN porque 0 < 3
E: se poda por debajo de este nodo MIN porque 2 < 3
FINTYEGRANTES:
Elaborado por:
1.- Castillo Cordero, Luz U18307219
2.- Sulca Lliuyacc, Frank U18215263
3.- Junior Mejía Vizarres U19207814
4.- Torres Escalante, Irvin U19305894
5.- Rodríguez Ochoa, Hilton U18102440
