Neurotic Pacman

Hola gente,
Bueno hoy realizamos la entrega final de nuestro proyecto de un agente inteligente que juegue Pacman utilizando redes neurales (o neuronales, aún no sabemos como es correcto xD) entrenadas usando un algoritmo genético.

Les voy a detallar un poco lo que hicimos y me voy a poner técnico así que a los que no les interesen los detalles de la implementación pueden irse hasta el video =P. En función de la información que obtuvimos de la publicación de Simon Lucas utilizamos un algoritmo genético un poco diferente ya que no realiza el crossover de las generaciones por lo tanto todas las nuevas generaciones de una población provienen de la selección de los mejores individuos de la población inicial y la mutación de esos mejores individuos para tratar de obtener mejores fitness en las siguientes generaciones. Adicionalmente, la mutación que utilizamos es la que describe Lucas en su investigación que consta de 4 tipos diferentes de mutaciones, cada una con una probabilidad de que ocurra:

- 0.1 de probabilidad de mutar todos los pesos de la red neural.
- 0.27  de probabilidad de mutar todos los pesos de una capa de sinapsis (capa de pesos entre las neuronas) escogida al azar.
- 0.27 de probabilidad de mutar todos los pesos de las sinapsis que entran a una neurona escogida al azar.
- 0.36  de probabilidad de mutar un sólo peso de toda la red escogido al azar.

Algo que no teníamos definido cuando hice el primer post es la manera en la que la red neural iba a controlar al Pacman y bueno ahora les puedo decir que lo que hace la red es evaluar todos los posibles moviemientos de Pacman a partir de su posición actual y decidir en función del output de la red cual es la mejor opción.

Adicional a lo que hizo Lucas en su investigación añadimos dos factores que fueron determinantes en los resultados que obtuvimos:
- Como notamos que en la mayoría de los casos en los que se lograba un rendimiento bajo del algoritmo se debía a la indecisión de Pacman en casos donde la evaluación resultaba en que se devolvía por el camino que iba entonces agregamos la condición para que Pacman se devuelva por el camino por donde venía debe cumplirse la condición de que el siguiente estado es considerablemente mejor que la opción de seguir por el mismo camino. El "considerablemente" lo definimos usando una variable la cual instanciamos en varios valores como 1.5, 2.0 o 2.5 (veces que debe ser mejor una decisión que la otra).
- Notamos que con cierta frecuencia, debido a la magnitud de los inputs de la red, el valor final se acercaba demasiado a 1 e incluso varias veces retornaba 1.0 como valor final por lo cerca que estaba el número al 1 y por la limitación en la representación de los números lo cual reducía la precisión al momento de evaluar los movimientos posibles por lo que decidimos escalar esos valores a algo más pequeño así que lo dividimos por la máxima distancia entre dos puntos en el mapa pero dividida entre 16 ya que con valores más grandes pasaba lo mismo pero con una tendencia a 0.

Bueno el resultado fue que logramos mejorar los scores que había obtenido Lucas, por recomendación de la profesora mejoraremos algunos detalles y lo publicaremos en alguna conferencia regional o internacional. Luego les cuento que tal nos fue con eso, acá les dejo el video de nuestra mejor corrida:



Menciono a mis dos compañeros de equipo:

Daniel Barreto - @volrath y Edgar Henriquez - @edgarhenriquez

La investigación en la que nos basamos para este trabajo: Evolving a Neural Network Location Evaluator to Play Ms. Pac-Man - Simon Lucas

Y nuestra presentación donde se muestran los gráficos de los resultados:
Neurotic Ms.Pacman

Cualquier pregunta la pueden hacer en los comentarios y seguro les respondo :).

See Ya,
Kris