Min Max

JUEGOS
•
•

Área de aplicación de los algoritmos heurísticos
Juegos bi-personales: oponente hostil
MINIMAX
– Oponente: MIN
Jugador: MAX
– MIN intenta mover a un estado que es el peor para MAX
– Etiquetar cada nivel del espacio de búsqueda de acuerdo
con quien le toca jugar
– Asignar un valor a cada nodo hoja
– Propagar estos valores hacia arriba
• Si el padre es un nodo MAX, darleel valor máximo de sus hijos
• Si el padre es un nodo MIN, darle el valor mínimo de sus hijos

– El valor de cada estado indica el valor del mejor estado que
ese jugador puede desear alcanzar. Estos valores se
utilizan para elegir entre los movimientos posibles.

VALOR DE CADA NODO n
+∞
-∞
0
f(n)
max(f(sj Є S(n)))
min(f(sj Є S(n)))

Si n es una posición ganadora MAX
Si n es unaposición perdedora MAX
Si es una situación de empate
Si está en p=profundidad máxima
Si n es nodo MAX y profundidad < p
Si n es nodo MIN y profundidad < p

MAX busca caminos que lleven a números positivos altos sabiendo que
MIN forzara el juego hacia posiciones con evaluación negativa
MAX

MAX
MIN

MIN

8
1

MAX

2

7

1

8

MAX

1
MIN

MIN
MAX

2
2

7

8

2MAX

1

2

MIN
MAX

1

2

7

1

MAX
8

3

MAX
MIN

0

3

MAX
MIN

2

9

3
2

3

2

5

0

7

90

07

4

2
2

6
1

5

6

Juegos con espacio de estados explorable exhaustivamente
–
–
–
–

Búsqueda sistemática del espacio de posibles movimientos
Se supone que el oponente utiliza la misma información y la utiliza
para ganarMINIMAX: cada nodo hoja se etiqueta 0 si es ganador para MIN y 1 si
es ganador para MAX
ESTRATEGIA GANADORA para MAX sería un sub-árbol en el que
todos sus nodos terminadores son ganadores

EJEMPLO: JUEGO DEL NIM
(En rojo “estrategia ganadora”)

MIN

MAX

MIN

MAX

MIN

MAX

7

1

6-1

5-1-1

0

4 - 1 - 1- 1

5-2

4-2-1

0

3-1-1-1-1

1

3-2-1-1

0

11

3-2-2

1

0

3-3-1

2-2-2-1

2-2-1-1-1

2-1-1-1-1-1

1

4-3

0

1

0

1

Juegos en los que es imposible o indeseable representar y buscar
en el grafo del juego
–
–
–
–
–
–
–
–
–
–

Exploración en un nº determinado de niveles: profundidad del juego determinada
n-movimiento hacia delante; n = nº de niveles que se exploran
A cada nodo hoja se leasigna un valor de acuerdo a una función de evaluación
heurística
El valor se propaga hacia atrás hasta el nodo raíz, es el mejor valor que se puede
alcanzar en n movimientos
Heurísticas suelen medir la ventaja de un jugador sobre otro.
Los grafos de juegos se examinan por nivel o ply determinado por espacio y
tiempo del ordenador
Efecto horizonte
Nodos del árbol son nodos MAX o MIN. Elobjetivo de MAX es maximizar el valor
de la función de evaluación heurística
Árbol con nodos MAX o MIN alternados
ESTRATEGIA GANADORA para MAX sería un sub-árbol en el que todos sus
nodos terminadores son ganadores

EJEMPLO: TIC – TAC – TOE (2 - ply)
HEURÍSTICA: E(n) = X(n) – O(n)
X(n) = nº de líneas ganadoras posibles para MAX
O(n) = nº de líneas ganadoras posibles para MIN

1

MAXJUGADA DE MAX

MIN

-1

-2

1

MAX
6-5=1

5-5=0

5-5=0

6-5=1

4-5=-1

5-6=-1

5-6=-1

5-5=0

6-6=0

5-4=1

4-6=-2

6-4=2

MÉTODO ALFA-BETA
–
–
–

Procedimiento para mejorar la eficiencia en juegos bipersonales
Completa y suple el método minimax
Minimax necesita dos pasadas
•
•

–
–

–
–

Una de generación
Una de evaluación

Búsqueda α-β buscaprimero en profundidad
La poda α-β se basa en la idea de disponer de dos valores que conforman
una ventana a la cual deben pertenecer los valores de f(n) para que sean
considerados
En los nodos MAX se utiliza el parámetro α que determina el máximo de los
valores de los nodos sucesores encontrados hasta el momento
En los nodos MIN se utiliza el parámetro β que va a ser, en cada momento, el...