Download Juegos con Oponentes

Búsqueda con Adversarios
Dr Jesús Antonio González Bernal
Dr.
Buscar soluciones enfrentando
adversarios
y En un ambiente de un videojuego,
videojuego es muy común que un
agente “conviva” con un conjunto de agentes
y ¿Qué hacer si el agente tiene que resolver un problema a partir
de una búsqueda,
q
, pero
p la secuencia de acciones no depende
p
exclusivamente del agente en sí?
2
Juegos con Dos Agentes
y Considere un videojuego en el cual dos agentes A y B
interactúan en un tablero dividido en celdas
y Asuma que primero el agente A actúa (se mueve a una celda),
celda)
después el agente B (se mueve a otra celda) y así sucesivamente
y Objetivo
j
A: lograr
g qque el agente
g
A este en la misma celda del
agente B
y Objetivo B: evitar que el agente A ocupe la misma celda que
ocupa B
3
Juegos con Dos Agentes
4
Juegos con Dos Agentes
` Para resolver este problema
problema, se puede actuar de la siguiente
forma:
` Para el agente A:
` Determinar todos los posibles movimientos a partir de un estado dado y
ver cual camino es el más ventajoso a través de una heurística
` Dadas las limitantes de tiempo y cómputo, en ocasiones no es posible
determinar con precisión el “mejor” movimiento
Análisis por horizonte limitado
` Se puede utilizar una estrategia de sensar / planear / actuar
` ¿Existirán estrategias más acordes a este tipo de problemas?
5
El procedimiento “minimax”
y Consideremos que en un juego tenemos a dos agentes
agentes, MAX
y MIN
y Asumamos que MAX tira primero seguido de un movimiento
de MIN
y Nodos en un nivel de p
profundidad impar
p corresponden
p
a
estados en donde MIN debe de tirar en seguida (nodos MIN)
y Nodos a un nivel par corresponden a estados en donde MAX
debe de ejecutar un movimiento (nodos MAX)
y El nodo raíz es de profundidad cero
y Cada jugador realizará una búsqueda de horizonte limitado para
realizar su movimiento
6
El procedimiento “minimax”
y Asumamos que cualquier movimiento de MIN o MAX busca
llegar a un estado en el cual tenga una mayor ventaja que el
resto
esto analizado
a a a o
y El procedimiento “minimax” consiste en que cada jugador
analice sus pposibles jjugadas,
g
las reacciones del contrario, sus
reacciones y así sucesivamente, hasta llegar al límite del
horizonte
y Los nodos en el límite del horizonte son evaluados a través de
una función heurística para estimar cual es la probabilidad de
que dichos nodos sean ganadores
ganadores, empate o perdedores
7
Etiquetado
` Como en cualquier búsqueda heurística
heurística, es necesario
establecer una función “f ” de evaluación para los nodos
` Consideremos como ejemplo
j p de trabajo
j al juego
j g del “gato”
g
(tic-tac-toe)
` Asumamos que el horizonte se establece a partir de una
profundidad
f d d d “2”
“ ”
` Como función de evaluación:
` f(tablero) = (# de columnas
columnas, renglones o diagonales vacías disponibles
para MAX) – (# de columnas, renglones o diagonales vacías disponibles
para MIN)
` f(tablero) = ∞,
∞ si tablero es una posición ganadora para MAX
` f(tablero) = - ∞, si tablero es una posición ganadora para MIN
8
Etiquetado
y Asumamos lo siguiente:
, f(tablero) = 66-4=2
4 2
y Para simplificar el problema, se utilizará la simetría de los
tableros (q
(que den posiciones
p
idénticas))
y
y Consideremos q
que MAX marca con una “x” al tablero y MIN
con un “o” al tablero
9
Procedimiento Minimax
10
Procedimiento Minimax
y A partir del árbol anterior,
anterior el estado ganador para MAX es:
y Considere que MIN responde a partir del siguiente
movimiento
i i
11
Procedimiento Minimax
12
Procedimiento Minimax
y A partir de este nuevo árbol de expansión
y MAX tiene dos posibles movimientos (se elige uno
aleatoriamente))
y Considere que MAX elige la tirada marcada en el árbol
y Considere que MIN responde con el siguiente movimiento
13
Procedimiento Minimax
14
Procedimiento Minimax (1/2)
y El etiquetado en el procedimiento “minimax”
minimax se puede llevar
a cabo a través de dos estrategias
y Desde un nodo MAX
MAX, se elige el máximo de los hijos
y Desde un nodo MIN, se elige el mínimo de los hijos
h(m), m sin sucesores
⎧
⎪
f (m) = ⎨max{ f (n) : n sucesor de m}, m ∈ MAX
⎪ min{ f (n) : n sucesor de m}, m ∈ MIN
⎩
min
max
min
Nodos evaluados con h(m)
15
max
MAX
MIN
Procedimiento Minimax (2/2)
y El etiquetado en el procedimiento “minimax”
minimax se puede llevar
a cabo a través de dos estrategias
y Se toma el convenio de “lo
lo que le conviene a MAX es
inversamente proporcional a lo que le conviene MIN”
) m sin sucesores, m MAX
⎧ h(m),
⎪
f (m) = ⎨− h(m), m sin sucesores, m MIN
⎪ max{ f (n) : n sucesor de m}
⎩
2
max
max
-8
MAX
MIN
16
8
-9
9
2
-2
-2
-9
-9
2
-3
3
Notas Procedimiento Minimax
y Minimax requiere realizar una búsqueda exhaustiva del árbol
dentro del horizonte limitado
y Minimax no considera podas en el árbol
7
8
17
>8
Poda α - β
y La estrategia “poda
poda α - β
β” permite realizar podas a un árbol a
partir de información que acarrea de los nodos inferiores
y Mantiene en cada llamado recursivo dos valores (α,
(α β),
β) donde
α es la cota inferior de los valores que se irán buscando en la
parte superior del árbol y β la cota superior
y Si α llega a ser igual o superior a β, no se realiza la búsqueda en
las demás ramas del nodo que se expande
y Poda α si el nodo que se expande es MAX
y Poda β si el nodo que se expande es MIN
18
Poda α - β: Algoritmo
y J: nodo actual
y Jk: k-ésimo hijo del nodo “J” (k = 1,…,b)
y h(J): valor de la función heurística evaluada en J
Procedimiento αβ(J, α, β)
Si J es terminal
terminal, devolver h(j)
2. k Å 1
3. Si J es MAX,, hacer
1. α Å max{α, αβ(Jk, α, β)}
2. Si α >= β, devolver β; en caso contrario continuar
3. Si k = b (#hijos
#
de J), devolver α
4. k Å k + 1, regresar a 3.1
1
1.
19
Poda α - β: Algoritmo
Procedimiento αβ(J,
αβ(J α,
α β) (continuación…)
(continuación )
4.
y
20
Si J es MIN, hacer
1
1.
β Å MIN{β,
MIN{β αβ(Jk, α,
α β)}
2. Si α >= β, devolver α; en caso contrario continuar
3
3.
Si k = b (#hijos de J)
J), devolver β
4. k Å k + 1, regresar a 4.1
NOTA: para el primer llamado del procedimiento, α = ∞ β=∞
∞,
Poda α - β: Ejemplo
y Marcar en el siguiente ejemplo las podas α - β:
MAX
max
MIN
min
max
min
max
16 15 14 13 12 11 10 9 8
21
7 6 5
4 3 2 1
Idea para Proyecto de Curso
y Implementación del Juego de Ajedrez
y Juego básico
y Mini-Max con poda α - β
22
¿Cómo implementar un juego de
ajedrez?
23