![[Challenge Logo]](../98-logo.gif){kind=logo}
Team Number: 006
School Name: Albuquerque Academy
Area of Science: Artificial Intelligence
Project Title: Genetic Programming of Hive Artificial Intelligences
Challenge Team Interim Report
|
Team Number: 006 School Name: Albuquerque Academy Area of Science: Artificial Intelligence Project Title: Genetic Programming of Hive Artificial Intelligences |
|
|
|
|
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)