El Juego como Problema de Búsqueda

En este algoritmo identificamos dos jugadores: max y min. El objetivo esencontrar la mejor movida para max.

Supondremos que max mueve inicialmente y que luego se turnan para jugar.

El espacio de busqueda queda definido por:

Estado inicial: Es una configuracion inicial del juego mas una indicacion dequien tiene la proxima movida.

Operadores: Corresponden a las jugadas legales se pueden hacer en el juego.Condicion Terminal: Determina cuando el juego se acabo.Funcion de Utilidad: Da un valor numerico a una configuracion final de un

juego. En un juego en donde se puede ganar, perder o empatar, los valorespueden ser 1, 0, o -1.

Generalmente no es posible buscar a una profundidad tal que permita llegar a lashojas del arbol.

Jorge Baier Aranda, PUC 1

Por esa razon, se considera generalmente una funcion de evaluacion de estadosque califica a los estados segun que 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 busqueda se vecomo un arbol en el cual:

• Los nodos que estan a profundidad par (suponiendo la raız esta a profundidad0) corresponden a turnos del jugador max.• Los nodos que estan 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 busqueda hasta un nivel de profundidad 2k. En este arbol,la primera movida corresponde a una jugada para max, por lo que las hojasdel arbol generado corresponden a configuraciones en donde min ha jugado porultima vez.

Aplicar la funcion de evaluacion a cada hoja del arbol.

Repetir mientras k ≥ 1

• Calcular la utilidad de los nodos de nivel 2k−1 como la mınima utilidad entrela de sus hijos.• Calcular la utilidad de los nodos de nivel 2k−2 como la maxima 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 juegopodemos usar la siguiente funcion de evaluacion para un tablero t:

E(t) = NA(t)−NC(t)

donde NA(t) es el numero de filas, columnas o diagonales abiertas para max(donde aun puede ganar) y NC(t) es el numero de filas, columnas o diagonalesabiertas 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. Lafigura 2 muestra otro arbol con profundidad 2, pero luego que min ya ha jugadoen una de las posiciones del tablero. Finalmente, la figura 3 muestra la ultimaetapa de la busqueda.

Jorge Baier Aranda, PUC 5

Figura 1: Primera etapa en la busqueda del gato

Jorge Baier Aranda, PUC 6

Figura 2: Segunda etapa en la busqueda del gato

Jorge Baier Aranda, PUC 7

Figura 3: Ultima etapa en la busqueda del gato

Jorge Baier Aranda, PUC 8

La poda Alfa-Beta

En muchos juegos minimax es ineficiente. Para ello, es posible usar la podaalfa-beta.

Consideremos el arbol de juego de la ultima etapa del gato (figura 3). Supongamosque un nodo hoja es evaluado en cuanto es generado.

Despues de evaluar el nodo A no tiene sentido seguir generando ni evaluando losnodos B, C o D.

El mismo tipo de poda se puede aplicar cuando las posiciones en la busqueda norepresentan juegos ganados para min o max.

Consideremos ahora la primera etapa del gato (figura 4). Supongamos que labusqueda se realiza usando una estrategia dfs y que cada vez que una hoja esgenerada su se computa su evaluacion. Supongamos, ademas, que tambien secalculan 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) esta acotado inferiormente por −1. A este valor se le conocecomo valor alfa.

El valor alfa de un nodo MAX es la cota inferior del valor de utilidad que seconoce hasta el momento.

Si durante el calculo del valor MAX de un nodo solo se conoce el valor de lautilidad de un subconjunto h de sus hijos, entonces el valor alfa corresponde a lamaxima utilidad que estos poseen.

Volviendo al ejemplo ¿Que pasa si estamos explorando el nodo C y ya sabemosque el valor para A es −1?

La respuesta es que no necesitamos seguir evaluando ningun sucesor de B pues,a lo mas, B tendra utilidad −1.

Al calcular el valor de C sabemos que B tiene un lımite superior de −1. A estevalor se le conoce por valor beta.

El valor beta de un nodo MIN es la cota inferior de la utilidad que se conocehasta 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 podadodel arbol de busqueda:

• La busqueda es abandonada bajo todo nodo min que tiene un valor beta menoro igual al valor alfa de alguno de sus antecesores max.• La busqueda 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 busqueda, 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 despues de producirel corte en el arco que une al nodo C con el nodo I.

En la misma figura, el algoritmo efectua un corte en el arco que une a K con Y .

Jorge Baier Aranda, PUC 11

Figura 4: Primera etapa de la busqueda del gato

Jorge Baier Aranda, PUC 12

A

(3)(2) (8) (5) (7) (6) (0) (1) (5) (2) (8) (4) (10) (2)

B C D

E F G H I J K

L M N O P Q R S T U V X YW

beta=3

alfa=3

