Búsqueda de dos agentes

Búsqueda

Grupo de Planificación y Aprendizaje (PLG)

Departamento de Informática
Escuela Politécnica Superior
Universidad Carlos III de Madrid

22 de diciembre de 2008

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Búsqueda de dos agentes

Búsqueda

Grupo de Planificación y Aprendizaje (PLG)

Departamento de Informática
Escuela Politécnica Superior
Universidad Carlos III de Madrid

22 de diciembre de 2008

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

En Esta Sección:

1 Búsqueda de dos agentes

Caracterización del problema
Algoritmo Minimax
Algoritmo Alfa-Beta
Otras técnicas

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Caracterización del problema

Suma nula: lo que gana uno, lo pierde el otro

Dos agentes (se puede generalizar, Maxn )
Información completa: se conoce en cada momento el
estado completo del juego
Deterministas o de información perfecta: no entra en juego
el azar (se puede generalizar)
Alternados: las decisiones de cada agente se toman de forma
alternada

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Resolución con función de evaluación perfecta

n0

n1 n2 n3

f ∗ (n) = 2 −3 8

Problema
Normalmente, no se conoce dicha función

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Resolución con búsqueda completa

+∞ n0

0 n1 −∞ n2 +∞ n3

Observaciones
Nodos hoja: ganar (∞), perder (−∞) o empatar (0)
Problema: es intratable; no se puede realizar en un tiempo
razonable

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Algoritmo Minimax
vi : Nodos max (juega el Minimax)
vi 1 : Nodos min (juega el oponente)

4 1 -3 1 -2 1

4 10 12 -3 20 -2
+∞

1 1 1 1 1 1 1 1 1 1 1

3 4 −∞ 10 12 3 -3 5 20 -4 -2
Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Cálculo del valor de cada nodo

Minimax


 +∞ si n es una situación ganadora
−∞ si n es una situación perdedora




0 si n es una situación de empate

f (n) =
 fev (n)
 si p = Profundidad-máxima
 máxSi ∈S(n) f (Si ) si n es nodo max y p < pmax



mı́nSi ∈S(n) f (Si ) si n es nodo min y p < pmax


Negamax

fev (n) si d = 0
f (n) =
máx(−f (S1 ), ..., −f (Sk )) si d > 0

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Algoritmo minimax
Procedimiento Minimax (Situación Profundidad)
SI Profundidad = pmax
ENTONCES devolver evaluación (Situación)
SI NO SI ganadora (Situación)
ENTONCES devolver + ∞
SI NO SI perdedora (Situación)
ENTONCES devolver - ∞
SI NO SI empate (Situación)
ENTONCES devolver 0
SI NO
S = sucesores (Situación)
L = lista de llamadas al MINIMAX (Si ∈ S, Profundidad + 1)
SI nivel-max (Profundidad)
ENTONCES devolver max (L)
SI NO devolver min (L)

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Tic-tac-toe – Minimax

Función de evaluación f (n): número de posibilidades de hacer

tres en raya del jugador menos número de posibilidades de
hacer tres en raya del oponente
Si colocamos la primera ficha en:
el centro: 4 posibilidades para hacer 3 en raya
(f (n) = 4 − 4 = 0)
en una esquina: 3 posibilidades (f (n) = 3 − 5 = −2)
en el centro de un lateral: 2 posibilidades (f (n) = 2 − 6 = −4)

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Tic-tac-toe – Minimax

X
X X X X
X
1

X X X X X X
X X X X X X

4−2=2 4−2=2 4−2=2 3−2=1 5−2=3 3−2=1

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Tic-tac-toe – Minimax

X
X X X X
X
1 0

X X X X X X X X X X X X

4−3=1 4−3=1 4−3=1 3−3=0 4−3=1 3−3=0

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Tic-tac-toe – Minimax

X
X X X X
X
1 0 1

X X X X X X
X X X X X X
4−2=2 4−2=2 4−2=2 4−2=2 4−2=2 3−2=1

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Poda en los nodos max

α= 4
β=+∞

α= 4
β=+∞; 6; 3
1 4>3
4

6
3

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Poda en los nodos min

α=−∞
1
β= 4

α=−∞; 2; 6
β= 4 6>4
4

1
2
6

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Poda Alfa-Beta

