PDF de programación - Juegos

Juegos
Juegos
© Fernando Berzal, [email protected]
© Fernando Berzal,
[email protected]

Tipos de juegos
Tipos de juegos

Juegos

deterministas

Juegos
de azar

Ajedrez, damas,
Ajedrez, damas,

Go, Othello

Backgammon,
Backgammon,

Monopoly

barquitos

Bridge, poker,

scrabble

Con
Con

información

perfecta

Con

información
imperfecta

11

Juegos
Juegos

Juego perfecto
Juego perfecto

 Dos jugadores
Dos jugadores
Movimientos intercalados
 Movimientos intercalados
 Suma cero (la ganancia de uno es la pérdida del otro).
 Suma cero (la ganancia de uno es la pérdida del otro).
Suma cero (la ganancia de uno es la pérdida del otro).
Suma cero (la ganancia de uno es la pérdida del otro).
 Información perfecta (ambos jugadores tienen acceso
Información perfecta (ambos jugadores tienen acceso
a toda la información sobre el estado del juego: no se
a toda la información sobre el estado del juego: no se
ocultan información el uno al otro).
ocultan información el uno al otro).
 No interviene el azar (p.ej. dados).
No interviene el azar (p.ej. dados).

Ejemplos:
Ejemplos:
NimNim, , Grundy

Grundy, 3 en raya, conecta

, 3 en raya, conecta--4, damas, ajedrez…
4, damas, ajedrez…

Juegos
Juegos

Función de evaluación:
Función de evaluación:
+1+1 si gana X
si gana X
--11 si gana O
si gana O
00 si hay tablas
si hay tablas

22

33

Juegos
Juegos

Complejidad de algunos juegos con adversario
Complejidad de algunos juegos con adversario

Juego

Estados

3 en raya

9! = 362280

Conecta-4

Damas

Ajedrez

Go

1013

1018

1047

10170

Minimax
Minimax

Considerando sólo nuestros posibles movimientos…
Considerando sólo nuestros posibles movimientos…
… elegiríamos el movimiento más prometedor (MAX):
… elegiríamos el movimiento más prometedor (MAX):

1

3

-1

0

Nuestro turno

Turno de nuestro oponente

44

55

Minimax
Minimax

Nuestro oponente, a continuación…
Nuestro oponente, a continuación…
… elegiría lo que más le conviene a él (MIN):
… elegiría lo que más le conviene a él (MIN):

-1

8

Nuestro turno

Turno de nuestro oponente

Minimax
Minimax

Si antes de realizar el movimiento,
Si antes de realizar el movimiento,
hubiésemos explorado un nivel más de profundidad, nos
hubiésemos explorado un nivel más de profundidad, nos
habría dado cuenta de que el movimiento no era bueno:
habría dado cuenta de que el movimiento no era bueno:

5

1 -1

8

6

2

0

Nuestro turno

Turno de nuestro oponente

66

77

Minimax
Minimax

Si suponemos que nuestro oponente es racional,
Si suponemos que nuestro oponente es racional,
deberíamos elegir otro movimiento inicial:
deberíamos elegir otro movimiento inicial:

1

-1

2

0

5

1 -1

8

6

2

0

Nuestro turno

Turno de nuestro oponente

Minimax
Minimax

Estrategia perfecta para juegos deterministas.
Estrategia perfecta para juegos deterministas.

IIDEADEA:: Elegir el movimiento que nos lleva a la posición
Elegir el movimiento que nos lleva a la posición
que nos asegura una recompensa máxima en el peor
que nos asegura una recompensa máxima en el peor
caso (valor
caso (valor minimax
caso (valor
caso (valor minimax

minimax).).
minimax).).

 MAX: Cuando movemos nosotros,
MAX: Cuando movemos nosotros,
elegimos el nodo de máximo valor.
elegimos el nodo de máximo valor.

MIN: Cuando mueve nuestro oponente,
 MIN: Cuando mueve nuestro oponente,
elige el nodo de menor valor (para nosotros).
elige el nodo de menor valor (para nosotros).

88

99

Minimax
Minimax

