Busqueda con adversarios


Hasta este momento hemos tratado de los entornos en los que nuestro agente inteligente busca la solucion a un problema, basandose en metodos sin informacion y metodo con informacion, pero en estos metodos que analizamos se trataban de entornos con un solo agente.

A continuacion debemos comenzar a tratar con entornos multiagentes en los que nuestro agente inteligente interacciona con otro u otros agentes inteligentes, esto plantea dos tipos de entornos

  • Colaborativo
  • Competitivos

En los primeros, los agentes colaboran para llegar a un objetivo comun, pero implica que deben observarse mutuamente para no estorbarse, ni que uno de ellos repita uno de los trabajos del otro.

En los segundos, seguimos mostrando una observancia de las acciones del contrario, pero en este caso, debemos ver que la complejidad es mayor si consideramos que e el entorno multiagente competitivo se pueden producir alianzas entre algunos agentes, dichas alianzas son generalmente temporales, ademas debemos de considerar si se trata de un enfoque por turnos o un enfoque en tiempo real.

En un entorno por turnos, el observar al contrario se vuelve uan tarea facil dado que solo hay que obervarlo mientras no sea nuestro turno; pero en un entorno de tiempo real, se debe de observar al contrario todo el tiempo, dado que nuestro entorno cambia segundo a segundo.

Estos entornos generalmente se analizan desde la perspectica de la teoria de juegos. Si observamos los arboles de busqueda de solucion para un entorno con dos agentes jugando por turnos podemos ver que el arbol de soluciones cambia con cada juagada o movimiento del adversario.

La principal estrategia de busqueda en este tipo de entorno es la estrategia minimax, en la cual se emplean dos funciones para evaluar cada nodo, min evalua los movimientos del primer jugador y max los del segundo, el valor de cada nodo y la forma de seleccionarlos corresponden a la evaluacion de cada agente para las funciones min y max.

El principal problema con la busqueda minimax es que el numero de estados a explorar, crece de forma exponencial, la idea para solucionar este inconveniente es realizar una poda del arbol, tal y como se hacia en los metodos anteriores, a este metodo se le conoce como poda alfa-beta en este caso se guardan los valores del peor y el mejor de los casos  examinados, y para la eleccion se evaluan los nodos contra esos valores, de tal forma que podamos descartar ramas completas del arbol.

Otra tecnica interesante es el uso de transposiciones, o de una tabla de transposicion, se basa en el hecho de que dentro de un arbol de soluciones hay nodos del arbol que son iguales, o producen el mismo resultado, solo que estan alterados, lo cual implica que no es necesario analizarlos, puesto que yo hubo un analisis de un nodo identico a el.

Imagine el juego del gato, para un analisis de transposiciones es exactamente lo mismo los estados en los que un jugador toma el centro y en el siguiente turno el otro toma una esquina, no importa que esquina sea, es el mismo movimiento.

1 Comment

¿Qué estas pensando?

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Salir /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Salir /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Salir /  Cambiar )

Conectando a %s

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.