Busqueda de dos agentes
Busqueda
Grupo de Planificacion y Aprendizaje (PLG)Departamento de InformaticaEscuela Politecnica Superior
Universidad Carlos III de Madrid
22 de diciembre de 2008
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Busqueda de dos agentes
Busqueda
Grupo de Planificacion y Aprendizaje (PLG)Departamento de InformaticaEscuela Politecnica Superior
Universidad Carlos III de Madrid
22 de diciembre de 2008
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
En Esta Seccion:
1 Busqueda de dos agentesCaracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Caracterizacion del problema
Suma nula: lo que gana uno, lo pierde el otro
Dos agentes (se puede generalizar, Maxn)
Informacion completa: se conoce en cada momento elestado completo del juego
Deterministas o de informacion perfecta: no entra en juegoel azar (se puede generalizar)
Alternados: las decisiones de cada agente se toman de formaalternada
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Resolucion con funcion de evaluacion perfecta
n0
n1 n2 n3
f ∗(n) = 2 −3 8
Problema
Normalmente, no se conoce dicha funcion
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Resolucion con busqueda completa
n0+∞
n10 n2−∞ n3+∞
Observaciones
Nodos hoja: ganar (∞), perder (−∞) o empatar (0)
Problema: es intratable; no se puede realizar en un tiemporazonable
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Algoritmo Minimax
vi : Nodos max (juega el Minimax)
1vi : Nodos min (juega el oponente)
4
14
4
1
31
4
10
1
−∞
1
10
1-3
12
1
121
3
-3
1
-3
+∞
1-2
20
1
51
20
-2
1
-41
-2
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Calculo del valor de cada nodo
Minimax
f (n) =
+∞ si n es una situacion ganadora−∞ si n es una situacion perdedora0 si n es una situacion de empatefev(n) si p = Profundidad-maximamaxSi∈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
f (n) =
{
fev(n) si d = 0max(−f (S1), ...,−f (Sk)) si d > 0
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Algoritmo minimax
Procedimiento Minimax (Situacion Profundidad)SI Profundidad = pmax
ENTONCES devolver evaluacion (Situacion)SI NO SI ganadora (Situacion)
ENTONCES devolver + ∞
SI NO SI perdedora (Situacion)ENTONCES devolver - ∞SI NO SI empate (Situacion)
ENTONCES devolver 0SI NO
S = sucesores (Situacion)L = lista de llamadas al MINIMAX (Si ∈ S, Profundidad + 1)SI nivel-max (Profundidad)ENTONCES devolver max (L)SI NO devolver min (L)
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Tic-tac-toe – Minimax
X
Funcion de evaluacion f (n): numero de posibilidades de hacertres en raya del jugador menos numero de posibilidades dehacer 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)
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Tic-tac-toe – Minimax
X
XX XX
XX
XX
XX
XX
XX
XX
XX
4−2=2 4−2=2 4−2=2 3−2=1 5−2=3 3−2=1
1
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Tic-tac-toe – Minimax
XX
X
XX XX
XX XX XX XX XX XX
1 0
4−3=1 4−3=1 4−3=1 3−3=0 4−3=1 3−3=0
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Tic-tac-toe – Minimax
X
XX
XX XX
XX
XX
XX
XX
XX
XX
1 0 1
4−2=2 4−2=2 4−2=2 3−2=14−2=2 4−2=2
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Poda en los nodos max
α= 4β=+∞
41
α= 4β=+∞; 6; 3 4 > 3
63
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Poda en los nodos min
1α=−∞
β= 4
4
α=−∞; 2; 6β= 4 6 > 4
21
6
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Poda Alfa-Beta
Nodos max: se utiliza el parametro α para guardar el valormaximo de los sucesores encontrado hasta el momento.α0 = −∞
Nodos min: se utiliza el parametro β para guardar el valormı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
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Alfa-Beta: Ejemplo
8
15
5
1
31
51
4
9
1
61
9
14
7
1
61
7
4
1
4
20
1
201
11
-31
10
18
8
1
8
1
5
10
1
101
11
-5
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Alfa-Beta: Ejemplo
α=−∞
β=+∞
α=−∞; 5β= +∞
1α=−∞
β=+∞
α= −∞
β=+∞; 5
5
α=−∞
β=+∞
α=−∞; 3; 5β= +∞
5
1α=−∞
β=+∞
3
3
1α= 3β=+∞
5
5
1α= 5β=+∞
4
4
α=−∞
β= 5α=−∞; 6β= 5
6
1α=−∞
β= 5
6
6
Poda (6 ≥ 5)
1 1
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Alfa-Beta: Ejemplo
α= 5β=+∞
α= 5β=+∞
1
5
5
1α= 5β=+∞
α= 5β=+∞; 7; 5
5
α= 5β=+∞
α=5; 6; 7β= +∞
7
1α= 5β=+∞
6
6
1α= 6β=+∞
7
7
α=5β=7
α=5β=7
5
1α=5β=7
4
4
Poda (5 ≥ 5)
1
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Alfa-Beta: Ejemplo
α= 5β=+∞
α=5; 8β=+∞
1
5
5
1
5
5
1α= 5β=+∞
α= 5β=+∞; 8
8
α= 5β=+∞
α=5; 8β=+∞
8
1α= 5β=+∞
8
8
1α= 8β=+∞
5
5
α=5β=8
α=5; 10β= 8
10
1α=5β=8
10
10
Poda (10 ≥ 8)
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Alfa-Beta: Ejemplo
8
15
5
1
31
51
4
6
1
61
9
14
7
1
61
7
4
1
4
20
1
201
11
-31
10
18
8
1
8
1
5
10
1
101
11
-5
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Algunos aspectos relacionados
Efecto horizonte: se produce al fijar una profundidadmaxima (horizonte)
Ordenacion de nodos: se ordenan los nodos hastaprofundidad k de acuerdo a una funcion de evaluacion massencilla f ′
Ventana inicial: se puede comenzar por valores de alfa y betadiferentes del mınimo y maximo valor, respectivamente
Profundizacion iterativa
Movimiento nulo: suponer que no se realiza ninguna acciones lo peor que se puede hacer en algunos casos (posiciones“zugzwang”)
Movimiento asesino: guardar estados y valores
Tablas de transposicicion: para evitar la re-expansion denodos
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Algunos aspectos relacionados
Busqueda secundaria: realizar busquedas parciales en losnodos en los que se detecten problemas
Extensiones selectivas: donde se realiza la busquedasecundaria
Calculo del valor de cada nodo: se puede utilizar la media,la suma ponderada, tener en cuenta las probabilidades, ...
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Estado de la cuestion 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 dedominios (GGP), . . .
Busqueda
Busqueda de dos agentes
Caracterizacion del problemaAlgoritmo MinimaxAlgoritmo Alfa-BetaOtras tecnicas
Otras tecnicas
Otras tecnicas equivalentes de suma nula: sss∗, B∗, numeros
conspiratorios, de prueba, y otros
No-deterministas: ∗-Minimax
Mas de dos oponentes: Maxn
En lugar de mantener un valor (alfa o beta) mantienen n
valores en un vectorSolo es aplicable si la suma de todas las puntuaciones es unvalor constante
Busqueda