Juegos

El Juego como Problema de Búsqueda En este algoritmo identificamos dos jugadores: max y min. El objetivo es encontrar la mejor movida para max. Supondremos que max mueve inicialmente y que luego se turnan para jugar. El espacio de b´ usqueda queda definido por: Estado inicial: Es una configuraci´ on inicial del juego m´as una indicaci´ on de qui´en tiene la pr´ oxima movida. Operadores: Corresponden a las jugadas legales se pueden hacer en el juego. Condici´ on Terminal: Determina cu´ando el juego se acab´ o. Funci´ on de Utilidad: Da un valor num´erico a una configuraci´ on final de un juego. En un juego en donde se puede ganar, perder o empatar, los valores pueden ser 1, 0, o -1. Generalmente no es posible buscar a una profundidad tal que permita llegar a las hojas del ´arbol. Jorge Baier Aranda, PUC

1

Por esa raz´ on, se considera generalmente una funci´ on de evaluaci´ on de estados que califica a los estados seg´ un qu´e tan buenos son para max.

Jorge Baier Aranda, PUC

2

El espacio de búsqueda Suponiendo que max es el que comienza el juego el espacio de b´ usqueda se ve como un ´arbol en el cual: • Los nodos que est´an a profundidad par (suponiendo la ra´ız est´a a profundidad 0) corresponden a turnos del jugador max. • Los nodos que est´an a profundidad impar corresponden a turnos del jugador min.

Jorge Baier Aranda, PUC

3

El algoritmo Minimax El algoritmo Minimax con profundidad limitada es el siguiente: Generar el ´arbol de b´ usqueda hasta un nivel de profundidad 2k. En este ´arbol, la primera movida corresponde a una jugada para max, por lo que las hojas del ´arbol generado corresponden a configuraciones en donde min ha jugado por u ´ltima vez. Aplicar la funci´ on de evaluaci´ on a cada hoja del ´arbol. Repetir mientras k ≥ 1 • Calcular la utilidad de los nodos de nivel 2k − 1 como la m´ınima utilidad entre la de sus hijos. • Calcular la utilidad de los nodos de nivel 2k − 2 como la m´ axima utilidad entre la de sus hijos. • k =k−1 La mejor jugada corresponde al hijo de mayor utilidad en del nodo inicial.

Jorge Baier Aranda, PUC

4

El Gato: un ejemplo sencillo Para ejemplificar el algoritmo, consideremos el juego del gato. En este juego podemos usar la siguiente funci´ on de evaluaci´ on para un tablero t: E(t) = NA(t) − NC (t) donde NA(t) es el n´ umero de filas, columnas o diagonales abiertas para max (donde a´ un puede ganar) y NC (t) es el n´ umero de filas, columnas o diagonales abiertas para min. Si t es un tablero ganado por max, E(t) = ∞ y si es un tablero perdido, E(t) = −∞ (aqu´ı en vez de ∞ podr´ıamos haber ocupado otro valor). La figura 1 muestra el algoritmo Minimax con un ´arbol de profundidad 2. La figura 2 muestra otro ´arbol con profundidad 2, pero luego que min ya ha jugado en una de las posiciones del tablero. Finalmente, la figura 3 muestra la u ´ltima etapa de la b´ usqueda. Jorge Baier Aranda, PUC

5

Figura 1: Primera etapa en la b´ usqueda del gato

Jorge Baier Aranda, PUC

6

Figura 2: Segunda etapa en la b´ usqueda del gato

Jorge Baier Aranda, PUC

7

´ Figura 3: Ultima etapa en la b´ usqueda del gato Jorge Baier Aranda, PUC

8

La poda Alfa-Beta En muchos juegos minimax es ineficiente. Para ello, es posible usar la poda alfa-beta. Consideremos el ´arbol de juego de la u ´ltima etapa del gato (figura 3). Supongamos que un nodo hoja es evaluado en cuanto es generado. Despu´es de evaluar el nodo A no tiene sentido seguir generando ni evaluando los nodos B, C o D. El mismo tipo de poda se puede aplicar cuando las posiciones en la b´ usqueda no representan juegos ganados para min o max. Consideremos ahora la primera etapa del gato (figura 4). Supongamos que la b´ usqueda se realiza usando una estrategia dfs y que cada vez que una hoja es generada su se computa su evaluaci´ on. Supongamos, adem´as, que tambi´en se calculan las evaluaciones para los nodos no-hoja, en cuanto es posible. Al calcular el valor para el nodo A, sabemos que el valor del nodo inicial (Start Jorge Baier Aranda, PUC

9

Node, en la figura) est´a acotado inferiormente por −1. A este valor se le conoce como valor alfa. El valor alfa de un nodo MAX es la cota inferior del valor de utilidad que se conoce hasta el momento. Si durante el c´alculo del valor MAX de un nodo s´ olo se conoce el valor de la utilidad de un subconjunto h de sus hijos, entonces el valor alfa corresponde a la m´axima utilidad que estos poseen. Volviendo al ejemplo ¿Qu´e pasa si estamos explorando el nodo C y ya sabemos que el valor para A es −1? La respuesta es que no necesitamos seguir evaluando ning´ un sucesor de B pues, a lo m´as, B tendr´a utilidad −1. Al calcular el valor de C sabemos que B tiene un l´ımite superior de −1. A este valor se le conoce por valor beta. El valor beta de un nodo MIN es la cota inferior de la utilidad que se conoce hasta el momento. Notemos que: Jorge Baier Aranda, PUC

