Una introducción a la Inteligenca Artificial (IA)



Descargar 2.01 Mb.
Página22/29
Fecha de conversión20.03.2018
Tamaño2.01 Mb.
Vistas523
Descargas0
1   ...   18   19   20   21   22   23   24   25   ...   29

4.9 teoría de Juegos.



Características de los juegos:

En la mayoría de las primeras investigaciones en búsqueda espacio-estado se utilizaron juegos de tablero comunes tales como el ajedrez, las damas chinas y el 8-puzzle. Además de su inherente atractivo intelectual, los juegos tienen ciertas características que los hacen ideales para estas investigaciones:



  • Contienen un conjunto bien definido de reglas, lo que hace posible generar el espacio de búsqueda y evita ambigüedades.

  • La configuración del tablero utilizada en los juegos se representa fácilmente en una computadora sin requerir de formalismos complejos.

  • Pueden generar espacios de estados extremadamente grandes, lo suficientemente grandes y complejos para requerir de técnicas que determinen las alternativas a explorar en la búsqueda de la solución.



  • La mayoría de la gente ha tenido alguna experiencia con éstos, lo que hace posible seguir y probar la efectividad de las heurísticas aplicadas.




  • Los programas de juegos, ofrecen retos, incluyendo un oponente cuyos movimientos no pueden ser anticipados certeramente. La presencia de este oponente añade a los programas un elemento de incertidumbre y la posibilidad de considerar la psicología como un factor táctico en la estrategia del juego.


4.9.1. Procedimiento mini-max.

Consideremos el caso general de un juego con dos participantes, los cuales alternan su participación hasta que concluye el juego. Una definición formal del juego sería la de un tipo de problema de búsqueda integrado por lo siguiente:




  • El estado inicial, que incluye la posición en el tablero y una indicación de a quien le toca empezar

  • Un conjunto de operadores, quienes definen que jugadas están permitidas a un jugador

  • Una prueba terminal que define el término del juego. Los estados en donde termina el juego se denominan estados terminales

  • Una función de utilidad que asigna un valor numérico al resultado obtenido en un juego.

Si se tratará de un problema de búsqueda normal, lo único que tendría que hacer el primer jugador (que llamaremos MAX) es determinar la secuencia de jugadas que conduzca a un estado terminal ganador y proceder a efectuar la primera jugada de la secuencia. Desafortunadamente, MIN también tiene algo que decir. Por lo tanto, MAX tiene que encontrar una estrategia que lo conduzca a un estado ganador sin importar lo que haga MIN.



4.9.2. Algoritmo mini-max.

El algoritmo mini-max sirve para determinar la estrategia óptima para MAX, y decidir así cuál es la mejor jugada. El algoritmo se compone de cinco pasos:




  1. Generación de todo el árbol de juego, completamente hasta alcanzar los nodos terminales

  2. Aplicación de la función de utilidad a cada estado terminal y obtención de su valor respectivo.

  3. Uso de la utilidad de los estados terminales para calcular la utilidad de los nodos del siguiente nivel superior en el árbol de búsqueda dependiendo del jugador en turno.

  4. Continuación del respaldo de los nodos hojas, en dirección a la raíz, una capa a la vez en base a la funcion:

Mejor=max(M(n), mejor)

Donde: M(n)=MÍNIMAX(n, profundidad+1, C(jugador))



C(jugador) es una función que cambia de jugador.


  1. Cuando los valores respaldados llegan a la parte superior del árbol MAX elige la jugada que le permite obtener el valor más alto. [1]

Ejercicio 4.7.


Dado un árbol, señalar las estrategias que podría elegir un jugador MAX para ganar, si se considera que un estado terminal para ser ganador MAX debe tener una valor mayor o igual a 6; mientras MIN debe tener un valor menor de 6 para ser ganador.




Problemas resueltos




Problema 1
Dado el árbol que aparece en la figura 6 en el que el valor adjunto a cada nodo es el de la función heurística F , que señala el grado en que cada nodo satisface las condiciones del objetivo:

