PDF de programación - Problemas de búsqueda entre búsqueda entre adversarios - Juegos

Problemas de
búsqueda entre
búsqueda entre

adversarios

Juegos

1

1

Introducción, I

(cid:122) Juegos

» Origen, 1928: John Von Newmann
Teorema fundamental de los juegos
– Teorema fundamental de los juegos
bipersonales de suma nula.

» Desarrollo, 1944:

– Von Newmann, J. Morgernsten, O. “Theory of

Games and Economic Behaviour”.
Ga es a d co o c e a ou

(cid:122) Aplicaciones

(cid:122) Elementos:

» Antropología, psicología, economía,

política, negocios, biología, IA, etc.

» Jugadores: personas, empresas, naciones,

» Conjunto de estrategias: operadores o

t d

d

t

entes biológicos, etc.
C j
i
acciones

t

» Resultado o Valor del juego: estado/s

objetivos/s

» Conjuntos de Pagos para cada jugador:
función de utilidad sobre las estrategias

2

2

Introducción, II
(cid:122) Clasificación desde diferentes

perspectivas:
» Cooperación
ió

C
– Cooperativos/no cooperativos

» Número de jugadores

– n=2 bipersonales:
n=2, bipersonales:

(cid:122) por naturaleza no cooperativos

– n>2, n-personales:

(cid:122) Pueden ser cooperativos. Dan lugar a

coaliciones

i

li
» Beneficios

– Suma nula (habituales en IA): la suma de

beneficios y pérdidas de los jugadores debe ser
0 (puede ser constante (cid:198) reescalado).

y p

j g

– Suma no nula.

» Duración
– Finitos:
Finitos:

(cid:122) tienen final programado (nº jugadas, ruinas,

etc.)

– Infinitos: sin final programado

3

3

Introducción, III

(cid:122) Formas de representación de un juego

» Forma matricial

– matriz de balances finales o matriz del juego:

j g

proporciona la utilidad de cada estrategia de cada
jugador para cada acción del resto de jugadores.

J2
A B
A 2 -3
B 0
2
C -5 10
Pagos de J2 a J1

J1

»Forma de árbol

A

B

C

A

B A

B

A

B

4

4

Juegos bipersonales, I
(cid:122) Los juegos bipersonales en la IA
» Son problemas con contingencias
» En ocasiones pueden tener una

E
ramificación alta
– por ejemplo en ajedrez, b ≈ 35

i

d

t

» Puede haber limitaciones de tiempo
» Puede haber limitaciones de tiempo

– Entorno semidinámico

(cid:122) En la resolución se utilizan:

» Funciones de evaluación
» 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
mejores estrategias para cada jugador.

» Métodos de poda

– Simplificación de la búsqueda.

5

5

Juegos bipersonales, II

(cid:122) Planteamiento general:

» 2 jugadores: MAX y MIN (MAX mueve

primero):
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

ió

» Función objetivo:

F
– Determina cuándo se acaba el juego (en nodos

bj

ti

objetivo o terminales)
(

» Función de utilidad (función u):
)

– Definida en nodos terminales (valores

numéricos)

– Resultado del juego. Por ejemplo:

(cid:122) +1 si gana MAX
(cid:122) +1 si gana MAX
(cid:122) -1 si gana MIN
(cid:122) 0 si empate (tablas)

6

6

Juegos bipersonales, III

(cid:122) Juegos que incorporan AZAR

» En ocasiones el azar interviene en los

juegos
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
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
probabilidad existente sobre las acciones
del jugador azar.

7

7

Juegos bipersonales, IV

» En aquellos juegos en que existe azar, es
posible recoger la información procedente
de nodos en los que interviene una
di t ib ió d
distribución de probabilidad para
determinar los nodos generados a partir del
nodo actual.

b bilid d

» Para determinar el valor esperado de la

p

utilidad se procede según la siguiente
definición:
EXPECTMINIMAX n
( )
=
UTILITY
UTILITY n
( )
( )



EXPECTMINIMAX s
( )


EXPECTMINIMAX s
( )

s successors n
( )
∈


P(s) EXPECTMINIMAX s
P(s)·EXPECTMINIMAX s
( )
( )


s successors n
( )
∈
– Ejemplo: un nodo con lanzamiento de un dado

max
min
∑
∑

si n es un nodo MAX
si n es un nodo MIN

