JIC : diseño y desarrollo de un bot inteligente para juegos de estrategia multijugador

Proyecto Final de Carrera JIC: Dise˜no y desarrollo de un bot inteligente para juegos de estrategia multijugador. Ingenier´ıa Inform´atica Autor: Pablo Castej´on Navarro Directora: Eva Onaind´ıa de la Rivaherrera Valencia - 28 de junio de 2011 ´ INDICE 2 ´ Indice 1. Introducci´on 4 1.1. Motivaci´on .............................. 4 1.2. Objetivos ............................... 4 1.3. Organizaci´on del documento . . . . . . . . . . . . . . . . . . . . 5 2. Diplomacy 6 2.1. Tableroyfichas ........................... 6 2.2. Fases ................................. 7 2.2.1. Primavera y Oto˜no . . . . . . . . . . . . . . . . . . . . . 7 2.2.2. Verano e Invierno . . . . . . . . . . . . . . . . . . . . . . 9 2.2.3. Findea˜no .......................... 9 2.3. Entorno DAIDE (Diplomacy AI Development Environment) . . 9 2.3.1. Sintaxis DAIDE . . . . . . . . . . . . . . . . . . . . . . . 10 2.3.2. Servidor ........................... 11 2.3.3. Bots.............................. 11 3. Fundamentos 13 3.1. Planificaci´on Distribuida . . . . . . . . . . . . . . . . . . . . . . 13 3.2. Resoluci´on de Problemas Cooperativos Distribuidos . . . . . . . 13 3.3. Planificaci´on Multi-Agente . . . . . . . . . . . . . . . . . . . . . . 15 4. JIC 20 4.1. Dise˜no................................. 20 4.2. Arquitectura ............................. 20 4.2.1. M´odulo de comunicaciones . . . . . . . . . . . . . . . . . 21 4.2.2. M´odulo de conocimiento . . . . . . . . . . . . . . . . . . 21 4.2.3. M´odulo de razonamiento . . . . . . . . . . . . . . . . . . 22 4.3. Funcionamiento............................ 22 4.3.1. Agentes individuales . . . . . . . . . . . . . . . . . . . . . 22 4.3.2. Agente coordinador . . . . . . . . . . . . . . . . . . . . . 26 4.4. Ejemplo................................ 30 5. Experimentaci´on 37 5.1. Variables ............................... 37 5.2. Torneos ................................ 37 5.2.1. JIC contra HaAI Berserk . . . . . . . . . . . . . . . . . . 37 5.2.2. JIC contra HaAI Vanilla . . . . . . . . . . . . . . . . . . 39 5.2.3. JIC contra DumbBot . . . . . . . . . . . . . . . . . . . . . 41 5.2.4. JIC contra todos . . . . . . . . . . . . . . . . . . . . . . . 42 6. Conclusiones 44 7. Trabajo futuro 44 ´ INDICE 3 8. Glosario de t´erminos utilizados en Diplomacy 45 8.1. Referente al mapa y las unidades . . . . . . . . . . . . . . . . . . 45 8.2. Referente a los movimientos y estados de les provincias . . . . . . 46 8.3. Referente a las fases del juego . . . . . . . . . . . . . . . . . . . . 47 8.4. Referente a las ordenes seg´un la fase . . . . . . . . . . . . . . . . 47 8.4.1. Movimento .......................... 47 8.4.2. Retirada............................ 47 8.4.3. Ajustes ............................ 47 Bibliograf´ıa49 1 INTRODUCCI ´ ON 4 1. Introducci´on 1.1. Motivaci´on Crear programas capaces de jugar a juegos de estrategia cl´asicos como Othello, el Ajedrez, el Risk, el Diplomacy o el Go ha sido un reto desde los comienzos de la inteligencia artificial (IA) [11]. El ajedrez, el Othello o el Backgammon se consideran resueltos en el sentido de haber conseguido programas capaces de vencer a los mejores jugadores. El inter´es en Diplomacy reside en su clasificaci´on como juego multijugador, simult´aneo, de suma cero y con capacidad para la negociaci´on entre jugadores. Esto conlleva que, para cada estado del juego, exista una ramificaci´on de posibilidades inabordable, haciendo de Diplomacy un juego extremadamente dif´ıcil de jugar y de analizar, si no es mediante t´ecnicas heur´ısticas. Por poner un ejemplo, el factor de ramificaci´on del ajedrez para el movimiento de apertura es 20 (202 = 400 movimientos para la primera ronda), mientras que para el Diplomacy hay 4.430.690.040.914.420 aperturas diferentes [11]. Estas caracter´ısticas hacen de Diplomacy el escenario id´oneo para investigar nuevos m´etodos de b´usqueda, planificaci´on, aprendizaje, negociaci´on y confianza en el campo de la IA. 1.2. Objetivos La mayor´ıa de los bots desarrollados hasta la fecha para jugar a Diplomacy utilizan m´etodos de razonamiento puramente deductivos. El objetivo de este trabajo es desarrollar un bot que, empleando m´etodos deductivos similares, sea capaz de optimizar el proceso de toma de decisiones ante un estado del juego dado, as´ı como el beneficio conjunto de las decisiones individuales sobre las posibilidades de cada unidad en juego. El bot desarrollado ser´a capaz de jugar a Diplomacy sin negociaci´on, en un modo de juego que no habr´a posibilidad de comunicarse entre jugadores ni, por tanto, de formar alianzas. Se propone una aproximaci´on desde el marco de la resoluci´on de problemas de cooperaci´on distribuida (Coperative Distributed Problem Solving - CDPS), m´as concretamente, como un problema de planificaci´on multiagente centralizado, en el que cada agente es capaz de elaborar un plan de acci´on con la informaci´on de que dispone y transmitirlo a un agente que centraliza las tareas de coordinaci´on entre los distintos agentes. As´ı pues, cada agente descentralizado se corresponder´a con una unidad del jugador. El agente dispone de la informaci´on de estado del juego, de modo que extrae la informaci´on perteneciente a su entorno inmediato y elabora un conjunto de planes de acci´on a una o m´as fases, ordenados por un valor de utilidad en funci´on del posicionamiento estrat´egico en el tablero de juego. El agente central (coordinador) es el encargado de solucionar los posibles conflictos entre los planes elaborados por cada agente individualmente. En nuestra propuesta, el coordinador, no solo soluciona los conflictos, sino que realiza una b´usqueda por el espacio de planes de los agentes para encontrar la combinaci´on que optimice la utilidad conjunta, o una aproximaci´on sub-´optima que no con- 1 INTRODUCCI ´ ON 5 lleve un tiempo de c´omputo excesivo. 1.3. Organizaci´on del documento En la secci´on 2 se hace una introducci´on al juego de mesa Diplomacy. En la secci´on 3 se presentan los fundamentos te´oricos estudiados para el desarrollo del trabajo. La secci´on 4 consiste en la explicaci´on del bot desarrollado, su dise˜no y arquitectura, as´ı como alg´un ejemplo de funcionamiento. La secci´on 5 recoge la experimentaci´on realizada para el testeo del bot. A continuaci´on se presentan secciones 6 y 7 que tratan las conclusiones y el trabajo futuro respectivamente. Y por ´ultimo, la bibliograf´ıa y el ap´endice A que consiste en un glosario de t´erminos utilizados en Diplomacy. 2 DIPLOMACY 6 2. Diplomacy Diplomacy es un juego de estrategia militar multijugador que se enmarca en la Europa de principios de siglo XX y representa a las principales potencias del momento: Rusia, Inglaterra, Alemania, Francia, Italia, Turqu´ıa y el Imperio austroh´ungaro. Cada uno de los 7 jugadores asume el rol de una de estas potencias y su objetivo es conseguir la supremac´ıa de Europa [16]. Figura 1: Tablero del juego con las fichas en su posici´on inicial. 2.1. Tablero y fichas El tablero de Diplomacy se corresponde con el mapa pol´ıtico de Europa de principios del siglo XX. El mapa se encuentra dividido en 75 provincias, 56 de tierra y 19 de mar, tal y como se puede apreciar en la figura 1. Cada provincia se compone a su vez de una o m´as regiones, pudiendo ser ´estas de dos tipos, mar´ıtimas o terrestres. Dependiendo de la configuraci´on regional de una provincia, ´esta se puede clasificar en uno de los siguientes tipos: Mar´ıtima: compuesta por una ´unica regi´on mar´ıtima. Interior: compuesta por una ´unica regi´on terrestre. Costera: compuesta por una regi´on mar´ıtima y una terrestre. Bi-costera: compuesta por una regi´on terrestre y dos regiones mar´ıtimas. Hay dos tipos de fichas, o unidades, en Diplomacy: armada y flota. Todas las unidades tienen la misma fuerza de ataque, la diferencia radica en la posibilidad de desplazamiento sobre el tablero. Las armadas s´olo pueden moverse entre regiones terrestres y las flotas s´olo entre regiones mar´ıtimas. Tan solo se permite una unidad por provincia, independientemente del n´umero de regiones que la compongan. 2 DIPLOMACY 7 De las restricciones de desplazamiento para cada tipo de unidad se deduce que las armadas no podr´an situarse en provincias mar´ıtimas, as´ı como las flotas no podr´an situarse en provincias interiores. De modo que, una unidad puede desplazarse por el tablero a las regiones adyacentes del tipo permitido para dicha unidad. La cantidad y tipo de unidades asignadas al inicio del juego a cada jugador depende de la potencia que representa. Todas las potencias tienen 3 unidades iniciales, excepto Rusia que tiene 4. Un subconjunto de las provincias del tablero permiten incrementar el n´umero de unidades del jugador, ´estas provincias se denominan centros de abastecimiento. El n´umero de centros de abastecimiento que posee un jugador es el n´umero m´aximo de unidades que puede disponer en un momento dado. Los centros de abastecimiento iniciales tienen la caracter´ıstica especial de permitir la creaci´on de nuevas unidades. El objetivo del juego es llegar a controlar, como m´ınimo, 18 centros de abastecimiento. 2.2. Fases El juego se divide en a˜nos y cada a˜no se divide en 5 fases: primavera, verano, oto˜no, invierno y fin de a˜no. Las fases de primavera y oto˜no permiten la negociaci´on previa entre jugadores antes de asignar las acciones a realizar por cada unidad. Las fases de verano, invierno y fin de a˜no son fases de ajuste del juego. En la tabla 1 se muestran las ´ordenes disponibles en cada una de estas fases. Fase del juego ´ Ordenes disponibles Primavera Mover, Defender, Apoyar movimiento, Apoyar defensa Verano Retirar, Disolver Oto˜no Mover, Defender, Apoyar movimiento, Apoyar defensa Invierno Retirar, Disolver Fin de a˜no Construir, Eliminar, Prescindir Cuadro 1: ´ Ordenes en las fases de Diplomacy 2.2.1. Primavera y Oto˜no Durante la fase de negociaci´on, los jugadores forman alianzas y llegan a acuerdos entre ellos. Estos acuerdos podr´an hacerse p´ublicos o matenerse en secreto. Los jugadores no est´an obligados a decir nada, pero una buena negociaci´on puede marcar la diferencia entre la victoria y la derrota. En esta fase la comunicaci´on y la confianza son extremadamente importantes para forjar alianzas con los oponentes y garantizar que no nos traicionar´an, as´ı como nuestra propia fiabilidad. Las unidades pueden defender su posici´on, desplazarse a una regi´on adyacente, apoyar la defensa de las unidades adyacentes en caso de ataque o apoyar 2 DIPLOMACY 8 el ataque a una provincia adyacente. Adem´as, las flotas pueden transportar armadas desde una provincia costera a otra formando una cadena que se llama convoy. Despu´es del per´ıodo de negociaci´on, los jugadores escriben ´ordenes secretas para cada unidad, estas ´ordenes se revelan y se ejecutan de forma simult´anea. Las posibles ´ordenes son: Hold (defender) : La acci´on hold(U,R) indica que la unidad U desea permanecer en la regi´on R. Esta acci´on tendr´a ´exito si ninguna otra unidad ataca, o si en el ataque, el n´umero de unidades apoyando la defensa es mayor o igual al n´umero de unidades apoyando el ataque. Move (mover o atacar) : La acci´on move(U,R1,R2)indica que la unidad U que ocupa la regi´on R1quiere moverse a o atacar la provincia que contiene la regi´on R2. Dependiendo de si la provincia est´a libre o no, se considerar´a un simple movimiento o un ataque a otra unidad. Mover: Esta acci´on puede no tener ´exito en caso de que m´as de una unidad quiera desplazarse a R2, en dicho caso la unidad que cuente con mayor n´umero de apoyos se desplazar´a a R2. Si las unidades implicadas en el conflicto de desplazamiento reciben el mismo n´umero de apoyos, ninguna de ellas tiene ´exito en su acci´on, permanecen en las regiones donde se encuentran y la regi´on se marca como punto muerto (standoff). Atacar: Si la provincia de destino est´a ocupada por otra unidad U2, se diferencian dos casos. Si U2se mueve con ´exito a otra posici´on, el proceso que se sigue es el mismo que en el caso de mover. Si la unidad U2defiende la provincia, ganar´a la batalla aquella unidad que cuente con mayor n´umero de apoyos. Si U2pierde la batalla, queda desplazada y su situaci´on se resolver´a en la siguiente fase de retirada. Support Hold (apoyar defensa) : La acci´on suphold(U1,R1,U2,R2)indica que la unidad U1situada en la regi´on R1apoya a la unidad U2en su acci´on de defender R2. R1debe ser adyacente a alguna de las regiones contenidas en la provincia a la que pertenece R2. Support Move (apoyar movimiento) : La acci´on supmov(U1,R1,U2,R2,R3) indica que la unidad U1 situada en R1 apoya a la unidad U2 en su movimiento de R2 a R3. R1debe ser adyacente a alguna de las regiones contenidas en la provincia a la que pertenece R3. Si una unidad de apoyo es atacada su apoyo se anula, lo que permite que las unidades afecten el resultado de los conflictos en las regiones no directamente adyacentes. 2 DIPLOMACY 9 2.2.2. Verano e Invierno En esta fase s´olo los jugadores con unidades desplazadas en la batalla, escriben una orden para cada una de sus unidades vencidas. Las ´ordenes posibles son: Retreat (retirada) : La unidad desplazada debe retirarse a otra provincia que no est´e ocupada y que no sea la posici´on que dej´o vacante la unidad que le atac´o. Disband (disolver) : Si no hay ninguna posici´on factible donde una unidad desplazada pueda retirarse, la unidad se disuelve. Si dos unidades se retiran a una misma posici´on, ambas son disueltas. El jugador puede elegir disolver una unidad en vez de retirarla. 2.2.3. Fin de a˜no Despu´es de cada fase de invierno, los centros de abastecimiento reci´en adquiridos se convierten en propiedad del jugador que los ocupa, y se recalcula el total de centros de abastecimiento de cada potencia. Los jugadores con menos centros de abastecimiento que unidades en el tablero deben eliminar unidades, mientras que los jugadores con m´as centros de abastecimiento que unidades en el tablero tienen derecho a construir unidades en sus centros de abastecimiento iniciales, siempre que est´en libres. Los jugadores que pierden e control sobre todos los centros de abastecimiento son eliminados del juego, y un jugador se declara el ganador cuando llega a controlar 18 o m´as de los 34 centros de abastecimiento. Los jugadores tambi´en podr´an acordar un empate, lo que ocurre cuando se producen estancamientos. Las ´ordenes de ajuste son: Build (construir) : Se crea una unidad nueva en una de las regiones de entre los centros de abastecimiento iniciales que se encuentre libre. Remove (eliminar) : Se elimina la unidad elegida. Waive (prescindir) : No se hace nada. Los jugadores hacen p´ublicas sus ´ordenes en cada una de las fases simult´aneamente. Si durante la resoluci´on de alguna de las fases de movimiento ninguna unidad es expulsada de su posici´on, la siguiente fase de retirada se salta, ya que no queda nada por hacer en ella. Para m´as informaci´on acerca de las reglas de juego se puede consultar, ”The rules of Diplomacy” [1]. 2.3. Entorno DAIDE (Diplomacy AI Development Environment) En enero de 2002, un grupo de programadores se unieron para desarrollar un entorno en el que varios bots dise˜nados para jugar a Diplomacy pudieran competir. A este entorno se le llam´o Diplomacy AI Development Environment 3 FUNDAMENTOS 16 Algoritmo 1 REFINAR(P, Π) 1: Entrada: Un plan parcial Py el problema Π 2: Salida: Un candidato m´ınimo de Pque es soluci´on para Πo “fallo“. 3: 4: if un candidato m´ınimo c de Pes una soluci´on para Πthen 5: return c 6: else 7: resultado := fallo 8: seleccionar una estrategia de refinamiento R 9: PP := R(P) 10: while PP 6=∅yresultado = fallo do 11: seleccionar un elemento Pide PP de forma no determinista 12: PP := PP \{Pi} 13: resultado := REFINAR(Pi,Π) 14: end while 15: return resultado 16: end if En el ´ambito de los sistemas multi-agente, no solo la planificaci´on es importante4, sino que la coordinaci´on tiene un papel clave para evitar conflictos entre dichos planes. El problema de planificaci´on multi-agente de define como: Dada una descripci´on del estado inicial, un conjunto de objetivos globales, un conjunto (al menos dos) de agentes, y para cada agente un conjunto de sus capacidades y sus objetivos privados, encontrar un plan para cada agente que consiga sus objetivos privados, de modo que dichos planes conjuntamente est´en coordinados y se alcancen los objetivos globales [3]. La resoluci´on de los problemas multi-agente se puede estructurar del siguiente modo: 1.- Refinar los objetivos globales o tareas en subtareas que puedan ser asignadas a agentes individuales. 2.- Asignar las subtareas a los agentes. 3.- Definir reglas o restricciones que prevengan a los agentes de producir planes conflictivos. 4.- Para cada agente: hacer un plan para conseguir sus objetivos. 5.- Coordinar los planes individuales de los agentes. 6.- Ejecutar los planes y sintetizar los resultados de las subtareas. Entre las distintas aproximaciones existentes al problema de la coordinaci´on en planificaci´on multi-agente encontramos: 4Cada agente individual puede realizar sus propios planes 3 FUNDAMENTOS 17 Coordinaci´on mediante filtrado [7] distingue dos aproximaciones a la coordinaci´on multi-agente. (1) Coordinaci´on expl´ıcita incluye agentes razonando sobre sus interacciones y negociaciones. Un problema con la coordinaci´on expl´ıcita es que puede consumir demasiado tiempo, lo que no resulta pr´actico en dominios altamente din´amicos. (2) Con coordinaci´on impl´ıcita, los agentes siguen reglas locales de comportamiento que garantizan que los agentes pueden actuar sin preocuparse por interferencias de otros agentes. Filtrado multi-agente es una extensi´on del filtrado individual de agentes que fue una estrategia dise˜nada para agentes en entornos din´amicos. Un agente usando un filtro individual establece una serie de objetivos. Debido a los cambios en el entorno, surgen oportunidades de tomar acciones adicionales o alternativas. Una estrategia de filtrado elimina las opciones que son incompatibles con el objetivo actual del agente. Una estrategia de filtrado multi-agente evita las opciones que son incompatibles con los objetivos de otros agentes. Las estrategias de filtrado se pueden aumentar con un mecanismo de anulaci´on. Los mecanismos de anulaci´on se basan en un valor umbral. Un agente audaz no tendr´a en cuenta muchas nuevas opciones (tendr´a un umbral alto), un agente cauteloso tendr´a un valor umbral bajo. En [8] los autores identifican una ´unica situaci´on de conflicto en su dominio, el tileworld multi-agente. En el ´ambito de tileworld, hay un mapa (malla) que est´a lleno de azulejos. Objetos (agujeros, baldosas, obst´aculos, etc) aparecen y desaparecen din´amicamente y los agentes reciben bonificaciones por tapar los agujeros con azulejos. Una estrategia de filtrado, el filtrado est´atico geogr´afico, se basa en la ubicaci´on de los agentes y de los agujeros. Se asigna a los agentes porciones no solapadas del mapa y filtran las opciones de los agujeros rellenos que no est´an en su regi´on. Usando la estrategia de filtrado publicaci´on de intenciones, los agentes deben poner en una pizarra su intenci´on de llenar un hueco. Los agentes evitan opciones de llenar agujeros que otro agente tiene intenci´on de llenar. Planificaci´on Global Parcial Generalizada En la Planificaci´on Global Parcial (PGP) [6] los agentes cooperan debido a que ninguno dispone de la informaci´on completa. PGP supone un CDPS , donde los agentes est´an dispuestos a ayudarse unos a otros sin ning´un tipo de compensaci´on. Para los entornos de CDPS, Durfee y Lesser identificar cuatro categor´ıas de t´ecnicas de coordinaci´on, que se engloban en PGP. 1.- Contrataci´on. El proceso de resoluci´on distribuido se contempla como un gran proceso y muchos solucionadores potenciales, como en computaci´on paralela. El objetivo de la coordinaci´on es utilizar los solucionadores de problemas hasta el extremo. 3 FUNDAMENTOS 18 2.- Intercambio de resultados. El intercambio de resultados se centra en ´areas donde las tareas son inherentemente distribuidas, pero los problemas derivados de un agente pueden estar relacionados con los problemas derivados de otros agentes. 3.- Organizaci´on. El conocimiento de la organizaci´on como, por ejemplo, los roles de los agentes y las responsabilidades pueden ayudar a los agentes a decidir qu´e tipo de informaci´on comunicar a qu´e agentes. 4.- Planificaci´on. La planificaci´on tradicional de la inteligencia artificial distribuida se ha centrado en evitar conflictos de recursos. Si los agentes pueden actuar de forma independiente, la atenci´on se centra en la cooperaci´on. PGP est´a orientada a un tipo particular de dominio multi-agente, el de las redes de sensores distribuidos. En su art´ıculo, una red distribuida de sensores ac´usticos monitorizando el movimiento de los veh´ıculos se utiliza como ejemplo en funcionamiento. El objetivo de esta red es ofrecer una visi´on coherente de los movimientos del veh´ıculo. Con el fin de hacerlo, los agentes deben interpretar los datos del sensor. Debido a que hay demasiados datos (en particular hay demasiado ruido), analizar exhaustivamente las entradas del sensor no es pr´actico. Por el intercambio de informaci´on, es posible interpretar los datos de forma precisa y oportuna. M´as concretamente, las t´ecnicas de coordinaci´on de redes de sensores distribuidos permiten a los agentes: (1) instruir (o proponer) a otros agentes para recoger datos espec´ıficos (por ejemplo, controlar un cierto camino),(2) determinar qu´e informaci´on enviar, a qui´en y cu´ando y (3) cooperar de otras maneras, por ejemplo, un agente que no tiene datos propios para interpretar se puede poner a trabajar en el an´alisis de los datos de otros agentes. Las redes de sensores din´amicas son entornos altamente din´amicos y se utilizan diferentes t´ecnicas de coordinaci´on PGP en diferentes circunstancias. Sin embargo, si se pretende que el medio es est´atico, entonces las siguientes 4 t´ecnicas se usan sucesivamente: 1.- Planificaci´on local. Un agente hace planes para todas las interpretaciones posibles de sus datos. 2.- Comunicaci´on con otros agentes. Para saber qu´e informaci´on enviar a qui´en y cu´ando, PGP utiliza dos tipos de organizaciones. La organizaci´on de nivel de tareas define las funciones y responsabilidades de los agentes con respecto a la realizaci´on de tareas. La organizaci´on de meta-nivel define los roles de autoridad, es decir, algunos agentes pueden dar ´ordenes a otros agentes. 3.- Iniciando un Plan Global Parcial. Para integrar los planes de otros agentes con su propio plan, un agente tratar´a de relacionar los objetivos de un plan con los objetivos de otro agente. Los objetivos pueden estar relacionados de varias maneras. 4.- Modificar PGPs. Si los agentes han recibido o construido un plan global parcial, pueden tratar de mejorarlo usando t´ecnicas tales como la redistribuci´on de tareas y el reordenamiento de tareas. Mediante el env´ıo de un PGP a otros agentes, el agente propone este plan 3 FUNDAMENTOS 19 a los otros agentes. Los dem´as agentes pueden aceptar los papeles indicados para ellos en el PGP , pueden rechazarlo o enviar una contrapropuesta en forma de PGP modificado. En el entorno TAEMS (Task Analysis, Environment Modeling, and Simulation), las tareas pueden estar compuestas de subtareas, formando una jerarqu´ıa con un nodo ra´ız llamado grupo de trabajo. Varios grupos de trabajo pueden coexistir. Para evaluar el desempe˜no de una tarea, dos caracter´ısticas son importantes, el tiempo transcurrido y la calidad de la ejecuci´on de la tarea. Un agente tiene creencias, cree la parte de la estructura de la tarea global que puede ver. Los agentes pueden comprometerse a realizar las tareas de otros agentes. Cada agente tiene un planificador local que planifica los recursos computacionales del agente, es decir, el planificador determina las tareas que un agente ejecutar´a y cu´ando. El prop´osito de los mecanismos de coordinaci´on es asegurar que el planificador local cuenta con la mejor entrada posible que permita la construcci´on de un programa de gran utilidad. En otras palabras, los mecanismos de coordinaci´on se utilizan para permitir que un agente haga un buen plan. Fusionado de planes usando un formalismo El punto de partida en [4] es que hay dos agentes que tienen planes que se pueden ejecutar sin tener en cuenta los planes del otro agente. En otras palabras, los agentes pueden llevar a cabo sus planes sin necesidad de coordinaci´on. Sin embargo, mediante la cooperaci´on de los agentes se encuentran los planes m´as eficientes. Una l´ogica de recursos se utiliza para representar los planes y acciones. La situaci´on objetivo es disponer de un conjunto de recursos de un tipo de recurso en particular. La situaci´on inicial es tambi´en un conjunto de recursos. Los agentes pueden realizar acciones, llamadas capacidades, que consumen recursos y producen recursos. Un plan puede ser representado como un grafo dirigido ac´ıclico, donde los v´ertices son los recursos y las capacidades y los arcos de conectan los recursos con capacidades, para indicar una relaci´on de consumo o de producci´on. Un plan puede producir m´as recursos de lo necesario, si (i) las capacidades producen recursos que no son utilizados por las capacidades posteriores en el plan y los recursos no son necesarios para la meta, o si (ii) los recursos se encuentran presentes en la situaci´on inicial. Estos recursos no utilizados se pueden considerar efectos colaterales de un plan. Otros agentes pueden ser capaces de utilizar estos recursos no utilizados. Aunque todos los agentes ya tienen todos los recursos que necesitan para su plan, mediante la compra de recursos de otros agentes, no es necesario que los produzcan por s´ı mismos. M´as precisamente, si un agente puede comprar todos los recursos ´utiles que una capacidad produce, entonces esa capacidad puede ser eliminada del plan. La eliminaci´on de una capacidad, a su vez, libera los recursos que se han consumido con anterioridad por la capacidad eliminada, lo que abre posibilidades para el comercio de m´as recursos. 4 JIC 20 4. JIC La Conquista de Valencia por el rey Jaime I, a diferencia de la de Mallorca, fue hecha con un importante contingente de aragoneses. De hecho, en 1231, Jaime I se reuni´o con el noble Blasco de Alag´on y el maestre de la Orden Militar del Hospital en Alca˜niz para fijar un plan de conquista de las tierras valencianas. Blasco de Alag´on recomend´o asediar las poblaciones en terreno llano y evitar las fortificadas. Sin embargo, lo primero que se tom´o fueron dos enclaves monta˜nosos: Morella, aprovechando Blasco la debilidad de su gobierno musulm´an; y Ares, lugar cercano a Morella tomado por Jaime I para obligar a Blasco de Alag´on a que le entregara Morella. La conquista de lo que posteriormente se convertir´ıa en el reino de Valencia comienza en 1232, con la toma de Morella [19]. JIC es el acr´onimo de Jaime I el Conquistador, el nombre designado para el bot desarrollado. JIC est´a implementado en Java sobre la estructura Player del paquete dip aportado por ` Angels Fabregues [9]. El paquete incluye el m´odulo de comunicaci´on con el servidor del juego y el modelo del mundo, lo que permite al desarrollador centrarse ´unicamente en la l´ogica de razonamiento del bot. 4.1. Dise˜no Como se coment´o en la secci´on 1.2, JIC pretende ser un bot capaz de jugar al juego Diplomacy sin negociaci´on, por lo que el grado de inteligencia para elaborar estrategias contando ´unicamente con las unidades propias del jugador, es lo que determinar´a cu´an bueno es en comparaci´on con otros bots existentes (2.3.3). 4.2. Arquitectura La arquitectura de JIC est´a organizada en tres m´odulos. Un m´odulo de comunicaciones dip que permite la comunicaci´on con el servidor de juego. Un m´odulo de conocimiento que est´a compuesto por dos bloques, el modelo del mundo generado por dip, en el que los agentes individuales y el agente coordinador pueden consultar el estado del juego, y una memoria que almacena la acci´on coordinada seleccionada por el coordinador en la fase de juego anterior a la actual. Y por ´ultimo, un m´odulo de razonamiento, que re´une los agentes individuales encargados de realizar planes individuales atendiendo a sus propios objetivos y un agente coordinador que resuelve las incoherencias entre los planes individuales y realiza la coordinaci´on de dichos planes que optimice la consecuci´on del objetivo global. La figura 2 muestra la arquitectura de JIC donde se pueden ver los tres m´odulos principales con sus componentes y las v´ıas de comunicaci´on entre ellos. 4 JIC 21 Figura 2: Arquitectura de JIC. 4.2.1. M´odulo de comunicaciones El m´odulo de comunicaciones se encargar´a de comunicarse con el servidor del juego, actualizando el modelo del mundo con la informaci´on recibida del servidor y enviando al servidor las decisiones tomadas por JIC. 4.2.2. M´odulo de conocimiento El m´odulo de conocimiento est´a compuesto por un modelo del mundo generado por dip y por una memoria de la fase anterior. El modelo del mundo contiene toda la informaci´on est´atica del tablero (la composici´on de las provincias y la adyacencia entre regiones), as´ı como la informaci´on din´amica actual del estado del juego (fase actual, situaci´on de las unidades militares y la posesi´on de centros de abastecimiento) La memoria almacena la acci´on coordinada que JIC ha seleccionado en la fase anterior de modo que se pueda emplear, en caso de interbloqueos con las acciones de otras potencias5, para obtener una acci´on coordinada sub´optima aplicando un algortimo pseudoaleatorio. Esta funcionalidad se explica m´as en detalle en el apartado fases de interbloqueo de la secci´on 4.3.2. 5Un interbloqueo se produce cuando las acciones de dos o m´as potencias persiguen los mismos objetivos sucesivamente sin ´exito, debido al equilibrio de las fuerzas que intervienen en las acciones de los agentes. 4 JIC 22 4.2.3. M´odulo de razonamiento El m´odulo de razonamiento se ha modelizado como un sistema de planificaci´on multi-agente con un agente coordinador, sin llegar a dise˜nar protocolos de comunicaciones. Dada la naturaleza de la informaci´on que se intercambia, no es necesario establecer un protocolo de comunicaci´on. Cada unidad propia del jugador se corresponde con un agente individual capaz de extraer la informaci´on necesaria del modelo del mundo y elaborar un conjunto de planes individuales. Cada agente podr´a tener en cuenta las acciones individuales del resto de agentes en la elaboraci´on de dichos planes. De la evaluaci´on de los soportes se encargar´a el agente centralizado. Una vez elaborados los planes de acci´on para el estado de juego actual, ´estos se env´ıan al agente coordinador. El agente coordinador es un agente central que recibe los planes de cada agente individual y genera la acci´on coordinada que ser´a enviada al servidor de juego. La forma en que el coordinador genera la acci´on coordinada depende de lo avanzado del estado del juego. Principalmente se encarga de resolver los posibles conflictos entre los planes propuestos por los agentes individuales y asignar soportes para optimizar el valor de utilidad de la acci´on coordinada frente a los valores de utilidad de los planes individuales. 4.3. Funcionamiento Para entender el funcionamiento de JIC hay que profundizar en el razonamiento que realizan tanto los agentes individuales como el agente coordinador. Los agentes individuales realizan fundamentalmente 3 funciones: (1) consultan el estado del juego en el m´odulo de conocimiento para determinar las acciones que pueden llevar a cabo, (2) eval´ua la utilidad de cada acci´on seg´un unos criterios geogr´aficos y (3) traza una serie de planes individuales que comunica al agente coordinador. Dependiendo del estado del juego y de los planes individuales que los agentes individuales propongan, el agente coordinador emplear´a un m´etodo diferente para seleccionar la acci´on coordinada: (1) una b´usqueda completa por el espacio de planes, (2) b´usquedas completas en subconjuntos de planes, (3) selecci´on de los mejores planes individuales y resoluci´on de conflictos o (4) generaci´on pseudoaleatoria sobre una acci´on coordinada anterior. 4.3.1. Agentes individuales Cada agente individual recibe la informaci´on del estado del juego, de la cual extrae la informaci´on relevante para el trazado del plan individual, ya sea a 1 fase o a m´as largo plazo. Esta informaci´on se compone de la provincia en la cual se encuentra situado el agente, las provincias adyacentes hasta 2 niveles, las regiones de qu´e est´an compuestas y las unidades aliadas y enemigas que pueda haber situadas en dichas provincias. A este conjunto de informaci´on lo denominaremos juego local. 4 JIC 23 El resultado del razonamiento de un agente individual es un conjunto de planes individuales ordenados seg´un un valor de utilidad estrat´egico. Asimismo, se determina las unidades aliadas y enemigas que pueden intervenir en el ´exito de cada plan. En primer lugar, una vez el agente dispone de la informaci´on del estado del juego local en el que se encuentra, genera una lista con todas las posibles acciones que puede llevar a cabo individualmente, es decir, defender la posici´on actual y los movimientos a cada una de las provincias adyacentes a su posici´on. La utilidad estrat´egica de una acci´on se obtiene mediante la aplicaci´on de un razonamiento deductivo como un valor de posicionamiento geogr´afico dentro del juego local. Como se coment´o en la secci´on 2.1, hay diferentes tipos de provincias en cuanto a transitabilidad (tierra/mar) y en cuanto a objetivos (centros de abastecimiento). Para la obtenci´on del valor de utilidad se tienen en cuenta dos criterios: Tipo de provincia de destino Es un valor relacionado con las provincias objetivo, de modo que se favorece m´as aquellas acciones que tengan como destino centros de abastecimiento frente a aquellas que no. Pero a su vez se diferencia entre tipos de centros de abastecimiento, pues no es igual desplazarse a uno propio, que a uno enemigo o a uno neutro, as´ı como el hecho de que sea un centro de abastecimiento inicial de alguna potencia. Los valores asignados se pueden consultar en la tabla 3. Tipo de provincia Valor Centro de abastecimiento inicial enemigo 2.5 Centro de abastecimiento libre 2.5 Centro de abastecimiento inicial propio 2 Centro de abastecimiento 2 Provincia normal 1 Cuadro 3: Valor geogr´afico por tipo de provincia Tipo de provincias adyacentes al destino Este valor se relaciona tanto con la transitabilidad como con los objetivos. Se trata de maximizar la relaci´on entre conectividad y objetivos futuros, ya que las provincias adyacentes al destino de la acci´on actual son objetivos potenciales a conseguir en la siguiente fase del juego. El valor se obtiene mediante el sumatorio de la ponderaci´on del n´umero de provincias de cada tipo. Los valores de ponderaci´on se indican en la tabla 4. Tipo de provincia Valor Centro de abastecimiento enemigo 1 Centro de abastecimiento libre 0.5 Centro de abastecimiento propio 0.25 Provincia normal 0.01 Cuadro 4: Valores de ponderaci´on por tipo de provincias adyacentes 4 JIC 24 As´ı pues, el valor de utilidad de una acci´on, es el resultado de la suma de estos dos valores geogr´aficos multiplicado por 100 para situarlo en una escala m´as adecuada. A la vez que se calcula el valor de utilidad para una acci´on, se obtiene tambi´en el n´umero de aliados y de enemigos que pueden intervenir en el ´exito de dicha acci´on. Tras la obtenci´on de los valores de utilidad de cada una de las acciones posibles para el agente, se obtiene la lista de planes a seguir seg´un el estado actual del juego local. Estos planes estar´an formados por una ´unica acci´on que puede perseguir objetivos a una fase (acciones) inmediatas, a 2 fases (objetivos a final de a˜no) o bien a m´as largo plazo. Podemos diferenciar tres objetivos generales siendo unos m´as prioritarios que otros: Defensivos Son aquellas acciones que llevan a un agente a recuperar o evitar la p´erdida de un centro de abastecimiento. Desde un punto inicial del juego, son los objetivos prioritarios, pues se identifican con la supervivencia de la potencia. Ofensivos Son acciones que conducen a la obtenci´on de centros de abastecimiento, ya sea inmediata o postergadamente. Estos objetivos son los que permiten la expansi´on y crecimiento de tropas. T´acticos Son acciones de desplazamiento de los agentes para la consecuci´on de objetivos a m´as largo plazo. Haciendo un an´alisis m´as exhaustivo del tipo de acciones que se corresponden con cada uno de estos objetivos, podemos identificar objetivos espec´ıficos y que servir´an para determinar los posibles planes de acci´on del agente: Recuperar centro de abastecimiento inicial . Dentro del conjunto de objetivos defensivos, este es el m´as cr´ıtico, puesto que supone la p´erdida de uno de los centros en los que podemos crear nuevas unidades. Recuperar centro de abastecimiento en Oto˜no . Este objetivo defensivo persigue prevenir la p´erdida de un centro de abastecimiento que se encuentre ocupado en la fase de FAL, de modo que no se tenga que disolver una unidad a final de a˜no. Obtener centro de abastecimiento . Este es el objetivo ofensivo m´as importante, pues se supone la ocupaci´on de un centro de abastecimiento, que no nos pertenece, en Oto˜no y se pretende defender la posici´on para adherir el territorio a final de a˜no. Desplazarse a centro de abastecimiento . Son acciones que periguen el desplazamiento en primavera a centros de abastecimiento que no nos pertenecen para su obtenci´on en oto˜no. Se pueden identificar como planes a 2 fases. Desbloquear unidad . Si se da el caso que un agente se encuentre totalmente rodeado de unidades aliadas, se considera la probabilidad de realizar un desplazamiento exitoso de cada una de estas unidades junto con el valor de utilidad de las acciones que conducen a las provincias en que se envuentran. Este es el primer caso de objetivo t´actico a tener en cuenta. 4 JIC 25 Desplazarse a primera l´ınea . Si el juego se desarrolla favorablemente, las tropas aliadas se ir´an alejando de los centros de abastecimiento iniciales, de modo que los juegos locales de los nuevos agentes creados no tendr´an ninguna informaci´on ´util para el trazado de planes. En este caso se requiere de m´as informaci´on, de manera que se pueda determinar de entre todas las acciones de desplazamiento que puede realizar el agente, cu´ales conducen al enemigo m´as cercano en menos fases. En primer lugar se determina la distancia al enemigo m´as cercano mediante el algoritmo 2 que equivale a una b´usqueda en anchura, y posteriormente se trazan aquellas rutas que llegan al enemigo/s m´as cercano, de modo que se mantendr´an aquellas acciones de desplazamiento que no incrementen el coste de llegar al enemigo. Atacar enemigo si la unidad se encuentra en primera linea de ataque y no puede perseguir ninguno de los objetivos anteriores, entonces se trata de desplazar al enemigo adyacente, asumiendo que puede estar bloqueando el acceso a centros de abastecimiento ajenos. Algoritmo 2 Distancia a primera linea 1: distance = 0 2: enemy find = false 3: open = provincias adyacentes(unit.province) 4: while !enemy find ∨n<20 do 5: next open.clear() 6: while open ! = ∅do 7: if open.first().containsEnemy() then 8: enemy find = true 9: break 10: else if !open.first().containsAllied() then 11: next open.add(provincias adyacentes(open.first)) 12: end if 13: open.removeFirst() 14: end while 15: if !enemy find then 16: distance++ 17: open = next open 18: end if 19: end while 20: return distance Objetivo espec´ıfico Identificador Recuperar centro de abastecimiento inicial 1 Recuperar centro de abastecimiento en Oto˜no 2 Obtener centro de abastecimiento 3 Desplazarse a centro de abastecimiento 4 Desbloquear unidad 5 Desplazarse a primera l´ınea 6 Atacar enemigo 7 Sin plan 10 Cuadro 5: C´odigos de identificaci´on de los planes de acci´on 4 JIC 32 El agente coordinador recibe los planes de cada agente individual y los inserta en una tabla como la de la figura 10. Los identificadores de acciones hacen referencia al n´umero de acci´on disponible para el agente individual con el identificador asociado. Los identificadores de acciones pueden ser desde 0 hasta el n´umero de acciones dicponibles para el agente, as´ı la acci´on 4 para SMY es Mover a ARM. ID agente ID acci´on utilidad Enemigo m´ax aliados ID plan CON 1 351 0 0 4 SMY 4 251 1 1 6 ANK 1 351 1 0 6 ANK 2 226 1 1 6 Cuadro 10: Base de datos de planes individuales en el agente coordinador. Con estos planes individuales el agente coordinador realiza toda la combinatoria posible sin soportes, lo que resulta en 2 combinaciones: Combinaci´on 1 Combinaci´on 2 Mover CON a BUL Mover CON a BUL Mover SMY a ARM Mover SMY a ARM Mover ANK a BLA Mover ANK a ARM Con la generaci´on de soportes surgen dos nuevas acciones coordinadas posibles: Combinaci´on 3 Combinaci´on 4 Mover CON a BUL Mover CON a BUL Mover SMY a ARM SMY apoya a ANK ANK apoya a SMY Mover ANK a ARM De las 4 combinaciones generadas, la combinaci´on 2 no cumple las restricciones 7, por lo que es eliminada. A continuaci´on se eval´ua el valor de utilidad de cada acci´on coordinada y se selecciona la acci´on coordinada ´optima. En este caso, el agente coordinador ha determinado que la Combinaci´on 3 es la mejor opci´on con un valor de utilidad coordinada de 1427 y tipos de planes 96. Finalmente el agente coordinador env´ıa la acci´on coordinada al servidor del juego. Tras la ejecuci´on de las acciones de cada potencia el estado del juego es como se muestra en la figura 6. En la imagen se puede apreciar que las acciones de los tres agentes han sido satisfactorias, consiguiendo, en caso de los desplazamientos, llegar a sus objetivos. Nuevamente se ejecuta el proceso de razonamiento por parte de los agentes individuales y el agente coordinador teniendo como resultado el plan coordinado siguiente: Defender BUL Mover ANK a BLA Mover ARM a SEV 6Este valor se determina sumando el identificador de cada plan de la acci´on coordinada previa inversi´on en la escala de identificadores de modo que los identificadores m´as bajos supongan valores m´as altos. En el caso de los soportes se toma el identificador de la acci´on soportada 4 JIC 33 En este caso la acci´on de Bulgaria es de tipo 3, que persigue consolidar la adhesi´on del centro de abastecimiento para poder crear una nueva unidad al final del a˜no. Figura 5: Oto˜no de 1901. Avanzando un poco hasta el oto˜no de 1905, vemos como JIC comienza a expandirse tratando de no dejar huecos entre sus filas de modo que ning´un enemigo pueda penetrar en la zona pr´oxima a sus centros de abastecimiento iniciales. En esta fase se consigue mediante la acci´on coordinada de Ruman´ıa y Bulgaria el desplazamiento a Serbia la que a final de a˜no pasar´a a formar parte del territorio de JIC. Figura 6: Oto˜no de 1905. 4 JIC 34 Durante las sucesivas fases se ha tratado de favorecer con las acciones de Inglaterra el avance de Turqu´ıa para llegar a una situaci´on de interbloqueo. (a) Primavera de 1916 (b) Oto˜no de 1916 (c) Oto˜no de 1919 (d) Oto˜no de 1921 (e) Primavera de 1924 (f) Oto˜no de 1924 (g) Primavera de 1925 (h) Oto˜no de 1925 Figura 7: Secuencia de fases hasta el interbloqueo. 4 JIC 35 Llegados a este punto, la primavera del 1926, Turqu´ıa dispone de 17 centros de abastecimiento, Inglaterra de 16 y de las restantes potencias tan solo permanece Italia con un centro de abastecimiento. Desde que Turqu´ıa consigui´o 8 centros de abastecimiento en el a˜no 1912, el agente coordinador est´a utilizando el m´etodo de las particiones de planes individuales. En la situaci´on actual, los planes individuales que se insertan en la primera partici´on, los de mayor inter´es, son los de las unidades situadas en el Mar J´onico (ION), M´unich (MUN), Silesia (SIL) y Mosc´u (MOS), todas ellas con planes de tipo 4. Tras la evaluaci´on de las posibles acciones coordinadas, el agente coordinador env´ıa al servidor la acci´on coordinada: Mover ION a TUN Mover MUN a KIE Mover SIL a BER Mover MOS a STP ... 7 Figura 8: Primavera de 1926. Las unidades de Inglaterra son flotas en su totalidad, por lo que no pueden penetrar en provincias terrestres, lo mejor que pueden hacer es permanecer en sus posiciones costeras defendiendo los centros de abastecimiento. Dado que estas acciones han fallado, en la siguiente fase el agente coordinador las recupera de la memoria y realiza una variaci´on en la acci´on de M´unich para que apoye la acci´on de Silesia, consiguiendo de este modo desplazar a la unidad de Inglaterra de la provincia de Berl´ın, solucionando el interbloqueo y ganando la partida. Figura 9: Oto˜no de 1926. 5 EXPERIMENTACI ´ ON 36 5. Experimentaci´on 5.1. Variables Para la realizaci´on de los experimentos se han tenido que asignar valores a ciertas variables que determinan el comportamiento de JIC. Estos valores se pueden consultar en la tabla 11. N´umero m´aximo de acciones sin plan permitidas por unidad 2 N´umero m´aximo de unidades en fases iniciales 7 N´umero m´aximo de unidades con el mismo tipo de plan en un subconjunto 8 Valor m´aximo de incremento de la utilidad de los soportes 500 Porcentaje de unidades en interbloqueo que deben variar su acci´on 0.3 Cuadro 11: Variables de JIC 5.2. Torneos Se han realizado una serie de torneos a 100 partidas variando el tipo y n´umero de los bots participantes para obtener una visi´on general de la efectividad del bot desarrollado. 5.2.1. JIC contra HaAI Berserk En un primer torneo hemos enfrentado a 3 bots de tipo JIC contra 4 bots de tipo HaAI. La versi´on de HaAI empleada es la Berserk, que se corresponde con un comportamiento m´as agresivo del bot. Los resultados se pueden observar en la tablas 12 y 13 Potencia Jugado Ganado Sobrevivido Eliminado Rusia 38 0 16 22 Alemania 47 7 17 23 Austria 44 4 20 20 Turqu´ıa 49 27 15 7 Francia 42 13 24 5 Inglaterra 33 2 22 9 Italia 47 6 16 25 Cuadro 12: Resultados por potencia de JIC Potencia Jugado Ganado Sobrevivido Eliminado Rusia 62 2 30 30 Alemania 53 1 22 30 Austria 56 3 13 40 Turqu´ıa 51 3 39 9 Francia 58 15 35 8 Inglaterra 67 9 52 6 Italia 53 5 27 21 Cuadro 13: Resultados por potencia de HaAI Berserk 5 EXPERIMENTACI ´ ON 37 Potencia Victoria Supervivencia Victoria Supervivencia JIC JIC HaAI HaAI Rusia 0 % 42 % 3 % 50 % Alemania 15 % 43 % 2 % 42 % Austria 9 % 50 % 5 % 25 % Turqu´ıa 55 % 68 % 6 % 81 % Francia 31 % 83 % 26 % 81 % Inglaterra 6 % 71 % 13 % 90 % Italia 13 % 39 % 9 % 56 % Cuadro 14: Estad´ısticas por potencia contra HaAI Berserk Para el c´alculo de los porcentajes de supervivencia se han descontado las partidas ganadas, por lo que el complementario del porcentaje hace referencia a aquellas partidas en que la potencia ha sido eliminada. De la tabla 14 hay que destacar 3 cosas. (1) La primera es el elevado factor de partidas ganadas por JIC cuando ha desempe˜nado el papel de Turqu´ıa, no s´olo destaca sobre las ganancias con las otras potencias, sino que tambi´en presenta un margen considerable con los resultados de HaAI. (2) JIC presenta mejores resultados en general con Italia, Francia, Turqu´ıa y Alemania, mientras que las potencias destacables de HaAI son Francia e Inglaterra. (3) A pesar de valores notorios de supervivencia, JIC presenta una menor capacidad de supervivencia en general. Sin embargo, como se puede apreciar en la tabla 15, el n´umero promedio de unidades de JIC que sobreviven al final de las partidas es mayor en algunos casos. El caso de Turqu´ıa nuevamente sobresale sobre los dem´as, indicando que muchas de las partidas iban camino de convertirse en victorias para JIC. Inglaterra tiene la desventaja de tener que acceder al Mar Mediterr´aneo para alcanzar la victoria, en caso contrario solo puede alcanzar un total de 14 centros de abastecimiento. De modo que los valores mostrados sugieren el dominio total de la costa nor-occidental del mapa por parte de Inglaterra en algunas partidas, sufriendo un bloqueo en Espa˜na, impidiendo su acceso a la victoria. Potencia Supervivientes Supervivientes JIC HaAI Rusia 4,13 3,87 Alemania 4,71 2,59 Austria 3,85 2,54 Turqu´ıa 8,13 4,79 Francia 3,63 4,89 Inglaterra 5,86 6,56 Italia 3,19 4,04 Cuadro 15: Promedio de unidades supervivientes A continuaci´on se muestran las estad´ısticas promediadas del resultado del juego de JIC. El porcentaje de victorias se ha calculado como la suma de victorias (independientemente de la potencia) dividido por el n´umero de partidas 5 EXPERIMENTACI ´ ON 38 total. El porcentaje de supervivencia es el resultado de promediar los porcentajes de la tabla 14. El n´umero de unidades es el promediado de las unidades supervivientes de la tabla 15 para cada bot. Victoria Supervivencia Unidades JIC 59 % 57 % 4,78 HaAI 37 % 61 % 4,18 Cuadro 16: Estad´ısticas de JIC contra HaAI Berserk Si se suman los porcentajes de victorias de cada bot se puede apreciar que no se llega al 100 %. El 4 % restante hace referencia a las partidas que han terminado en empate y por lo tanto no hay ning´un ganador. El bajo porcentaje de empates indica que se ha conseguido resolver un mayor n´umero de interbloqueos. A la vista de los resultados expuestos, se puede afirmar que en un torneo entre ambos bots, JIC y HaAI Berserk, el comportamiento del primero tiene mejor resultado que el del segundo, consiguiendo un mayor n´umero de victorias y unas tasas de supervivencia similares. 5.2.2. JIC contra HaAI Vanilla Este torneo tiene las mismas caracter´ısticas que el anterior, salvo por la versi´on del bot HaAI utilizada. La versi´on Vanilla se caracteriza por ser m´as defensiva que el Berserk. Los resultados del torneo de 100 partidas son los siguientes: Potencia Jugado Ganado Sobrevivido Eliminado Rusia 44 2 17 25 Alemania 48 1 9 38 Austria 42 2 19 21 Turqu´ıa 43 23 19 1 Francia 34 10 21 3 Inglaterra 50 4 39 7 Italia 39 4 15 20 Cuadro 17: Resultados por potencia de JIC Potencia Jugado Ganado Sobrevivido Eliminado Rusia 56 1 39 16 Alemania 52 1 34 17 Austria 58 2 20 36 Turqu´ıa 57 3 50 4 Francia 66 13 51 2 Inglaterra 50 2 46 2 Italia 61 2 37 22 Cuadro 18: Resultados por potencia de HaAI Vanilla 5 EXPERIMENTACI ´ ON 39 Potencia Victoria Supervivencia Victoria Supervivencia JIC JIC HaAI HaAI Rusia 5 % 40 % 2 % 71 % Alemania 2 % 19 % 2 % 67 % Austria 5 % 48 % 3 % 36 % Turqu´ıa 53 % 95 % 5 % 93 % Francia 29 % 88 % 20 % 96 % Inglaterra 8 % 85 % 4 % 96 % Italia 10 % 43 % 3 % 63 % Cuadro 19: Estad´ısticas por potencia contra HaAI Vanilla Los porcentajes de supervicencia de supervivencia de HaAI se han visto incrementados considerablemente, mientras que los porcentajes de victoria para ambos bots ha decrecido. Esto es debido en parte al comportamiento defensivo de la versi´on Vanilla, pero como se ver´a en la tabla 21, el elevad´ısimo n´umero de empates producidos tambi´en est´a relacionado. Resulta interesante que JIC haya conseguido la victoria en dos ocasiones pese al car´acter m´as defensivo de Vanilla8. Pese al decremento generalizado de los porcentajes de victoria de JIC, se mantienen las proporciones entre potencias, siendo m´as favorable la actuaci´on con Turqu´ıa y Francia que con las dem´as. Potencia Supervivientes Supervivientes JIC HaAI Rusia 4,12 3,90 Alemania 4,44 5,03 Austria 2,58 3,05 Turqu´ıa 10 5,66 Francia 5,05 5,69 Inglaterra 5,64 6,46 Italia 3,53 3,57 Cuadro 20: Promedio de unidades supervivientes Victoria Supervivencia Unidades JIC 46 % 60 % 5,05 HaAI 24 % 74 % 4,76 Cuadro 21: Estad´ısticas de JIC contra HaAI Vanilla Hay que destacar que en este experimento el n´umero de empates alcanzados sobrepasa enormemente al de los dem´as experimentos. En total se ha llegado a 30 empates, frente a los 4 empates contra Berserk, 5 contra DumbBot o los obtenidos contra todos los bots. 8Puesto que en el torneo contra la versi´on Berserk de HaAI no se alcanz´o en ninguna ocasi´on, ver tabla 12. 5 EXPERIMENTACI ´ ON 40 Como se puede ver en la tabla 21 la superioridad de JIC en un enfrentamiento directo con la versi´on Vanilla del bot HaAI es m´as que evidente, alcanzando pr´acticamente el doble de victorias. 5.2.3. JIC contra DumbBot En esta ocasi´on hemos utilizado 3 bots tipo JIC y 4 bots de tipo DumbBot versi´on 8. Potencia Jugado Ganado Sobrevivido Eliminado Rusia 44 2 18 24 Alemania 42 2 19 21 Austria 49 8 25 16 Turqu´ıa 43 23 14 6 Francia 39 9 26 4 Inglaterra 39 0 35 4 Italia 44 3 23 18 Cuadro 22: Resultados por potencia de JIC Potencia Jugado Ganado Sobrevivido Eliminado Rusia 56 2 22 32 Alemania 58 2 20 36 Austria 51 5 14 32 Turqu´ıa 57 16 30 11 Francia 61 11 36 14 Inglaterra 61 9 47 5 Italia 56 4 18 34 Cuadro 23: Resultados por potencia de DumbBot Lo m´as destacable de este experimento respecto de los anteriores es la notoria mejora en el comportamiento con Austria Potencia Victoria Supervivencia Victoria Supervivencia JIC JIC DumbBot DumbBot Rusia 5 % 43 % 4 % 41 % Alemania 5 % 48 % 2 % 36 % Austria 16 % 61 % 10 % 30 % Turqu´ıa 53 % 70 % 28 % 73 % Francia 23 % 87 % 18 % 72 % Inglaterra 0 % 90 % 15 % 90 % Italia 7 % 56 % 7 % 35 % Cuadro 24: Estad´ısticas por potencia contra DumbBot 5 EXPERIMENTACI ´ ON 41 Potencia Supervivientes Supervivientes JIC DumbBot Rusia 3,44 2,36 Alemania 2,95 1,90 Austria 4,12 2,00 Turqu´ıa 7,00 6,30 Francia 3,04 2,86 Inglaterra 8,94 8,30 Italia 3,52 2,33 Cuadro 25: Promedio de unidades supervivientes Al igual que ocurr´ıa en el experimento 5.2.2 el n´umero de supervivientes promedio de JIC con Inglaterra y los porcentajes de Dumbbot con Francia, Italia y Turqu´ıa, dejan ver que nuevamente ha sufrido el bloqueo al Mar Mediterr´aneo. Victoria Supervivencia Unidades JIC 47 % 65 % 4,72 DumbBot 48 % 54 % 3,72 Cuadro 26: Estad´ısticas de JIC contra DumbBot Aunque los resultados obtenidos de la experimentaci´on son similares para ambos bots, la inferioridad num´erica de JIC hace m´as meritorios sus resultados que los de DumbBot. 5.2.4. JIC contra todos El ´ultimo de los torneos realizados pretend´ıa observar el comportamiento de JIC en un entorno m´as variable, por lo que se ha enfrentado a los 3 bots anteriores simult´aneamente. Se han realizado 4 rondas de 100 partidas, en las que uno de los bots se encontraba en inferioridad num´erica, esto es, en cada ronda hab´ıa dos bots de cada tipo menos uno que se encontraba solo. En estos experimentos se va a mostrar ´unicamente los porcentajes de victoria, supervivencia, n´umero de supervivientes y duraci´on de cada una de las rondas. La ´ultima columna de las tablas 27 a 30 , duraci´on, hace referencia al a˜no promedio en que cada bot alcanza la victoria en cada una de las rondas. ´ Este ´ultimo valor puede indicar lo buenas que son las soluciones alcanzadas por cada bot a largo plazo, es decir, aquellos bots que presentan un menor valor de duraci´on han trazado planes con un coste temporal menor llevando a conseguir el objetivo global del juego. 1 JIC, 2 Berserk, 2 Vanilla y 2 DumbBot Victoria Supervivencia Unidades Duraci´on JIC 14 % 65 % 4,95 1919 Berserk 27 % 78 % 3,59 1927 Vanilla 22 % 84 % 4,53 1932 DumbBot 29 % 47 % 3,20 1930 Cuadro 27: Estad´ısticas con JIC en inferioridad REFERENCIAS 48 [16] E. G. Romero. Planificaci´on estrat´egica para el juego diplomacy. Master’s thesis, Departamento de Sistemas Inform´aticos y Computaci´on. Universidad Polit´ecnica de Valencia, 2011. [17] R.G. Smith. The contract net: A formalism for the control of distributed problem solving. In Proceedings of the 5th international joint conference on Artificial intelligence-Volume 1, page 472. Morgan Kaufmann Publishers Inc., 1977. [18] Eric Wald. A framework for playing the diplomacy board game over a network. http://sourceforge.net/projects/parlance/, 2008. [19] Wikipedia. Jaime i de arag´on — wikipedia, la enciclopedia libre, 2011. [Internet; descargado 28-junio-2011]. DIRECCIÓ DE L’ESCOLA TÈCNICA SUPERIOR D’ENGINYERIA INFORMÀTICA / DIRECCIÓN DE LA ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA INFORMÁTICA Informe Director de Projecte Final de Carrera Informe Director de Proyecto Final de Carrera Dades del Projecte/Datos del Proyecto Tipus/Tipo: A Departament/Departamento B Projectes específics/Proyectos específicos C Empreses o Universitats/Empresas o Universidades Títol/Título: JIC: Diseño y desarrollo de un bot inteligente para juegos de estrategia multijugador Titulació/Títulación: Ingeniero en Informática Nom de l’alumne/Nombre del alumno: Pablo Castejón Navarro A emplenar pel Director del Projecte / A cumplimentar por el Director del Proyecto Eva Onaindia de la Rivaherrera, director del projecte/director del proyecto, ……………………………………………………………………………………, codirector del projecte,/codirector del proyecto, autoritzen la persona interessada perquè sol·licite ser avaluada per tribunal i adjuntem el següent informe./autorizamos a la persona interesada para que solicite ser evaluada por tribunal y adjuntamos el siguiente informe. València, ..28 de ....Junio....... de 2011. Informe del PFC / Informe del PFC El presente trabajo final de carrera se enmarca en el contexto del proyecto de investigación CONSOLIDER “Agreement Technologies”, en el que el grupo GTI-IA (Grupo de Tecnología InformáticaInteligencia Artificial) de la UPV colabora, entre otros, con el IIIA (Instituto de Investigación en Inteligencia Artificial) del CSIC. El objetivo prioritario del proyecto CONSOLIDER es el diseño e implementación de técnicas sociales en contextos multiagente (negociación, argumentación, toma de decisiones colectivas, etc.), y uno de los entornos en los que el CSIC está experimentando dichas técnicas es en el juego Diplomacy, principalmente la aplicación de técnicas de negociación multiagente. Para poder experimentar dichas técnicas en Diplomacy, se hacía necesario disponer previamente de un bot propio capaz de jugar a Diplomacy y que cumpliera una serie de características. El bot que se ha desarrollado en este PFC (JIC) responde a un modelo de resolución cooperativa de problemas distribuidos que facilitará la posterior inclusión de técnicas de negociación multiagente. JIC es un bot que sigue un razonamiento puramente deductivo, al estilo de algunos otros bots existentes en la literatura, y que muestra una gran capacidad de supervivencia en el juego, característica fundamental para poder incorporar luego técnicas de negociación entre diferentes jugadores. Es más, los experimentos demuestran que el bot JIC supera en rendimiento al resto de bots, siendo el que más victorias consigue en torneos mixtos donde han competido todos los bots más relevantes para el juego Diplomacy . La realización de este trabajo ha permitido al alumno Pablo Castejón Navarro iniciarse en el tema de investigación de Planificación en Inteligencia Artificial, Planificación distribuida y Coordinación de planificación en Sistemas multiagente. Pablo Castejón Navarro ha disfrutado de una beca durante la realización del PFC y continuará su trabajo con la incorporación del bot JIC en una plataforma multiagente. Actualmente, se está preparando una publicación del trabajo realizado que se enviará a una revista.