Download Tema 3: Juegos bipersonales - Grupo de Inteligencia Artificial

Tema 3: Juegos bipersonales
Resumen:
3. Juegos bipersonales
3.1. Juegos bipersonales básicos (con información perfecta)
3.2. Juegos bipersonales con elementos de azar
3.3
Juegos bipersonales con información incompleta
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Resolución de problemas con múltiples agentes
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Entorno multiagente
•
•
•
•
•
Situación:
múltiples agentes (jugadores) actúan en el mismo entorno
las acciones de los demás agentes influyen en la medida de
rendimiento de cada agente
ningún agente puede controlar las acciones de los demás agentes
hasta cierto punto, un agente puede predecir las acciones de los demás
Tipos de problemas multiagente :
• escenarios cooperativos: metas compartidas
• escenarios parcialmente cooperativos: algunas metas compartidas,
otras opuestas
• escenarios antagónicos: metas opuestas
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Escenarios antagónicos: Juegos de suma cero
Juegos de suma cero:
• juegos donde las ganancias y perdidas suman cero
• lo que un jugador gana es lo que el otro pierde
• ejemplo “clásico” de escenarios antagónicos
• p.E.: Ajedrez, Póker, …
– Juegos con recompensas: la ganancia /perdida tiene cantidad
• el jugador quiere maximizar la cantidad
– Juegos sin recompensas: solo se gana o se pierde
Tipos de juegos:
• elementos de azar:
– con elementos de azar (backgammon) /
sin elementos de azar (damas)
• información:
– información perfecta (damas) /
información incompleta (póker)
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Tema 3: Juegos bipersonales
Resumen:
3. Juegos bipersonales
3.1. Juegos bipersonales básicos (con información perfecta)
3.2. Juegos bipersonales con elementos de azar
3.3
Juegos bipersonales con información incompleta
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Modelar juegos bipersonales
•
Modelo similar a la búsqueda con un único agente (juegos unipersonales):
– Estados: cada situación del juego define un estado
– Acciones:
• jugadas permitidas en una determinada situación
• los jugadores ejecutan sus acciones de forma alternando
– Estado inicial: estado actual del juego
– Estado final: estado en el que termina el juego
•
•
•
Hay dos jugadores: max y min
No se busca un plan de acciones ya que el jugador contrario influye en el
progreso
Objetivo de un agente:
– encontrar la mejor jugada para él (la jugada que tiene las mayores posibilidades de
llevarle a ganar el juego)
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejemplo: Tres en Raya
Tres en Raya:
• dos jugadores (min y max)
• los jugadores van poniendo fichas en las casillas
de un tablero 3x3
– max usa las fichas X / min usa las fichas O
gana max
– una casilla puede contener como mucho una ficha
• Reglas:
– Inicialmente el tablero está vacío
– max empieza y los jugadores se van alternando en
poner sus fichas
gana min
– max gana si obtiene una raya de tres fichas X
– min gana si obtiene una raya de tres fichas O
– si todas las casillas están ocupadas sin que haya
una raya de 3 fichas del mismo tipo, hay empate
–1–
empate
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Modelar juegos bipersonales
Conocimientos mínimos a priori de los agentes max y min :
– s0
– expandir: s  {si1, ..., sin}
posición inicial (estado inicial)
cjto. finito de posiciones sucesores
– terminal?: s  true | false
prueba terminal
– U: s  k, k∈ℜ
función parcial de utilidad del juego
Nótese:
• la función expandir
– codifica las jugadas (acciones) permitidas en una posición s
– supone implícitamente que los jugadores se alternan en realizar las jugadas
• la función de utilidad está definida sólo en los estados terminales s
– juegos de suma cero sin recompensas: max gana si y sólo si min pierde
– gana max: U(s) = +∞ / gana min : U(s) = –∞ / empate: U(s) = 0
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejemplo: Árbol de juego para Tres en Raya
max
min
...
max
...
min
... ...
...
–∞
+∞
terminal
0
utilidad
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Árboles de juego
Definición:
Sea N un conjunto de nodos, E⊆N×N, L = {max,min}, y G = (N,E,L) un árbol
etiquetado. G es un árbol de juego si
– G no es vacío
– la raíz está etiquetada max
– todos los sucesores de max son etiquetados min
– todos los sucesores de min son etiquetados max
Observaciones:
• cada nivel del árbol de juego representa un ply (media jugada)
– en los nodos etiquetados max, es el turno del agente max
– en los nodos etiquetados min, es el turno del agente min
• las hojas de un árbol de juego (completamente desarrollado)
representan las posiciones terminales del juego
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Estrategias
Problema del agente max: ¿cómo determinar su mejor jugada?
• max podría aplicar métodos de búsqueda estándar, usando las posiciones en
las que él gana como estados meta
• pero min no querría realizar las acciones que el plan de max prevé para él !
Estrategia:
• define las jugadas de max para cada posible jugada de min
• un subárbol del árbol de juego
Estrategia óptima (ó racional) :
• la estrategia que implica el mejor resultado garantizado para max
• escenarios totalmente antagónicos con agentes racionales:
– max puede asumir que min hará lo mejor para sí mismo, lo cual el lo peor para max
• la estrategia óptima para max es la estrategia minimax:
– maximizar la utilidad mínima en cada jugada
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejemplo: estrategia minimax
estrategia óptima:
mejor jugada de max: a1
max
0
a2
a1
-∞
0
min
a3
a1,1 a1,2
a1,3
0
+∞
a2,1 a2,2
-∞
a2,3
a3,1
a3,2
a3,3
+∞ –∞
0
0
–∞
terminal
utilidad
0
+∞
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Método minimax
Método Minimax:
1.
Generar el árbol de juego completo
2.
Aplicar la función de utilidad en cada nodo terminal
3.
Propagar las utilidades hacia arriba
– en los nodos max, usar la utilidad máxima de los sucesores
– en los nodos min, usar la utilidad mínima de los sucesores
4.
Eventualmente los valores de utilidad llegan al nodo raíz (max)
5.
La jugada óptima de max es la que lleva al sucesor de utilidad máxima
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Algoritmo Minimax básico
• α : máximo de la utilidad de los
sucesores de un nodo max
• β : mínimo de la utilidad de los
sucesores de un nodo min
Algoritmo:
• funciones mutuamente recursivas
• estado es el estado actual
{MaxValor en el Minimax básico}
{MinValor en el Minimax básico}
Función MaxValor(estado)
Si terminal?(estado) entonces
devolver(U(estado))
sucesores ← expandir(max, estado)
α ← −∞
Para cada s∈sucesores hacer
α ← max(α, MinValor(s))
devolver(α)
Fin {MaxValor}
Función MinValor(estado)
Si terminal?(estado) entonces
devolver(U(estado))
sucesores ← expandir (min, estado)
β ← +∞
Para cada s∈sucesores hacer
β ← min(β,MaxValor(s))
devolver(β)
Fin {MinValor}
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Decisiones imperfectas
Problema: crecimiento exponencial del árbol de juego
• incluso en juegos muy simples, es imposible desarrollar el árbol de
juego completo hasta todos sus nodos terminales
Solución: Heurísticas
• sustituir la prueba terminal por una prueba suspensión que detiene la
búsqueda aún sin llegar a una posición terminal:
– límite de profundidad fijo
– posiciones “en reposo”
• aplicar una función de evaluación e, que estime la utilidad esperada
del juego correspondiente a una posición s determinada
– suele ser función lineal ponderada : e(s) = w1 f1(s) + w2 f2(s) + . . . + wn fn(s)
– Ajedrez:
e(s) = “suma de los valores materiales en s”
– Tres en Raya: e(s) = “nº de líneas abiertas para líneas max en s” –
“nº de líneas abiertas para líneas min en s”
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejemplo: minimax con suspensión
estrategia óptima:
mejor jugada de max: a1
max
3
a2
a1
3
min
a1,1 a1,2
evaluación e
3
12
a3
2
a1,3
8
a2,1 a2,2
2
4
–1–
2
a2,3
a3,1
a3,2
6
14
5
a3,3
2
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Algoritmo Minimax con suspensión
Algoritmo:
• funciones mutuamente recursivas
• estado es el estado actual
• α : máximo de la evaluación de los
sucesores de un nodo max
• β : mínimo de la evaluación de los
sucesores de un nodo min
{MaxValor: Minimax con suspensión}
{MinValor: Minimax con suspensión}
Función MaxValor(estado)
Si suspensión?(estado) entonces
devolver(e(estado))
sucesores ← expandir(max, estado)
α ← −∞
Para cada s∈sucesores hacer
α ← max(α, MinValor(s))
devolver(α)
Fin {MaxValor}
Función MinValor(estado)
Si suspensión?(estado) entonces
devolver(e(estado))
sucesores ← expandir (min, estado)
β ← +∞
Para cada s∈sucesores hacer
β ← min(β,MaxValor(s))
devolver(β)
Fin {MinValor}
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejemplo: Tres en Raya
Suspensión en ply 3
2
max
-∞
min
max
1
...
-∞
...
-∞
...
+∞
-∞ + ∞
1
2
1
+∞
1
2
1
1
+∞
...
+∞
+∞
2
0
2
-∞
2
+∞
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
–1–
0
0
2
+∞
Juegos con recompensas variables
• Juegos sin recompensas variables:
– gana max: U(s) = +∞ / gana min : U(s) = –∞ / empate: U(s) = 0
• Juegos de recompensas variables: por ejemplo ganar puntos/dinero/…
– La utilidad de un nodo hoja depende de la recompensa
• la propia recompensa puede define la utilidad
– La función de evaluación tiene que evaluar la recompensa esperada
– Ejemplo: cantidad de dinero que se gana, …
• A veces la estrategia minimax es dudosa:
99
99
a1,1 a1,2
99
1000
a2
a1
a1,3
?
1000
a2,1
100
–1–
100
a2,2
101
a2,3
102
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejercicio 3.1
Considérese el siguiente árbol de juego desarrollado hasta ply 3. Los nodos
están etiquetados con los valores de la función de evaluación e.
a) Evalúe el árbol del juego en base al algoritmo minimax.
b) ¿Cuál es la mejor jugada para el agente max?
7
6
8
5
2
3
0
–1–
–2
6
2
5
8
9
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
2
Poda α-β
Nótese:
• a veces es posible calcular la utilidad de un nodo sin tener que evaluar
todos sus sucesores
max
3
a2
a1
≤2
3
min
a1,1 a1,2
3
12
a3
a1,3
8
a2,1 a2,2
2
2
a2,3
a3,1
14
–1–
a3,2
5
a3,3
2
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Poda α-β
Utilidad más alta encontrada en un nodo max hasta el momento: α
α
max
min
...
Condición de poda: β≤α
• La utilidad Umin del nodo min
será como mucho β
• La utilidad Umax del nodo max
será al menos α
• No es necesario explorar los
sucesores restantes de min, ya
que se cumple en todo caso:
Umin ≤ β ≤ α ≤ Umax
β
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Poda α-β
Utilidad más baja encontrada en un nodo min hasta el momento: β
β
min
max
...
Condición de poda: α≥β
• La utilidad Umax del nodo max
será al menos α
• La utilidad Umin del nodo min
será como mucho β
• No es necesario explorar los
sucesores restantes de max, ya
que se cumple en todo caso:
Umin ≤ β ≤ α ≤ Umax
α
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Minimax con poda α-β
• α es el mejor valor de evaluación
para max en el camino hasta estado
• β es el mejor valor de evaluación
para min en el camino hasta estado
Algoritmo:
• funciones mutuamente recursivas
• estado es el estado actual
{MaxValor: Minimax con poda α−β}
{MinValor: Minimax con poda α−β}
Función MaxValor(estado,α,β)
Función MinValor(estado,α,β)
Si suspensión?(estado) entonces
Si suspensión?(estado) entonces
devolver(e(estado))
devolver(e(estado))
sucesores ← expandir(max, estado)
sucesores ← expandir (min, estado)
Para cada s∈sucesores hacer
Para cada s∈sucesores hacer
α ← max(α, MinValor(s,α,β ))
β ← min(β,MaxValor(s,α,β ))
Si α ≥ β entonces devolver(α)
Si β ≤ α entonces devolver(β)
devolver(α)
devolver(β)
Fin {MaxValor}
Fin {MinValor}
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejercicio 3.2
Considerese el árbol de juego del ejercicio anterior. Evalúe el árbol
utilizando el algoritmo minimax con poda α-β. Cuando aplica una poda,
indique la condición de poda correspondiente.
7
6
8
5
2
3
0
–1–
–2
6
2
5
8
9
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
2
Resumen minimax
Análisis:
• la eficiencia de minimax con poda α-β depende del orden en el que se
exploran los nodos
• en promedio, la poda α-β permite expandir 50% menos nodos que minimax
Problemas:
• efecto horizonte:
– la búsqueda se suspende justo cuando el jugador está por hacer una gran jugada
• suposición de racionalidad perfecta:
– suponga que max está a punto de perder si min juega de forma óptima
– sin embargo, hay una jugada que hace ganar a max, si min hace un solo error
Extensiones:
• heurísticas “fuertes” basados en meta-razonamiento
– algoritmos de búsqueda guiados por la utilidad esperada de expandir un nodo
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Tema 3: Juegos bipersonales
Resumen:
3. Juegos bipersonales
3.1. Juegos bipersonales básicos (con información perfecta)
3.2. Juegos bipersonales con elementos de azar
3.3
Juegos bipersonales con información incompleta
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Juegos bipersonales con elemento de azar
• Muchos jugos tienen elementos de azar:
– p.E.: cualquier juego con dados
• ¿Cómo tratar estos elementos?
• Algoritmo: EXPEXTMINIMAX
• Idea:
– Utilizar el algoritmo minimax
– Añadir un nuevo jugador: “azar” que se incluye en el árbol siempre que haya
un evento independiente de los jugadores y cuyo resultado es aleatorio
– Los sucesores de un nodo “azar” son las posibles situaciones que podrían ser
el resultado de este elemento de azar
• p.E.: todos los posibles resultados de tirar un dado
– Cada uno de los sucesores de un nodo “azar” tiene asociado la probabilidad de
que este resultado ocurra
• p.E.: en el caso del dado: P(1)=1/6, …, P(6)=1/6
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejemplo: Backgammon simplificado
• Estado inicial:
0 1 2 3 4
5
• Objetivo:
– mover las fichas al lado opuesto (max=
, al campo 5 y min=
al campo 0)
• Reglas:
– max empieza y los jugadores se van alternando sus jugadas
– Cada jugada consiste primero en tirar una moneda; la cara tiene el valor 1 y la
cruz el valor 2. Después se mueve una de las fichas 1 o 2 campos en la
dirección deseada (dependiendo del resultado de la tirada de la moneda)
– No es posible mover una ficha a un campo que tiene una ficha del oponente
– Si un jugador no puede mover sus fichas pierde su turno (si puede, tiene que
mover una ficha)
– Gana el jugador que primero ha movido ambas fichas al campo deseado
• El elemento de azar ocurre antes de elegir la jugada
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejemplo: Backgammon simplificado
Representación eficiente de estados: (x1,x2,y1,y2)
x1 y x2 posiciones de las fichas blancas e y1,y2 posiciones de las fichas negras
Árbol del juego:
1;1/2
(1,0,5,5)
1;1/2
1;1/2
(2,0,5,5)
(0,1,5,5)
…
…
(0,2,5,5)
azar
min
azar
(1,0,5,4)
max
2;1/2
(2,0,4,5)
max
2;1/2
2;1/2
(1,0,4,5)
azar
(0,0,5,5)
(1,1,4,5)
…
azar
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Expectminimax
• Objetivo: elegir la mejor jugada para max
• ¿Cómo propagar los valores de utilidad/evaluación de los nodos hoja a los
nodos superiores?
• Solución:
ExpectMinimax(n) =
; si n es nodo terminal o de suspensión
e(n)
 max
