Introducción, I
Juegos
Origen, 1928: John Von Newmann
Teorema fundamental de los juegos bipersonales de suma nula.
Desarrollo, 1944: Oskar Morgernsten
“Theory of Games and Economic Behaviour”
Aplicaciones
Antropología, psicología, economía, política, negocios, biología, IA, etc.
Elementos:
Jugadores: personas, empresas, naciones, entes biológicos, etc.
Conjunto de estrategias: operadores o acciones
Resultado o Valor del juego: estado/s objetivos/s
Conjuntos de Pagos para cada jugador: función de utilidad sobre las estrategias
Introducción, II
Clasificación desde diferentes perspectivas:
Cooperación
Cooperativos/no cooperativos
Número de jugadores
n=2, bipersonales:
por naturaleza no cooperativos
n>2, n-personales:
Pueden ser cooperativos. Dan lugar a coaliciones
Beneficios
Suma nula:
la suma de beneficios y pérdidas de los jugadores debe ser 0. (Son habituales en IA).
Suma no nula: caso contrario
Duración
Finitos:
tienen final programado (nº jugadas, ruinas, etc.)
Infinitos: sin final programado
Introducción, III
(Gp:) Pagos de J2 a J1
A
B
A
B
A
B
C
B
A
Formas de representación de un juego
Forma matricial
matriz de balances finales o matriz del juego: proporciona la utilidad de cada estrategia de cada jugador para cada acción del resto de jugadores.
Forma de árbol
Juegos bipersonales, I
Los juegos bipersonales en la IA
Son problemas con contingencias
En ocasiones pueden tener una ramificación alta
por ejemplo en ajedrez, b ? 35
Puede haber limitaciones de tiempo
Entorno semidinámico
En la resolución se utilizan:
Funciones de evaluación
Evalúan los operadores utilizados por cada jugador.
Ayudan a decidir el resultado del juego y las mejores estrategias para cada jugador.
Métodos de poda
Simplificación de la búsqueda.
Juegos bipersonales, II
Planteamiento general:
2 jugadores: MAX y MIN (MAX mueve primero):
Estado inicial
Posición del tablero e identificación del primer jugador a mover
Función sucesora:
Lista de pares (movimiento, estado) indica cada movimiento legal y su estado resultante
Función objetivo:
Determina cuándo se acaba el juego (en nodos objetivo o terminales)
Función de utilidad (función u):
Definida en nodos terminales (valores numéricos)
Resultado del juego. Por ejemplo:
+1 si gana MAX
-1 si gana MIN
0 si empate (tablas)
Juegos bipersonales, III
Juegos que incorporan AZAR
En ocasiones el azar interviene en los juegos
Lanzamientos de monedas, dados, generación de números aleatorios, cartas, etc.
El árbol del juego tiene que reflejar dicha contingencia, introduciendo al azar como si de un jugador más se tratase
La toma de decisiones se puede ver influenciada por la distribución de probabilidad existente sobre las acciones del jugador azar
Ejemplo: lanzamiento de un dado
Equilibrado ?
No equilibrado ? distintas probabilidades para cada valor del dado
Juegos bipersonales, IV
Ejemplo: tres en raya
El estado inicial y los movimiento legales de cada jugador definen el árbol del juego.
(Gp:) Inicialmente MAX puede realizar uno de entre nuevo movimientos posibles
Jugadas alternas entre MAX (x) y MIN (o), hasta llegar a un estado terminal
(Gp:) El valor de cada nodo hoja indica el valor de la función utilidad desde el punto de vista de MAX (valores altos son buenos para MAX y bajos buenos para MIN)
Decisiones óptimas en juegos de dos adversarios, I
Algoritmo minimax
Tiene por objetivo decidir un movimiento para MAX.
HIPÓTESIS
Jugador MAX trata de maximizar su beneficio (función de utilidad).
Jugador MIN trata de minimizar su pérdida.
Aplicación algoritmo:
1) Generar árbol entero hasta nodos terminales
2) Aplicar función u a nodos terminales
3) Propagar hacia arriba para generar nuevos valores de u para todos los nodos
minimizando para MIN
maximizando para MAX
4) Elección jugada con máximo valor de u
MINIMAX-VALUE(n) =
UTILITY(n) Si n es un nodo terminal
maxs ? Sucesor(n) MINIMAX-VALUE(s) Si n es un nodo MAX
mins ? Sucesor(n) MINIMAX-VALUE(s) Si n es un nodo MIN
Decisiones óptimas en juegos de dos adversarios, II
Ejemplo: tres en raya
(Gp:) Nodos MAX, le toca mover a MAX
(Gp:) Nodos MIN
(Gp:) Valores de la función de utilidad para MAX
La mejor jugada de MAX es A1 porque genera el mayor valor minimax entre sus nodos sucesores: ÓPTIMA
La mejor jugada entonces de MIN es A11 porque genera el menor valor minimax entre sus nodos sucesores.
(Gp:) Valores minimax (cada nodo tiene asociado valor minimax o MINIMAX-VALUE(n))
Decisiones óptimas en juegos de dos adversarios, III
Algoritmo:
function MINIMAX-DECISION(state) return una acción
inputs: state, estado actual en el juego
v ? MAX-VALUE(state)
return una acción de SUCCESSORS(state) con valor v
function MAX-VALUE(state) returns valor utilidad
if TERMINAL-TEST(state) then return UTILITY(n)
v ? – ?
for s en SUCCESSORS(state) do
v ? MAX(v, MIN-VALUE(s))
return v
function MIN-VALUE(state) returns valor utilidad
if TERMINAL-TEST(state) then return UTILITY(n)
v ? ?
for s en SUCCESSORS(state) do
v ? MIN(v, MAX-VALUE(s))
return v
La complejidad (m = máxima profundidad), como es una búsqueda en profundidad, es:
Temporal:
Espacial:
Para juegos reales la complejidad temporal hace que sea impracticable. Es válido para casos de libro.
Ejemplo de juego con azar, I
Sean dos jugadores, MAX y MIN. Para poder jugar han de depositar una fianza de 1€ en el pot (bote en el centro de la mesa). Se reparte una carta a cada jugador de un mazo que contiene, a partes iguales, Ases (A) y Reyes (K). Una vez repartidas las cartas el jugador MAX escoge su jugada (según muestra la figura adjunta).
MAX siempre está obligado a apostar 2, 4 ó 6 €.
Después de anunciar su jugada, efectúa lo propio el jugador MIN. En su caso tiene dos opciones:
ver la apuesta (en cuyo caso iguala la cantidad apostada por MAX) o
no ver la apuesta (pasar).
PAGOS:
1) Si MIN no ve la apuesta pierde el dinero que puso en el bote.
2) Si MIN ve la apuesta se vuelven las cartas:
i) Si las cartas son diferentes gana la mejor, con el criterio: A es preferida a K
ii) Si ambas cartas son iguales se reparte el bote equitativamente.
Ejemplo de juego con azar, II
(Gp:) 1
(Gp:) 1
(Gp:) 1
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 1
(Gp:) 1
(Gp:) 1
(Gp:) 3
(Gp:) 5
(Gp:) 7
(Gp:) 1
(Gp:) 1
(Gp:) 1
(Gp:) -3
(Gp:) -5
(Gp:) -7
(Gp:) 1
(Gp:) 1
(Gp:) 1
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) (A, A)
(Gp:) (K, K)
(Gp:) (A, K)
(Gp:) (K, A)
(Gp:) -3
(Gp:) -5
(Gp:) -7
(Gp:) -3
(Gp:) Solución MINIMAX: “apostar 2”
Representar el árbol del juego indicando en los nodos hoja los pagos según la función de utilidad de MAX "incremento de capital obtenido en la jugada".
Indicar cuál sería la estrategia preferida para el jugador MAX en la jugada (K, A) según el criterio MINIMAX
3 posibles acciones: +2, +4, +6
2 posibles acciones: ver, no-ver
Ej. de pago si secuencia de jugada es [(A,K), +4, ver]
Ver ? comparar(A,K) ? gana(MAX)
Pago-a-MAX = 4 + 1 = 5 (4 de ver la apuesta, 1 del bote)
(¡ojo!, el pago representa incremento de capital)
Página siguiente  |