indique el orden en que se visitan los nodos, distinguiendo los que lo se han generado de aquellos que se han elegido en el proceso de búsqueda de la solución, para el procedimiento de búsqueda en escalada.

SOLUCION :
¿Q pretende este problema? En el presente problema se muestra la aplicación de una estrategia irrevocable, en concreto el método de gradiente, en la resolución de un problema de búsqueda heurística.
Se trata de realizar una búsqueda en profundidad sin posibilidad de retroceso, donde la elección del nodo a expandir depende de una función heustica; por tanto, este método no pertenece al conjunto de estrategias que no emplean información del dominio. La variable elegido almacenaaquel nodo por el que f aumente de forma más abrupta. Por tanto, se recorre el camino de máxima pendiente con respecto al valor de la función heurística utilizada. Teniendo en cuenta el algoritmo que aparece anteriormente:

22

Punto 1) m = A, elegido = A

2.1) Se expande A

2.1.(1) nuevo = D

2.1. (3) Como f(D) > f(A), elegido = D

2.1.(1) nuevo = F

2.1.(1) nuevo = G

Al final, elegido = D y f(elegido) = 3.

2.2.) m = D

2.1) se expande D

2.1.(1) nuevo = H

2.1.(3) Como f(H) > f(D), elegido = H

2.1.(1) nuevo = J



Al final, elegido = H y f(elegido) = 4

2.2.) m = H

2.1.) Se expande H

2.1. (2) Fin, ya que B es un estado meta.




Por lo tanto, el camino para llegar a la meta ha sido: A, D, H, B

Consideraciones finales:


El método más adecuado para este problema es el de escalada, debido a que en aquellos caminos que conducen a un nodo meta, f es una función creciente. Es decir, la infalibilidad del método aplicado se ajusta al problema planteado. Además, no hay garana en otros algoritmos no informados de que el camino recorrido sea tan corto, ya que éste dependerá del orden arbitrario en que se hayan elegido los nodos.

Problema 2
Recorra el grafo de la figura 7 según el procedimiento primero el mejor, suponiendo que los nodos esn etiquetados según el valor de la función de evaluación heustica "distancia estimada a la meta" en cada uno de ellos. Para ello, opte por indicar los valores de la lista ABIERTA y CERRADA a lo largo de cada ciclo del procedimiento, o bien represente los árboles de búsqueda considerados sucesivamente hasta alcanzar la solución.
Considere que el costo en la generación de cada sucesor en el grafo anterior es un costo uniforme de valor 1 y realice el mismo estudio siguiendo el procedimiento A*. Analice las diferencias, en caso de existir, entre las dos soluciones obtenidas, indicando cuál de los dos métodos encuentra una solución más eficiente. ¿Q condiciones debería cumplir el procedimiento A* para que la solución obtenida tuviera la garana de ser óptima?

Figura 10




SOLUCION:
¿Q pretende este problema? En este ejercicio se realizará una comparación entre los algoritmos de búsqueda heurística primero el mejor y A*.

a. Procedimiento primero el mejor.


Se van a dibujar los arcos del árbol que une el nodo raíz con cada nodo a través de los mejores caminos encontrados en el grafo (ver figura 8). También se indicará el orden en que los nodos son seleccionados para su expansión. En cada momento se seleccionará de ABIERTA aquel nodo cuyo valor de distancia estimada a la meta sea el menor. Se describirá cómo evolucionan ABIERTA y CERRADA tras cada paso del algoritmo. Según el algoritmo del apartado teórico:

24
ABIERTA CERRADA Paso 1) A (14) Vacía Paso 2) C(3), B(5) A



Paso 3) B(5), F(6), G(8) A,C, Paso 4) F(6), D(7), G(8), E(9) A,C,B, Paso 5) J(2), I(4), D(7), G(8), E(9) A,C,B,F Paso 6) I(4), D(7), G(8), E(9) A,C,B,F,J
En este ciclo del algoritmo se encuentra un descendiente (G) del nodo que se está expandiendo (J), ya que estaba en ABIERTA. A pesar de ello no se produce reorientación por ser el anterior camino desde G al nodo raíz de menor costo que el encontrado ahora.


Método primero el mejor.

