INGENIERIA INFORMATICA Y SISTEMAS
INTELIGENCIA ARTIFICIAL
BUSQUEDAS CON ADVERSARIOS
Sesión 5
Árboles y búsqueda con adversario
Los entornos competitivos, en los
cuales los objetivos del agente están
en conflicto, dan ocasión a problemas
de búsqueda entre adversarios, a
menudo conocido como juegos.
Ing. Victor Jaime Polo Romero 3
La manera natural de responder un
juego es mediante un árbol de juegos
que es un tipo especial de árbol
semántico en los que los nodos
representan configuraciones de
tableros
Ing. Victor Jaime Polo Romero 4
y las ramas indican como una
configuración puede transformarse en
otra mediante un solo movimiento.
Ing. Victor Jaime Polo Romero 5
Por supuesto existe un giro especial en
el hecho de que las decisiones son
tomadas por dos adversarios que
toman una decisión a la vez.
Un juego se define formalmente
como una clase de problemas de
búsquedas con los componentes
siguientes:
Ing. Victor Jaime Polo Romero 7
El estado inicial:
• Que incluye la posición del tablero e
identifica al jugador que mueve.
Ing. Victor Jaime Polo Romero 8
Una función sucesor:
• Que devuelve una lista de pares
(movimiento, estado), indicando un
movimiento legal y el estado que resulta.
Ing. Victor Jaime Polo Romero 9
Un test Terminal:
• Que determina cuando se termina el
juego. A los estados donde el juego se ha
terminado se les llama estados terminales.
Ing. Victor Jaime Polo Romero 10
Una función de utilidad:
• También llamada función objetivo o
función de rentabilidad, que da un valor
numérico a los estados terminales.
• En los juegos, el resultado es un triunfo,
pérdida o empate, con valores +1, -1 o 0.
Un árbol (parcial) de búsqueda para el juego de tres en raya.
Ing. Victor Jaime Polo Romero 12
Búsqueda entre adversarios
• Uso: decidir mejor jugada en cada momento para cierto tipo de juegos.
• ¿Que tipo de juegos?– 2 jugadores. – Movimientos alternos (jugador MAX, jugador MIN)
Ing. Victor Jaime Polo Romero 13
Representación del juego
• Representación del estado
• Representación del estado ganador (por estructura o propiedades o función
de utilidad)
• Definir los operadores de movimiento
Ing. Victor Jaime Polo Romero 14
Búsqueda entre adversarios
Ing. Victor Jaime Polo Romero 15
Búsqueda entre adversarios
• En una busqueda con adversarios se debe: generar todo el árbol de jugadas.
• Se etiquetan las jugadas terminales, dependiendo de si gana MAX o MIN, con un valor de utilidad de, por ejemplo, “+1” o “-1”.
• El objetivo es encontrar un conjunto de movimientos accesible que dé como ganador a MAX.
• Se propagan los valores de las jugadas terminales de las hojas hasta la raíz.
• Una búsqueda en profundidad minimiza el espacio.
Ing. Victor Jaime Polo Romero 16
Búsqueda entre adversarios
Ing. Victor Jaime Polo Romero 17
Búsqueda entre adversarios
Ing. Victor Jaime Polo Romero 18
Búsqueda entre adversarios
• Aproximación heurística: definir una función que nos indique lo cerca que estamos de una jugada ganadora (o perdedora).
• En esta función interviene información del dominio.
• Esta función no representa ningún coste ni es una distancia en pasos.
• Por convención:– las jugadas ganadoras se evalúan a “+”– las jugadas perdedoras se evalúan a “-”
• El algoritmo busca con profundidad limitada.• Cada nueva decisión implicará repetir parte
de la búsqueda.
Ing. Victor Jaime Polo Romero 19
Algoritmo minimax (1)
• Calcula la decisión minimax del estado actual.
• Usa un cálculo simple recurrente de los valores minimax de cada estado sucesor.
• La recursión avanza hacia las hojas del árbol.
• Los valores minimax retroceden por el árbol cuando la recursión se va deshaciendo.
Ing. Victor Jaime Polo Romero 20
Algoritmo minimax (2)
• Primero utiliza la función Utilidad para descubrir que sus valores son 3, 12 y 8.
• Entonces toma el mínimo de estos valores, 3, y lo devuelve como el valor del nodo B.
A
B
Ing. Victor Jaime Polo Romero 21
Minimax
Ing. Victor Jaime Polo Romero 22
Ejemplo 3 en rayae: estado x profundidad enteroe = número de filas, columnas y diagonales completas disponibles para max - número de filas, columnas y diagonales completas disponibles para minmax juega con X y desea maximizar emin juega con y desea minimizar evalores altos: buena posición para el que tiene que mover (profundidad par o impar)Controlar las simetrías
X
X
X0
X
0
X
0
X
0
X
0 X
0 X
X 0
0 X X0
X
0
X
0
X 0
6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-4=1 6-4=2 5-6=-1 6-6=0 6-6=0 5-6=-1 4-6=-2
Min= -1 Min= 1 Min= -2
Max = 1
La mejor jugada de max es pues tras lo cual min podría jugar X 0 X
Ing. Victor Jaime Polo Romero 23
0 X
X 0 X 0
X X
0 X X
0 XX
X 00 X
X 0 X0
X 0 X 0X 0 X 0
X 0 X 0
X 0 0 X
4-2=2
3-2=1
4-2=2
2-2=0
4-2=2
3-2=1
Min=0
0 XX 0
0 X X 0
0 X 0 X
0 0 X X
4-2=2 4-2=2 5-2=3 3-2=1 4-2=2 4-2=2
Min=0Min=1
Min=0
Max = 1
La mejor jugada de max es pues tras lo cual min podría jugar 0 XX
0 0 XX
0 0 XX
0 0 XX
……………...
……………...
Ing. Victor Jaime Polo Romero 24
0 0 XX
0 0 X XX
X 0 0 XX
0 0X XX
0 0 XX X
0 0 XX X
X 0 00 XX
X 0 0 XX 0
X 0 0 XX 0
X 0 0 X 0X
2-1=1
3-1=2
2-1=1
3-1=2
Min=1
Min= -
Min= -
Min= - Min= -
Max=1
La mejor jugada de max es pues X 0 0 XX
Ing. Victor Jaime Polo Romero 25
Poda alfa-beta
• Problema de la búsqueda minimax: el número de estados que tiene que examinar es exponencial con el número de movimientos.
• Es posible calcular la decisión minimax correcta sin mirar todos los nodos en el árbol.
• La poda alfa-beta permite eliminar partes grandes del árbol, sin influir en la decisión final.
A
B C D
a1
a2a3
b1 b2b3 c1 c2 c3
d1 d2 d3
3 12 8 2 4 6 14 5 2
3
3 2 2
MAX
MIN
El mejor movimiento de MAX en la raíz es a1, porque conduce al sucesor con el valor minimax mas alto, y la mejor respuesta de MIN es b1, por que conduce al sucesor con el valor minimax mas bajo.
A
B C D
3
[-, +]
[-, 3]
(a)
(a) La primera hoja debajo de B tiene el valor 3. De ahí B, que es un nodo MIN, tiene un valor de cómo máximo 3.
A
B C D
3
[-, +]
[-, 3]
(b)
(b) La segunda hoja debajo de B tiene el valor 12; MIN evitara este movimiento, entonces el valor de B es todavía como máximo 3.
12
A
B C D
3
[3, +]
[3, 3]
(c)
(c) La tercera hoja debajo de B tiene el valor 8; hemos visto a todos los sucesores de B, entonces el valor de B es exactamente 3. Ahora, podemos deducir que el valor de la raíz es al menos 3., por que MAX tiene una opción digna de 3 en la raíz.
12 8
A
B C D
3
[3, +]
[3, 3]
(d)
(d) La primera hoja debajo de C tiene el valor 2. De ahí, C que es un nodo MIN, tiene un valor de cómo máximo 2. Pero sabemos que B vale 3, entonces MAX nunca elegiría C. Por lo tanto, no hay ninguna razón en mirar a los otros sucesores de C. Este es un ejemplo de la poda Alfa-Beta.
12 8
[- , 2]
2
A
B C D
3
[3, 14]
[3, 3]
(e)
(e) La primera hoja debajo de D tiene el valor 14,entonces D vale como máximo 14. Este todavía es mas alto que la mejor alternativa de MAX (es decir, 3), entonces tenemos que seguir explorando a los sucesores de D. Note también que ahora tenemos límites sobre todos los sucesores de la raíz, entonces el valor de la raíz es como máximo 14.
12 8
[- , 2] [- , 14]
2 14
A
B C D
3
[3, 3]
[3, 3]
(f)
(f) El segundo sucesor de D vale 5, así que otra vez tenemos que seguir explorando. El tercer sucesor vale 2, así que ahora D vale exactamente 2. La decisión de MAX en la raíz es moverse a B, dando un valor de 3.
12 8
[- , 2] [2,2]
2 14 5 2
Poda alfa-beta
• Los dos parámetros alfa y beta describen los límites sobre los valores que aparecen a lo largo del camino: = el valor de la mejor opción (el más alto) que
se ha encontrado hasta el momento en cualquier punto del camino, para MAX
= el valor de la mejor opción (el más bajo) que se ha encontrado hasta el momento en cualquier punto del camino, para MIN
• La búsqueda alfa-beta actualiza el valor de y según se va recorriendo el árbol y termina la recursión cuando encuentra un nodo peor que el actual valor o correspondiente.
MAX
Vi
{ }Si Vi > modificar Si Vi poda
Retornar
{ }Si Vi < modificar Si Vi poda
Retornar
MIN
Vi
Las cotas y se transmiten de padres a hijos de 1 en 1 y en el orden de visitade los nodos. es la cota inferior de un nodo max. es la cota superior de un nodo min.
Ing. Victor Jaime Polo Romero 35
Fin