Árbol con 2 niveles (2--ply):
Árbol con 2 niveles (2
ply):

Minimax
Minimax

1010

1111

Minimax
Minimax

Búsqueda
Búsqueda minimax

minimax (primero en profundidad):
(primero en profundidad):

2

2

1

2

1

2

7 1

8

2

7 1

8

2

7 1

8

MAX
MIN

Minimax
Minimax

Complejidad
Complejidad

b b = Factor de ramificación del árbol
= Factor de ramificación del árbol
dd = Profundidad del árbol de juego
= Profundidad del árbol de juego

 Tiempo:

Tiempo: O(O(bbdd))..

 Espacio:

Espacio: O(O(bdbd))..

Ejemplo
Ejemplo

En el ajedrez, b≈35 y d≈100, por lo que
En el ajedrez, b≈35 y d≈100, por lo que nono
podemos explorar el árbol completo del juego.
podemos explorar el árbol completo del juego.

1212

1313

Poda
Poda αα--ββ

Poda
Poda αα--ββ

1414

1515

Poda
Poda αα--ββ

Poda
Poda αα--ββ

1616

1717

Poda
Poda αα--ββ

Poda
Poda αα--ββ

1818

1919

Poda
Poda αα--ββ

2020

Poda
Poda αα--ββ

0
−∞=
∞=

αααα
ββββ

αααα
ββββ

0=ββββ
−∞=
∞=
0

0
0
−∞=
0=

αααα
ββββ

0
−∞=
∞=

αααα
ββββ

0=α

0=β

0=β

αααα
ββββ

−∞=
∞=
0

0

-3

0=α

αααα 0
=
ββββ
∞=
-3

0=ββββ

αααα
ββββ

−∞=
0=

3

max

min

max

min

max

0

5

-3 3

3

-3 0

2

-2 3

2121

Poda
Poda αα--ββ

max

min

max

αααα 0
=
ββββ
∞=

αααα
ββββ

−∞=
0=

αααα 0
=
ββββ
∞=

αααα
ββββ

=
=

0
0

min

αααα
ββββ

−∞=
0=

αααα
ββββ

=
0
−=

3

αααα
ββββ

−∞=
0=

max

0

5

-3 3

3

-3 0

2

-2 3

2222

Poda
Poda αα--ββ

 La poda

La poda αα--ββ no afecta al resultado del juego.
no afecta al resultado del juego.

Cuanto mejor ordenemos los movimientos,
 Cuanto mejor ordenemos los movimientos,
más efectiva será la poda.
más efectiva será la poda.
más efectiva será la poda.
más efectiva será la poda.

 Con una ordenación “perfecta”,
Con una ordenación “perfecta”,
la complejidad del algoritmo es
la complejidad del algoritmo es O(O(bbdd/2/2))..

En otras palabras, con el mismo esfuerzo
En otras palabras, con el mismo esfuerzo
podremos explorar un árbol del doble de profundidad.
podremos explorar un árbol del doble de profundidad.

2323

Poda
Poda αα--ββ

¿Por qué se llama poda
¿Por qué se llama poda αα--ββ??

 αα es el valor de la mejor opción encontrada para el
es el valor de la mejor opción encontrada para el

jugador MAX:
jugador MAX:

MAX evitará cualquier movimiento
MAX evitará cualquier movimiento
MAX evitará cualquier movimiento
MAX evitará cualquier movimiento
que tenga un valor v peor que
que tenga un valor v peor que αα
(poda si v<
(poda si v<αα).).

 β β es el valor de la mejor opción encontrada para MIN
es el valor de la mejor opción encontrada para MIN

(mínimo encontrado hasta ahora):
(mínimo encontrado hasta ahora):

MIN evitará cualquier movimiento
MIN evitará cualquier movimiento
que tenga, para él, un valor v peor
que tenga, para él, un valor v peor
que que ββ (poda si v>

(poda si v> ββ))

2424

En la práctica…
En la práctica…

Si disponemos de 100 segundos por movimiento y
Si disponemos de 100 segundos por movimiento y
podemos explorar 10
podemos explorar 1044 nodos por segundo,
nodos por segundo,
sólo podremos analizar 1066 nodos por movimiento:
nodos por movimiento:
sólo podremos analizar 10