Nodos max: se utiliza el parámetro α para guardar el valor

máximo de los sucesores encontrado hasta el momento.
α0 = −∞
Nodos min: se utiliza el parámetro β para guardar el valor
mı́nimo de los sucesores encontrado hasta el momento.
β0 = +∞
Poda en los nodos max:

αp ≥ βp−1
Poda en los nodos min:

βp ≤ αp−1

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Alfa-Beta: Ejemplo

5 1 4 1 8 1

5 9 7 4 20 8 10

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

3 5 4 6 9 6 7 4 20 1 -3 10 8 5 10 1 -5

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Alfa-Beta: Ejemplo

α=−∞ α=−∞; 5
β=+∞ β= +∞

5
α=−∞ α= −∞
1 1 1
β=+∞ β=+∞; 5
6
5
α=−∞ α=−∞; 3; 5 α=−∞ α=−∞; 6
β=+∞ β= +∞ β= 5 β= 5
4
5 6
3
α=−∞ α= 3 α= 5 α=−∞
1 1 1 β= 5 1
β=+∞ β=+∞ β=+∞ Poda (6 ≥ 5)
3 5 4 6

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Alfa-Beta: Ejemplo

α= 5 α= 5
β=+∞ β=+∞

5
5
α= 5 α= 5
1 1 1
β=+∞ β=+∞; 7; 5
5
5
7
α= 5 α=5; 6; 7 α=5 α=5
β=+∞ β= +∞ β=7 β=7 Poda (5 ≥ 5)
7
6 4

α= 5 α= 6 α=5
β=+∞ 1 β=+∞ 1 β=7 1
6 7 4

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Alfa-Beta: Ejemplo

α= 5 α=5; 8
β=+∞ β=+∞
8
5
5
α= 5 α= 5
1 1 1
β=+∞ β=+∞; 8
5 5 10
8
α= 5 α=5; 8 α=5 α=5; 10
β=+∞ β=+∞ β=8 β= 8
5
8 10
α= 5 α= 8 α=5
1 1 1
β=+∞ β=+∞ β=8 Poda (10 ≥ 8)
8 5 10

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Alfa-Beta: Ejemplo

5 1 4 1 8 1

5 6 7 4 20 8 10

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

3 5 4 6 9 6 7 4 20 1 -3 10 8 5 10 1 -5

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Algunos aspectos relacionados

Efecto horizonte: se produce al fijar una profundidad
máxima (horizonte)
Ordenación de nodos: se ordenan los nodos hasta
profundidad k de acuerdo a una función de evaluación más
sencilla f ′
Ventana inicial: se puede comenzar por valores de alfa y beta
diferentes del mı́nimo y máximo valor, respectivamente
Profundización iterativa
Movimiento nulo: suponer que no se realiza ninguna acción
es lo peor que se puede hacer en algunos casos (posiciones
“zugzwang”)
Movimiento asesino: guardar estados y valores
Tablas de transposicición: para evitar la re-expansión de
nodos
Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Algunos aspectos relacionados

Búsqueda secundaria: realizar búsquedas parciales en los

nodos en los que se detecten problemas
Extensiones selectivas: donde se realiza la búsqueda
secundaria
Cálculo del valor de cada nodo: se puede utilizar la media,
la suma ponderada, tener en cuenta las probabilidades, ...

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Estado de la cuestión en juegos de dos jugadores

Ajedrez: HiTech, Deep Thought-Blue, Fritz

Damas: Chinook
Othello: Logistello
Backgammon: NeuroGammon
Juegos resueltos: Tic-Tac-Toe, Cuatro en Raya, Qubic,
Go-Moku, Damas (oficialmente desde 2007), . . .
IA en juegos actuales: estrategia (ORTS), independencia de
dominios (GGP), . . .

Búsqueda
 Caracterización del problema
Algoritmo Minimax
Búsqueda de dos agentes
Algoritmo Alfa-Beta
Otras técnicas

Otras técnicas

Otras técnicas equivalentes de suma nula: sss∗ , B∗ , números

conspiratorios, de prueba, y otros
No-deterministas: ∗-Minimax
Más de dos oponentes: Maxn
En lugar de mantener un valor (alfa o beta) mantienen n
valores en un vector
Sólo es aplicable si la suma de todas las puntuaciones es un
valor constante

Búsqueda