DECISIONES ÓPTIMAS EN JUEGO

Fecha de clases: 15 de julio/2014

INTRODUCCIÓN

En los entornos multiagente (cooperativos o competitivos), cualquier agente tiene que considerar las acciones de otros agentes. La imprevisibilidad de estos otros agentes puede introducir muchas contingencias en el proceso de resolución de problemas. Los entornos competitivos, en los cuales los objetivos de los agentes están en conflicto, dan ocasión a problemas de búsqueda entre adversarios, a menudo conocidos como juegos.

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.

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 1040 nodos distintos árbol de búsqueda: 35100 o 10154. Los juegos, como el mundo real, requieren la capacidad de tomar alguna decisión (la jugada) cuando es infactible calcular la decisión óptima.

DECISIONES ÓPTIMAS EN JUEGO.

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)

EL PROCEDIMIENTO MINIMAX.

Calcula la decisión minimax del estado actual.

Usa un cálculo simple recurrente de los valores minimax de cada estado sucesor.

La recursión avanza hacia las hojas del árbol.

Los valores minimax retroceden por el árbol cuando la recursión se va deshaciendo.

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 es O (bm);

En espacio es O (bm) si se generan todos los sucesores a la vez;

O (m) si se generan los sucesores uno por uno.

Juegos reales: los costos de tiempo son inaceptables, pero este algoritmo sirve como base para el primer análisis matemático y para algoritmos más prácticos. 

Las estrategias maximin y minimax conducen a los dos jugadores del juego a situaciones en las que ningún jugador tiene razón o incentivo alguno para cambiar su posición. Así mismo, se dice que un jugador posee una estrategia dominante si una estrategia particular es preferida a cualquier otra estrategia a disposición de él.

CONCLUSIÓN

Se han visto estrategias en las que un solo agente busca la solución a un problema. Existen otro tipo de problemas en los que dos agentes compiten por un mismo objetivo. Las búsquedas con adversarios son parte de la teoría matemática de juegos, y para la I.A. se centran en los de un tipo determinado.

Algunas teorías buscan encontrar las estrategias racionales, que se utilizan en situaciones donde el resultado depende no solamente de las estrategias propias y las condiciones del entorno, sino también en las estrategias utilizadas por otros jugadores con objetivos distintos.

BIBLIOGRAFÍAS

Ceccaroni, L. 2007. Inteligencia Artificial: Búsqueda entre adversarios.

Russell, S., Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. Segunda Edición. Pearson Education. España.

Fernando Fernández Rodríguez. 2005. Teoría de juegos: análisis matemático de conflictos. Curso Interuniversitario “Sociedad, Ciencia, Tecnología y Matemáticas”