Tras mucho tiempo sin actualizar esta triste bitácora ha llegado el momento de dotarla de nuevo y jugoso contenido. El tema de hoy es un nuevo capítulo sobre mi proyecto de fin de carrera, si, aquél que empecé a dar vueltas hace más de dos años y que me quita el sueño y la vida desde entonces.
Para abrir boca hoy le proporcionaremos conocimiento a mi pequeña amiga traga bolas. Bueno, para quien no la conozca, os presento a la señorita pacman. Es una muchachita dulce y asustadiza a la que le dan miedo los fantasmas pero que puede llegar a ponerse muy agresiva si abusa de las pastillas. Aunque la pobre tiene un problema, no sabe ir a ninguna parte sin que alguien le indique el camino. Se podría decir que es un poco despistada y que se desorienta con facilidad. Así que me he propuesto enseñarle una serie de reglas para que pueda desenvolverse por sí misma.
Objetivo
El algoritmo elegido para controlar a Ms. Pacman está basado en ICE Pambush 3, presentando en el CIG2009 por Takashi Ashida, Takeru Miyama, Hiroshi Matsumoto, y Ruck Thawonmas, miembros de la Ritsumeikan University en Japón. Ellos fueron los ganadores de la competición en dicho congreso y son los actuales poseedores del record mundial, es por ello que he decidido homenajearlos llamando a mi algoritmo Emboscada Helada.
El objetivo del juego es alcanzar la mayor puntación posible. La forma de conseguir más puntos en el juego es comer fantasmas y el algoritmo explota esta característica. El principal objetivo de Emboscada Helada es atraer a los fantasmas a posiciones próximas a una píldora de poder para que cuando estos están lo suficientemente cerca tomársela y perseguirlos. Viendo el esquema se observa mejor esta forma de actuar.
Conjunto de reglas
A continuación explicaré de la forma más sencilla que pueda las diferentes reglas que rigen el comportamiento de esta inteligencia artificial. Estas se aplican en orden de prioridad ascendente y se selecciona cada turno la primera de ellas que cumpla la condición.
- Regla 1: Si hay una píldora de poder cerca y el fantasma más próximo no está ni lejos ni demasiado cerca se quedará emboscando en una posición cercana a la píldora de poder.
- Regla 2: Si está a distancia de emboscada y se le acerca algún fantasma a ella o a la píldora se moverá hacia la píldora de poder más próxima para comérsela.
- Regla 3: Si no hay fantasmas comestibles, hay una píldora de poder cerca y hay algún fantasma agresivo que no esté muy lejos entonces se dirigirá hacia la píldora de poder más próxima por el camino más directo.
- Regla 4: Si no hay fantasmas comestibles y hay algún fantasma agresivo que no esté muy lejos tomará el camino hacia la píldora de poder más próxima evitando los fantasmas agresivos.
- Regla 5: Si hay algún fantasma comestible cerca y además hay algún fantasma agresivo que no esté muy lejos se moverá hacia el fantasma comestible más próximo intentando evitar los fantasmas agresivos.
- Regla 6: Si hay alguna píldora y además el fantasma agresivo más próximo está medianamente lejos se dirigirá hacia la píldora más cercana.
- Regla 7: Si hay algún fantasma comestible cerca y todos los fantasmas agresivos están lejos entonces irá tras el fantasma comestible más próximo por el camino más directo.
- Regla 8: Si existe una píldora de poder, no existen píldoras normales que estén en un cruce de caminos que contiene una píldora de poder, no existen fantasmas agresivos o estos están lejos, la píldora de poder más próxima está lejos y hay alguna píldora normal que esté cerca, entonces, se dirigirá hacia dicha píldora.
- Regla 9: Si existe una píldora normal que no está en un cruce de caminos que contiene una píldora de poder y no existen fantasmas agresivos u estos están lejos, entonces se desplazará hacia dicha píldora.
Como os habréis dado cuenta, o si no ya estoy aquí para apuntarlo, el determinar si una píldora o un fantasma están lo suficientemente cerca o lejos es subjetivo, y el ordenador necesita de parámetros deterministas para decidir si aplica una regla u otra. Estas constantes que se utilizan para la toma de decisiones no las incluyo en el artículo porque no son necesarias para comprender el funcionamiento. Pero si alguna mente ávida de conocimiento quiere profundizar siempre puede consultar los enlaces con información extendida que se incluyen al final del post.
Puntos fuertes
La principal virtud de esta estrategia radica en que explota muy bien el encadenar combos de matar fantasmas. Para los que no hayan jugado nunca, cuando se come uno el primer fantasma se ganan 200 puntos, pero los siguientes que comas antes de que se pase el efecto de la píldora de poder van duplicando su valor, es decir, 400, 800 y 1600. Es decir si encadenas un combo completo ganas 3000 puntos del tirón.
Puntos débiles
Las constantes para la toma de decisiones no son todo lo buenas que podrían ser. Han sido estimadas manualmente analizando el comportamiento y la respuesta de Ms. Pacman. Una posible mejora radicaría en aplicar un algoritmo de optimización.
Además, un defecto importante que tiene esta estrategia es que no huye demasiado bien. El algoritmo no está pensado para ello y a veces se arriesga tanto para conseguir un combo de fantasmas que acaba muriendo. Tampoco está demasiado fino el algoritmo que decide que ruta tomar.
Video de funcionamiento
Todo lo explicado queda reflejado en el siguiente video. Si eres uno de esos locos programadores que se dedican a este tipo de viles actividades reconocerás el entorno de ejecución en un segundo. Si no lo eres, no te preocupes, el video es para todos los públicos. A la izquierda podréis observar la ventanita con la ejecución de la estrategia, y si, la señorita Pacman se mueve ella solita. El video está en HD y tó para que no os perdáis detalle.
En próximas entregas, espero que en menos de dos años xD, intentaré optimizar este algoritmo aplicando alguna técnica que incluso podría llegar a enorgullecer a Darwin.
Bueno, esto es todo por hoy, si has aguantado hasta aquí te felicito, porque menudo tostón. Si me conoces y sales algún día de fiesta conmigo tienes derecho a que te invite a una cervecita por aguantar esta “lectura ligera”. Pero si tu rollo es el masoquismo y piensas que aún no has tenido suficiente te dejo estos enlaces, eso sí, tendrás que usarlos bajo tu propia responsabilidad.
Enlaces de interés
- Ms. Pacman, por si hay alguien con ganas de jugar: juego
- Código de la inteligencia Emboscada Helada: código
- Diseño de controlador para Ms. Pacman: diseño
- Sitio web con información del proyecto: sitio
- Repositorio del código del proyecto: repositorio