10

• Los valores alfa de los nodos max nunca pueden decrecer. • Los valores beta de los nodos min nunca pueden crecer. Dada estas restricciones podemos establecer las siguientes reglas para el podado del ´arbol de b´ usqueda: • La b´ usqueda es abandonada bajo todo nodo min que tiene un valor beta menor o igual al valor alfa de alguno de sus antecesores max. • La b´ usqueda es abandonada bajo todo nodo max que tiene un valor alfa mayor o igual al valor beta de alguno de sus antecesores min. Durante la b´ usqueda, los valores alfa y beta se computan de la siguiente manera: • El valor alfa de un nodo max es igual al mayor valor calculado en sus sucesores. • El valor beta de un nodo min es el menor valor calculado en sus sucesores. La figura 5 muestra los valores alfa-beta de los nodos justo despu´es de producir el corte en el arco que une al nodo C con el nodo I. En la misma figura, el algoritmo efect´ ua un corte en el arco que une a K con Y . Jorge Baier Aranda, PUC

11

Figura 4: Primera etapa de la b´ usqueda del gato

Jorge Baier Aranda, PUC

12

A

B

E

L (2)

C

beta=3

F

M (3)

N (8)

G

O (5)

P (7)

alfa=3

H

Q (6)

R (0)

D

beta=1

I

S (1)

T (5)

J

U (2)

V (8)

K

W (4)

X Y (10) (2)

Figura 5: Poda alfa-beta antes de revisar el nodo D.

Jorge Baier Aranda, PUC

13

Alfa-Beta en pseudo código Si P es la profundidad m´axima a la que se quiere llegar, entonces llamando a AB(s, −∞, +∞, 0, P ) se obtiene el recorrido del ´arbol con poda alfa-beta. AB(nodo, α, β, prof, limite) 1 if prof = limite 2 then return Ut(nodo) 3 for each ni ∈ {n1, n2, . . . , nk } = Sucesores(nodo) 4 do if prof m´ od 2 = 0 5 then α ← m´ ax{α; AB(ni, α, β, prof + 1, P )} 6 if α ≥ β 7 then return β 8 if i = k 9 then return α 10 else β ← m´ın{β; AB(ni, α, β, prof + 1, P )} 11 if β ≤ α 12 then return α 13 if i = k 14 then return β

Jorge Baier Aranda, PUC

14

Eficiencia de Alfa-Beta Supongamos que el ´arbol tiene profundidad d y cada nodo (excepto los nodos hoja) tienen exactamente b sucesores. Si no realizamos poda alfa-beta, deberemos revisar bd nodos hoja. La eficiencia de la poda depender´a obviamente del orden en que se generan los nodos. ¿Cu´al es el mejor caso? ¿Y el peor? Es posible demostrar que en el caso promedio, alfa-beta permite aumentar aproximadamente a 43 d la profundidad de la b´ usqueda revisando la misma cantidad de nodos que sin poda.

Jorge Baier Aranda, PUC

15

Predicción en Múltiples Etapas Supongamos que queremos construir un algoritmo que prediga la temperatura del d´ıa domingo. Este algoritmo recibir´a el d´ıa de la semana y las observaciones meteor´ ologicas de ´este. Supongamos que x1, x2, . . ., x5, x6 son vectores que codifican el d´ıa y las observaciones meteorol´ ogicas hechas el lunes, martes, . . ., s´abado. Lo que queremos es encontrar una funci´ on F que dado un vector de “descripci´ on diaria” entregue una temperatura. Para dise˜ nar la estrategia de aprendizaje es conveniente notar que: • Los datos de la serie se conocen siempre en el mismo orden. • La temperatura del domingo se conoce al final de la serie. Generalicemos el problema para una serie de n datos (x1, . . . , xn) donde se produce un resultado esperado z. Jorge Baier Aranda, PUC

16

Si enfrentamos el problema usando aprendizaje supervisado, deberemos alimentar al algoritmo de aprendizaje con los datos (x1, z), (x2, x), . . . , (xn, z). Supongamos que F es una funci´ on que calcula la salida de una red neuronal. En ese caso, el problema se reduce a actualizar los pesos de ´esta, para cada ejemplo, usando la siguiente f´ ormula:

w←w+

m X

∆wt

(1)

t=1

donde ∆wt est´a dado por: ∆wt = α(z − F (xt, w))∇w F (xt, w)

Jorge Baier Aranda, PUC

17

Usando diferencias temporales El m´etodo de diferencias temporales es una variaci´ on del enfoque de aprendizaje supervisado.

La idea considera que la diferencia entre las distintas predicciones debe ayudar a tener un mejor aprendizaje.

Esto se puede lograr definiendo dt = F (xt+1, w) − F (xt, w) y notando que

z − F (xt, w)) =

m X

(F (xk+1, w) − F (xk , w)),

con z = F (xm+1, w)

k=t Jorge Baier Aranda, PUC

18

As´ı, es posible reescribir la ecuaci´ on de la siguiente manera: ∆wt = w + =w+

m X t=1 m X

α(z − F (xt, w))∇w F (xt, w) α∇w F (xt, w)

t=1

m X

dk

k=t

El aprendizaje ahora depende de las diferencias entre las predicciones para los elementos de la serie. Sin embargo, es equivalente al aprendizaje reforzado. La familia de algoritmos de aprendizaje T D(λ) usan la siguiente f´ ormula para la actualizaci´ on de los pesos: w=w+

m X t=1

α∇w F (xt, w)

m X

λk−tdk ,

k=t

con 0 ≤ λ ≤ 1. Emp´ıricamente se ha visto que T D(λ) tiene mejores resultados que la t´ecnica de aprendizaje reforzado pura. Jorge Baier Aranda, PUC

19

Aprendiendo a Jugar con Diferencias Temporales Si se utiliza una estrategia minimax, una buena funci´ on de evaluaci´ on perfecta (digamos, J(·)) es aquella que entrega, con exactitud, la utilidad de cada nodo, es decir, el valor que tendr´ıa si pudi´eramos expandir el ´arbol hasta lo m´as profundo posible. Queremos tener un m´etodo para encontrar la funci´ on J(·). En general, en los juegos de tablero, cuando esta funci´ on es conocida, es simplemente una tabla que, dada una posici´ on, retorna -1, 0 o 1. ˜ w), que Realmente, nos interesa encontrar una estimaci´ on de J, digamos J(t, dado un tablero t y un vector de par´ametros w, retorne una estimaci´ on para J(t). ˜ w) como un problema de aprendizaje ¿Se puede ver el problema de aprender J(t, de m´ ultiples etapas? Bajo algunos supuestos acerca del contrincante, la respuesta es s´ı. La raz´ on es que en general podremos observar una serie x1, . . . , xn que corresponde a los distintos tableros que se generan durante el juego en donde MAX Jorge Baier Aranda, PUC

20

puede jugar, y, finalmente, tendremos un resultado (1,0 o -1). ˜ n+1, w) es el As´ı, para una secuencia de tableros x1, . . . , xn, xn+1 (donde J(x resultado final del juego), podemos aplicar una f´ ormula del siguiente estilo para actualizar w: n n X X ˜ t, w) w=w+ α∇w J(x λk−tdk t=1

k=t

Sin embargo, si MAX juega usando la estrategia minimax, es m´as conveniente que la estrategia tome eso en cuenta. Para ello, se invent´ o el algoritmo TDLeaf(λ) que modifica la estimaci´ on de las hojas de un ´arbol minimax.

Jorge Baier Aranda, PUC

21

El algoritmo TDLeaf(λ) En el algoritmo minimax, la evaluaci´ on asignada a la ra´ız corresponde al valor que tiene la hoja de una rama ´ optima, es decir la rama que tiene la mejor secuencia de movidas para MAX. La idea en TDLeaf es modificar J˜ pensando en el valor asignado a la hoja que da el valor al nodo ra´ız, y no en el valor del nodo ra´ız. El algoritmo se resume de la siguiente manera: Sean x1, . . . , xn−1 los tableros donde MAX pudo jugar y xn el tablero final (r(xn) ˜ n, w) ← r(xn). es el resultado del juego). Diremos, por simplicidad que J(x 1. Para cada estado xi, hacer xli igual a la hoja del ´arbol minimax que sirve para computar el valor minimax de xi. 2. Para cada t ∈ 1..n − 1 computar ˜ lt+1, w) − J(x ˜ lt, w) dt ← J(x Jorge Baier Aranda, PUC

22

3. Actualizar w de acuerdo a la formula: w ←w+α

n−1 X t=1

˜ lt, w) ∇J(x

n−1 X

λj−tdt.

j=t

Se ha comprobado que TDLeaf ha tenido excelentes resultados para entrenar jugadores de ajedrez.

Jorge Baier Aranda, PUC

23