si n es un nod
si n es un nod

i
l
si n es terminal

i

s successors n
( )
∈

o ALEATORIO
o ALEATORIO

(cid:122) Si Equilibrado (cid:198)
(cid:122) Si Equilibrado (cid:198)

iP
iP

=

1
6

i
i∀ K
∀ = K

1,
1,

,6
,6

(cid:122) Si No equilibrado (cid:198) distintas probabilidades para
8

cada valor del dado

8

Juegos bipersonales, IV

(cid:122) Ejemplo: tres en raya

Inicialmente MAX puede realizar uno de entre nueve

movimientos posibles
movimientos posibles

Jugadas alternas entre

MAX (x) y MIN (o),
hasta llegar a un
hasta llegar a un
estado terminal

El valor de cada nodo hoja
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)
buenos para MIN)

El estado inicial y los movimiento legales de

cada jugador definen el árbol del juego.

9

9

Decisiones óptimas en juegos

de dos adversarios, I

(cid:122) Algoritmo minimax

» Tiene por objetivo decidir un movimiento

para MAX.
para MAX.
» HIPÓTESIS

10

10

(cid:122) Jugador MAX trata de maximizar su

beneficio (función de utilidad).

(cid:122) Jugador MIN trata de minimizar su pérdida
(cid:122) 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

3) P
valores de u para todos los nodos

h i

ib

(cid:122) minimizando para MIN
(cid:122) maximizando para MAX

– 4) Elección jugada con máximo valor de u
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
d MAX
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

(cid:122) Algoritmo:

function MINIMAX-DECISION(state) return una acción

inputs: state, estado actual en el juego
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)
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

(cid:122) La complejidad (m = máxima profundidad), como es una

búsqueda en profundidad, es:

– Temporal:
– Espacial:

( mbO
)
(bmO
)

(cid:122) Para juegos reales la complejidad temporal hace que sea

impracticable. Es válido para casos de libro.

11

11

Decisiones óptimas en juegos

de dos adversarios, III

(cid:122) Ejemplo

Nodos MAX, le toca mover a MAX

Nodos MIN

Valores de la función de utilidad para MAX

Valores minimax (cada nodo
ti
tiene asociado valor minimax

i
o MINIMAX-VALUE(n))

i d

l

i

• La mejor jugada de MAX es A1 porque genera el mayor
valor minimax entre sus nodos sucesores: ÓPTIMA
L
• La mejor jugada entonces de MIN es A11 porque genera
el menor valor minimax entre sus nodos sucesores.

d MIN

A

d

t

j

j

12

12

Ejemplo de juego con azar, I

(cid:122) 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)
partes iguales, Ases (A)
y Reyes (K). Una vez
repartidas las cartas el
jugador MAX escoge su
jugada (según muestra
la figura adjunta)
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
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
dinero que puso en el
bote.

2) Si MIN ve la apuesta
se vuelven las cartas:

i) Si 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.

13

13

Ejemplo de juego con azar, II

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

(A, A)

(K, K)

(A, K)

(K, A)

-3

-3

-5

-7

0

1

0

1

0

1

3

1

5

1

7

1

-3

1

-5

1

-7

1

0

1

0

1

0

1

Solución MINIMAX: “apostar 2”

Ej. de pago si secuencia de jugada es [(K,A), +4, ver]
Ver (cid:198) comparar(K,A) (cid:198) gana(MAX)
Pago-a-MAX = 4 + 1 = 5 (4 de ver la apuesta, 1 del bote)
(¡ojo!, el pago representa incremento de capital)

14

14

Decisiones imperfectas en
juegos de dos adversarios
(cid:122) Decisión imperfecta (cid:197)(cid:198) Estrategia Mixta
(cid:122) El algoritmo minimax asume una expansión

hasta el final (en realidad es imposible)
hasta el final (en realidad es imposible).
» Se usa una función de evaluación (f), que sea una

estimación de u.

(cid:122) Función de evaluación:

» El papel que hace f es el de u en nodos

terminales, ordenando de manera correcta los
nodos en los que se calcula

» Ejemplos:

1. Estrategia con:

(cid:122)

(cid:122)

50% posibilidades de ganar,
25% de perder,
25% de empate.

(cid:122)
F = 1*0.50+(-1)*0.25+0*0.25=0.25

2. En ajedrez, valorando piezas: peón =