Paso 7) D(7), G(8), E(9) A,C,B,F,J,I,

Tenemos un caso análogo al del ciclo anterior.

Paso 8) H(5), G(8), E(9) A,C,B,F,J,I,D

Al expandir D se genera I, que ya estaba CERRADA. El nuevo camino encontrado hasta I

no es menos costoso que el anterior; por lo tanto, no hay que redirigir arcos.



Paso 9) L(7), G(8), E(9) A,C,B,F,J,I,D,H

Paso 10) G(8),E(9) A,C,B,F,J,I,D,H,L
Con la generación de M se llega al final del algoritmo. La lista ABIERTA debe mantenerse ordenada a lo largo de todo el proceso, ya que el "siguiente nodo a expandir" es el primero de dicha lista.
El camino encontrado siguiendo los punteros, que siempre deben señalar al mejor antecesor de un nodo en el grafo, es:

A, B, D, H, L, M

b. Procedimiento A*



25

Ahora habrá que sumar a la distancia estimada a la meta el costo del camino de menor coste encontrado hasta cada nodo, para formar una nueva función heurística f (ver figura 9) La ventaja, por tanto, es que este algoritmo tiene en cuenta el camino recorrido hasta el nodo dado, lo que evita ciertas deficiencias que aparecían en el caso del algoritmo primero el mejor. En la lista ABIERTA y entre paréntesis, al lado de cada nodo, figura el valor que la función heustica toma en este nodo. El proceso de finalización del algoritmo A* va a ser algo diferente al de primero el mejor. En este último la búsqueda finaliza cuando se genera un nodo meta desde su nodo padre; en cambio, en el nodo A*, hasta que el nodo meta no es seleccionado para ser expandido, el algoritmo no acaba. Esto garantiza que el camino encontrado sea óptimo si se cumple la siguiente condición:

Para todo n, h(n) <= h*(n) (h*(n): costo real óptimo desde el nodo n hasta una meta)
Como en el caso del algoritmo anterior, no se va a tener que producir ninguna reorientación, ya que el costo de los nuevos caminos encontrados hasta un nodo en ninn caso va a ser menor que el del camino que ya se había encontrado con anterioridad hasta ese nodo.

ABIERTA CERRADA Paso 1) A(0+14) Vacía Paso 2) C(1+3), B(1+5) A

Paso 3) B(1+5), F(2+6), G(2+8) A,C Paso 4) F(2+6), D(2+7), G(2+8), E(2+9) A,C,B Paso 5) J(5), I(7), D(9), G(10), E(11) A,C,B.F

Paso 6) y 7) D(9), G(10), E(11) A,C,B,F,J,I

No es necesario redirigir G desde J ni D desde I

Paso 8) H(3+5), G(10), E(11) A,C,B,F,J,I,D
En este caso, se ha encontrado un nuevo camino desde el nodo I hasta la raíz, que pasa por D; pero este camino es del mismo costo que el existente con anterioridad; por tanto, no habrá reorientación del enlace que parte de I.

Paso 9) G(10), E(11), L(4+7) A,C,B,F,J,I,D,H

Paso 10) K(3), E(11), L(11) A,C,B,F,J,I,D,H,G

No hay reorientación desde J.

Paso 11) E(11), L(11) A,C,B,F,J,I,D,H,G,K

26

El proceso finaliza cuando se expande el nodo K que es un nodo meta.


El camino encontrado es A, C, G, K que es mejor que el hallado mediante el método primero el mejor.

Método A*
Mientras que el algoritmo primero el mejor no garantiza que la solución encontrada sea óptima, A* si lo hace, siempre que la función h de distancia estimada a la meta cumpla: Para todo n, h(n)

<= h*(n), donde h* representa distancias reales óptimas de cada nodo a una meta. En este problema no se cumple la condición anterior. Por ejemplo, h(G) = 8 y en realidad estaba a una distancia de 1 de un nodo meta. Esto quiere decir que en este caso no se puede garantizar que la solución encontrada sea óptima.

Problema 3

Dado EL árbol de la figura 11

a. Señale en dicho árbol las estrategias ganadoras - si es que las hubiera- para un jugador

