JUEGOS

Fecha de la clase: 8 de Enero

INTRODUCCIÓN

En esta clase se realizaron unos trabajos de investigación en clase en los que se expusieron cada uno de los trabajos en uno de estos vimos sobre los juegos y las decisiones óptimas para estos donde tenemos que estos multiagentes pueden ser cooperativos o competitivos.

MARCO TEÓRICO

JUEGOS

La Teoría de Juegos estudia de manera formal y abstracta las decisiones óptimas que deben tomar diversos adversarios en conflicto, pudiendo definirse como el estudio de modelos matemáticos que describen el conflicto y la cooperación entre entes inteligentes que toman decisiones. Tales decisiones se consideran estratégicas, es decir, que los entes que participan en el juego actúan teniendo en cuanta las acciones que tomarían los demás.

La teoría de juegos es capaz de ofrecer cuestiones de interés para estudiantes de todas las ramas de las Ciencias Sociales y la Biología, así como técnicas para tomar decisiones prácticas. (Fernández, F)

Los juegos son interesantes porque son demasiado difíciles de resolver. El ajedrez, por ejemplo, tiene un factor de ramificación promedio de 35 y los juegos van a menudo a 50 movimientos por cada jugador:

Grafo de búsqueda: aproximadamente 10^40 nodos distintos árbol de búsqueda: 35^100 o 10^154. Los juegos, como el mundo real, requieren la capacidad de tomar alguna decisión (la jugada) cuando es infactible calcular la decisión óptima. (Ceccaroni, L).

DESICIONES ÓPTIMAS EN JUEGOS

Un juego puede definirse formalmente como una clase de problemas de búsqueda con los componentes siguientes:

– El estado inicial

– Una función sucesor, que devuelve una lista de pares (movimiento, estado)

 – Un test terminal, que determina cuándo termina el juego (por estructura o propiedades o función utilidad)

 – Una función utilidad. (Ceccaroni, L).

ALGORITMO MINIMAX:

El algoritmo calcula la decisión minimax del estado actual. Usa un cálculo simple recurrente de los valores minimax de cada estado sucesor, directamente implementando las ecuaciones de la definición. La recursión avanza hacia las hojas del retroceder árbol, y entonces los valores minimax retrocedió por el árbol cuando la recursión se va deshaciendo. Por ejemplo, en la Figura, el algoritmo primero va hacia abajo a los tres nodos izquierdos, y utiliza la función Utilidad para descubrir que sus valores son 3, 12 y 8 respectivamente. Entonces toma el mínimo de estos valores, 3, y lo devuelve como el valor del nodo B. Un proceso similar devuelve hacia arriba el valor de 2 para C y 2 para D. Finalmente, tomamos el máximo de 3, 2 y 2 para conseguir el valor de 3 para el nodo de raíz.

El algoritmo minimax realiza una exploración primero en profundidad completa del árbol de juegos. Si la profundidad máxima del árbol es m, y hay b movimientos legales en cada punto, entonces la complejidad en tiempo del algoritmo minimax es O(b^m). La complejidad en espacio es O(bm) para un algoritmo que genere todos los sucesores a la vez, o O(m) para un algoritmo que genere los sucesores uno por uno.

Para juegos reales, desde luego, los costos de tiempo son totalmente poco prácticos, pero este algoritmo sirve como base para el análisis matemático de juegos y para algoritmos más prácticos. (Russell, S y Norvig, P).

CONCLUSIÓN

En anteriores temáticas tratamos sobre agentes que usaban estrategias en la que solo un agente realizaba la búsqueda a la solución, pero en los juegos tenemos dos agentes luchando por tratar de buscar un mismo objetivo.

BIBLIOGRAFÍA

Ceccaroni, L. 2007. Inteligencia Artificial Busqueda entre Adversarios. En Línea. Formato PDF. Disponible en http://www.cs.upc.edu/~luigi/II/IA-2007-fall/2d-busqueda-entre-adversarios-(es).pdf

Fernández, F. 2005. Teoría de Juegos. En Línea. Formato PDF. Disponible en http://imarrero.webs.ull.es/sctm05/modulo1lp/5/ffernandez.pdf

Russell, S y Norvig, P. 2004.  INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. Segunda edición.  PEARSON EDUCATION, S.A. Impreso en España.