Challenge Team Interim Report

[Challenge Logo]

    Team Number: 006

    School Name: Albuquerque Academy

    Area of Science: Artificial Intelligence

    Project Title: Genetic Programming of Hive Artificial Intelligences

Final Report

Interim Report

Problem Definition:
To evolve the hive AI of the "ghosts" in Pacman to better pursue and catch basic, non-evolving pacmen. Pacman is a classic video game in which ghosts chase a pacman through a two-dimensional rectangular grid, known as the "maze." If a ghost and the pacman ever occupy the same square at the same time, the pacman is dead and the ghost is considered to have fulfilled its objective. Usually, there is only one pacman that is controlled by the player. In our simulation, there will be several pacmen which will function as a control that our evolved ghosts will combat.

Problem Solution:
Utilizing genetic programming algorithms, we will evolve multiple base ghost types over a series of generations. Drawing again from our analogy of ants and bees in the evolution of hive intelligence, over the course of a game, the ghosts will use simulated "pheromones" to communicate with each other. We will test the teams of ghosts by totaling the number of pacmen each team can catch during a given number of timesteps in several games. The computer will mix and match the programs of the fittest ghosts and teams in an effort to further advance the AI of the ghost population. After doing so, another round will commence as the newly evolved teams compete against each other.

Progress to Date:
We have most of the code already written for our project. We have coded the entire environment for our simulation, including a maze generator. Our maze generator efficiently generates a maze on a grid that consists mostly of "hallways" which are long but only one grid cell wide. The maze generator will never produce a maze with dead ends. It provides us with virtually unlimited spaces for our ghosts to compete in so that they will not evolve to take advantage of the peculiarities of one maze. We plan to have several different strategies for our non-evolving pacmen so that the ghosts can not predict what a given opponent will do for certain. To date we have coded some of these strategies. Our current implementation includes a command set that the ghosts will eventually use for their evolved programs. Currently, the ghosts use hard-coded programs that are written using this command set. So far we have not coded the crossover algorithms for the ghosts, which will be used to create new programs based on which previous strategies have been the most effective. This is the major remaining step in our coding before we can proceed to testing. We expect to finish this aspect in the next two weeks, leaving us plenty of time to test.

Expected Results:
We expect to accumulate a large amount of data pointing to the gradual evolution of the ghost AI. We expect to see them catch all of the pacmen more and more quickly. Since we are not evolving the pacmen, they will be a control against which we can measure the development of the ghosts. We expect the ghosts to evolve a hive intelligence mimicking that of ants and bees.

Team Members

Sponsoring Teachers

Project Advisor(s)