PDF de programación - Árboles de juegos - Análisis y Diseño de Algoritmos

Árboles de juegos
Árboles de juegos
Análisis y Diseño de Algoritmos
Análisis y Diseño de Algoritmos

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

Árboles de juegos
Árboles de 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…

Árboles de juegos
Árboles de 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

Árboles de juegos
Árboles de juegos

Complejidad de algunos juegos
Complejidad de algunos juegos

Juego

Estados

3 en raya

9! = 362280

Conecta-4

Damas

Ajedrez

Go

1013

1018

1050

10170

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

44

55

Minimax
Minimax

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

Minimax
Minimax

66

77

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.

88

99

Poda
Poda αα--ββ

Poda
Poda αα--ββ

1010

1111

Poda
Poda αα--ββ

Poda
Poda αα--ββ

1212

1313

Poda
Poda αα--ββ

Poda
Poda αα--ββ

1414

1515

Poda
Poda αα--ββ

1616

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

1717

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

1818

Poda
Poda αα--ββ

 La poda

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

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

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

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

1919

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> ββ))

2020

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:
Solución habitual:

 Cota de profundidad
Cota de profundidad

 Función de evaluación (heurística): Solución aproximada
Función de evaluación (heurística): Solución aproximada

p.ej.
p.ej.
EvalEval(s)

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

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

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

2121

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 αα--ββ..

2222

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

Aplicación: Ajedrez
Aplicación: Ajedrez

2323

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

 Damas

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

perfecto parapara todas
piezas (443748

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

base de datos
los finales de partida
todas los finales de
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
a Gary Kasparov en 1997
venció 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 se niegan
son demasiado

jugar contra
contra
demasiado malosmalos (b>300).
(b>300).

niegan a a jugar

2424

Juegos de azar
Juegos de azar

Hay juegos, como el
Hay juegos, como el Backgammon
interviene el azar (en forma de dados):
interviene el azar (en forma de dados):

Backgammon, en los que
, en los que

2525

Juegos de azar
Juegos de azar

Juegos de azar
Juegos de azar

A1 como mejor

movimiento

A2 como mejor

movimiento

2 resultados con
probabilidades

(0.9, 0.1)

2626

2727

Bibliografía
Bibliografía

Stuart Russell & Peter Norvig
 Stuart Russell & Peter
Norvig: : Artificial Intelligence:
Artificial Intelligence:
[second edition]. Chapter 6:
A Modern Approach [second edition]. Chapter 6:
A Modern Approach
Search. . Prentice Hall, 2002. ISBN
Prentice Hall, 2002. ISBN
Adversarial
Adversarial Search
0137903952.
0137903952. http://aima.cs.berkeley.edu/
http://aima.cs.berkeley.edu/

2828