Repositorio Institucional de Documentos

Proyecto de fin de Carrera Ingenier´ıa en Inform´atica Curso 2010/2011 Personajes con Razonamiento Basado en Casos para videojuegos en primera persona Javier Olmos Lanceta Director: Manuel Gonz´alez Bedia Co-Director: Francisco Ser´on Arbeloa Departamento de Inform´atica e Ingenier´ıa de Sistemas Centro Polit´ecnico Superior Universidad de Zaragoza Septiembre de 2011 Personajes con Razonamiento Basado en Casos para videojuegos en primera persona RESUMEN Actualmente los videojuegos han llegado a un punto de realismo gr´afico dif´ıcil de superar y aun as´ı cualquier jugador experto reconoce que el realismo en la interacci´on es deficitario. El problema de fondo, al que se ha empezado a dedicar tiempo y dinero en los ´ultimos a˜nos no es gr´afico, sino que se centra en c´omo mejorar aspectos de comportamiento, como la inteligencia artificial, para dotar de mayor credibilidad a los personajes virtuales. Siguiendo este enfoque, ha aparecido recientemente un nuevo inter´es por aplicar t´ecnicas de modelado cognitivo que buscan que los personajes virtuales muestren mayor semejanza con el comportamiento humano. El objetivo de este proyecto es usar t´ecnicas cognitivas para crear un personaje que se comporte, en su conducta, de la manera m´as humana posible. La t´ecnica seleccionada para este fin ha sido el uso de un sistema de razonamiento basado en casos para implementar la hip´otesis de los “marcadores som´aticos” de Antonio Damasio [13]. El modelo de Damasio es la teor´ıa m´as aceptada sobre el modo en que los humanos toman decisiones, y c´omo se ven afectadas por las emociones. El funcionamiento del modelo de decisi´on implementado es como sigue: El personaje tiene una memoria con experiencias pasadas y un valor que le indica si fue buena o mala dicha experiencia. En un momento de la partida busca en su memoria c´omo actuar ante la situaci´on que encuentra. En su memoria se har´a una criba previa de casos asignados como positivos por su experiencia y el personaje elegir´a el m´as parecido a la situaci´on actual. Lo primero que exige este proyecto es estudiar qu´e herramientas tenemos disponibles para llevarlo a cabo. Se estudiar´an a fondo herramientas como Pogamut y SQLite. Pogamut son un conjunto de librer´ıas en java para el manejo de personajes del Unreal Tournament 2004. SQLite es un gestor de bases de datos, muy simple y completo con gran r´apidez de ejecuci´on perfecto para juegos en tiempo real. Una vez concluido ese trabajo previo, se analizar´a c´omo queremos que se comporte el personaje. Como el entorno de trabajo es muy amplio hay que simplificarlo. Se deben elegir los par´ametros m´as importantes que el personaje debe tener en cuenta para elegir el comportamiento futuro, como el entorno de un juego da demasiada informaci´on hay que seleccionar la m´as adecuada. Adem´as se crean los comportamientos que el personaje podr´a ejecutar, intentando darle diversidad de acci´on, para poder controlar las diversas situaciones que se encuentre en la partida. Los comportamientos ser´an ´arboles de binarios de tama˜no variable entre cuatro y siete niveles dependiendo de las acciones que lo conformen. Los resultados finales obtenidos demuestran que las t´ecnicas implementadas son ´utiles e interesantes para seguir avanzando en trabajos futuros. i Agradecimientos Durante los a˜nos que ha durado la carrera, incluyendo este ´ultimo hay mucha gente a la que tengo que estar muy agradecido por haberme apoyado en los buenos y malos momento, ya sea con peque˜nos o grandes gestos. A mi familia, especialmente a mis padres, Lourdes y Jes´us, y sus respectivas parejas, Josetxo y Diana, por aguantarme tantos a˜nos escuchando cosas que seguramente no entend´ıan, aunque como siempre me ha dicho mi madre le gustaba escucharme porque ve´ıa que me divert´ıa con lo que hac´ıa. Tambi´en mis hermanas peque˜nas, Ana e Izaskun, me han ayudado mucho aunque no lo sepan, porque siempre consegu´ıan que desconectara al sacar mi lado gracioso o picajoso con ellas. Aunque siempre se dice que la familia no se elije, yo no puedo quejarme de la que me ha tocado. A mis amigos (tanto de infancia, como del cps) que, como siempre, han estado ah´ı durante toda la carrera y en especial este ´ultimo a˜no, interes´andose por mis avances y haciendo preguntas sobre el proyecto que yo no me hab´ıa hecho y que me han ayudado a avanzar. Adem´as tambi´en les tengo que agradecer, y mucho, el ser esas v´alvulas de escape necesarias para desconectar de todo y disfrutar de una vida social por lo menos aceptable, tan importante es terminar un trabajo con la mejor nota posible como disfrutar de una buena fiesta con los amigos. A todos los habitantes del cps que han compartido tiempo, sufrimientos y alegr´ıas conmigo. Y a Sergio, Carlos y ´ Angel por habernos ayudado mutuamente en lo posible a controlar todo el entorno del juego. A mis tutores Paco y Manolo por ayudarme en todo lo posible, y en especial por haberme permitido juntar en un mismo proyecto dos de los temas que m´as me atraen, videojuegos y cerebro. Su ayuda en todo este tiempo ha sido fundamental para m´ı, tanto en los buenos momentos, dejando claro que no todo estaba tan bien, como en los malos, mostrando que todo tiene soluci´on aunque no parezca cercana. Tal como dijo la escritora Gladys Bronwyn Stern, “La gratitud en silencio no sirve a nadie”, as´ı que yo solo puedo decir, GRACIAS. iii ´ Indice general 1. Introducci´on 1 1.1. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Contenido de la memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3. Contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3.1. Emociones y videojuegos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Cuestiones exploradas o trabajo previo 7 2.1. Pogamut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1. C´omo crear un bot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2. SQLite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3. T´ecnicas y herramientas desechadas . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3. Descripci´on del modelo 15 3.1. Condiciones de la partida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2. Variables de entorno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3. SomaticMarkerBot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3.1. Comportamientos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4. Dise˜no de Experimentos y Resultados 23 4.1. Par´ametros de los experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.1.1. Ventana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.1.2. M´etricas de selecci´on de caso . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.1.3. M´etricas “premio/castigo” . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2. Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2.1. Experimento 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2.2. Experimento 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2.3. Experimento 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.2.4. Experimento 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2.5. Experimento 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.3. Ideas generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 v 5. Conclusiones y valoraci´on personal 35 5.1. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.2. Trabajo o l´ıneas futuras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.3. Valoraci´on personal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 A. Planificaci´on 47 B. Botprize 55 B.1. Reglas de competici´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 B.1.1. The task . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 B.1.2. To enter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 B.1.3. Testing protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 B.2. Resultados botprize 2010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 B.3. Resultados de los jueces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 C. Teor´ıa de Damasio 59 C.1. Modelo emocional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 C.1.1. Emociones primarias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 C.1.2. Emociones secundarias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 C.1.3. Estados corporales “como si” . . . . . . . . . . . . . . . . . . . . . . . . . . 62 C.2. La fr´ıa cognici´on no es suficiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 C.2.1. Hip´otesis del marcado som´atico . . . . . . . . . . . . . . . . . . . . . . . . . 64 D. CBR: T´ecnicas de Razonamiento basado en Casos 67 D.1. Caracter´ısticas generales de las 4 fases . . . . . . . . . . . . . . . . . . . . . . . . . 67 D.1.1. Recuperaci´on de Casos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 D.1.2. Reutilizaci´on de Casos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 D.1.3. Revisi´on de Casos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 D.1.4. Retenci´on de Casos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 D.2. Variaciones del CBR t´ıpico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 D.3. CBR y otras t´ecnicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 E. Instalaci´on del entorno 73 E.1. Prerrequisitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 E.2. Proceso de instalaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 E.3. Ejecuci´on de un bot en UT2004 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 E.3.1. Configuraci´on del servidor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 E.3.2. Conexi´on del bot al servidor . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 vi F. Lista de comandos y mensajes 79 F.1. Lista de comandos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 F.2. Lista de mensajes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 G. Listeners 83 H. Variables de entorno 89 I. Funciones de la base de casos 101 J. Acciones simples 103 J.1. Caminar (Walk) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 J.2. Recoger objetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 J.3. Huir (RUN AWAY FROM PLAYER) . . . . . . . . . . . . . . . . . . . . . . . . . 105 J.4. Atacar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 J.4.1. Pasos previos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 J.4.2. Buscar enemigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 J.4.3. Elegir arma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 J.4.4. Calcular distancia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 J.4.5. Hay rival y tengo arma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 J.4.6. Hay rival, pero lejos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 K. ´ Arboles de comportamiento 115 L. Experimentos 129 L.1. Experimento 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 L.1.1. Caso 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 L.1.2. Caso 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 L.1.3. Caso 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 L.1.4. Caso 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 L.2. Experimento 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 L.2.1. Caso 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 L.2.2. Caso 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 L.2.3. Caso 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 L.2.4. Caso 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 L.3. Experimento 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 L.3.1. Caso 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 L.3.2. Caso 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 vii L.76.Formas de atacar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 L.77.Memoria del bot Exp:4 Cas:1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 L.78.Tabla de victorias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 L.79.Comportamientos generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 L.80.Comportamientos de ataque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 L.81.Comportamientos defensivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 L.82.Formas de recoger objetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 L.83.Formas de atacar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 L.84.Memoria del bot Exp:4 Cas:2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 L.85.Tabla de victorias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 L.86.Comportamientos generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 L.87.Comportamientos de ataque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 L.88.Comportamientos defensivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 L.89.Formas de recoger objetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 L.90.Formas de atacar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 L.91.Memoria del bot Exp:5 Cas:1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 xiv Cap´ıtulo 1 Introducci´on 1.1. Objetivos El objetivo fundamental del proyecto es la creaci´on de un agente aut´onomo virtual (bot) cuyo comportamiento est´e controlado por un sistema de Razonamiento Basado en casos (Case-based reasoning, CBR) que permita guardar experiencias pasadas con las que el agente organice su comportamiento futuro. Una vez implementado, el prop´osito es determinar las condiciones de una estrategia general para el comportamiento del bot, independiente de su situaci´on concreta y del desarrollo de la partida. Se ha elegido esta t´ecnica para el modelado del agente por su sinton´ıa con la teor´ıa de los marcadores som´aticos de Damasio. Nuestra experiencia previa, siguiendo las ideas de Damasio, quedar´ıa reflejada en la base de casos mediante el valor de satisfacci´on “que posee cada uno” y nuestra capacidad deliberativa se modelar´ıa mediante la m´etrica usada para elegir un caso en lugar de otro, despu´es de haber discriminado los casos peor valorados. Como afirma Damasio: “en un proceso de decisi´on, inicialmente un valor emocional producido por experiencias pasadas restringe el n´umero de opciones sobre las que elegir y posteriormente nuestra capacidad deliberativa elije la mejor opci´on de las restantes”. Entendido un sistema CBR como una metodolog´ıa que hay que adaptar al contexto del trabajo, se propone que: El bot posee experiencias pasadas (casos) almacenadas en la base de casos. Cada caso es una pareja “situaci´on del entorno - comportamiento”. Seg´un la situaci´on actual del entorno, el bot decide qu´e situaci´on pasada se asemeja m´as a la actual. El bot act´ua igual que lo hizo en la situaci´on anterior. Se determina si el resultado de esa situaci´on ha sido satisfactorio o no. El valor de satisfacci´on para dicha situaci´on se almacena en la base de casos. De esta manera se van reorganizando los casos, hasta el punto en que para cada situaci´on del entorno se tiene identificado el comportamiento m´as id´oneo, por medio del valor de satisfacci´on. Para alcanzar dicho objetivo se partir´a del entorno de visualizaci´on que proporciona el juego Unreal Tournament 2004, juego de c´odigo abierto y con un conjunto de librer´ıas que permiten crear 1 bots de manera independiente al entorno gr´afico. Dicho conjunto de librer´ıas se llaman Pogamut1 (versi´on 3.1). La base de casos se crear´a con un simple gestor de bases de datos SQLite32, mediante su driver para java SQLiteJDBC. El uso de java se debe a que las librer´ıas Pogamut se encuentran en dicho lenguaje. La forma de usar estas herramientas se comenta en la secci´on 2.1. Como trabajo previo al planteamiento de la hip´otesis se tiene que demostrar el correcto funcionamiento de las librer´ıas Pogamut en el entorno del juego. La hip´otesis de este proyecto se centra en evaluar si se puede aplicar un sistema CBR en este tipo de juegos que requieren una r´apida respuesta. La conclusi´on final determinar´a si es posible el uso de este sistema y cu´ales son las mejores condiciones, para el aprovechamiento m´aximo y para que se obtengan los mejores resultados posibles. Como ya hemos indicado, se intentar´a obtener un patr´on global que modele la estrategia del bot que mejor act´ue en cualquier tipo de entorno del juego. Con este patr´on global se quiere establecer de manera gen´erica c´omo se deber´ıa afrontar un juego de estas caracter´ısticas con la mayor probabilidad de ´exito en el menor tiempo posible, evitando as´ı que un jugador humano tenga que descubrir por ´el mismo c´ual es la mejor forma de actuar. En el Anexo A: “Planificaci´on” se muestra el detalle temporal del proyecto. 1.2. Contenido de la memoria A lo largo de este documento, se pueden encontrar las siguientes secciones: Introducci´on: Incluye los objetivos y se establece el contexto en el que se encuadra el trabajo. Cuestiones exploradas o trabajo previo: Cuestiones y herramientas consultadas para el desarrollo del proyecto. Descripci´on del modelo: Una vez establecidas las cuestiones y comprendidas las herramientas se explica el desarrollo del proyecto, detallando todo el proceso seguido para la realizaci´on del bot. Dise˜no de experimentos y resultados: Como resultado final del proyecto se establecen unos experimentos para comprobar que se cumplen los objetivos planteados. Conclusiones y valoraci´on personal: Conclusi´on global sobre el desarrollo del proyecto, posibles l´ıneas futuras y valoraci´on del proyecto. Glosario: Definici´on de algunos t´erminos. Bibliograf´ıa: Fuentes de informaci´on consultadas para realizar este proyecto. Anexos: Informaci´on adicional del proyecto, referenciada desde apartados anteriores. 1.3. Contexto ¿Pueden pensar las m´aquinas? Esta pregunta fue planteada por Alan M. Turing3en un famoso trabajo de 1950 [1] (Figura 1.1). Mediante un famoso test que lleva su nombre, Turing introduce un criterio operacional para dirimir si el comportamiento de un artefacto deber´ıa ser considerado 1http://diana.ms.mff.cuni.cz/main/tiki-index.php 2http://www.sqlite.org/ 3Alan M. Turing, matem´atico, cript´ografo y fil´osofo ingl´es de mediados del siglo XX. 2 como “inteligente”. En principio parecer´ıa obvio que este don solo se puede asociar a los seres humanos, que durante millones de a˜nos han desarrollado las estructuras neuronales que conforman sus complejos cerebros. Sin embargo, la respuesta a esta pregunta no es sencilla. Depender´a, como bien dijo Turing,“de qu´e entendamos por pensar”. Seg´un la Real Academia Espa˜nola de la Lengua4, “pensar” supone el acto de “examinar con cuidado algo para formar dictamen”. Una definici´on de este tipo deja una puerta abierta a la existencia de m´aquinas inteligentes. Figura 1.1: Explicaci´on gr´afica del test de Turing En este trabajo nos interesamos por una de las versiones del Test de Turing aplicada al entorno de los videojuegos. Los videojuegos actuales, poseen una gran diversidad, y proporcionan un abanico de opciones capaz de satisfacer a cualquier tipo de p´ublico. Los principales g´eneros de videojuegos son: aventuras, deportes, educativos, estrategia, shooter, lucha, juegos de mesa, party, plataformas, rol y simulaci´on (Ver Glosario). De todos estos g´eneros, este estudio se centrar´a en los de tipo Shooter, debido al concurso Botprize5. La finalidad de dicho concurso es crear bots para el Unreal Tournament 20046que simulen el comportamiento de un jugador humano (en el Anexo B: “Botprize” se muestran las bases de la competici´on). Esta competici´on responde a una inquietud por parte de la industria del videojuego en incorporar herramientas “inteligentes” a sus dise˜nos. En estos ´ultimos tiempos se han extendido las t´ecnicas de inteligencia artificial de tal modo que actualmente cubren un conjunto de intereses m´as amplios que los iniciales. Una de las ideas que ha fomentado este cambio hacia una “nueva IA” es la de reproducir emociones humanas, algo impensable en la “IA tradicional”. Se considera que reproducir aspectos como las emociones o la personalidad de los seres humanos nos llevar´a a mostrar“humanidad”en las m´aquinas. Actualmente t´erminos como emociones, conciencia y humanidad ocupan gran cantidad de proyectos dedicados a avanzar en t´ecnicas de inteligencia artificial. 1.3.1. Emociones y videojuegos Las emociones son fen´omenos fisiol´ogicos que nos hacen “sentir” y de las que podemos aprender para formar conductas que en el futuro nos ayudar´an. Los videojuegos actuales tratan de dos modos distintos su relaci´on con las emociones. Por una parte, buscan reforzar las conductas del jugador en diversos aspectos, por ejemplo, “ense˜nando a un ni˜no a como razonar”. Por otro lado intentan despertar las emociones del jugador en momentos puntuales del juego para tener una mayor interacci´on. Existen muchas hip´otesis o ideas que giran en torno a las emociones, restando importancia a la l´ogica. Una de las m´as importantes es la que se va a aplicar en este proyecto: La hip´otesis del “marcador som´atico”. 4www.rae.es/rae.html 5http://botprize.org/ 6http://www.unrealtournament.com/ 3 Hip´otesis del marcador som´atico Antonio Damasio7en su libro “El error de descartes” [13] intenta demostrar que las emociones forman parte del razonamiento, lo que ser´ıa seg´un ´el mismo dice, “una racionalidad de las emociones”. Damasio intenta dar explicaci´on a los comportamientos de algunos de sus pacientes que han sufrido da˜nos en el l´obulo central. ´ Estos no muestran ning´un signo de emoci´on ante situaciones sensibles o tr´agicas8, y aunque conservan todas sus facultades cognitivas, pierden la capacidad para tomar decisiones. Damasio llega a la conclusi´on de que “la defectuosa capacidad de toma de decisiones se debe a la ausencia de emociones”, registrando evidencias experimentales acerca de comportamientos nada exitosos por parte de estos sujetos, en dos aspectos principalmente: Emplean, irracionalmente, cantidades de tiempo desmedidas en tareas triviales9. Toman malas decisiones – en vez de retrasarlas – por la falta de motivaci´on que manifiestan sus representaciones mentales sobre estados futuros. Damasio desarrolla el modelo de “marcadores som´aticos” para explicar, desde un punto de vista neurofisiol´ogico, el porqu´e del comportamiento de sus pacientes. Su “hip´otesis del marcador som´atico” propone que la participaci´on emocional en el proceso de deliberaci´on pr´actica y toma de decisiones, lejos de constituir una interferencia perturbadora, es m´as bien una condici´on de posibilidad del mismo. Si nuestra deliberaci´on pr´actica tuviese que desarrollarse seg´un los criterios de la teor´ıa de la decisi´on10, no podr´ıamos tomar decisiones adecuadas en situaciones de urgencia, debido a la complejidad del c´alculo requerido y al gran n´umero de cursos de acci´on alternativos a evaluar. Este n´umero, sin embargo, es dr´asticamente reducido, seg´un Damasio, por la participaci´on de las emociones en la selecci´on de alternativas que ser´an tenidas en cuenta. La idea de Damasio, de que las emociones ayudan a realizar una selecci´on previa, ha generado una corriente de investigaciones que busca la manera m´as eficiente de modelar las emociones artificialmente. Estas investigaciones se centran en situaciones en las que la racionalidad no funciona tan r´apido como se desear´ıa [15] o en situaciones en las que no es necesario racionalizar completamente para tomar un decisi´on [16]. Para aplicar esta hip´otesis existen t´ecnicas que se ajustan perfectamente, como es el caso de los sistemas de razonamiento basados en casos, que pueden usarse para ver como las emociones reducen las opciones antes de tomar una decisi´on. En el Anexo C: “Teoria de Damasio”, se explica con m´as detalle su hip´otesis del marcador som´atico, as´ı como el modelo emocional que plantea. Razonamiento Basado en Casos y Emociones Kolodner11 propuso en la d´ecada de los 80 un modelo de razonamiento conocido como “sistema de razonamiento basado en casos” [4]. Este modelado se caracterizaba por superar alguno de los 7Antonio Damasio, profesor de Neurociencia, Neurolog´ıa y Psicolog´ıa en la Universidad de Southern California y director del Instituto del Cerebro y la Creatividad. 8En [13] los experimentos realizados con este tipo de sujetos no presentan las respuestas de conductancia cut´anea de los individuos normales. 9En [13] se narra la conducta de un paciente con el que Damasio pretende concretar una futura cita, y al que le sugiere dos fechas diferentes con s´olo unos pocos d´ıas de separaci´on. En palabras del propio Damasio: [. . . ] el paciente saco su agenda y empez´o a consultar el calendario. [. . . ] Durante casi media hora, el paciente enumer´o motivos a favor y en contra de cada una de las dos fechas [. . . ] llevado por un agotador an´alisis de costes y beneficios, [...] Finalmente le dijimos que deb´ıa venir la segunda de las dos fechas. Su respuesta fue igualmente tranquila y r´apida. Dijo: <<Est´a bien>>. 10Seg´un la teor´ıa de decisi´on cl´asica [14] el mecanismo para la correcta elecci´on de una opci´on estar´ıa basado en un an´alisis l´ogico de la situaci´on (sin contaminaci´on emocional), se seleccionar´ıa la opci´on que maximizase el provecho subjetivo esperado. 11Janet L. Kolodner es una cient´ıfica cognitive Americana, profesora en el instituto tecnol´ogico de Georgia. 4 problemas que afectaban a los sistemas expertos. En lugar de basarse exclusivamente en el conocimiento general del dominio de un problema, se utiliza el conocimiento espec´ıfico de experiencias previas en situaciones concretas. Un sistema de razonamiento basado en casos fundamentalmente resuelve un problema, por medio de la adaptaci´on de soluciones dadas con anterioridad a problemas similares [5]. Un sistema CBR t´ıpico, est´a compuesto por cuatro etapas secuenciales que se invocan siempre que es necesario resolver un problema [6]. La Figura 1.2, muestra el ciclo de vida de un sistema de razonamiento basado en casos cl´asico, donde las cuatro etapas del proceso son: Figura 1.2: Ciclo de vida de un sistema CBR. Recuperaci´on de los casos o problemas m´as relevantes al nuevo problema. Utilizaci´on (adaptaci´on) de los casos o problemas recuperados con la intenci´on de solucionar el problema presente. Revisi´on de la soluci´on propuesta inicialmente por el sistema. Retenci´on (aprendizaje) de la nueva soluci´on como parte de un nuevo caso. Al igual que otros mecanismos de resoluci´on de problemas, el objeto de un sistema CBR es el de encontrar la soluci´on a un problema determinado. La misi´on del algoritmo de recuperaci´on, consiste en buscar en la memoria del sistema y seleccionar aquellos ejemplos m´as similares (junto con sus soluciones) al problema presente. Los casos (problema-soluci´on) seleccionados son reutilizados para generar una soluci´on. Si es posible, la soluci´on se revisa y finalmente se crea un nuevo caso que se almacena en la memoria del sistema. Los casos almacenados en la memoria pueden ser eliminados o modificados, pudiendo crearse nuevos casos a trav´es de la mezcla de caracter´ısticas de otros ya existentes. La intervenci´on humana puede ser necesaria a lo largo del ciclo de vida de un sistema CBR, especialmente en las dos ´ultimas fases del ciclo (revisi´on y retenci´on). Este hecho supone uno de los mayores inconvenientes de esta metodolog´ıa, y ha sido se˜nalado como un gran inconveniente por sus detractores. En ocasiones se elimina esta fase para la automatizaci´on completa del sistema. En el Anexo D: “T´ecnicas de Razonamiento basado en Casos” se ampl´ıa la explicaci´on de los sistemas CBR. La aplicaci´on de sistemas CBR a videojuegos est´a empezando a dar sus frutos a la hora de crear comportamientos para NPC (Ver Glosario) m´as realistas. Principalmente se est´an haciendo 5 investigaciones en juegos RTS (Ver Glosario), ya que consiguen aprovechar mucho mejor el ciclo de vida de un sistema CBR. El mayor problema que ten´ıan las t´ecnicas tradicionales de inteligencia artificial con este tipo de juegos era su amplio espacio de b´usqueda para decidir qu´e acci´on tomar en un momento dado. Con los sistemas CBR se consigue reducir este problema al extraer de jugadores expertos sus conocimientos y convertirlos en casos. Algunos de los juegos en los que han sido probadas estas t´ecnicas (la mayor´ıa son juegos RTS) son WARGUS [7, 8, 9], C-evo [10], RoboCup (no es un videojuego en s´ı mismo)[11] y Monopoly [12]. 6 Cap´ıtulo 2 Cuestiones exploradas o trabajo previo En esta secci´on se van a comentar los primeros pasos e importantes pasos de la realizaci´on de este proyecto, que se han dedicado a la investigaci´on y a conocer el funcionamiento las herramientas que se van a usar, como son Pogamut y SQLite3. Se a˜nadir´a un breve apartado en el que se ver´an reflejadas las t´ecnicas y herramientas que durante el desarrollo han sido consideradas para su posible utilizaci´on pero que por diversos motivos se fueron desechando. 2.1. Pogamut Es una plataforma de c´odigo abierto usada para el r´apido desarrollo de comportamientos en agentes virtuales incrustados en un entorno 3D del videojuego Unreal Tournament 2004. En [17] se puede encontrar una explicaci´on m´as profunda de c´omo funciona internamente esta plataforma, as´ı como algunas de las t´ecnicas implementadas por los creadores de Pogamut (ALMA1[18]). Entre otras cosas se explica la arquitectura de Pogamut y todos los componentes que la integran (Figura 2.1): Figura 2.1: Arquitectura de Pogamut. Unreal Tournament 2004: Videojuego sobre el que se trabaja. GameBots 2004: Exporta e importa informaci´on del juego en lenguaje UnrealScript, a trav´es de protocolos TCP/IP (Ver Glosario). GaviaLib: Librer´ıa dentro de Pogamut que se encarga de traducir UnrealScript (Ver Glosario) y pasarlo a Java2y permite conectar agentes a casi cualquier entorno virtual. En la Figura 2.2 se ve su arquitectura a alto nivel. (1) Procesa los mensajes del entorno. (2) Env´ıa los comandos al mundo virtual. (3) Interfaz del agente. 1http://www.dfki.de/˜gebhard/alma/index.html 2http://www.java.com/es/ 7 Pogamut Agent: Conjunto de clases java derivadas de las clases b´asicas de GaviaLib. IDE Netbeans3: Mediante su plugin de Pogamut permite trabajar con las librer´ıas m´as c´omodamente e incluso permite una f´acil conexi´on con el servidor del juego. Figura 2.2: Arquitectura a alto nivel de GaviaLib Antes de pasar a crear un bot hay que instalar la plataforma Pogamut y conectar el bot desde Netbeans al juego mediante los servidores UT2004 espec´ıficos del juego. Todo ello se explica con detalle en el Anexo E: “Instalaci´on del entorno”. 2.1.1. C´omo crear un bot Una vez que se tiene el servidor conectado a Netbeans es el momento de empezar a programar el bot. Para eso lo primero es entender que proporciona Netbeans con su plantilla b´asica, y a partir de ah´ı desarrollar el bot. La plataforma Pogamut tiene un sinf´ın de clases y m´etodos, pero todas est´an relacionadas por lo que conociendo un grupo seleccionado de clases se puede crear un bot y esas clases se encargan de comunicarse con el resto. Las clases principales son: cz.cuni.amis.pogamut.ut2004.utils.UT2004BotRunner: Lanza un thread de ejecuci´on (Ver Glosario) para ejecutar al bot. Se sit´ua dentro del main principal. Se acaba cuando se elimina al bot de la partida. cz.cuni.amis.utils.exception.PogamutException: En todas las funciones donde se ejecutan instrucciones de Pogamut hay que capturar excepciones. Se encarga de tratar cualquier excepci´on de Pogamut. cz.cuni.amis.pogamut.ut2004.bot.impl.UT2004BotModuleController: Contiene el controlador m´as avanzado del sistema. Tiene todos los m´odulos ´utiles para manejar el bot. Es la clase principal. cz.cuni.amis.pogamut.base.communication.worldview: Ofrece tanto los sentidos del bot y como la memoria simple. Muestra c´omo est´a representado el mundo por medio de “listeners”, eventos que van ocurriendo en el mundo. Esta clase es la encargada de recogerlos y tratarlos posteriormente si se quiere configurar el bot para que actue cuando los vaya recibiendo. Adem´as hay dos grupos de clases que son muy importantes ya que contienen los comandos y mensajes que se pueden introducir en GameBots2004, pero que no han sido incluidos como clases principales porque son las clases anteriores las que se encargan de gestionar esos comandos y mensajes (Anexo F: “Lista de comandos y mensajes” muestra una lista de todos los comandos y mensajes que existen en la comunicaci´on entre UT2004, GameBots2004 y Pogamut). A continuaci´on se presenta en detalle el concepto de las dos clases m´as importantes. 3http://netbeans.org/ 8 UT2004BotModuleController Esta es la clase principal del sistema, la que se encarga de manejar los m´odulos que controlan al bot y de establecer el protocolo de comunicaci´on (Ver Glosario) con el entorno. Las funciones que establecen el protocolo de comunicaci´on son las siguientes: prepareBot(): Establece la configuraci´on del mundo antes de saber nada sobre UT2004. Simplemente prepara el sistema virtual. Se ejecuta antes de conectar al bot con el entorno pero despu´es de construir el UT2004Bot. getInitializeCommand(): Aqu´ı es donde se caracteriza al bot con las opciones deseadas (nombre, habilidad, skin. . . ). Env´ıa un objeto Initialize que contiene todos los par´ametros generales del bot. botInitialized(GameInfo info, ConfigChange config, InitedMessage init): Primera vez que el bot tiene informaci´on sobre el mundo, aunque todav´ıa no ha sido creado. Se llama a esta funci´on una vez que el servidor ha enviado el mensaje INITED (clase de java: InitedMessage). Esto significa que el comando INIT ha sido ejecutado correctamente y la comunicaci´on entre el bot y el servidor es correcta. En este momento ya es posible establecer nuevas comunicaciones entre el bot y el servidor, aunque todav´ıa el bot no ha sido creado en el entorno, por lo que los comandos de movimiento no se pueden ejecutar, pero si los de informaci´on del juego (GameInfo), configuraci´on del sistema actual (ConfigChange) y mensajes de inicializaci´on (InitedMessage). botSpawned(GameInfo info, ConfigChange config, InitedMessage init, Self self): Se ejecuta cuando se crea el bot por primera vez, justo al entrar en el entorno del juego. logic(): Funci´on principal del sistema. Entra justo despu´es de crear el bot. Solo sale de ella cuando tiene lugar alg´un evento externo (por ejemplo, se muere el bot. . . ) o cuando se elimina al bot de la partida. Todo lo que se ejecute dentro de la funci´on debe ser procesado r´apidamente ya que se ejecuta cada 0.25 segundos. Esas son las funciones que sirven para crear el protocolo de comunicaci´on y este es el protocolo de comunicaci´on: 1. Se invoca a this.prepareBot() 2. Recibe un mensaje HELLO BOT que se encarga de pedir la conexi´on de un bot con el servidor. Si el servidor est´a saturado u ocupado se termina la conexi´on. 3. ! Env´ıa un mensaje READY. Como respuesta el servidor env´ıa al juego un mensaje NFO (info) con informaci´on sobre la partida. 4. Ahora es cuando se establece la comunicaci´on con GameBots2004. 5. Captura el evento InitCommandRequested confirmando que la inicializaci´on est´a preparada. 6. Ejecuta this.getInitializeCommand(). 7. ! Env´ıa el comando INIT que se ha creado en la funci´on anterior, con los par´ametros iniciales del bot. 8. Recibe el mensaje ConfigChange. 9. Recibe el mensaje InitedMessage. 9 CONDICI´ ON M´ AXIMO ELEGIDO ¿POR QU´ E? N´umero de participantes 32 4 Suficiente n´umero de participantes para no sobrecargar el sistema y para tener siempre enemigos visibles. Niveles del bot 8 3 Nivel “jugador experimentado”, es un nivel adecuado a la mayor´ıa de jugadores t´ıpicos del juego. Autoajustar nivel SI/NO NO Para los resultados ser´a mejor no tener unos enemigos que var´ıen su calidad. Permiso de recoger armas SI/NO SI Cualquier arma del escenario puede ser recogida. Puntos objetivo 999 25 Menos de 15 puntos son partidas muy r´apidas y poco aclaratorias. M´as de 40 son partidas redundantes. Tiempo de juego 999 min 30 min Para el n´umero de puntos objetivo los 30 minutos son m´as que suficientes. Protecci´on al renacer 30.0 s 2.0 s Tiempo invulnerable reci´en renacido (sino dispara). Da tiempo a un primer movimiento pero no permite coger armas con seguridad. Color de los equipos SI/NO NO En una partida DeathMatch no es necesario. Arrojar armas SI/NO SI Puede tirar el arma si interesa. Agitar armas SI/NO SI Los disparos del arma tienen vibraciones. Translocador inicial SI/NO NO Las ´unicas armas iniciales son la shield gun (para protegerse) y el Assault Rifle (para atacar). Sarcasmo SI/NO NO No es necesario. Mutadores 29 0 Complica el nivel de la partida y las posibilidades, por lo que se prescinde de ellos, ya que en las partidas normales no existe ninguno. Tabla 3.3: Par´ametros globales de la partida. Con estos datos ya se ha establecido una parte del entorno de trabajo. A continuaci´on se mostrar´an las variables de entorno elegidas para proporcionar los conocimientos que tendr´a el bot sobre dicho entorno. Dichas variables, como se ver´a, van a reducirse dr´asticamente, porque el bot solo puede manejar un pu˜nado de ellas pero el juego proporciona m´as de cien posibles variables, desde una simple informaci´on de salud del bot, hasta el tipo de suelo que est´a pisando 3.2. Variables de entorno Las variables de entorno codifican toda la informaci´on que el bot puede recibir del juego y que le permiten saber c´omo es la situaci´on en la que se encuentra y a partir de esa situaci´on saber 16 c´omo actuar (buscando en su memoria un caso parecido). Despu´es de analizar todas las variables, se lleg´o a la conclusi´on de que las que usar´ıa el bot para situarse y comparar casos ser´ıan las siguientes: DeathsToWin: Muertes que quedan para ganar la partida. ´ Util para saber si los comportamientos est´an siendo buenos o no (cu´antas menos muertes queden m´as cerca estar´a de la victoria y mejor se estar´a comportando). People: Determina si hay rivales en su visi´on. EndGame: Tiempo que falta para terminar la partida. Es interesante saber si la partida se est´a alargando en exceso o no, para arriesgar m´as o menos. Armor: Cantidad de escudo que tiene el bot en ese instante. Es un control de estado del bot b´asico Ammo: Cantidad de munici´on que tiene el bot en ese instante sobre el total que puede conseguir para ese arma. Es un control de estado del bot b´asico Health: Cantidad de salud que tiene el bot en ese instante. Es un control de estado del bot b´asico. MyDeaths: N´umero de muertes sufridas por el bot. Puede ayudar a determinar si los comportamientos son muy agresivos o muy contemplativos. Sensor: Controla si ha muerto recientemente o si est´a viendo un proyectil en ese momento. Si ha muerto recientemente no tendr´a armas y puede ser menos aconsejable participar en la batalla. NWeapon: Cantidad de armas en el inventario. Nunca es bueno ir a una batalla sin armas. NAmmo: Cantidad de munici´on en el inventario sobre el total que puede obtener. Nunca es bueno ir a una batalla sin munici´on. En el Anexo H:“Variables de entorno”hay una extensa lista con todas las variables que proporciona el juego, explicando su significado y porqu´e no han sido elegidas. Los motivos principalmente se centran en que son informaciones de nivel avanzado y que el bot no necesita conocer para poder moverse por el entorno. Una vez establecidas las condiciones de la partida y la informaci´on que podr´a recibir, se debe establecer el bot. 3.3. SomaticMarkerBot Al plantear la idea de usar CBR como la estructura para representar los marcadores som´aticos en la Teor´ıa de Damasio, en un juego como UT2004, lo m´as natural es encontrarse problemas que impidan desarrollar la metodolog´ıa de manera exacta a como se plantea te´oricamente, por eso mismo el sistema CBR propuesto en este proyecto var´ıa sobre el original. La Figura 3.1 muestra las diferencias entre lo que se puede considerar un CBR cl´asico y lo que ser´ıa el CBR modificado para adaptarse al UT2004. En general no hay grandes diferencias conceptuales. Pasamos a indicar las modificaciones: Los pasos que sigue este CBR modificado son los siguientes: Antes de empezar, la base de casos se carga la memoria del bot (en forma de algunos casos). Cada caso consta de: 17 Figura 3.1: CBR cl´asico y CBR UT2004. Variables de entorno: Informan c´omo est´a el juego en un momento determinado (secci´on 3.2). Comportamiento: Forma de actuar que tuvo el bot en ese momento. Se guarda una asignaci´on al comportamiento, por lo que no es posible modificar los comportamientos en tiempo real. Adaptabilidad: Valor que simula el marcador som´atico de Damasio, indicando lo buena o mala que es la relaci´on entre variables de entorno y comportamiento en un caso particular. Con este valor se puede simular el concepto de emoci´on a la hora de elegir una opci´on, tal como propone Damasio. Las parejas “variables de entorno-comportamiento” que hayan sido negativas para el bot en su ejecuci´on bajar´an su valor de adaptabilidad discrimin´andolas antes de tenerlas en cuenta en futuras situaciones. Y las que hayan sido positivas aumentar´an su valor, estando siempre en la parte superior de la base de casos, consiguiendo que siempre el bot las tenga en cuenta, aunque luego, al deliberar, elija otra de menor valor pero m´as adecuada a la situaci´on real. Dicha base de casos debe permitir modificar, leer y eliminar casos. Dichas funciones est´an explicadas en el Anexo I: “Funciones de la base de casos”. Una vez el juego ha sido lanzado, la ejecuci´on es iterativa hasta que acaba la partida. El proceso es el siguiente: Nuevo Caso: El bot recoge informaci´on del juego (variables de entorno elegidas) y crea un nuevo caso con valor de adaptabilidad y comportamiento nulos. Recuperar: Se busca en la base de casos aquel que m´as se parece al actual. Como ya se ha dicho antes estar´an ordenados por el valor de adaptabilidad y s´olo se tendr´an en cuenta los primeros. De esta criba por adaptabilidad se pasa a la selecci´on de un ´unico caso, en funci´on de la m´etrica, que m´as se asemeje a la situaci´on actual. Usar: Una vez se tiene el caso recuperado, se ejecuta su comportamiento un n´umero de veces suficiente para que haya podido probarse su utilidad. Con este se tiene el caso soluci´on. Revisar: En este momento se debe comprobar c´omo ha funcionado el caso. La m´etrica que comprueba la utilidad se basa en el n´umero de muertes que ha sufrido el bot, el n´umero de muertes que ha provocado y la variaci´on de salud, todo en el periodo de tiempo en el que el caso ha estado ejecut´andose. Con todo ello se actualiza el valor de adaptabilidad para ese caso. Retener: Finalmente se modifica la base de casos y vuelve a repetirse todo el proceso. 18 La principal diferencia con el CBR t´ıpico es que los casos son introducidos inicialmente, debido a problemas en la creaci´on de comportamientos en tiempo real y solo se modifica el valor de adaptabilidad, en ning´un caso se crea un nuevo caso mezcla de otros anteriores, ni se repara un caso creado, ya que no se modifican. Al no permitir que los casos se creen en tiempo de ejecuci´on, el bot necesita un amplio conjunto de comportamientos variados, para facilitar su adaptaci´on a diversas situaciones y que esos mismos comportamientos vayan ordenandose seg´un avanza el bot en la partida. 3.3.1. Comportamientos Los comportamientos son los que permiten al bot adaptarse y actuar de diversas maneras (que pueden ser mejores o peores en funci´on de la situaci´on en la que se encuentre). Los comportamientos se han creado en forma de ´arbol (Figura 3.2), por lo que dependiendo de las condiciones de la partida, el ´arbol binario1discurre por una rama u otra, actuando de la mejor manera posible. En las hojas de cada comportamiento est´an las llamadas “acciones simples”. El tama˜no de los ´arboles es variable, entre cuatro y cinco niveles, como se ver´a en el Anexo K: “´ Arboles de comportamiento”. Figura 3.2: ´ Arbol binario Estas “acciones simples” son las que determinan qu´e va a hacer el bot (recoger objetos, atacar, huir. . . ). Hay muchas posibilidades a la hora de elegir cuales van a ser esas acciones simples, tantas como se quiera, pero para el ´ambito de este proyecto se determin´o que hab´ıa que restringirlas de la mejor manera posible y elegir las consideradas m´as ´utiles para el estudio, puesto que el proyecto se desarrolla en un entorno acotado. En el Anexo J: “Acciones simples” hay un completo y extenso an´alisis de cu´ales son las mejores acciones simples y porqu´e han sido elegidas frente a otras opciones tambi´en consideradas. El resultado final de ese an´alisis se muestra en la Tabla 3.4. Acci´on simple ¿Que hace? walk Permite andar por el mundo de un punto de navegaci´on a otro. protector Recoge objetos de salud o de escudo que est´en disponibles. pickHealth Recoge objetos de salud que est´en disponibles. 1http://es.wikipedia.org/wiki/ %C3 %81rbol binario 19 Acci´on simple ¿Que hace? pickArmor Recoge objetos de escudo que est´en disponibles. army Recoge cualquier arma que est´e disponible y cualquier munici´on disponible asociada a un arma del inventario del bot. runAwayFromPlayer Huye de un rival en direcci´on contraria siempre que pueda. attackNearestVisiblePlayerWithSpeed Ataca al jugador visible m´as cercano usando su arma m´as r´apida. attackNearestVisiblePlayerWithAmmo Ataca al jugador visible m´as cercano usando su arma con m´as munici´on. attackNearestVisiblePlayerWithDamage Ataca al jugador visible m´as cercano usando su arma que provoque m´as da˜no. attackNearestPlayerWithSpeed Ataca al jugador m´as cercano usando su arma m´as r´apida. attackNearestPlayerWithAmmo Ataca al jugador m´as cercano usando su arma con m´as munici´on. attackNearestPlayerWithDamage Ataca al jugador m´as cercano usando su arma que provoque m´as da˜no. attackRandomVisiblePlayerWithAccuracy Ataca a un jugador visible aleatoriamente usando su arma m´as precisa. attackRandomVisiblePlayerWithDamage Ataca a un jugador visible aleatoriamente usando su arma que provoque m´as da˜no. attackFurthestVisiblePlayerWithAccuracy Ataca al jugador visible m´as lejano usando su arma m´as precisa. attackFewerDeathsPlayerWithSpeed Ataca al jugador que tenga menos muertes usando su arma m´as r´apida. attackFewerDeathsPlayerWithAmmo Ataca al jugador que tenga menos muertes usando su arma con m´as munici´on. attackFewerDeathsPlayerWithDamage Ataca al jugador que tenga menos muertes usando su arma que provoque m´as da˜no. attackMostDeathsPlayerWithSpeed Ataca al jugador que tenga m´as muertes usando su arma m´as r´apida. attackMostDeathsPlayerWithAccuracy Ataca al jugador que tenga m´as muertes usando su arma m´as precisa. attackMostDeathsPlayerWithDamage Ataca al jugador que tenga m´as muertes usando su arma que provoque m´as da˜no. Tabla 3.4: Acciones simples. Una vez que se tienen las 21 acciones simples, que conformar´an las hojas de los ´arboles de comportamiento, hay que determinar que comportamientos van a crearse. Con 21 acciones simples, las combinaciones posibles de comportamientos crecen exponencialmente por lo que en este caso la mejor opci´on era ir a buscar agrupaciones interesantes y variadas, ya que reducir de manera l´ogica todas las opciones obtenidas era impensable ( ∼21 ∼5∗1019 sin contar con que la forma 20 de colocar las acciones, tambi´en puede modificar los resultados). Finalmente se lleg´o a la conclusi´on de tener 2 formas diferentes de recolectar objetos para comprobar cu´al de las dos era mejor (si recoger elementos de salud, escudo y armamento, o recoger elementos de salud/escudo y armamento) y 4 formas de ataque (para armas r´apidas, armas con mucho da˜no, armas con mucha munici´on y una mezcla de ataques arriesgados, como, por ejemplo, atacar al m´as lejano o al que m´as muertes lleva asignadas). Adem´as para tener mayor variedad de comportamientos se establecieron dos grupos de comportamientos, de ataque y defensivos, dentro de los cuales hay peque˜nas variaciones, pero que no afectan al dise˜no del ´arbol, ´unicamente sirven para determinar si dentro de un comportamiento de ataque hay que ser m´as o menos agresivo, o si en un comportamiento defensivo hay que ser muy cauto o no es necesario serlo tanto. Un ejemplo de ´arbol de comportamiento es el de la Figura 3.3. Figura 3.3: ´ Arbol de comportamiento. El conjunto de todos los ´arboles (16 en total) se encuentran en el Anexo “´ Arboles de comportamiento”. En total si sumamos los diferentes comportamientos tenemos 16 posibilidades (56 si atendemos a las leves modificaciones dentro de cada grupo), que se reparten entre las 112 situaciones de entorno prefijadas para formar parte de la memoria del bot. Con esta cantidad de casos se asegura que exista una amplia gama de posibles soluciones (tanto defensivas, como de ataque) para entornos similares. Con todos estos elementos establecidos ya tenemos el SomaticMarkerBot creado y dispuesto a pasar por una bater´ıa de experimentos que intentar´an demostrar si es ´util usar un sistema CBR en videojuegos de respuesta r´apida como UT2004. 21 22 Cap´ıtulo 4 Dise˜no de Experimentos y Resultados Los experimentos se han desarrollado con dos objetivos en mente: (1) probar si las t´ecnicas aplicadas en este proyecto son adecuadas para el manejo de bots y una vez conseguido, (2) obtener un patr´on de comportamiento gen´erico que muestre la mejor estrategia de actuaci´on de un bot independiente de las condiciones concretas en el entorno del videojuego utilizado. En esta secci´on se dar´a una explicaci´on de los par´ametros que componen cada configuraci´on experimental, se mostrar´an los resultados de cada experimento discutiendo sus resultados y se establecer´an unas conclusiones globales a partir de ellos. El objetivo es obtener un patr´on de comportamiento universal para un bot cualquiera en el entorno del videojuego Unreal Tournament. 4.1. Par´ametros de los experimentos Para cada experimento se han establecido unas condiciones fijas de la partida (Tabla 3.3). Adem´as hay tres condiciones que var´ıan a lo largo de los experimentos y que son las que permiten obtener variedad de resultados. Estas tres condiciones son: la ventana de trabajo, la m´etrica de selecci´on de caso y la m´etrica “premio/castigo”. 4.1.1. Ventana La ventana de trabajo simboliza los elementos de la base de casos que est´an visibles para el bot, o sea, en la ventana de trabajo se encontrar´an los casos que los “marcadores som´aticos” del bot hayan determinado como casos v´alidos. Como ya se ha visto, el marcador que utiliza el bot y que permite ordenar la lista de experiencias es el valor de adaptabilidad que “mide” si un caso ha sido bueno o malo previamente. En estos experimentos se va a trabajar con ventanas de 5, 25 y 50 casos. 4.1.2. M´etricas de selecci´on de caso Se utilizan para elegir un ´unico caso entre los situados en la ventana de trabajo. Despu´es de seleccionar una serie de casos (ventana), esta m´etrica se encarga de determinar cu´al de ellos es el m´as id´oneo en la situaci´on actual. Cuantos m´as par´ametros se tengan en cuenta en esta m´etrica m´as discriminativa ser´a la elecci´on, ya que habr´a m´as variedad en los valores de elecci´on de caso. El m´as id´oneo ser´a aquel que difiera menos de la situaci´on actual. Son utilizadas cuatro m´etricas. 23 M´etrica 1 Tiene en cuenta a todas las variables de entorno que controla el bot. Cada variable de entorno (secci´on 3.2) del caso que se est´a probando se compara con el valor de la misma variable de entorno en el momento actual y se multiplica por un valor, que junto al rango de valores que puede tener cada variable de entorno, determina la importancia que tiene. dtw = 10 * ∆(DeathsToWin_caso, DeathsToWin_actual).1 p=45*∆(People_caso, People_actual).2 e = 3 * ∆(EndGame_caso, EndGame_actual).3 ar = 5 * ∆(Armor_caso, Armor_actual).4 am = 30 * ∆(Ammo_caso, Ammo_actual).5 he = 10 * ∆(Health_caso, Health_actual).6 my = 10 * ∆(MyDeaths_caso, MyDeaths_actual).7 s=15*∆(Sensors_caso, Sensors_actual).8 nw = 3 * ∆(NWeapons_caso, NWeapons_actual).9 na = 30 * ∆(NAmmos_caso, NAmmos_actual).10 valor_idoneidad = dtw + p + e + ar + am + he + my + s + nw + na. M´etrica 2 Tiene en cuenta las muertes que quedan para ganar la partida (DeathsToWin). Premia matar enemigos lo antes posible. valor_idoneidad = 10 * ∆(DeathsToWin_caso, DeathsToWin_actual). M´etrica 3 Tiene en cuenta las muertes que ha sufrido el bot (MyDeaths). Da preferencia a no sufrir muertes, antes que a matar enemigos. valor_idoneidad = 10 * ∆(MyDeaths_caso, MyDeaths_actual). M´etrica 4 Tiene en cuenta las muertes que quedan para ganar (DeathsToWin), las muertes sufridas (MyDeaths) y la salud del bot (Health). Busca un equilibrio a las dos m´etricas anteriores. dtw = 10 * ∆(DeathsToWin_caso, DeathsToWin_actual). he = 10 * ∆(Health_caso, Health_actual). my = 10 * ∆(MyDeaths_caso, MyDeaths_actual). valor_idoneidad = dtw + he + my. 1[0, 250] 2[0, 45] 3[0, 180] 4[0, 150] 5[0, 30] 6[0, 1000] 7[0, 250] 8[0, 45] 9[0, 24] 10[0, 30] 24 4.1.3. M´etricas “premio/castigo” Se encargan de valorar si un comportamiento ha sido bueno o malo. Dependiendo del modo en que se premie o castigue al bot, cambia su modelo de aprendizaje. Con una mala m´etrica “premio/castigo” el bot no aprender´a satisfactoriamente y no lograr´a los objetivos. Solo se tienen en cuenta tres de las variables de entorno: DeathsToWin, MyDeaths, Health. Las m´etricas utilizadas son tambi´en tres. Matar siempre Premia matar cuantos m´as rivales mejor y castiga severamente no matar a nadie. dea = ∆(MyDeaths_inicioComport, MyDeaths_finalComport). kil = 1.2 * ∆(DeathsToWin_inicioComport, DeathsToWin_finalComport). extra = -2 sino mata. hea = (∆(Health_inicioComport, Health_finalComport))/100. NuevaAdaptabilidad = (Antigua - dea + kil + hea + extra)/10. Evitar muerte, pero actuando Premia al bot para que no le maten, pero sigue penalizando que no mate, aunque no tanto como la anterior. dea = 1.2 * ∆(MyDeaths_inicioComport, MyDeaths_finalComport). kil = ∆(DeathsToWin_inicioComport, DeathsToWin_finalComport). extra = -0.2 sino mata. hea = (∆(Health_inicioComport, Health_finalComport))/100. NuevaAdaptabilidad = (Antigua - dea + kil + hea + extra)/10. Evitar muerte huyendo Premia al bot para que no le maten, incluso evitando siempre que se pueda una confrontaci´on. No matar a otro bot y que no le maten a uno mismo, es considerado muy positivo. dea = 1.2 * ∆(MyDeaths_inicioComport, MyDeaths_finalComport). kil = ∆(DeathsToWin_inicioComport, DeathsToWin_finalComport). extra1 = + 2 sino mata. extra2 = + 2 sino le matan. hea = (∆(Health_inicioComport, Health_finalComport))/100. NuevaAdaptabilidad = (Antigua - dea + kil + hea + extra1 + extra2)/10. 4.2. Experimentos 4.2.1. Experimento 1 En el primer ejemplo se utilizan unas condiciones de partida para tener una referencia en futuros experimentos. A partir de ah´ı el resto de ejemplos llevar´an al l´ımite las condiciones de experimentaci´on, la ventana (secci´on 4.1.1) y las m´etricas (secciones 4.1.2 y 4.1.3) buscando la mejor manera de aprovechar al m´aximo la t´ecnica CBR sin perder de vista los objetivos de ganar partidas con el mayor ´exito posible y de obtener el patr´on ´optimo de juego. 25 Figura 4.14: Comportamientos de ataque y defensa Figura 4.15: Recoger objetos y Tipos de ataque Figura 4.16: Inicio base de casos Las dos m´etricas “premio/castigo” probadas parece que son adecuadas pero ser´ıa interesante comprobar si con una m´etrica que variara mucho del objetivo final (matar enemigos) se consiguen igualmente resultados ´optimos. 4.2.5. Experimento 5 Este experimento intenta cambiar radicalmente la m´etrica “premio/castigo” (secci´on 4.1.3). Ahora premia que al bot no le maten, pero tambi´en que evite enfrentamientos, algo totalmente opuesto a la mec´anica del juego. El resto de condiciones siguen siendo las consideradas ´optimas. Condiciones Tama˜no de ventana: 25 casos. M´etricas para elegir caso: M´etrica 1. M´etrica premio/castigo: Evitar muerte huyendo. 32 Discusi´on Con este cambio radical de m´etrica “premio/castigo” lo primero que se puede observar r´apidamente es que el objetivo de ganar las partidas no se cumple (10 25 muertes por partida y 0 20 victorias). Esto es debido a que la nueva m´etrica va en contra de la esencia del juego. Si la clave de este juego es conseguir m´as muertes que el rival y se tiene una m´etrica que premia huir del enemigo y no atacar, es esperable que suceda lo que se ve en la Figura 4.17. Figura 4.17: Victorias del bot Otra de las conclusiones que arroja este experimento es el hecho de que los comportamientos defensivos no son ´utiles para este tipo de juegos. En la Figura 4.18 y Figura 4.19 se observa c´omo los comportamientos defensivos son mayoritarios. Figura 4.18: Comportamientos de ataque y defensa Figura 4.19: Inicio base de casos De la segunda gr´afica de la Figura 4.20 se extrae que las armas m´as r´apidas son las que m´as veces se usan en los comportamientos defensivos, pero como el objetivo final del juego (ganar) nose ha producido se puede concluir que no es la mejor forma de elegir armas aunque inicialmente se haya podido pensar lo contrario. 33 Figura 4.20: Recoger objetos y Tipos de ataque 4.3. Ideas generales Despu´es de esta extensa colecci´on de experimentos se pueden extraer unos principios o ideas generales para los usuarios de este tipo de juegos, ya sea dise˜nando bots o jugando en persona. 1. El comportamiento que llevar´a a un bot o a un jugador a ganar partidas se debe basar en atacar de“manera muy agresiva”. Se entiende como“manera muy agresiva”, el hecho de atacar siempre que se pueda, aunque a la vez se sufran m´as ataques, ya que lo m´as importante, antes que evitar ataques, es estar en constante b´usqueda de enemigos enfrent´andose a ellos. 2. La mejor manera de atacar, como se ha podido constatar, es llevando el arma que m´as da˜no produzca. Esto ir´ıa en contra de una intuici´on previa que llevar´ıa a pensar que un arma r´apida es m´as ´util en un entorno tan r´apido y cambiante como es el del Unreal Tournament 2004. 3. La tercera idea clave es que la forma de recoger objetos en el juego no es significativo para su resultado. El bot ganador no debe preocuparse de recoger los objetos de salud y escudo por separado o a la vez. Solo de atacar y, cuando tiene problemas de salud o de arma, ir en busca del elemento m´as cercano. 4. Vistas las comparaciones entre m´etricas de selecci´on de caso y los resultados obtenidos en las Figuras 4.4, 4.5, 4.12, 4.16 y 4.19 y su respectivas tablas extendidas del Anexo L, se puede establecer que no existen grandes diferencias entre unas m´etricas y otras. Es de destacar, sin embargo que, la m´etrica 1 de selecci´on (que usa las 9 variables de entorno que controla el bot), al tener m´as variables para valorar los casos, puede elegir sin tener varios casos con el mismo valor. En esta situaci´on, el valor de adaptabilidad determina cu´al es el mejor. Centr´andose m´as en la t´ecnica CBR, se puede extraer la conclusi´on de que la ventana de trabajo, que criba inicialmente los casos, debe ser de un tama˜no medio (25 casos, aprox.) para evitar usar los peores casos (ventanas grandes, 50 casos, aprox.) y para evitar que haya poco margen para imprevistos si la situaci´on del entorno cambia radicalmente (ventanas peque˜nas, 5 casos, aprox.). Lo importante de esta t´ecnica es que ofrece la posibilidad de tener una gran variedad de casos para diversas situaciones y que aquellos que han obtenido peores resultados son desterrados antes de hacer la elecci´on, por lo que el tama˜no de ventana medio ofrece un punto de equilibrio entre la gran variedad de casos y la criba de casos peor valorados. Por ´ultimo, viendo los resultados del experimento 5, se puede constatar que los algoritmos usados en este proyecto son adecuados. Inicialmente se podr´ıa pensar que las diferentes estrategias no tendr´ıan gran reflejo en los resultados, que podr´ıan ser muy parecidos, pero con este ´ultimo experimento ha quedado demostrado que si las m´etricas elegidas no siguen la mec´anica del juego los resultados no llevan al bot a su objetivo fundamental (ganar partidas). 34 Cap´ıtulo 5 Conclusiones y valoraci´on personal Este cap´ıtulo contiene las conclusiones extra´ıdas durante el proceso de realizaci´on de este Proyecto Final de Carrera y unas propuestas de posibles l´ıneas de trabajo futuro. Al final se presenta una valoraci´on de lo que su realizaci´on ha supuesto a nivel personal. 5.1. Conclusiones A lo largo de este proyecto se ha realizado un estudio acerca de si un sistema CBR basado en la hip´otesis de los “marcadores som´aticos” podr´ıa ser ´util en el control de un bot. Este estudio se basaba en la idea de que el ser humano, en condiciones de toma de decisi´on, toma sus decisiones en funci´on de unas experiencias pasadas y esas experiencias reducen las opciones disponibles antes de iniciar un proceso de deliberaci´on. Para ello, se ha seguido un proceso riguroso consistente en estudiar las herramientas disponibles, desarrollar el SomaticMarkerBot con sus comportamientos y establecer una serie de experimentos que probaran si los objetivos finales se hab´ıan conseguido. A continuaci´on se va a comentar el proceso seguido en la realizaci´on del proyecto, resumiendo las partes m´as importantes y mostrando un resumen de las conclusiones que se han ido extrayendo, finalizando con un an´alisis final, con el que se pretende determinar si la hip´otesis de trabajo planteda en 1.1 se ha conseguido. Estudio de herramientas Esta fase sirvi´o para familiarizarse con las herramientas y con la l´ınea de investigaci´on planteada. El trabajo desarrollado durante este periodo consumi´o unas 80 horas (16 % del trabajo global) de las dedicadas al proyecto, lo que demuestra la importancia que ha tenido en este caso la familiarizaci´on con el entorno. Las dos herramientas usadas, aparte del juego, en este proyecto han sido la plataforma Pogamut y el gestor de bases de datos SQLite. La plataforma Pogamut como se comenta en la secci´on 2.1, es un conjunto de librer´ıas que permiten establecer la comunicaci´on con el videojuego Unreal Tournament 2004, sin necesidad de aprender a manejar su lenguaje de scripting (UnrealScript1), ni su sistema de comunicaci´on, ya que con estas librer´ıas se pueden crear bots del juego en java. 1http://en.wikipedia.org/wiki/UnrealScript 35 Despu´es de haber trabajado con esta plataforma se puede decir que a´un es muy incompleta. Los autores de dichas librer´ıas son los mismos que explican su funcionamiento en [17]. Durante el desarrollo del proyecto hemos pasado de la versi´on 2.0, muy simple, a la versi´on 3.1, bastante m´as completa, pero sin excesivos comentarios en el c´odigo que lo hiceran entendible. Aun as´ı, una vez que se adapt´o el sistema a nuestro proyecto, se pudo comprobar (secci´on 2.1.1) c´omo los pasos para construir un bot son bastante b´asicos al tener ´unicamente cuatro clases principales: (1) UT2004BotRunner que se encargar de lanzar el thread del bot; (2) PogamutException que maneja todas las excepciones que puedan surgir en el c´odigo; (3) UT2004BotModuleController (secci´on 2.1.1) que contiene el controlador principal del juego; y (4) WorldView (secci´on 2.1.1) que controla los eventos que se producen en el entorno del juego. Al crear el bot se empieza a entender, finalmente, c´omo funciona el sistema, especialmente las clases UT2004BotModuleController y WorldView. Como se puede ver en los apartados UT2004BotModuleController y WorldView (completado en Anexo G) de la secci´on 2.1.1, dichas clases manejan todo el conjunto de movimientos, de ataques y de memoria del bot, facilitando su uso, ya que sin estas librer´ıas de Pogamut, la comunicaci´on del bot con el juego se realizar´ıa por mensajes s´ıncronos y as´ıncronos. Estos mensajes s´ıncronos y as´ıncronos, en Pogamut est´an contenidos en clases individuales (Anexo F) que permiten a UT2004BotModuleController y WorldView tratar con ellos de una manera simple. Por eso se puede afirmar que el principal problema de trabajar con esta plataforma ha sido su constante cambio y su falta de documentaci´on, pero que una vez comprendida, ha resultado m´as c´omodo crear nuevos datos a partir de los existentes, siempre y cuando la comunicaci´on entre Pogamut y el sistema fuera correcta, ya que m´as de una vez los datos pedidos al entorno eran devueltos incompletos o err´oneos. El gestor de bases de datos SQLite (secci´on 2.2) es un gestor muy simple y r´apido en tiempos de ejecuci´on. No funciona como una base de datos cliente-servidor, sino que el motor enlaza con el programa reduciendo su tiempo de latencia. Despu´es de analizarlo se puede confirmar que la velocidad de la que hace gala consigue que las entradas/salidas de la base de datos no interfieran en la partida. El ´ultimo paso en este estudio de herramientas se dedic´o a probar si se podr´ıan usar algunas herramientas “pre-fabricadas” que facilitaran el trabajo, especialmente en la metodolog´ıa del sistema CBR. En la secci´on 2.3 se muestran las herramientas consultadas. Se pudo concluir que aunque las ideas de alguna de ellas (jColibri2) eran bastante interesantes, introducir una nueva herramienta al sistema supon´ıa ralentizar el proceso. En un entorno en “tiempo real” (0.25 segundos de ciclo de ejecuci´on), como el de este juego, se necesitan las m´ınimas herramientas posibles, por este motivo se desech´o especialmente el uso de jColibri2, el cual ofrecia una metodolog´ıa completa de un sistema CBR. Desarrollar SomaticMarkerBot Despu´es de seleccionar estas herramientas, se llev´o a cabo el desarrollo del personaje (40 % del trabajo global), siguiendo los siguientes pasos: (1) se establecieron las condiciones en las que se iba a desarrollar la partida; (2) se determinaron qu´e variables de entorno iban a dar informaci´on al bot; y (3) se organiz´o la base de comportamientos del bot. Durante la selecci´on de condiciones de la partida (secci´on 3.1) se han regulado las variables que pod´ıan controlarse desde el servidor antes de lanzar una partida. Despu´es de haber elegido aquellas m´as adecuadas se puede asegurar que el n´umero de participantes elegido y el nivel de los rivales ha sido el adecuado puesto que han permitido evolucionar al bot, dejandole ganar una gran cantidad de partidas. Con un n´umero distinto de bots o con diferentes niveles en los bot, estos no ganaban (por lo tanto no ten´ıan casos valorados como positivos), o ganaban muy f´acilmente (impidiendo un buen eso del sistema CBR). 36 Con las variables de entorno ha habido un gran problema de dimensionalidad. Un bot recibe m´as de 100 potenciales inputs de informaci´on del entorno (Anexo H) de las cuales la mayoria son datos superfluos o demasiado t´ecnicos (velocidad de giro del bot en el aire, gravedad en el entorno actual...). Finalmente en la secci´on 3.2 se muestran las 9 variables de entorno elegidas, consideras como primordiales: muertes para ganar, si ve enemigos, tiempo para terminar, cantidad de escudo, salud y munici´on actual, muertes sufridas, n´umero de armas en el inventario, cantidad de munici´on de dichas armas y controladores de estado (si ha muerto recientemente o ve un proyectil cerca). Estas variables permiten tener un control simple pero completo de la escena y el bot conoce todos sus signos vitales (salud, armas...) y lo que m´as le interesa del entorno (ver enemigos, ver proyectiles...). Uno de los mayores problemas ha sido seleccionar cu´ales de las m´as de 100 informaciones recibidas se deb´ıan utilizar (hasta solo 9). Los diferentes comportamientos del bot supusieron la parte fundamental del desarrollo. Inicialmente se pens´o que los comportamientos deber´ıan ser din´amicos, pero una vez entendido el sistema y la informaci´on que facilitaba el juego, se vio claramente que no era posible, por lo que una parte fundamental del sistema CBR se tuvo que modificar. Por este motivo se entendi´o que hab´ıa que crear los comportamientos desde el inicio y lo m´as variados posible para que dieran al bot el m´aximo dinamismo posible. En la secci´on 3.3 se muesta c´omo funciona el sistema CBR en el SomaticMarkerBot, y como la hip´otesis de los “marcadores som´aticos” se ve reflejada. El proceso es el mismo que un sistema CBR t´ıpico (secci´on 1.3.1) salvo que los casos no se modifican ni retocan en ning´un momento ya que los comportamientos son pre-establecidos. Lo ´unico que hace variar la posici´on de un caso en la memoria del bot son sus experiencias pasadas, y tal como se explica en la secci´on 3.3, el valor de adaptabilidad es el encargado de evaluar esas experiencias. Dicho valor de adaptabilidad ser´ıa el “marcador som´atico” que determina lo bueno o malo que es un caso. Con los comportamientos se tom´o la decisi´on de que fueran ´arboles binarios y que a partir de las informaciones que se reciben del entorno, se fueran desplazando hacia las hojas, donde se encuentran las “acciones simples”. Como se explica en la secci´on 3.3.1 las “acciones simples” son las que determinan que va a hacer el bot a m´as bajo nivel (andar, huir, atacar, recoger objetos). Estas acciones simples tambi´en son muy extensas, ya que no hay una ´unica forma de atacar o de huir. El conjunto total de posibles combinaciones (Anexo J) se redujo a un n´umero mucho menor: 21 (Tabla 3.4). Con esta simplificaci´on se han generado los comportamientos. ´ Estos tambi´en han tenido que reducirse, porque con el n´umero de niveles y de hojas de un ´arbol variable, se podian llegar a generar ∼5∗1019 comportamientos distintos y eso sin tener en cuenta que el orden de las ramas y hojas del ´arbol tambi´en generar´ıa algunos m´as. Finalmente se llego a la decisi´on de crear 16 tipos de ´arboles de comportamiento (Anexo K), los cuales se podr´ıan diferenciar por: 2 formas diferentes de recoger objetos (salud, escudo y armamento, o salud/estudo y armamento), 4 formas de ataque (para armas r´apidas, armas con mucho da˜no, armas con mucha munici´on y una mezcla de ataques arriesgados, como, por ejemplo, atacar al m´as lejano o al que m´as muertes lleva asignadas). Adem´as, para tener mayor variedad de comportamientos se establecieron dos grupos diferentes, de ataque y defensivos. Dentro de estos tipos de comportamientos hay divisiones internas: Para los comportamientos de ataque existen tres variedades que van desde los poco agresivos (atacan con velocidad normal y sin correr), hasta los muy agresivos (atacan con velocidad m´axima y corriendo siempre) y para los comportamientos defensivos se describieron cuatro variedades que iban desde los poco precavidos (tiene la misma preferencia entre huir y atacar), hasta los muy precavidos o huidizos (intenta huir siempre de sus enemigos, salvo que la situaci´on sea muy favorable). En conclusi´on, el desarrollo de los comportamientos nos plante´o el problema de que deb´ıan ser determinados antes de empezar y que hab´ıa muchas variables que reducir hasta tener un conjunto de datos manejable. La ventaja es que si se aprovecha las experiencia de jugadores expertos al crearlos, se elimina aquella fase de un sistema CBR donde casi siempre tiene que participar un ser humano, la revisi´on. 37 Experimentos Una vez el bot estaba construido, se han dise˜nado experimentos que demostraran si los objetivos iniciales se cumpl´ıan. Estos experimentos ten´ıan tres condiciones que variaban de uno a otro buscando diversas condiciones para las pruebas: (1) ventana de trabajo (secci´on 4.1.1) que contiene los primeros N casos ordenados por el valor de adaptabilidad; (2) m´etricas de selecci´on de caso (secci´on 4.1.2) que se encargan de elegir un ´unico caso entre los situados en la ventana; y (3) m´etricas de “premio/castigo” (secci´on 4.1.3) que se encargan de valorar si un comportamiento ha sido bueno/malo modificando su valor de adaptabilidad. Cada experimento tiene su propia ventana de trabajo y su propia m´etrica “premio/castigo” y dentro de cada experimento var´ıa la m´etrica de selecci´on de caso para establecer las comparaciones entre ellas. Tras la evaluaci´on de dichos experimentos se pueden extraer un conjunto de conclusiones, tal como se se˜nalan a continuaci´on: Seg´un lo visto en el experimento 1 (secci´on 4.2.1: ventana de 50 casos y m´etrica premio/castigo centrada en“matar siempre”) , el uso de una ventana de 50 casos sobre los 112 posibles provoca que casos valorados como negativos no desaparezcan de la ventana de trabajo por lo que se siguen usando y ralentizan al bot en su objetivo de conseguir victorias (aun as´ı consigue una media de 13 20 victorias), y casos valorados como positivos no se usan tanto como deber´ıan. La m´etrica de “matar siempre” provoca que el mejor comportamiento sea el de ataque agresivo. Tambi´en se observa, desde este primer experimento, que las dos opciones para recoger objetos resultan indiferentes para el bot. El experimento 2 (secci´on 4.2.2: ventana de 25 casos y m´etrica premio/castigo centrada en “matar siempre”) demuestra que una ventana de trabajo m´as reducida que la anterior consigue que los casos peor valorados desaparezcan de la ventana, de este modo los resultados son mejores (15 20 victorias) y m´as fiables porque en el momento de elegir un caso los ´unicos que se encuentran en la ventana son aquellos mejor valorados. Con este experimento se observa un indicio bastante fiable de que los comportamientos de ataque muy agresivos y las armas que provocan m´as da˜no son las mejores opciones de juego. El experimento 3 (secci´on 4.2.3: ventana de 5 casos y m´etrica premio/castigo centrada en “matar siempre”) incide en el hecho de seguir reduciendo la ventana de trabajo. Los resultados son enga˜nosos ya que muestran que el resultado final este experimento es el mejor de todos (19 20 victorias), pero con una ventana de 5 casos el bot est´a desprotegido ante un cambio radical de situaciones o escenario, puesto que los mejores casos tardar´ıan mucho en reducir su valor para dar entrada a nuevos casos en la ventana. El cuarto experimento (secci´on 4.2.4: ventana de 25 casos y m´etrica premio/castigo centrada en“evitar muerte, pero actuando”) demuestra que un forma de premiar al bot menos agresiva que las anteriores (“matar siempre”) sigue funcionando igual o mejor (16 20 victorias) que en el experimento 2. Incluso los comportamientos se mantienen igual de agresivos aunque no se les premie tanto, como en los experimentos anteriores. La forma de recoger objetos sigue dependiendo de otros factores y la mejor forma de atacar es con las armas que m´as da˜no causan, evitando en todo momento el resto de combinaciones, incluida la de armas r´apidas que inicialmente eran consideradas la mejor opci´on. El ´ultimo experimento (secci´on 4.2.5: ventana de 25 casos y m´etrica premio/castigo centrada en “evitar muerte huyendo”) demuesta que, si en los casos anteriores con m´etricas de ataque (“matar siempre” y “evitar muerte, pero actuando”) el bot ganaba partidas, con una m´etrica opuesta, priorizando lo defensivo, el bot es incapaz de ganar ( 0 20 victorias, 10 25 muertes por partida), debido a la m´etrica opuesta a la esencia del juego (conseguir m´as muertes que los rivales). 38 Hip´otesis de trabajo: ¿conseguida? Como resumen de esos experimentos se obtienen estas conclusiones que determinan que los objetivos iniciales se cumplen, tal como se se˜nala a continuaci´on: El sistema CBR y la hip´otesis de los “marcadores som´aticos” es muy ´util en el control de bots en entornos cambiantes. La base de casos se va acomodando a las situaciones que surgen y permiten que el bot con las condiciones de partida establecidas inicialmente, acabe ganando las partidas sea cual sea la situaci´on presenciada. Esta conclusi´on muestra la importancia que pueden tener este tipo de sistemas en la creaci´on de bot m´as humanos. Superando algunas limitaciones (modificaci´on de comportamientos en tiempo de ejecuci´on y movimientos menos mec´anicos) este sistema podr´ıa ser el futuro en la creaci´on de bots, dada su f´acil adaptaci´on a entornos cambiantes. Tambi´en se han obtenido conclusiones claras sobre cu´ales son las mejores condiciones de un bot para ganar partidas. Los bots que van al ataque con el arma que m´as da˜no cause tienen un mayor porcentaje de probabilidades de ganar las partidas (77,5 % de victorias entre el experimento 2 y 4), siempre y cuando las m´etricas elegidas para premiar/castigar al bot sea coherente con la mec´anica del juego (conseguir m´as muertes que los rivales). La forma de atacar siempre debe ser la m´as agresiva de todas (corriendo y a m´axima velocidad), incluso aunque la m´etrica “premio/castigo” favorezca m´as las actitudes menos agresivas. Las armas que m´as da˜no causan en todo momento se consideran como la mejor opci´on, aunque inicialmente dada la mec´anica del juego se pudiera pensar que las armas m´as r´apidas pudieran ser mejores. La forma de recoger objetos resulta indiferente, ya que el bot se preocupa, ´unica y exclusivamente, de atacar. Las m´etricas de selecci´on de caso no establecen grandes diferencias por las que decantarse entre unas y otras, lo importante es que cuando dos casos tengan la misma importancia en una situaci´on se elija el que las experiencias pasadas tenga considerado como mejor (valor de adatabilidad m´as alto). 5.2. Trabajo o l´ıneas futuras Tras la realizaci´on de este proyecto se proponen a continuaci´on algunas de las posibles l´ıneas de trabajo futuras: Tener en cuenta m´as variables de entorno, especialmente aquellas consideradas de nivel de avanzado ya que podr´ıan mejorar los resultados. Conocer la invulnerabilidad de los rivales (no es recomendable atacar a un rival que sea invulnerable). Si el bot es invulnerable puede atacar con m´as frecuencia de lo est´andar. Determinar en qu´e tipo de suelo se encuentra, no es lo mismo estar en el agua que en tierra firme. Conocer la velocidad de movimientos, la gravedad y cualquier otro elemento f´ısico del entorno que ayude a comprender mejor por donde se mueve el bot. A˜nadir alguna t´ecnica de IA, especialmente a las acciones simples, para que los movimientos del bot sean m´as humanos. Trabajar con las nuevas actualizaciones de Pogamut, las cuales permiten obtener m´as y mejores datos, de esta manera se podr´ıa depurar el c´odigo obteniendo seguramente mejores resultados, especialmente en lo referente a movimientos y disparos del bot. 39 Conseguir la modificaci´on en tiempo real de los comportamientos, en vez de tenerlos definidos e inalterables (salvo la adaptabilidad) desde el inicio. De esta manera se podr´ıan crear nuevos comportamientos o modificar los existentes y tener una base de casos m´as evolucionada en el tiempo. Introducir nuevas hip´otesis interesantes derivadas de las ya existentes. Como es el caso de la “serendipia”, malas decisiones que traen buenos resultados [19]. 5.3. Valoraci´on personal El balance general al realizar este proyecto ha sido positivo. La posibilidad de realizar un proyecto completo de principio a fin me ha permitido tener una visi´on global de las partes que ´este entra˜na. Se han podido poner en pr´acticas bastantes cosas aprendidas durante la carrera, sobre todo en el aspecto de desarrollo de proyectos. La posibilidad de descubrir nuevas t´ecnicas de inteligencia artificial, que hoy en d´ıa est´an muy presentes, ha servido para comprender que aunque estamos muy lejos de conseguir robots de apariencia “humana” se avanza en una l´ınea muy prometedora, ya que como se puede ver en las conclusiones del proyecto, la aplicaci´on de estas t´ecnicas sirven para adaptar el bot a cualquier entorno, algo considerado genuinamente humano. Respecto a las dificultades encontradas en el desarrollo de este proyecto considero que ha habido dos dificultades principalmente: (1) comprender herramientas hechas por otras personas sin una documentaci´on adecuada y en constante evoluci´on y, (2) reducir el entorno a un espacio de trabajo limitado sin perder la globalidad del entorno. 40 Glosario Juegos de aventuras: En este g´enero, el usuario se mete en la piel de un personaje que debe avanzar a trav´es de una o varias tramas que conforman la historia del juego. Juegos de deportes: Abarcan una gran cantidad de deportes (reales y ficticios) en los que el usuario compite por ser el mejor en diversas competiciones. Juegos educativos: Tienen como objetivo prioritario potenciar alg´un aspecto pedag´ogico. Suelen ir orientados al p´ublico m´as joven. Juegos de estrategia: Son aquellos en los que el usuario se encarga de gestionar un gran n´umero de recursos de forma simult´anea para la consecuci´on de los objetivos. La acci´on de todos los usuarios puede realizarse en tiempo real (todos al mismo tiempo, RTS) o por turnos (cada usuario tiene un marco de tiempo para realizar una acci´on mientras los dem´as esperan su turno). Suelen ser juegos de gesti´on (control de parques, hospitales, etc) o b´elicos. Juegos de shooter: Juegos de car´acter b´elico en los que el objetivo del usuario es abrirse camino a trav´es del juego disparando a todo jugador que se ponga a tiro. Juegos de lucha: G´enero en el que los combates cuerpo a cuerpo cobran especial protagonismo. Juegos de “Mesa”: Esta categor´ıa est´a compuesta por todos aquellos videojuegos encargados de emular los tradicionalmente conocidos como “juegos de mesa”, juegos f´ısicos que cuentan con un tablero y fichas (ajedrez, mahjong, etc). Juegos de “Party”: Este tipo de juegos se centra en el entretenimiento en grupo. Normalmente se utiliza un modo de juego por turnos, en el que gana el usuario que mayor puntuaci´on consiga al cabo de un n´umero determinado de etapas. Juegos de plataformas: Es una de las categor´ıas m´as antiguas. El usuario encarna a un jugador que avanza por un mundo en el que debe saltar, correr y alcanzar determinados elementos repartidos por el entorno si quiere alcanzar su objetivo. Los hay tanto bidimensionales como tridimensionales, pero los juegos de culto de este g´enero son del tipo 2D. Juegos de rol: En ellos, el usuario representa un papel y debe interactuar con el entorno y el resto de jugadores del videojuego para poder mejorar sus caracter´ısticas. Juegos de simulaci´on: Este tipo de juegos se encargan de reproducir una escena cotidiana (cuidar una mascota, conducir un determinado tipo de veh´ıculo, dirigir la vida de un personaje, etc.). NPC: Siglas del t´ermino ingl´es “Non-Player Character”. Utilizado como sin´onimo de bot y agente aut´onomo. RTS: Siglas del t´ermino ingl´es “Real-time Strategy”. Son videojuegos de estrategia en los que no hay turnos sino que el tiempo transcurre de forma continua para los jugadores. 41