El Juego como Problema de Bsqueda

En este algoritmo identicamos 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 denido por: Estado inicial: Es una conguraci 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 conguraci on nal 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 calica a los estados seg un qu e tan buenos son para max.

Jorge Baier Aranda, PUC

El espacio de bsqueda
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

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 conguraciones 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 =k1 La mejor jugada corresponde al hijo de mayor utilidad en del nodo inicial.

Jorge Baier Aranda, PUC

El Gato: un ejemplo sencillo

Para ejemplicar 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 las, columnas o diagonales abiertas para max (donde a un puede ganar) y NC (t) es el n umero de las, 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 gura 1 muestra el algoritmo Minimax con un arbol de profundidad 2. La gura 2 muestra otro arbol con profundidad 2, pero luego que min ya ha jugado en una de las posiciones del tablero. Finalmente, la gura 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

Figura 2: Segunda etapa en la b usqueda del gato

Jorge Baier Aranda, PUC

 Figura 3: Ultima etapa en la b usqueda del gato

Jorge Baier Aranda, PUC 8

La poda Alfa-Beta
En muchos juegos minimax es ineciente. Para ello, es posible usar la poda alfa-beta. Consideremos el arbol de juego de la u ltima etapa del gato (gura 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 (gura 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 gura) 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 gura 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 gura, 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

alfa=3

beta=3

beta=1

L (2)

M (3)

N (8)

O (5)

P (7)

Q (6)

R (0)

S (1)

T (5)

U (2)

V (8)

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 cdigo

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

Eciencia 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 eciencia 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 4 usqueda revisando la misma cantidad 3 d la profundidad de la b de nodos que sin poda.

Jorge Baier Aranda, PUC

15

Prediccin en Mltiples 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 codican 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 nal 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:
m

ww+
t=1

wt

(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 deniendo dt = F (xt+1, w) F (xt, w) y notando que

m

z F (xt, w)) =
k=t
Jorge Baier Aranda, PUC

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

con z = F (xm+1, w)

18

As , es posible reescribir la ecuaci on de la siguiente manera:

m

wt = w +
t=1 m

(z F (xt, w))w F (xt, w)

m

=w+
t=1

w F (xt, w)
k=t

dk

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:
m m

w=w+
t=1

w F (xt, w)
k=t

ktdk ,

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. (t, w), que Realmente, nos interesa encontrar una estimaci on de J , digamos J dado un tablero t y un vector de par ametros w, retorne una estimaci on para J (t). (t, w) como un problema de aprendizaje Se puede ver el problema de aprender J 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, nalmente, tendremos un resultado (1,0 o -1). (xn+1, w) es el As , para una secuencia de tableros x1, . . . , xn, xn+1 (donde J resultado nal del juego), podemos aplicar una f ormula del siguiente estilo para actualizar w: n n (xt, w) w=w+ w J ktdk
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 modica 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. pensando en el valor asignado a la hoja que La idea en TDLeaf es modicar J 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, . . . , xn1 los tableros donde MAX pudo jugar y xn el tablero nal (r(xn) (xn, w) r(xn). es el resultado del juego). Diremos, por simplicidad que J 1. Para cada estado xi, hacer xl arbol minimax que sirve para i igual a la hoja del computar el valor minimax de xi. 2. Para cada t 1..n 1 computar (xl l dt J t+1 , w) J (xt , w)
Jorge Baier Aranda, PUC 22

3. Actualizar w de acuerdo a la formula:

n1 n1

w w+
t=1

(xl J t, w)
j =t

j tdt.

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

Jorge Baier Aranda, PUC

23