s∈ expandir(max,n)(ExpectMinimax(s)) ; si n es nodo max


min
(ExpectMinimax(s)) ; si n es nodo min si n es nodo min
s
∈
expandir(m
in,
n)


(P(s) ⋅ ExpectMinimax(s)) ; si n es nodo azar
∑
s∈ expandir(min,n)
• Implementación: ejercicio
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejemplo: Backgammon simplificado
• Situación actual: (toca a max)
0 1 2 3 4
5
cara
(3,4,1,2); max tiene que mover una ficha (blanca) una posición
• Suponemos el algoritmo expectminimax con un nivel de suspensión de 5
• Como función de evaluación se usa la siguiente: e((a,b,c,d))=a+b+c+d
• valores altos de a y b son buenos para max porque indican que sus fichas
están cerca de la meta (5)
• valores altos de c y d son buenos para max porque indican que las fichas
de min estan lejos de su meta (0)
• para el estado actual: e((3,4,1,2))=10
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
max
azar
min
azar
max
1;1/2
10,5
(4,4,1,1)
2;1/2
1;1/2
11
10
10,5
(4,4,1,2)
(5,4,0,2)
1;1/2
10
(4,4,0,2)
10,5
2;1/2
11
2;1/2
(4,4,1,0)
11,51;1/2
(3,5,1,1)
2;1/2
11,5
(3,5,0,2)
11,5
(3,5,1,2) 11
2;1/2
10,5
11
10
(3,5,1,0)
10,5
1;1/2
2;1/2
1;1/2
(4,5,0,2)
(4,4,0,2)
(5,4,1,0)
9,5 1;1/2
2;1/2
9,5
1;1/2
e(nodo)
(5,4,1,1) 11
(4,5,1,1) 11
(4,4,1,1) 10
11
11
10
10
10
10
(4,5,1,0)
9
(4,4,1,0)
11
(4,5,1,1)
9
11
12
(5,5,1,1)
12
11
(4,5,0,2)
11
12
(5,5,0,2)
12
10
(4,5,1,0)
10
2;1/2
–1–
11
(5,5,1,0)
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
11
Funciones de evaluación/utilidad
Criterios de los funciones de evaluación/utilidad:
• no pueden devolver +∞ o –∞ (los nodos azar tendrían siempre valores +∞
o –∞)
•
la escala de los valores si importa (no como en el algoritmo minimax):
max
2,1
0,1
0,9
2
1,3
2,1
azar
min
4,9
0,9
4,9
4,8
0,1
0,9
0,1
2
3
1
4
2 3
3 1
1 4
4
2
–1–
0,9
0,1
2
30
1
40
2 30
30 1
1 40
40
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Funciones de evaluación/utilidad
Caso ideal:
• La función de evaluación debe ser una transformación lineal positiva de la
probabilidad de ganar (o de la recompensa esperada)
e(nodo)
P(ganar|nodo)
• Muchas veces es difícil establecer una función e que cumple este criterio (véase
el ejemplo)
• Juegos con recompensas:
– la propia recompensa suele proporcionar una buena función de evaluación
– Ejemplo: backgammon simplificado donde, además, el perdedor paga al ganador 1
euro por cada unidad de distancia de sus fichas respecto a la meta
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Estrategia ExpectMinimax/ Estartegias alternativas
max
• Estrategia del algoritmo ExpectMinimax:
– max siempre hace lo mejor para él (máximo)
– min siempre hace lo mejor para si mismo
1,8
(mínimo)
– nodos de azar se pondera la utilidad por la 0,7 0,3
probabilidad
azar
1,4
0,4
0,1
0,6
0,9
0,1
0
1
Estrategia optimista
5
3
-1 -4
Estrategia pesimista
– elige el máximo en los nodos de azar
– elige el mínimo en los nodos de azar
5
3
0,7
3
0,3
-1
0,4
-4
-4
-1
1
0,6
0,9
0,1
0,7
0,3
5
0
1
3
-1
–1–
0,4
-4
0
0,6
0,9
0,1
5
0
1
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
El dinero como función de utilidad
• El dinero puede proporcionar una función de utilidad
• Pero considera el siguiente ejemplo:
– Un ganador de un concurso puede aceptar el premio de 1.000.000 euros o jugarse
el premio a cara y cruz. Si acierta gana el 3.000.000 euros y si no acierta pierde
todo.
1.500.000 E
1.000.000 E
0,5
0E
0,5
3.000.000 E
• Mejor U(s)∈(0..10): U(0E)=0; U(1.000.000E)=8; U(3.000.000E)=9
U=4,5
1.000.000 E
U=8
0,5
–1–
0,5
0 E 3.000.000 E
U=0
U=9
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Complejidad ExpectMinimax
• Proporcional al número de nodos en el árbol
• d- nivel de suspensión, b- factor de ramificación
• Si no tuviéramos nodos de azar, sería la misma complejidad que en
el minimax: O(bd)
• Si en cada jugada existe un elemento de azar con n posibilidades, la
complejidad se convierte en O(bd*nd)
• Ejemplo Backgammon: n=21 (2 dados) y b≈20
Nr. jugadas anticipadas
incluyendo un nivel azar (d)
Nr. nodos (ap.)
1
20*21=420
2
176400
3
74088000
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejercicio 3.3
Considere el siguiente árbol de juego. Evalúe el árbol utilizando el
algoritmo expectminimax. Las probabilidades de los diferentes nodos son
0,5 para cada acción en los nodos de azar del nivel 3 y los que se indican en
el árbol para los nodos de nivel 1.
max
azar
0,2
0,7
0,1
0,1
0,9
0,3
0,7
min
azar
7 6 7 0 8 9 12 11 1 1 3 4 4 4 0 1 7 2 3 -2 0 6 2 8 7 7 7 6
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Varios jugadores y alternancia no simétrica
Para más (o menos) jugadores y alternancias no estrictamente simétricas
• Ejemplo:
– Parchis: Si un jugador tiene un seis le toco otra vez
– “La oca”: “de oca en oca y tiro porque me toca”
• Minimax y Expectminimax son igualmente aplicables:
– simplemente se añaden los nodos correspondientes en la posición
correspondiente en el árbol
min
max
azar
0,2
0,7
0,1
…
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejercicio 3.4
El algoritmo ExpectMinimax también es aplicable en determinados casos
en los que sólo actúa un agente y en los que existen elementos de azar.
Considere el siguiente juego. Un agente A quiere apostar dinero en una
casa de apuestas. Las reglas de las apuestas son siempre las mismas: hay
una probabilidad de ganar del 0,4 y de perder del 0,6. El agente puede
elegir entre las siguientes acciones: irse a casa con el dinero que le queda,
o apostar cualquier cantidad (entera) de su dinero.
Utilice el algoritmo ExpectMinimax para decidir que le conviene hacer al
agente si tiene un euro. Para ello realiza el árbol hasta incluyendo dos
rondas de apuestas. ¿Qué función de evaluación se puede usar?
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Tema 3: Juegos bipersonales
Resumen:
3. Juegos bipersonales
3.1. Juegos bipersonales básicos (con información perfecta)
3.2. Juegos bipersonales con elementos de azar
3.3
Juegos bipersonales con información incompleta
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Juegos bipersonales con información incompleta
En muchos juegos los jugadores no conocen el estado del juego completamente
• El agente solo tienen información parcial sobre el estado actual
• El agente sólo sabe que el juego se encuentra en alguno de los estados que
concuerdan con la información de la que disponen
• El estado actual real es uno de una serie de estados posibles
• Ejemplo:
– juegos con cartas (que se reparten al principio), bridge, versiones simples de
póker, …
(Primera) Idea:
• Considerar cada posible valor de los parámetros desconocidos y su
probabilidad de ocurrencia / crear un árbol para cada posible estado
• Aplicar el algoritmo ExpectMinimax
• Elegir la acción que es mejor en todos los posibles casos
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
ExpectMinimax con información incompleta
• Situación actual del agente:
– En un momento dado (estado indeterminado s0) existen n combinaciones distintas
de valores para los parámetros desconocidos (estados posibles s1,…,sn)
– La probabilidad de que el estado actual sea si es p(si) con p(s1)+…+p(sn)=1
– El agente puede elegir entre m posibles acciones: a1,…,am
• Combinar todos los posibles árboles (para todos los posibles estados s1,…,sn)
s0
p(s1)
a1
U(a1|s1)
s1
am
…
p(sn)
…
a1
U(a1|sn)
U(am|s1)
sn
am
…
U(am|sn)
• Obtener las utilidades para cada acción y cada posible estado si
n
• Calcular la utilidad de cada acción: U (ai ) = ∑ p( sk ) ⋅U (ai | sk )
k =1
• Realizar la acción ai que maximize U(ai)
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejemplo 1: “Apuestas 1”
• Dos jugadores (min y max) y una baraja de cartas con 2 ases (A), 2 reyes
(K) y 2 reinas (Q).
• Reglas:
– Cada jugador pone un euro en el bote. Después obtiene una carta.
– A continuación max puede pasar (min gana el bote), o puede apostar 2 o 4
euros.
– Min puede pasar (max gana el bote) o igualar (poner igualmente dos euros).
– Si min igual la apuesta de max, ambos enseñan sus cartas.
– Gana el bote aquel jugador cuyas cartas tiene mayor valor (A>K>Q)
– Si ambas cartas tienen el mismo valor entonces se reparte el bote (nadie
gana ni pierde).
• Problema para max:
– max ha tenido una carta K y no conoce la carta de min
– ¿Qué acción conviene a max?
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Aplicar ExpectMinimax: Apuestas 1
<K,?>
2/5 <K,A>
<K,Q> 2/5
1/5 <K,K>
4
p
4
p
2
2
2
-1
4
p
0
p
1
i
p
i
p
i
p
0
i
1
3
1
5
1
0
1
0
1
-1
-5
p
-3
i
1
-3 1
-1
p
• Calcular la utilidad de cada acción:
U ( p ) = 2 / 5 ⋅ −1 + 1 / 5 ⋅ −1 + 2 / 5 ⋅ −1 = −1
U ( 2 ) = 2 / 5 ⋅ 1 + 1 / 5 ⋅ 0 + 2 / 5 ⋅ −3 = −0,8 Acción óptima: apostar 2 euros
U ( 4 ) = 2 / 5 ⋅ 1 + 1 / 5 ⋅ 0 + 2 / 5 ⋅ −5 = −1,4
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
i
-5
Aplicar ExpectMinimax: Apuestas 1
¿Porqué la utilidad de apostar 2 euros es -0,8?
• max tiene mayores posibilidades de perder dinero que de ganar dinero
Analizamos:
• si max tiene un K y apuesta 2 euros:
– Si min tiene K (probabilidad 1/5) max no pierde nada
– Si min tiene A (probabilidad 2/5) max pierde 3 euros
• solo en el peor de los casos, es decir, si min iguala la apuesta
• es lo que debería hacer min si tiene A
– Si min tiene Q (probabilidad 2/5) max gana 1 euro
• solo en el peor de los casos, es decir, si min pasa
• eso es lo más razonable para min si tiene Q
• el algoritmo siempre considera el peor caso para max
– se supone que min siempre actúa lo mejor posible
La solución es razonable:
• En muchos casos este algoritmo funciona aceptablemente bien
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejemplo 2: “Adivina la carta”
Consideramos el siguiente juego hipotético:
• min coge una carta de una baraja (A o K con la misma probabilidad) y max
tiene que adivinarla
• max puede pasar o intentarlo. si pasa min le paga 1 euro
• Luego min decide si pasa (tiene que pagar 10 euros a max) o permite a max
que lo intente.
• Finalmente, max intenta adivinar la carta.
• Si acierta gana 5 euros de min y si no acierta pierde 5 euros a min.
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejemplo 2: Adivinar la carta
<?>
<K>1/2
p
1/2 <A>
p
i
+5
1
p
i
1
p
i
i
+5
+5
+10
+5
+10
K
A
K
A
+5
-5
-5
+5
• ¿Qual es la mejor jugada para max: pasar o intentarlo?
U ( p ) = 1 / 2 ⋅1 + 1 / 2 ⋅1 = 1
U (i ) = 1 / 2 ⋅ 5 + 1 / 2 ⋅ 5 = 5
Según el algoritmo, max debe intentar de
adivinar la carta aunque tenga un 50% de
posibilidad de perder 5 euros. Mientras si
pasa gana 1 euro seguro.
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
¿Porqué no funciona bien el algoritmo?
• El algoritmo es:
– demasiado optimista para max
• Se supone que max siempre hace lo mejor para él
– Si la carta que tiene min es K max dirá K
– Si la carta que tiene min es A max dirá A
– PERO: en realidad max no sabe la carta que tiene min
• Para hacer lo mejor para si mismo, max necesita toda la información
– sólo tiene información parcial
→
Solución: ExpectMinimax con estados de creencias
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Primero formalizar mejor el proceso de decisión en
juegos bipersonales
Antes de nada:
– Formalizar el modelo de transición de estados del problema (el espacio de estados).
– ¡Esta formalización es la misma para minimax y expectminimax y minimax con
estados de creencia!
Tenemos (conocimientos a priori del agente):
– estados, conjunto S={s0,s1,…}
– acciones, conjunto de acciones AC={a1, a2, …}
Conocimientos a priori y suposiciones:
• En cada estado hay un conjunto de acciones aplicables
– Sea A: S×AC→{0,1} una función que estima si se puede aplicar a en s
1, si a es aplicable al estado s
A( s , a ) = 
0, en otro caso
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Primero formalizar mejor el proceso de decisión en
juegos bipersonales
Más conocimientos a priori:
• Cada realización de una acción en un estado lleva con una determinada
probabilidad a otro estado y genera una observación
– el agente percibe las observaciones después de que se haya realizado la acción
a,1/4,o1
s3
a,3/4,o2
s1
s2
– aplicar a en s3 lleva con probabilidad ¼ a s1 (generando o1) y con
probabilidad ¾ a s2 (generando o2)
– Conjunto posible de observaciones en el dominio: OB={o1, o2, …}
– Se supone una observación por defecto od∈OB que se percibe si “no se observa
nada” (p.e.: mi oponente coge una carta y no me la enseña)
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Primero formalizar mejor el proceso de decisión en
juegos bipersonales
Más conocimientos a priori:
• Formalizar las transiciones:
a,1/4,o1
s3
a,3/4,o2
s1
s2
– T:S×AC×S→[0,1] es un modelo de transición
– T(s,a,s’) denota la probabilidad de que la acción a aplicado a s lleva al
estado s’ (p. E.:T(s3,a,s1)=1/4)
– T cumple que:
•
1, si A(a, s) = 1
T ( s , a, s' ) = 
∑
s' ∈S
0, en otro caso
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Primero formalizar mejor el proceso de decisión en
juegos bipersonales
Más conocimientos a priori:
• Formalizar las observaciones:
a,1/4,o1
s3
a,3/4,o2
s1
s2
– O: S×AC×S×OB →{0,1} es un modelo de observaciones
1, si la transición del estado s al estado s'

O( s, a, s ' , o) =  con la acción a genera la observación o
0, en otro caso

– O determina si una observación se genera como resultado de aplicar a a s
y teniendo como estado resultado s’ (p. E.:O(s3,a,s1,o1)=1)
– Se supone:
• Cada tupla S×AC×S tiene una y sólo una observación asociada
• Esta observación puede ser la observación por defecto od
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Primero formalizar mejor el proceso de decisión en
juegos bipersonales
Más conocimientos a priori:
• Los modelos de observaciones y transiciones definen 3 tipos de acciones
posibles:
Acciones deterministas
a,1,o1
s3
s1
Acciones con elementos
de azar no observables
a,1/4,o1
s3
a,3/4,o1
- el resultado de a en s
es determinista
- solo hay una posible
observación
- resultado observable
- p.e.: “jugar un as”
s1
s2
- el resultado de a en s
es probabilística
- la observación recibida
es siempre la misma
- resultado no observable
- p.e.: “coger una carta min”
–1–
Acciones con elementos
de azar observables
a,1/4,o1
s3
a,3/4,o2
s1
s2
- el resultado de a en s
es probabilística
- la observación recibida
es distinta en cada caso
- resultado observable
- p.e.: “coger una carta max”
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Primero formalizar mejor el proceso de decisión en
juegos bipersonales
• Ejemplo:
– Supón un juego hipotético con cartas: 4 ases (A) y 4 reyes (K)
– Cada jugador tiene unas cartas de la baraja (y no ve las cartas del otro jugador)
– Los jugadores se alternan
• Hay dos turnos de coger cartas
• En cada turno cada jugador puede coger una carta o pasar
– Al final gana el que tiene mayor proporción de ases respecto a reyes y, si ámbos tiene
la misma proporción, el que tiene más ases
– ¿Como se definirían los elementos del modelo de transición?:
Estados, Acciones, Observaciones
A(si,a)=¿?
T(si,a,sj)=¿?
O(si,a,sj,ok)=¿?
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Primero formalizar mejor el proceso de decisión en
juegos bipersonales
• Ejemplo:
– Estados:
• <x,y>; x - las cartas de max; y – las cartas de min
• S={<x,y> con x,y∈{{},{A},{K},{A,A},{A,K},…} }
– Acciones:
• AC={“coger carta max”, “coger carta min”, “pasar max”, “pasar min”}
– Observaciones:
• OB={“K”,”A”,”nada”)
– A(si,a): definido por las reglas del juego
•
•
•
•
•
Están definidos por las reglas del juego,
A(<x,y>,”pasar max”,<x,y>)=1, si le toca a max
A(<x,y>,”pasar min”,<x,y>)=1, si le toca a min
A(<x,y>,”coger carta min”,<x,y>)=1, si le toca a min
A(<x,y>,”coger carta max”,<x,y>)=1, si le toca a max
• Se supone que se controla el progreso (a quien toca en cada momento y que acciones puede
realizar) del juego por algún mecanismo a parte.
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Primero formalizar mejor el proceso de decisión en
juegos bipersonales
Ejemplo:
– T(s,a,s’): definido por las reglas del juego
• Sea s=<x,y> y |x| e |y| el número de cartas de max y min; y xA, yA, xK e yK el número de
ases y de reyes de max y min
•
•
•
•
•
•
•
T(<x,y>,”pasar max”,<x,y>)=1
T(<x,y>,”pasar min”,<x,y>)=1
T(<x,y>,”coger carta max”,<x∪{A},y>) =(4- xA – yA)/(8- |x| - |y|)
T(<x,y>,”coger carta max”,<x∪{K},y>) =(4- xK – yK)/(8- |x| - |y|)
T(<x,y>,”coger carta min”,<x,y∪{A}>) =(4- xA – yA)/(8- |x| - |y|)
T(<x,y>,”coger carta min”,<x,y∪{K}>) =(4- xK – yK)/(8- |x| - |y|)
Para todas las demás pares de (s,a,s’): T(s,a,s’)=0
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Primero formalizar mejor el proceso de decisión en
juegos bipersonales
Ejemplo:
– O(si,a,sj,ok): definido por las reglas del juego
•
•
•
•
•
•
•
O(<x,y>,”pasar max”,<x,y>,nada)=1
O(<x,y>,”pasar min”,<x,y>,nada)=1
O(<x,y>,”coger carta max”,<x∪{A},y>,A) =1
O(<x,y>,”coger carta max”,<x∪{K},y>,K) =1
O(<x,y>,”coger carta min”,<x,y∪{A}>,nada) =1
O(<x,y>,”coger carta min”,<x,y∪{K}>,nada) =1
Para todas las demás pares de (s,a,s’,o): O(s,a,s’,o)=0
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Primero formalizar mejor el proceso de decisión en
juegos bipersonales
• El modelo de transición define el grafo del problema (espacio de estados):
• La misma acción puede llevar a diferentes estados (con alguna probabilidad)
<{A},{K,A}>
“coger carta max”, p=2/5, A
<{A,A},{K,A}>
“coger carta min”, p=2/5,nada
“pasar max”, p=1, nada
<{A,A},{K}>
<{A,A},{K,K}>
“coger carta min”, p=3/5,nada
“pasar min”, p=1, nada
“coger carta max”, p=2/5, A
“coger carta max”, p=3/5, K
<{A,A,K},{K}>
–1–
<{A,A,A},{K}>
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
ExpectMinimax con estados de creencias
• Los jugadores no conocen exactamente el estado actual del juego
– sólo tienen información parcial del estado del juego
– sólo saben que el juego se encuentra en alguno de los estados que concuerdan con
la información de la que disponen
• Estados de creencia: anotado por b
– distribución de probabilidad sobre todos los posibles estados del juego
– Sea S={s1,…,sn} el conjunto de estados del problema/juego.
– b=((s1,p1),…,(sn,pn))
• pi= probabilidad/creencia de que el estado actual es si
• p1+…+pn=1
– Representación comprimida de un estado de creencia:
• omitir todos los estados con probabilidad 0
– Definimos b(s)= la probabilidad del estado s en el estado de creencia b
• Si b=((s1,p1),…,(sn,pn)), entonces b(s1)=p1
• Idea:
– Adaptar EpectMinimax a los estados de creencia
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Estado de creencias
Ejemplos:
• Apuestas 1:
– Estados: <x,y>, x,y ∈{K,Q,A} x- carta de max, y- carta de min
– Situación actual: ambos jugadores tienen una carta, max tiene K y no sabe la
carta de min
– Estado de creencia (comprimido) de max:
• ((<K,Q>, 2/5),(<K,K>, 1/5), (<K,A>, 2/5))
• Adivinar la carta:
– Estados: <x>, x ∈{K,A} x- carta que tiene min
– Situación actual: min tiene una carta y max no sabe cual es
– Estado de creencia (comprimido) de max:
• ((<K>, 1/2),(<A>, 1/2))
OJO:
– Por simplicidad omitimos otra información que está contenida en el estado/estado
de creencia acerca de la situación actual del juego
– p.e.: en qué momento del juego se está, quién tiene el turno, …
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
ExpectMinimax con estados de creencias
• Problemas a resolver:
– 1. ¿Cómo cambia el estado de creencia al realizar una acción?
• crear el árbol del juego
– 2. ¿Cómo se evalúa la utilidad de un estado de creencia?
• evaluar los nodos hoja
– 3. ¿Cómo propagar la utilidad a los nodos superiores del árbol?
• propagar las utilidades para tomar una decisión
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
1. ¿Cómo cambia el estado de creencias al realizar
una acción?
• O¿Cómo podemos crear el árbol del juego?:
– La realización de una acción proporciona una observación y cambia el estado
(y, por tanto el estado de creencia).
– Si la acción contiene elementos de azar que son observables, cada
observación genera un nuevo estado de creencia
– Cada acción se modeliza de la sigiente forma en el árbol del juego:
posibles acciones en b
nodo de azar
nodo de decisión de un
agente (max o min)
b
a1, pa1
a2, pa2
posibles observaciones al
realizar a en b con sus
respectivas probabilidades
(puede ser sólo una
observacion en acciones
deterministas o no
observables)
…
o1, po1
b11’
on, pon
…
probabilidad de que se pueda
ejecutar la acción suponiendo b
b1n’
estados de creencia resultantes en
función de la observación
¿Cómo calcular
estos valores?
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
2. ¿Cómo cambia el estado de creencias al realizar
una acción?
• ¿Cómo calcular los valores?
b
pa1 = p (a1 | b) = ∑ b( s ) ⋅ A( s, a )
s∈S
a1, pa1
po1 = p(o1 | b, a1 )
o1, po1
b11’
= α ⋅ ∑∑ b( s ) ⋅ T ( s, a1 , s ' ) ⋅ O( s, a1 , s' , o1 )
on, pon
…
s '∈S s∈S
b1n’
b11 ' ( s ' ) = β ⋅ ∑ b( s ) ⋅ T ( s, a1 , s ' ) ⋅ O( s, a1 , s ' , o1 )
s∈S
α y β son factores que aseguran que
n
∑p
i =1
α=
1
n
∑∑∑ b(s) ⋅ T (s, a , s' ) ⋅ O(s, a , s' , o )
i =1 s '∈S s∈S
1
1
1
–1–
oi
β=
=1 y
∑b
s '∈S
11
' (s' ) = 1
1
∑∑ b(s) ⋅ T (s, a , s' ) ⋅ O(s, a , s' , o )
s '∈S s∈S
1
1
1
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
1. ¿Cómo cambia el estado de creencias al realizar
una acción?
• Ejemplo: Consideramos el siguiente espacio de estados
c,2/3,o1
s5
c,1/3,o1
b,1/2,o2
s1
b,1/4,o1
s3
a,1,o1
s2
a,1,o1
c,1,o1
b,1/2,o1
b,3/4,o2
s4
Acciones deterministas:
((s3,1))
a,1
o1,1
((s2,1))
((s2,1/3),(s3,2/3))
((s3,1/3),(s5,2/3))
a,1/3
a,1
o1,1
o1,1
((s2,2/3),(s3,1/3)
((s2,1))
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
1. ¿Cómo cambia el estado de creencias al realizar
una acción?
• Ejemplo:
c,2/3,o1
s5
c,1/3,o1
b,1/2,o2
s1
b,1/4,o1
s3
a,1,o1
s2
c,1,o1
a,1,o1
b,3/4,o2
b,1/2,o1
¡Dependiendo del estado, una misma
acción podría ser determinista, con
elementos de azar observable o con
elementos de azar no observable !
s4
Acciones con elementos de azar (observable y no observable):
((s1,1/3),(s2,1/3),(s3,1/3))
((s2,1/3),(s3,2/3))
c,2/3
b,1
o1,2/6
((s1,1/2),(s4,1/2))
o2,4/6
o1,1
((s4,3/4),(s5,1/4))
((s2,4/6),(s5,2/6))
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
1. ¿Cómo cambia el estado de creencias al realizar
una acción?
• Ejemplo:
–
–
–
–
Supón un juego hipotético con cartas: 4 ases (A) y 4 reyes (K)
Estados: <x,y>; x - las cartas de max e y – las cartas de min
Sea el siguiente estado hipotético de creencia: ((<{A},{A}>,3/7),(<{A},{K}>,4/7))
Sea la siguiente secuencia de acciones: 1-max coge otra carta, 2- min coge otra carta,
3- max puede jugar una de sus cartas, …
((<{A},{A}>,3/7),(<{A},{K}>,4/7))
coger carta max, p=1
A,p=3/7
K,p=4/7
((<{A,K},{A}>,1/2),(<{A,K},{K}>,1/2))
coger carta min, p=1
((<{A,A},{A}>,1/3),(<{A,A},{K}>,2/3))
nada, p=1
((<{A,K},{A,A}>,1/5),(<{A,K},{A,K}>,3/5),(<{A,K},{K,K}>,1/5))
jugar K, p=1
jugar A, p=1
nada, p=1
nada, p=1
((<{A},{A,A}>,1/5),(<{A},{A,K}>,3/5),
(<{A},{K,K}>,1/5))
…
((<{K},{A,A}>,1/5),(<{K},{A,K}>,3/5),
(<{K},{K,K}>,1/5))
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
2. ¿Cómo se evalúa la utilidad de un estado de
creencia?
• Suponemos que tenemos una función de utilidad U(s) o de evaluación e(s)
– definida para los estados
• Calcular U/e de un estado de creencia:
U (b) = ∑ b( s ) ⋅ U ( s )
s∈S
e(b) = ∑ b( s ) ⋅ e( s )
s∈S
• La utilidad de un estado de creencia es la media de las utilidades de todos los
estados posibles ponderados por su probabilidad
• Ejemplo:
- sean los estados <x,y>, con x,y∈N,
- la función de evaluación e(<x,y>)=x-y:
→ e( ((<3,4>,1/4),(<5,2>,3/4)) )=1/2*(-1)+1/2*3=2
• Importante: U/e(s) tiene que ser acotada:
• No puede tomar valores como ∞ o -∞
• U/e:S→ (nmin, nmax) , siendo (nmin, nmax) un intervalo limitado (positivo y/o negativo)
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
3. ¿Cómo propagar la utilidad a los nodos
superiores del árbol?
• Propagación de los valores de utilidad:
• En principio igual que en el algoritmo ExpectMiniMax teniendo en cuenta las
probabilidades de poder realizar una acción:
b
pa1=2/3
Nodos max: max( pai ⋅ U ( bi ))
pa2=1
-2
4/6
od, p=1
-2
Nodos azar:
4/6
pa2=1/4
pa3=2/3
-3
5/3
o1, p=1/3
n
od, p=1
o2, p=2/3
od, p=1
pa2=1/2
pa1=1
0
od, p=1
2
-3
i =1
i
i
Nodos min: min( pai ⋅ U ( bi ))
4/3
od, p=1
Nodos finales o de suspensión:
4/3
1
∑ p U( b )
- como visto antes
pa2=1
0
4/3
o2, p=2/3
o1, p=1/3
2
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
–1–
1
Ejemplo: De nuevo el ejemplo 2: Adivinar la carta
((K,1/2),(A,1/2))
p
i
((K,1/2),(A,1/2))
((K,1/2),(A,1/2))
0
p
i
1
((K,1/2),(A,1/2))
10
Se omiten los nodos de azar (todas
las acciones son deterministas) y las
probabilidades de poder realizar las
acciones (todas son 1)
((K,1/2),(A,1/2)) 0
K
A
((K,1/2),(A,1/2)) ((K,1/2),(A,1/2))
(1/2*5)+(1/2*-5)=0
(1/2*-5)+(1/2*5)=0
• Max hace lo mas razonable: pasar y ganar el euro seguro
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejemplo 3: Póker (muy) simplificado
Juego: Dos jugadores (max y min) y una baraja con 4 ases (A) y 4 reyes (K)
Reglas:
– Primero max obtiene una carta y luego min.
– Después max puede elegir entre coger o no otra carta.
– Después min decide si coge otra carta.
– Finalmente los dos enseñan sus cartas. Gana aquel cuyas cartas tienen mayor
valor según el siguiente orden:
• {K,K}<{K}<{A,K}<{A}<{A,A}
• El ganador recibe 3 euros del perdedor
• Si ambos tienen cartas del mismo valor entonces nadie gana ni pierde dinero.
• Problema:
– Max y min tienen ambos una carta. Max tiene un A y no sabe que tiene min
– Max quiere saber si debe o no coger una segunda carta
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejemplo 3: Póker (muy) simplificado
– Estados:
• <x,y>; x - las cartas de max; y – las cartas de min
– Acciones:
• AC={“2ª max”, “2ª min”, “no 2ª max”, “no 2ª min”}
– Observaciones:
• OB={“K”,”A”,”nada”)
– A(si,a): definido por las reglas del juego
• Las acciones están definidos en todos los estados (teniendo en cuenta cuando toca a cada
jugador)
Ojo:
– se supone que el estado del juego respecto a “la secuencia de pasos” (se controla en
otra parte)
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejemplo 3: Póker (muy) simplificado
– T(s,a,s’): Sea s=<x,y> y |x| e |y| el número de cartas de max y min; y xA, yA, xK e yK
el número de ases y de reyes de max y min:
•
•
•
•
•
•
•
T(<x,y>,”no 2ª max”,<x,y>)=1
T(<x,y>,”no 2ª min”,<x,y>)=1
T(<x,y>,”2ª max”,<x∪{A},y>) =(4- xA – yA)/(8- |x| - |y|)
T(<x,y>,”2ª max”,<x∪{K},y>) =(4- xK – yK)/(8- |x| - |y|)
T(<x,y>,”2ª min”,<x,y∪{A}>) =(4- xA – yA)/(8- |x| - |y|)
T(<x,y>,”2ª min”,<x,y∪{K}>) =(4- xK – yK)/(8- |x| - |y|)
Para todas las demás pares de (s,a,s’): T(s,a,s’)=0
– O(si,a,sj,ok): definido por las reglas del juego
•
•
•
•
•
•
•
O(<x,y>,”no 2ª max”,<x,y>,nada)=1
O(<x,y>,”no 2ª min”,<x,y>,nada)=1
O(<x,y>,”2ª max”,<x∪{A},y>,A) =1
O(<x,y>,”2ª max”,<x∪{K},y>,K) =1
O(<x,y>,”2ª min”,<x,y∪{A}>,nada) =1
O(<x,y>,”2ª min”,<x,y∪{K}>,nada) =1
Para todas las demás pares de (s,a,s’,o): O(s,a,s’,o)=0
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejemplo 3: Póker (muy) simplificado
Se omiten:
- nodos de azar innecesarios
- probabilidades de acciones (todas 1)
0*4/7+2,8*3/7=1,2
((<A,K>,4/7),(<A,A>,3/7))
2ª
2ª
1,71
((<A,K>,4/7),(<A,A>,3/7))
((<AK,K>,1/2),
(<AK,A>,1/2))
2ª
3/7,A
4/7,K
0
((<AA,K>,2/3),
(<AA,A>,1/3))
((<A,AA>,1/7),
(<A,KA>,4/7),
(<A,KK>,2/7))
2ª
((<A,K>,4/7),
(<A,A>,3/7))
(4/7*3)+
(1/7*-3)+
2ª
(3/7*0)=1,71
(4/7*3)+
((<AK,AA>,1/5), ((<AK,K>,1/2), ((<AA,AA>,1/15), ((<AA,K>,2/3),
(<AK,KA>,3/5), (<AK,A>,1/2)) (<AA,KA>,8/15), (<AA,A>,1/3)) (2/7*3)=2,14
2ª
(<AK,KK>,1/5))
(1/5*-3)+
(3/5*0)+
(1/5*3)=0
2ª
(1/2*3)+
(1/2*-3)=0
2ª2,8
(<AA,KK>,6/15))
(1/15*0)+
(8/15*3)+
(6/15*3)=2,8
–1–
(2/3*3)+
(1/3*3)=3
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Comentarios: Estrategia del algoritmo
• La estrategia del jugador max esta implementado de la siguiente forma:
– En estados de decisión de max, se supone que max elige la mejor opción
(máximo)
– En estados de azar, se supone una utilidad de las diferentes posibilidades
ponderado por la probabilidad
• sería posible cambiar a una estrategia más optimista o más pesimista
– En estados de decisión de min, se supone que min elige siempre la mejor opción
(mínimo):
• Respecto a min, eso es demasiado pesimista
– a min también le puede faltar información por lo que no es siempre capaz de
elegir la mejor acción para él.
• Posible extensión del algoritmo:
– Podemos suponer que min hace la mejor jugada según su estado de creencias
– Para saber que acción hará min, max debe simular las acciones de min según su
“creencia sobre el estado de creencia de min”
– Min tiene varios posibles estados de creencias, cada una con una probabilidad
determinada
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Simular el razonamiento de min
Si max no cogiese ninguna carta,
¿qué jugada de min es la más probable?
1,71
((<A,K>,4/7),(<A,A>,3/7))
2ª
2ª
((<A,K>,4/7),(<A,A>,3/7))
((<A,AA>,1/7),(<A,KA>,4/7),(<A,KK>,2/7))
2,14
1,71
Pensamiento de min:
¿Si min tuviera A?
(no sabe que max tiene A)
Probabilidad: 3/7
((<A,A>,3/7),(<K,A>,4/7))
-1,71
2ª
((<A,AA>,1/7),
(<A,AK>,2/7),
(<K,AK>,2/7),
(<K,AA>,2/7))
¿Si min tuviera K?
(no sabe que max tiene A)
Probabilidad:4/7
((<A,K>,4/7),(<K,K>,3/7))
1,29
2ª
2ª
((<A,KA>,2/7),
(<A,KK>,2/7),
(<K,KK>,1/7),
(<K,KA>,2/7))
((<A,A>,3/7),
(<K,A>,4/7))
-1,71
-1,29
2ª
((<A,K>,4/7),
(<K,K>,3/7))
1,71
1,29
Con la información de max: min debe coger una segunda carta con probabilidad 4/7 (si tuviera un Rey)
Y no debería coger una segunda carta con probabilidad 3/7 (si tuviera un As).
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Simular el razonamiento de min
• Introducción del resultado de las acciones de min en el razonamiento de max:
((<A,K>,4/7),(<A,A>,3/7))
1,2
2ª
2ª
U=1,96
((<A,K>,4/7),(<A,A>,3/7))
p=4/7
2ª
2ª
((<A,AA>,1/7),
(<A,KA>,4/7),
(<A,KK>,2/7))
((<A,K>,4/7),
(<A,A>,3/7))
1,71
2,14 n
• Propagación de las utilidades en los nodos min:
p=3/7
∑ p U (b )
i =1
i
i
• Se puede seguir este mismo razonamiento de forma recursiva:
– Para simular el razonamiento de min, min simularía el razonamiento de max y así
sucesivamente hasta se llega a los nodos finales
– Creencia de min de lo que cree max que cree min …
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Comentarios: Descubrir información
• Conocer el estado con más certeza mejora considerablemente el
razonamiento de max.
• El propio hecho de que min elige una u otra acción puede cambiar el estado
de creencias de max
• Supón que max no coge ninguna carta adicional pero min sí coge una:
– ¿Cómo sería el estado de creencia de max después de esta secuencia?
((<A,K>,4/7),(<A,A>,3/7))
2ª
((<A,K>,4/7),(<A,A>,3/7))
((<A,AA>,1/7),
(<A,KA>,4/7),
(<A,KK>,2/7))
• Usando la simulación del razonamiento de min de antes:
– Para ser racional, min debe coger una segunda carta si tiene un Rey y no debe
coger una segunda carta si tiene As: cabe suponer que tenía Rey
((<A,K>,4/7),(<A,A>,3/7))
2ª
((<A,K>,4/7),(<A,A>,3/7))
((<A,KA>,1/2),
(<A,KK>,1/2))
• Se puede utilizar la simulación del razonamiento de min para descubrir
información
• Muchas veces conviene realizar jugadas cuyo único fin es el de descubrir
información (p.e.: juegos de cartas,
...)
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Comentarios ExpectMinimax con estados de
creencias
• Complejidad
– El algoritmo es mucho más complejo que los algoritmos Minimax y
ExpectMinimax
– El número de estados es finito, pero el número de estados de creencia es
infinito (por el uso de las probabilidades)
– El cálculo de los estados de creencias resultantes a la aplicación de una acción
es más costoso que el calculo del estado siguiente
– Mayor falta de información implica:
•
•
•
•
Estados de creencias son más difusos (más estados posibles)
Las acciones propuestas son menos viables
El cálculo de los estado se creencia es más costoso
Ejemplo: adivinar 2 cartas entre 30
• Las extensiones del algoritmo (simulación del razonamiento de min)
aumentan aún más la complejidad
• Posibles mejoras de la complejidad: comprimir los estados de creencia:
– Concentrarse en la información más relevante (p.e: en el póker: probabilidad de
que el contrario tenga mejores cartas que yo)
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf
Ejercicio 3.4
Póker simplificado 2:
Considere el siguiente juego de dos jugadores (B y C) y una baraja con 4 ases
(A) y 4 reyes (K):
– Para jugar, cada jugador pone un euro en el bote. B obtienen una carta y puede
elegir si quiere otra. Después obtiene C su(s) cartas.
– A continuación B puede pasar (C gana el bote), o puede apostar 2 euros.
– Si apuesta le toca a C. C puede pasar (B gana el bote) o igualar (poner la misma
cantidad que B).
– Si C iguala la apuesta de B, ambos enseñan sus cartas. Gana el bote aquel jugador
cuyas cartas tiene mayor valor según el siguiente orden:
• {K,K}<{K}<{A,K}<{A}<{A,A}
– Si ambos tienen cartas del mismo valor entonces se reparte el bote.
• Problema:
– B ha cogido solo una carta y C ha obtenido un As:
– C quiere saber si le conviene coger una segunda carta
Resuelve el problema de decisión de C.
–1–
Fundamentos de Inteligencia Artificial
3º Ing. Sup. Inf