MAX y para un jugador MIN. Se considera que un estado extremo - o nodo terminal

(hojas del árbol)- es ganadora para MAX si su valor es superior o igual a 6. Contrariamente, un estado ganador para MIN es aquél cuyo valor es inferior a 6. Razone las respuestas.

b. Recorra el árbol, de izquierda a derecha, siguiendo el método de poda alfa-beta indicando claramente (por ejemplo, tachándolos con una x) los nodos en que se produce un corte en el proceso de búsqueda. Explique el razonamiento seguido en dichas situaciones, concretando el tipo de corte producido. Encuadre o marque los nodos terminales que no ha sido necesario considerar. Finalmente, señale el valor de la decisión inicial más acertada para MAX.

c. Realice el mismo estudio que en el apartado anterior b), suponiendo ahora que la rz del árbol es un nodo MIN

Figura 11




SOLUCION:
¿Qué pretende este problema? Al ser éste el primer ejercicio sobre poda alfa-beta, se introducirá a lo largo del mismo la notación gráfica que se va a emplear para este algoritmo en el resto del capítulo.

a) Estrategia ganadora para un jugador MAX:
Para MAX existen dos estrategias ganadoras que aparecen marcadas en la figura 21; una de ellas sería tomar el camino central y la otra el de la izquierda (se elegia finalmente la central, ya que es la que conduciría a MAX a un valor más alto). En la figura aparecen marcados los enlaces que conducen a MAX a ganar el juego.

Para MIN no habrá ninguna estrategia ganadora, por haber al menos una estrategia ganadora para

MAX.




Figura 12
Aunque el enunciado del problema no lo pide ¿qué pasaa si el nodo inicial fuese MIN (ver figura 13).


En este caso no existe estrategia ganadora para MIN, ya que desde el nodo raíz los nodos terminales con valor más bajo a los que se puede acceder son de valor 6, con lo cual MAX ganaría la partida. Los enlaces marcados vuelven a representar la estrategia ganadora para MAX.

b) Con respecto a cada nodo, se especificarán en el árbol de búsqueda dos tipos de datos:


El primero lo constituyen los valores de alfa y beta con los que se hace cada llamada recursiva desde ese nodo. Se adoptará el siguientes convenio: si las llamadas se hacen desde un nodo MAX, alfa se el valor que podrá ir aumentando tras cada llamada recursiva, hasta igualar o superar a beta , en cuyo caso se producirá una poda alfa. Este tipo de llamadas se representarán de la forma (alfa = valor1, valor2), ya que lo que se pretende resaltar es que es el cambio de alfa el que determina el que haya poda o no. Si, por el contrario, las llamadas recursivas se hacen desde un nodo MIN, se beta la variable que podrá ir disminuyendo tras cada llamada. La poda beta se producirá si beta iguala o queda por debajo de alfa (que permanece fijo) en algún momento. En este caso, para resaltar el hecho de que es la variable que determina la existencia o no de poda, este tipo de llamadas se representa de la forma (valor1, beta = valor2).
El segundo dato relacionado con cada nodo, que es importante especificar, es el resultado que se devuelve al nodo padre, como consecuencia de la ejecución del algoritmo.
Teniendo en cuenta las anteriores consideraciones, el árbol de squeda quedaría de la siguiente forma(mientras no se indique lo contrario y para el resto de problemas que abordan este tipo de búsqueda, se supondrá que la búsqueda con retroceso realizada se lleva a cabo de izquierda a derecha):
La decisión más acertada sería seguir el camino central, a través del cual se conseguiría llegar a un nodo terminal de valor 7. Este es el camino a elegir debido a que a través de él se produce la última actualización (incremento) del valor de alfa mandado desde el nodo raíz en cada llamada recursiva.

UNIDAD V APLICACIONES DE LA INTELIGENCIA ARTIFICIAL




Compartir con tus amigos:
1   ...   18   19   20   21   22   23   24   25   ...   29


La base de datos está protegida por derechos de autor ©psicolog.org 2019
enviar mensaje

enter | registro
    Página principal


subir archivos