BÚSQUEDA ENTRE ADVERSARIOS

Fecha de Clase: 6 - 10 de Julio 2015
INTRODUCCIÓN

En esta clase se introdujo a las búsquedas entre adversarios, es un tema muy importante de conocer ya que hasta ahora las búsquedas que hemos revisado han sido simples (con un solo jugador), pero en este documento vamos a introducir en lo que respecta a búsquedas con más de un jugador. Para estos hay que conocer sobre los entornos multiagentes (cooperativo y competitivo), donde intervienen mas de un agente, y estos trae mas dificultades entre los agentes, ya que el agente tendrá que saber cómo actuar ante otro las acciones de otro agente.

OBJETIVO

Estudiar las búsquedas entre adversarios o mejor conocidas como juegos.

MARCO TEÓRICO

ENTORNOS MULTIAGENTES

Los podemos dividir en dos partes: Cooperativo y Competitivo.

COMPETITIVOS: Un rasgo de alta incidencia en el entorno actual es la competencia, ella contribuye a que las organizaciones desarrollen capacidades, reformulen políticas, planteen estrategias y busquen asociarse para introducirse, mantenerse y ampliarse en el mercado. Tanto las organizaciones que se encargan de la producción de bienes materiales, como las que se dedican a la  prestación de servicios, se encuentran inmersas en este ambiente competitivo.

Las organizaciones desarrollan sus actividades dentro de una realidad circundante: El entorno que condiciona considerablemente su funcionamiento. En gran medida, el mayor o menor éxito de las empresas dependerá de su  acierto en relacionarse adecuadamente con el conjunto de elementos externos a la misma.

Este conjunto de variables, entre las que se encuentran: El comportamiento del  mercado, los costos, las innovaciones en la tecnología y los aspectos sociales,  culturales, políticos y legales, cambian con el transcurso del tiempo.

En estas circunstancias las organizaciones deben procurar mantener un equilibrio dinámico y permanente.(Benites, E. 2014?)

COOPERATIVOS: Cooperan para obtener una secuencia de acciones (plan) que permita llegar desde un estado inicial a un estado final.  Cada agente utiliza un método diferente para planificar. Uno de ellos planifica “hacia adelante”, partiendo del estado inicial y avanzando hacia el estado final.  El otro agente planifica “hacia atrás”, comenzando desde el estado final  y  retrocediendo  hacia  el  estado  inicial.   La  tarea  de  planificación  termina  cuando ambos  agentes  obtienen  un  plan  parcial  para  llegar  desde  su  estado  de  partida  a  un mismo estado intermedio. (Garcia, J. 2000)

JUEGOS

En la IA existen tipos distintos de juegos: juegos de sumas de cero y juegos suma no cero.

JUEGO DE SUMA DE CERO

En los juegos de suma cero el beneficio total para todos los jugadores del juego, siempre suma cero, es decir, un jugador se beneficia solamente a expensas de otros el ajedrez es un ejemplo de juego de suma cero, porque se gana exactamente la cantidad que pierde el oponente.(Neumann, J y Morgenstern, O. 1944)

Tabla 1. suma de cero

JUEGO DE SUMA NO CERO

La mayoría de los ejemplos reales son juegos de suma no cero, porque algunos desenlaces tienen resultados netos mayores o menores que cero. En otras palabras, la ganancia de un jugador no necesariamente se corresponde con la pérdida de otro. (Neumann, J y Morgenstern, O. 1944)

DECISIONES ÓPTIMAS EN JUEGOS

Para la toma óptima de decisiones podemos basarnos en los siguientes parámetros:

EJEMPLO DE APLICACIÓN

Imagen 1. Juego tres en raya

Estado inicial: tablero vacío + ficha de salida

Función Sucesor:  

• 9 movimientos posibles, uno por casilla
• Aplicable si la casilla no está ocupada
• Estado resultante: colocar la ficha que toca en la casilla especificada

Test terminal: tableros completos o con línea ganadora

Función Utilidad:

• 1 si es ganador para MAX
• 0 si es tablas (empate)
• -1 si es ganador para MIN

VALOR MINIMAX

Un jugador quien usa el criterio minimax escoge una estrategia que, entre todas las estrategias posibles, minimiza el daño de la mejor contra-estrategia del otro jugador. Es decir, una estrategia óptima según el criterio minimax es una que minimiza el daño máximo que puede hacer el contrincante. (Waner, S. 2007)

ALGORITMO MINIMAX

Es un algoritmo de decisión para minimizar la pérdida máxima aplicada en juegos de adversarios donde cada jugador conoce el estado del otro. Elección del mejor movimiento para cada jugador,  suponiendo que el contrincante escogerá el peor. El espacio de estados se representa mediante árboles, donde:

•  Nodo: Representa una situación del juego.
• Sucesores de un nodo: Situaciones del juego a las que se accede por movimientos legales aplicando sus reglas.
•  Nivel: Contiene todas las situaciones posibles para uno de los jugadores.

El algoritmo Minimax es un procedimiento recursivo y el corte de la recursión está dado por alguna de las siguientes condiciones: (Lopez, B. 2012.)

• Gana algún jugador
• Se han explorado N capas, siendo N el límite establecido
• Se ha agotado el tiempo de exploración
• Se ha llegado a una situación estática donde no hay grandes cambios de un nivel a otro.

CONCLUSIÓN

La búsquedas entre adversarios o mejor conocidas como juegos es importante su estudio puesto que a través de la historia muchos de los investigadores de la inteligencia artificial han indagado en esta rama ya que los juegos traen dificultades que hacen  más interesante el estudio de este tipo de búsqueda. Los juegos también son conocidos como suma de cero que son entre dos jugadores tomando en cuenta las decisiones y estrategias óptimas (estado inicial, función sucesor, test terminal y función terminal), examinando el valor minimax. Para esto se han desarrollado algoritmos minimax que realiza la exploración por la búsqueda primero en profundidad y utilizan la recursión.

BIBLIOGRAFÍA

Benites, E. 2014?. INTELIGENCIA ARTIFICIAL. FORMATO PDF. Disponible en: http://sisbib.unmsm.edu.pe

Garcia, J. 2000. Agentes inteligentes cooperativos. 

Neumann, J y Morgenstern, O. 1944. Theory of Games and Economic Behavior.

Russell, S. y Norvig, P. 2004. INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. PEARSON EDUCACION. 2 ed. Madrid.

Waner, S. 2007. TEORIA DE JUEGOS. Formato HTML. Disponible en: http://www.zweigmedia.com

Lopez, B. 2012. Algortimo minimax. Formato HTML. Disponible:http://www.itnuevolaredo.edu.mx/