Solución habitual: Exploración del árbol
Solución habitual: Exploración del árbol

 Cota de profundidad
Cota de profundidad

 IDS [

Iterative Deepening

IDS [Iterative
Se realiza una búsqueda en profundidad con una cota de
Se realiza una búsqueda en profundidad con una cota de
profundidad creciente, hasta que se agota el tiempo.
profundidad creciente, hasta que se agota el tiempo.

Deepening Search

Search]: ]:

2525

En la práctica…
En la práctica…

Si disponemos de 100 segundos por movimiento y
Si disponemos de 100 segundos por movimiento y
podemos explorar 1044 nodos por segundo,
nodos por segundo,
podemos explorar 10
sólo podremos analizar 1066 nodos por movimiento:
nodos por movimiento:
sólo podremos analizar 10

Solución habitual: Evaluación de los nodos
Solución habitual: Evaluación de los nodos

Se utiliza una función de evaluación heurística que
 Se utiliza una función de evaluación heurística que
evalúa la bondad de un nodo dependiendo de ciertos
evalúa la bondad de un nodo dependiendo de ciertos
criterios (en el ajedrez: número de piezas amenazadas,
criterios (en el ajedrez: número de piezas amenazadas,
control del centro del tablero…)
control del centro del tablero…)

p.ej.
p.ej.
evaleval(s)

(s) = w= w11 ff11(s) + w

(s) + w22 ff22(s) + … +

(s) + … + wwnn ffnn(s)(s)

2626

En la práctica…
En la práctica…

Aplicación: Ajedrez
Aplicación: Ajedrez
b=35
b=35

 44--ply (novato)
ply (novato)

d = 4 → → bbdd = 1.5 x 10
d = 4
d = 4
d = 4 → → bb = 1.5 x 10
= 1.5 x 1066
= 1.5 x 10

 88--ply (maestro): Programa típico para PC
ply (maestro): Programa típico para PC

d = 8
d = 8 → → bbdd = 2.25 x 10

= 2.25 x 101212

ply (¿Kasparov

 1212--ply (¿
d = 12 → → bbdd = 3.4 x 10
d = 12

Kasparov?):?):

= 3.4 x 101818

En En DeepDeep Blue, el valor medio de b
Blue, el valor medio de b
se reducía de 35 a 6 utilizando la poda
se reducía de 35 a 6 utilizando la poda αα--ββ..

2727

En la práctica…
En la práctica…

Aplicación: Ajedrez
Aplicación: Ajedrez

2828

En la práctica…
En la práctica…

 Damas

Damas: Chinook
: Chinook venció
Tinsley, en 1994
Tinsley, en 1994 usando
el el juego
juego perfecto
o o menosmenos piezas

perfecto parapara todas
piezas (443748

, Marion
campeón del del mundomundo, Marion
datos queque definía
definía
partida con 8
con 8

base de datos
todas los finales de
los finales de partida
posiciones).).

millones de de posiciones

venció al al campeón
usando unauna base de

(443748 millones

 Ajedrez
 Ajedrez

: Deep Blue venció
: Deep Blue venció

Ajedrez: Deep Blue
Ajedrez: Deep Blue
analizando
analizando 200 200 millones
usando
usando 8000
permitían
permitían analizar

venció a Gary Kasparov en 1997
venció a Gary Kasparov en 1997
a Gary Kasparov en 1997
a Gary Kasparov en 1997
segundo y y
posiciones porpor segundo

millones de de posiciones

8000 características

características y y heurísticas

heurísticas queque le le

analizar algunas

algunas secuencias

secuencias de de hasta

hasta 40 ply.
40 ply.

Othello: Los
 Othello
contra
contra ordenadores

: Los campeones
ordenadores porque

campeones humanos

humanos se se niegan

niegan a a jugar
jugar

porque son

son demasiado

demasiado buenos
buenos..

 GoGo: Los

: Los campeones
ordenadores
ordenadores porque

porque son

campeones humanos

humanos se