juegos tres en raya

8/13/2019 Juegos Tres en Raya

1/23

El Juego como Problema de Bsqueda

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

Supondremos que maxmueve 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


2/23

Por esa razon, se considera generalmente una funcion de evaluacionde estadosque califica a los estados segun que tan buenos son para max.



3/23

El espacio de bsqueda

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 raz esta a profundidad0) corresponden a turnos del jugador max.

Los nodos que estan a profundidad impar corresponden a turnos del jugadormin.



4/23

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 evaluaciona cada hoja del arbol.

Repetir mientras k 1

Calcular la utilidad de los nodos de nivel 2k1como la mnimautilidad entrela de sus hijos.

Calcular la utilidad de los nodos de nivel2k2como la maximautilidad entrela de sus hijos.

k=k 1

La mejor jugada corresponde al hijo de mayor utilidad en del nodo inicial.



5/23

El Gato: un ejemplo sencillo

Para ejemplificar el algoritmo, consideremos el juego del gato. En este juego

podemos 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 podramos 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 minya ha jugadoen una de las posiciones del tablero. Finalmente, la figura 3 muestra la ultimaetapa de la busqueda.



6/23

Figura 1: Primera etapa en la busqueda del gato



7/23

Figura 2: Segunda etapa en la busqueda del gato



8/23

Figura 3: Ultima etapa en la busqueda del gato



9/23

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 Ano 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 busqueda norepresentan juegos ganados para min o max.

Consideremos ahora la primera etapa del gato (figura 4). Supongamos que la

busqueda 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



10/23

Node, en la figura) esta acotado inferiormente por 1. A este valor se le conocecomo valor alfa.

El valor alfade un nodo MAX es la cota inferior del valor de utilidad que se

conoce 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 Cy 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 lmite 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 conocehasta el momento.

Notemos que:



11/23

Los valores alfa de los nodos maxnunca 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 busqueda:

La busqueda es abandonada bajo todo nodo minque tiene un valor beta menoro igual al valor alfa de alguno de sus antecesores max.

La busqueda es abandonada bajo todo nodo maxque tiene un valor alfa mayoro 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 maxes igual al mayor valor calculado en sus sucesores. El valor beta de un nodo mines 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.



12/23

Figura 4: Primera etapa de la busqueda del gato



13/23

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.



14/23

Alfa-Beta en pseudo cdigo

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 ifprof = limite

2 then return Ut(nodo)

3 for eachni {n1, n2, . . . , nk} = Sucesores(nodo)

4 do ifprof 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 mn{;AB(ni, , , prof+ 1, P)}

11 if

12 then return

13 if i = k

14 then return



15/23

Eficiencia de Alfa-Beta

Supongamos que el arbol tiene profundidad d y cada nodo (excepto los nodoshoja) tienen exactamenteb sucesores. Si no realizamos poda alfa-beta, deberemos

revisar 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 43dla profundidad de la busqueda revisando la misma cantidadde nodos que sin poda.



16/23

Prediccin en Mltiples Etapas

Supongamos que queremos construir un algoritmo que prediga la temperaturadel da domingo. Este algoritmo recibira el da de la semana y las observaciones

meteorologicas de este.

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

Lo que queremos es encontrar una funcion Fque 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.



17/23

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

Supongamos que Fes 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)



18/23

Usando diferencias temporales

El metodo de diferencias temporales es una variacion del enfoque de aprendizaje

supervisado.

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)



19/23

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

ktdk,

con 0 1.

Empricamente se ha visto que TD() tiene mejores resultados que la tecnica deaprendizaje reforzado pura.



20/23

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, es

decir, el valor que tendra 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 tablerot y un vector de parametros w, retorne una estimacion paraJ(t).

Se puede ver el problema de aprender J(t,w)como un problema de aprendizaje

de 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



21/23

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 para

actualizar w:w= w +

n

t=1

wJ(xt,w)

n

k=t

ktdk

Sin embargo, si MAX juega usando la estrategia minimax, es mas conveniente

que la estrategia tome eso en cuenta.

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



22/23

El algoritmo TDLeaf()

En el algoritmo minimax, la evaluacion asignada a la raz 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 Jpensando en el valor asignado a la hoja queda el valor al nodo raz, y no en el valor del nodo raz.

El algoritmo se resume de la siguiente manera:

Sean x1, . . . ,xn1los tableros donde MAX pudo jugar y xnel tablero final (r(xn)es el resultado del juego). Diremos, por simplicidad que J(xn,w) r(xn).

1. Para cada estado x

i, hacer x

l

i igual a la hoja del arbol minimax que sirve paracomputar el valor minimax de xi.2. Para cadat 1..n 1 computar

dt J(xlt+1,w) J(x

lt,w)



23/23

3. Actualizar w de acuerdo a la formula:

w w +

n1

t=1

J(xlt, w)

n1

j=t

jtdt.

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


juegos tres en raya

Documents