beta=1

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 maxima a la que se quiere llegar, entonces llamando aAB(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 mod 2 = 0

5 then α← max{α; 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 nodoshoja) tienen exactamente b sucesores. Si no realizamos poda alfa-beta, deberemosrevisar bd nodos hoja.

La eficiencia de la poda dependera obviamente del orden en que se generan losnodos.

¿Cual es el mejor caso?

¿Y el peor?

Es posible demostrar que en el caso promedio, alfa-beta permite aumentaraproximadamente a 4

3d la profundidad de la busqueda revisando la misma cantidadde nodos que sin poda.

Jorge Baier Aranda, PUC 15

Predicción en Múltiples Etapas

Supongamos que queremos construir un algoritmo que prediga la temperaturadel dıa domingo. Este algoritmo recibira el dıa de la semana y las observacionesmeteorologicas de este.

Supongamos que x1, x2, . . ., x5, x6 son vectores que codifican el dıa y lasobservaciones meteorologicas hechas el lunes, martes, . . ., sabado.

Lo que queremos es encontrar una funcion F que dado un vector de “descripciondiaria” entregue una temperatura.

Para disenar 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 seproduce un resultado esperado z.

Jorge Baier Aranda, PUC 16

Si enfrentamos el problema usando aprendizaje supervisado, deberemos alimentaral algoritmo de aprendizaje con los datos (x1, z), (x2, x), . . . , (xn, z).

Supongamos que F es una funcion que calcula la salida de una red neuronal.

En ese caso, el problema se reduce a actualizar los pesos de esta, para cadaejemplo, usando la siguiente formula:

w← w +m∑

t=1

∆wt (1)

donde ∆wt esta dado por:

∆wt = α(z − F (xt,w))∇wF (xt,w)

Jorge Baier Aranda, PUC 17

Usando diferencias temporales

El metodo de diferencias temporales es una variacion del enfoque de aprendizajesupervisado.

La idea considera que la diferencia entre las distintas predicciones debe ayudara 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∑

k=t

(F (xk+1,w)− F (xk,w)), con z = F (xm+1,w)

Jorge Baier Aranda, PUC 18

Ası, es posible reescribir la ecuacion de la siguiente manera:

∆wt = w +m∑

t=1

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

= w +m∑

t=1

α∇wF (xt,w)m∑

k=t

dk

El aprendizaje ahora depende de las diferencias entre las predicciones para loselementos de la serie. Sin embargo, es equivalente al aprendizaje reforzado.

La familia de algoritmos de aprendizaje TD(λ) usan la siguiente formula para laactualizacion de los pesos:

w = w +m∑

t=1

α∇wF (xt,w)m∑

k=t

λk−tdk,

con 0 ≤ λ ≤ 1.

Empıricamente se ha visto que TD(λ) tiene mejores resultados que la tecnica deaprendizaje reforzado pura.

Jorge Baier Aranda, PUC 19

Aprendiendo a Jugar con Diferencias Temporales

Si se utiliza una estrategia minimax, una buena funcion de evaluacion perfecta(digamos, J(·)) es aquella que entrega, con exactitud, la utilidad de cada nodo, esdecir, el valor que tendrıa si pudieramos expandir el arbol hasta lo mas profundoposible.

Queremos tener un metodo para encontrar la funcion J(·). En general, en losjuegos de tablero, cuando esta funcion es conocida, es simplemente una tablaque, dada una posicion, retorna -1, 0 o 1.

Realmente, nos interesa encontrar una estimacion de J , digamos J(t,w), quedado un tablero t y un vector de parametros w, retorne una estimacion para J(t).

¿Se puede ver el problema de aprender J(t,w) como un problema de aprendizajede multiples etapas?

Bajo algunos supuestos acerca del contrincante, la respuesta es sı.

La razon es que en general podremos observar una serie x1, . . . ,xn que corres-ponde 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).

Ası, para una secuencia de tableros x1, . . . ,xn,xn+1 (donde J(xn+1,w) es elresultado final del juego), podemos aplicar una formula del siguiente estilo paraactualizar w:

w = w +n∑

t=1

α∇wJ(xt,w)n∑

k=t

λk−tdk

Sin embargo, si MAX juega usando la estrategia minimax, es mas convenienteque la estrategia tome eso en cuenta.

Para ello, se invento el algoritmo TDLeaf(λ) que modifica la estimacion de lashojas de un arbol minimax.

Jorge Baier Aranda, PUC 21

El algoritmo TDLeaf(λ)

En el algoritmo minimax, la evaluacion asignada a la raız corresponde al valor quetiene la hoja de una rama optima, es decir la rama que tiene la mejor secuenciade movidas para MAX.

La idea en TDLeaf es modificar J pensando en el valor asignado a la hoja queda 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)es el resultado del juego). Diremos, por simplicidad que J(xn,w)← r(xn).

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

dt ← J(xlt+1,w)− J(xl

t,w)

Jorge Baier Aranda, PUC 22

3. Actualizar w de acuerdo a la formula:

w← w + αn−1∑t=1

∇J(xlt, w)

n−1∑j=t

λj−tdt.

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

Jorge Baier Aranda, PUC 23